Python Language
Python Lex-Yacc
Buscar..
Introducción
PLY es una implementación pura de Python de las populares herramientas de construcción de compiladores lex y yacc.
Observaciones
Enlaces adicionales:
Empezando con PLY
Para instalar PLY en su máquina para python2 / 3, siga los pasos descritos a continuación:
- Descarga el código fuente desde aquí .
- Descomprima el archivo zip descargado.
- Navegue en la carpeta
ply-3.10
descomprimida - Ejecute el siguiente comando en su terminal:
python setup.py install
Si completó todo lo anterior, ahora debería poder usar el módulo PLY. Puede probarlo abriendo un intérprete de python y escribiendo import ply.lex
.
Nota: No utilice pip
para instalar PLY, se instalará una distribución rota en su máquina.
El "¡Hola mundo!" de PLY - Una calculadora simple
Demostremos el poder de PLY con un ejemplo simple: este programa tomará una expresión aritmética como una entrada de cadena e intentará resolverla.
Abre tu editor favorito y copia el siguiente código:
from ply import lex
import ply.yacc as yacc
tokens = (
'PLUS',
'MINUS',
'TIMES',
'DIV',
'LPAREN',
'RPAREN',
'NUMBER',
)
t_ignore = ' \t'
t_PLUS = r'\+'
t_MINUS = r'-'
t_TIMES = r'\*'
t_DIV = r'/'
t_LPAREN = r'\('
t_RPAREN = r'\)'
def t_NUMBER( t ) :
r'[0-9]+'
t.value = int( t.value )
return t
def t_newline( t ):
r'\n+'
t.lexer.lineno += len( t.value )
def t_error( t ):
print("Invalid Token:",t.value[0])
t.lexer.skip( 1 )
lexer = lex.lex()
precedence = (
( 'left', 'PLUS', 'MINUS' ),
( 'left', 'TIMES', 'DIV' ),
( 'nonassoc', 'UMINUS' )
)
def p_add( p ) :
'expr : expr PLUS expr'
p[0] = p[1] + p[3]
def p_sub( p ) :
'expr : expr MINUS expr'
p[0] = p[1] - p[3]
def p_expr2uminus( p ) :
'expr : MINUS expr %prec UMINUS'
p[0] = - p[2]
def p_mult_div( p ) :
'''expr : expr TIMES expr
| expr DIV expr'''
if p[2] == '*' :
p[0] = p[1] * p[3]
else :
if p[3] == 0 :
print("Can't divide by 0")
raise ZeroDivisionError('integer division by 0')
p[0] = p[1] / p[3]
def p_expr2NUM( p ) :
'expr : NUMBER'
p[0] = p[1]
def p_parens( p ) :
'expr : LPAREN expr RPAREN'
p[0] = p[2]
def p_error( p ):
print("Syntax error in input!")
parser = yacc.yacc()
res = parser.parse("-4*-(3-5)") # the input
print(res)
Guarde este archivo como calc.py
y ejecútelo.
Salida:
-8
¿Cuál es la respuesta correcta para -4 * - (3 - 5)
?
Parte 1: Tokenizing entrada con Lex
Hay dos pasos que llevó a cabo el código del ejemplo 1: uno fue tokenizar la entrada, lo que significa que buscó los símbolos que constituyen la expresión aritmética, y el segundo paso fue analizar , lo que implica analizar los tokens extraídos y evaluar el resultado.
Esta sección proporciona un ejemplo simple de cómo tokenizar la entrada del usuario, y luego la divide línea por línea.
import ply.lex as lex
# List of token names. This is always required
tokens = [
'NUMBER',
'PLUS',
'MINUS',
'TIMES',
'DIVIDE',
'LPAREN',
'RPAREN',
]
# Regular expression rules for simple tokens
t_PLUS = r'\+'
t_MINUS = r'-'
t_TIMES = r'\*'
t_DIVIDE = r'/'
t_LPAREN = r'\('
t_RPAREN = r'\)'
# A regular expression rule with some action code
def t_NUMBER(t):
r'\d+'
t.value = int(t.value)
return t
# Define a rule so we can track line numbers
def t_newline(t):
r'\n+'
t.lexer.lineno += len(t.value)
# A string containing ignored characters (spaces and tabs)
t_ignore = ' \t'
# Error handling rule
def t_error(t):
print("Illegal character '%s'" % t.value[0])
t.lexer.skip(1)
# Build the lexer
lexer = lex.lex()
# Give the lexer some input
lexer.input(data)
# Tokenize
while True:
tok = lexer.token()
if not tok:
break # No more input
print(tok)
Guarde este archivo como calclex.py
. Usaremos esto cuando construyamos nuestro analizador de Yacc.
Descompostura
Importe el módulo usando
import ply.lex
Todos los lexers deben proporcionar una lista llamada
tokens
que define todos los posibles nombres de token que puede producir el lexer. Esta lista siempre es obligatoria.tokens = [ 'NUMBER', 'PLUS', 'MINUS', 'TIMES', 'DIVIDE', 'LPAREN', 'RPAREN', ]
tokens
también podrían ser una tupla de cadenas (en lugar de una cadena), donde cada cadena denota un token como antes.
La regla de expresiones regulares para cada cadena puede definirse como una cadena o como una función. En cualquier caso, el nombre de la variable debe tener el prefijo t_ para denotar que es una regla para hacer coincidir tokens.
Para tokens simples, la expresión regular se puede especificar como cadenas:
t_PLUS = r'\+'
Si es necesario realizar algún tipo de acción, se puede especificar una regla de token como una función.
def t_NUMBER(t): r'\d+' t.value = int(t.value) return t
Tenga en cuenta que la regla se especifica como una cadena de documentación dentro de la función. La función acepta un argumento que es una instancia de
LexToken
, realiza alguna acción y luego devuelve el argumento.Si desea usar una cadena externa como regla de expresión regular para la función en lugar de especificar una cadena de documentación, considere el siguiente ejemplo:
@TOKEN(identifier) # identifier is a string holding the regex def t_ID(t): ... # actions
Una instancia de objeto
LexToken
(llamemos a este objetot
) tiene los siguientes atributos:-
t.type
que es el tipo de token (como una cadena) (por ejemplo:'NUMBER'
,'PLUS'
, etc.). Por defecto,t.type
se establece en el nombre que sigue al prefijot_
. -
t.value
que es el lexema (el texto realt.value
) -
t.lineno
que es el número de línea actual (esto no se actualiza automáticamente, ya que el lexer no sabe nada de los números de línea). Actualiza lineno usando una función llamadat_newline
.
def t_newline(t): r'\n+' t.lexer.lineno += len(t.value)
-
t.lexpos
que es la posición del token en relación con el comienzo del texto de entrada.
-
Si no se devuelve nada de una función de regla de expresiones regulares, el token se descarta. Si desea descartar un token, alternativamente puede agregar el prefijo t_ignore_ a una variable de regla de expresiones regulares en lugar de definir una función para la misma regla.
def t_COMMENT(t): r'\#.*' pass # No return value. Token discarded
...Es lo mismo que:
t_ignore_COMMENT = r'\#.*'
Por supuesto, esto no es válido si está realizando alguna acción cuando ve un comentario. En cuyo caso, use una función para definir la regla de expresiones regulares.
Si no ha definido un token para algunos caracteres pero aún quiere ignorarlo, use
t_ignore = "<characters to ignore>"
(estos prefijos son necesarios):t_ignore_COMMENT = r'\#.*' t_ignore = ' \t' # ignores spaces and tabs
Al crear la expresión regular maestra, lex agregará las expresiones regulares especificadas en el archivo de la siguiente manera:
- Las fichas definidas por funciones se agregan en el mismo orden en que aparecen en el archivo.
- Los tokens definidos por cadenas se agregan en orden decreciente de la longitud de la cadena que define la expresión regular para ese token.
Si coincide
==
y=
en el mismo archivo, aproveche estas reglas.
Los literales son tokens que se devuelven como son. Tanto
t.type
comot.value
se establecerán en el propio carácter. Defina una lista de literales como tales:literals = [ '+', '-', '*', '/' ]
o,
literals = "+-*/"
Es posible escribir funciones de token que realizan acciones adicionales cuando se combinan literales. Sin embargo, deberás configurar el tipo de token de forma adecuada. Por ejemplo:
literals = [ '{', '}' ] def t_lbrace(t): r'\{' t.type = '{' # Set token type to the expected literal (ABSOLUTE MUST if this is a literal) return t
Manejar errores con la función t_error.
# Error handling rule def t_error(t): print("Illegal character '%s'" % t.value[0]) t.lexer.skip(1) # skip the illegal token (don't process it)
En general,
t.lexer.skip(n)
omite n caracteres en la cadena de entrada.
Preparativos finales
Construya el lexer usando
lexer = lex.lex()
.También puede colocar todo dentro de una clase y llamar a la instancia de uso de la clase para definir el lexer. P.ej:
import ply.lex as lex class MyLexer(object): ... # everything relating to token rules and error handling comes here as usual # Build the lexer def build(self, **kwargs): self.lexer = lex.lex(module=self, **kwargs) def test(self, data): self.lexer.input(data) for token in self.lexer.token(): print(token) # Build the lexer and try it out m = MyLexer() m.build() # Build the lexer m.test("3 + 4") #
Proporcione entrada utilizando
lexer.input(data)
donde los datos son una cadenaPara obtener los tokens, use
lexer.token()
que devuelve tokens coincidentes. Puede iterar sobre lexer en un bucle como en:for i in lexer: print(i)
Parte 2: Análisis de entrada Tokenized con Yacc
Esta sección explica cómo se procesa la entrada tokenizada de la Parte 1: se realiza utilizando las gramáticas libres de contexto (CFG). Se debe especificar la gramática y los tokens se procesan de acuerdo con la gramática. Bajo el capó, el analizador utiliza un analizador LALR.
# Yacc example
import ply.yacc as yacc
# Get the token map from the lexer. This is required.
from calclex import tokens
def p_expression_plus(p):
'expression : expression PLUS term'
p[0] = p[1] + p[3]
def p_expression_minus(p):
'expression : expression MINUS term'
p[0] = p[1] - p[3]
def p_expression_term(p):
'expression : term'
p[0] = p[1]
def p_term_times(p):
'term : term TIMES factor'
p[0] = p[1] * p[3]
def p_term_div(p):
'term : term DIVIDE factor'
p[0] = p[1] / p[3]
def p_term_factor(p):
'term : factor'
p[0] = p[1]
def p_factor_num(p):
'factor : NUMBER'
p[0] = p[1]
def p_factor_expr(p):
'factor : LPAREN expression RPAREN'
p[0] = p[2]
# Error rule for syntax errors
def p_error(p):
print("Syntax error in input!")
# Build the parser
parser = yacc.yacc()
while True:
try:
s = raw_input('calc > ')
except EOFError:
break
if not s: continue
result = parser.parse(s)
print(result)
Descompostura
Cada regla gramatical está definida por una función donde la cadena de documentación de esa función contiene la especificación gramatical libre de contexto apropiada. Las declaraciones que conforman el cuerpo de la función implementan las acciones semánticas de la regla. Cada función acepta un solo argumento p que es una secuencia que contiene los valores de cada símbolo gramatical en la regla correspondiente. Los valores de
p[i]
se asignan a símbolos gramaticales como se muestra aquí:def p_expression_plus(p): 'expression : expression PLUS term' # ^ ^ ^ ^ # p[0] p[1] p[2] p[3] p[0] = p[1] + p[3]
Para los tokens, el "valor" de la
p[i]
es el mismo que el atributop.value
asignado en el módulo lexer. Por lo tanto,PLUS
tendrá el valor+
.Para no terminales, el valor se determina por lo que se coloque en
p[0]
. Si no se coloca nada, el valor es Ninguno. Además,p[-1]
no es lo mismo quep[3]
, ya quep
no es una lista simple (p[-1]
puede especificar acciones incrustadas (no se trata aquí)).
Tenga en cuenta que la función puede tener cualquier nombre, siempre que esté precedida por p_
.
La
p_error(p)
se define para detectar errores de sintaxis (igual queyyerror
en yacc / bison).Se pueden combinar varias reglas gramaticales en una sola función, lo que es una buena idea si las producciones tienen una estructura similar.
def p_binary_operators(p): '''expression : expression PLUS term | expression MINUS term term : term TIMES factor | term DIVIDE factor''' if p[2] == '+': p[0] = p[1] + p[3] elif p[2] == '-': p[0] = p[1] - p[3] elif p[2] == '*': p[0] = p[1] * p[3] elif p[2] == '/': p[0] = p[1] / p[3]
Se pueden usar caracteres literales en lugar de fichas.
def p_binary_operators(p): '''expression : expression '+' term | expression '-' term term : term '*' factor | term '/' factor''' if p[2] == '+': p[0] = p[1] + p[3] elif p[2] == '-': p[0] = p[1] - p[3] elif p[2] == '*': p[0] = p[1] * p[3] elif p[2] == '/': p[0] = p[1] / p[3]
Por supuesto, los literales deben especificarse en el módulo lexer.
Las producciones vacías tienen la forma
'''symbol : '''
Para establecer explícitamente el símbolo de inicio, use
start = 'foo'
, dondefoo
es algo que no es terminal.La configuración de la precedencia y la asociatividad se puede hacer utilizando la variable de precedencia.
precedence = ( ('nonassoc', 'LESSTHAN', 'GREATERTHAN'), # Nonassociative operators ('left', 'PLUS', 'MINUS'), ('left', 'TIMES', 'DIVIDE'), ('right', 'UMINUS'), # Unary minus operator )
Los tokens se ordenan de menor a mayor precedencia.
nonassoc
significa que esos tokens no se asocian. Esto significa que algo comoa < b < c
es ilegal mientras quea < b
todavía es legal.parser.out
es un archivo de depuración que se crea cuando se ejecuta el programa yacc por primera vez. Cada vez que se produce un conflicto de desplazamiento / reducción, el analizador siempre cambia.