Python Language
Python Lex-Yacc

Introducción

Observaciones

Empezando con PLY

Para instalar PLY en su máquina para python2 / 3, siga los pasos descritos a continuación:

1. Descarga el código fuente desde aquí .
2. Descomprima el archivo zip descargado.
3. Navegue en la carpeta ply-3.10 descomprimida
4. 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

1. Importe el módulo usando import ply.lex

2. 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.

3. 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 objeto t ) tiene los siguientes atributos:

     1. 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 prefijo t_ .
     2. t.value que es el lexema (el texto real t.value )
     3. 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 llamada t_newline .

       def t_newline(t):
           r'\n+'
           t.lexer.lineno += len(t.value)
     

     4. 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:

     1. Las fichas definidas por funciones se agregan en el mismo orden en que aparecen en el archivo.
     2. 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 como t.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.

4. 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 cadena

   Para 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 atributo p.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 que p[3] , ya que p 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 que yyerror 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' , donde foo 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 como a < b < c es ilegal mientras que a < 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.