Python Language
Python Lex-Yacc

introduzione

Osservazioni

Iniziare con PLY

Per installare PLY sulla tua macchina per python2 / 3, procedi come indicato di seguito:

1. Scarica il codice sorgente da qui .
2. Decomprimere il file zip scaricato
3. Passare alla cartella ply-3.10 decompressa
4. Esegui il seguente comando nel tuo terminale: python setup.py install

Se hai completato tutto quanto sopra, ora dovresti essere in grado di utilizzare il modulo PLY. Puoi testarlo aprendo un interprete python e digitando import ply.lex .

Nota: non utilizzare pip per installare PLY, ma installerà una distribuzione interrotta sulla macchina.

"Ciao, mondo!" di PLY - A Simple Calculator

Dimostriamo la potenza di PLY con un semplice esempio: questo programma prenderà un'espressione aritmetica come input di stringa e tenterà di risolverlo.

Apri il tuo editor preferito e copia il seguente codice:

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)

Salva questo file come calc.py ed calc.py .

Produzione:

-8

Qual è la risposta giusta per -4 * - (3 - 5) .

Parte 1: Tokenizing Input con Lex

Esistono due passaggi eseguiti dal codice dell'esempio 1: uno stava tokenizzando l'input, il che significa che cercava i simboli che costituiscono l'espressione aritmetica e il secondo passo era l' analisi , che comporta l'analisi dei token estratti e la valutazione del risultato.

Questa sezione fornisce un semplice esempio di come tokenizzare l'input dell'utente, e quindi scomposizione riga per riga.

    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)

Salva questo file come calclex.py . Lo useremo quando costruiamo il nostro parser Yacc.

Abbattersi

1. Importa il modulo usando import ply.lex

2. Tutti i lexer devono fornire un elenco chiamato tokens che definisca tutti i possibili nomi di token che possono essere generati dal lexer. Questa lista è sempre richiesta.

    tokens = [
       'NUMBER',
       'PLUS',
       'MINUS',
       'TIMES',
       'DIVIDE',
       'LPAREN',
       'RPAREN',
    ]
   

tokens potrebbero anche essere una tupla di stringhe (piuttosto che una stringa), in cui ogni stringa indica un token come prima.

3. La regola regex per ogni stringa può essere definita come una stringa o come una funzione. In entrambi i casi, il nome della variabile deve essere preceduto da t_ per indicare che si tratta di una regola per la corrispondenza dei token.

   • Per i token semplici, l'espressione regolare può essere specificata come stringhe: t_PLUS = r'\+'

   • Se è necessario eseguire un tipo di azione, è possibile specificare una regola token come funzione.

        def t_NUMBER(t):
            r'\d+'
            t.value = int(t.value)
            return t
     

     Nota, la regola è specificata come una stringa doc all'interno della funzione. La funzione accetta un argomento che è un'istanza di LexToken , esegue un'azione e quindi restituisce l'argomento.

     Se si desidera utilizzare una stringa esterna come regola regex per la funzione anziché specificare una stringa doc, considerare il seguente esempio:

        @TOKEN(identifier)         # identifier is a string holding the regex
        def t_ID(t):
            ...      # actions
     

   • LexToken dell'oggetto LexToken (chiamiamo questo oggetto t ) ha i seguenti attributi:

     1. t.type che è il tipo di token (come una stringa) (ad esempio: 'NUMBER' , 'PLUS' , ecc.). Per impostazione predefinita, t.type è impostato sul nome che segue il prefisso t_ .
     2. t.value che è il lessema (il testo vero e proprio corrisponde)
     3. t.lineno che è il numero di linea corrente (questo non viene aggiornato automaticamente, poiché il lexer non sa nulla dei numeri di riga). Aggiorna lineno usando una funzione chiamata t_newline .

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

     4. t.lexpos che è la posizione del token rispetto all'inizio del testo di input.

   • Se non viene restituito nulla da una funzione di regola regex, il token viene scartato. Se vuoi scartare un token, puoi in alternativa aggiungere il prefisso t_ignore_ a una variabile della regola di espressione regolare invece di definire una funzione per la stessa regola.

        def t_COMMENT(t):
            r'\#.*'
            pass
            # No return value. Token discarded
     

     ...Equivale a:

        t_ignore_COMMENT = r'\#.*'
     

     ^{Questo è ovviamente non valido se stai compiendo qualche azione quando vedi un commento. In tal caso, utilizzare una funzione per definire la regola regex.}

     Se non hai definito un token per alcuni personaggi ma desideri comunque ignorarlo, usa t_ignore = "<characters to ignore>" (questi prefissi sono necessari):

        t_ignore_COMMENT = r'\#.*'
        t_ignore  = ' \t'    # ignores spaces and tabs
     

   • Quando si costruisce la regex master, lex aggiungerà le espressioni regolari specificate nel file come segue:

     1. I token definiti dalle funzioni vengono aggiunti nello stesso ordine in cui appaiono nel file.
     2. I token definiti dalle stringhe vengono aggiunti in ordine decrescente della lunghezza della stringa della stringa che definisce la regex per quel token.

     Se stai cercando == e = nello stesso file, approfitta di queste regole.

   • I letterali sono token che vengono restituiti così come sono. Sia t.type che t.value saranno impostati sul carattere stesso. Definisci una lista di letterali in quanto tale:

     literals = [ '+', '-', '*', '/' ]
     

     o,

     literals = "+-*/"
     

     È possibile scrivere funzioni token che eseguono ulteriori azioni quando i valori letterali sono abbinati. Tuttavia, dovrai impostare il tipo di token in modo appropriato. Per esempio:

     literals = [ '{', '}' ]
     
     def t_lbrace(t):
         r'\{'
         t.type = '{'  # Set token type to the expected literal (ABSOLUTE MUST if this is a literal)
         return t
     

   • Gestire gli errori con la funzione 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)
     

     In generale, t.lexer.skip(n) salta n caratteri nella stringa di input.

4. Preparazioni finali:

   Costruisci il lexer usando lexer = lex.lex() .

   Puoi anche inserire tutto in una classe e chiamare l'istanza di utilizzo della classe per definire il lexer. Per esempio:

    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")     #
   

   Fornire input utilizzando lexer.input(data) cui i dati sono una stringa

   Per ottenere i token, utilizzare lexer.token() che restituisce i token corrispondenti. Puoi scorrere su lexer in un loop come in:

   for i in lexer: 
       print(i)
   

Parte 2: Parsing Input Tokenized con Yacc

Questa sezione spiega come viene elaborato l'input tokenizzato dalla Parte 1, che viene eseguito utilizzando Grammatiche Context Free (CFG). La grammatica deve essere specificata e i token vengono elaborati in base alla grammatica. Sotto il cofano, il parser usa un parser 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)

Abbattersi

• Ogni regola grammaticale è definita da una funzione in cui la docstring a quella funzione contiene le specifiche grammaticali appropriate senza contesto. Le affermazioni che costituiscono il corpo della funzione implementano le azioni semantiche della regola. Ogni funzione accetta un singolo argomento p che è una sequenza contenente i valori di ciascun simbolo grammaticale nella regola corrispondente. I valori di p[i] sono mappati ai simboli grammaticali come mostrato qui:

    def p_expression_plus(p):
        'expression : expression PLUS term'
        #   ^            ^        ^    ^
        #  p[0]         p[1]     p[2] p[3]
  
        p[0] = p[1] + p[3]
  

• Per i token, il "valore" del corrispondente p[i] è uguale all'attributo p.value assegnato nel modulo lexer. Quindi, PLUS avrà il valore + .

• Per i non-terminali, il valore è determinato da qualunque cosa sia posizionata in p[0] . Se non viene inserito nulla, il valore è Nessuno. Inoltre, p[-1] non è lo stesso di p[3] , poiché p non è una lista semplice ( p[-1] può specificare azioni incorporate (non discusse qui)).

Si noti che la funzione può avere qualsiasi nome, purché preceduto da p_ .

• La p_error(p) è definita per yyerror errori di sintassi (come yyerror in yacc / bison).

• Più regole grammaticali possono essere combinate in un'unica funzione, che è una buona idea se le produzioni hanno una struttura simile.

    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] 
  

• I caratteri letterali possono essere usati al posto dei token.

    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]
  

  Naturalmente, i valori letterali devono essere specificati nel modulo lexer.

• Le produzioni vuote hanno il '''symbol : '''

• Per impostare in modo esplicito il simbolo di partenza, utilizzare start = 'foo' , dove foo è un non-terminale.

• L'impostazione della precedenza e dell'associatività può essere eseguita utilizzando la variabile di precedenza.

    precedence = (
        ('nonassoc', 'LESSTHAN', 'GREATERTHAN'),  # Nonassociative operators
        ('left', 'PLUS', 'MINUS'),
        ('left', 'TIMES', 'DIVIDE'),
        ('right', 'UMINUS'),            # Unary minus operator
    )
  

  I token sono ordinati dalla precedenza più bassa a quella più alta. nonassoc significa che quei token non si associano. Ciò significa che qualcosa come a < b < c è illegale mentre a < b è ancora legale.

• parser.out è un file di debug che viene creato quando il programma yacc viene eseguito per la prima volta. Ogni volta che si verifica uno spostamento / riduzione del conflitto, il parser si sposta sempre.