Python Language
Python Lex-Yacc

Wprowadzenie

Uwagi

Rozpoczęcie pracy z PLY

Aby zainstalować PLY na swoim komputerze dla python2 / 3, wykonaj kroki opisane poniżej:

1. Pobierz kod źródłowy stąd .
2. Rozpakuj pobrany plik zip
3. Przejdź do rozpakowanego folderu ply-3.10
4. Uruchom następujące polecenie w swoim terminalu: python setup.py install

Jeśli wykonałeś wszystkie powyższe czynności, powinieneś być w stanie korzystać z modułu PLY. Możesz to przetestować, otwierając interpreter Pythona i wpisując import ply.lex .

Uwaga: Nie należy używać pip zainstalować warstwy, to zainstaluj uszkodzony dystrybucję na komputerze.

„Witaj, świecie!” PLY - prosty kalkulator

Pokażmy potęgę PLY na prostym przykładzie: ten program weźmie wyrażenie arytmetyczne jako ciąg znaków i spróbuje go rozwiązać.

Otwórz swój ulubiony edytor i skopiuj następujący kod:

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)

Zapisz ten plik jako calc.py i uruchom go.

Wynik:

-8

Co jest poprawną odpowiedzią dla -4 * - (3 - 5) .

Część 1: Tokenizacja danych wejściowych za pomocą Lexa

Są dwa etapy, że kod w przykładzie 1 przeprowadzone: onu tokenizing wprowadzania, co oznacza, że wyglądał symboli tworzących wyrażenia arytmetycznego, a drugi etap przetwarzania, który wymaga analizy wyekstrahowane znaki i ocenę wyników.

Ta sekcja zawiera prosty przykład tego, jak tokenizować dane wejściowe użytkownika, a następnie dzieli je wiersz po wierszu.

    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)

Zapisz ten plik jako calclex.py . Użyjemy tego podczas budowania naszego parsera Yacc.

Awaria

1. Zaimportuj moduł za pomocą import ply.lex

2. Wszyscy lekserzy muszą dostarczyć listę zwaną tokens która definiuje wszystkie możliwe nazwy tokenów, które mogą być wytworzone przez leksera. Ta lista jest zawsze wymagana.

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

tokens mogą być również krotką łańcuchów (a nie ciągiem), przy czym każdy ciąg oznacza token jak poprzednio.

3. Reguła wyrażeń regularnych dla każdego łańcucha może być zdefiniowana albo jako łańcuch, albo jako funkcja. W obu przypadkach nazwa zmiennej powinna być poprzedzona przez t_, aby wskazać, że jest to reguła dopasowywania tokenów.

   • W przypadku prostych tokenów wyrażenie regularne można określić jako ciągi znaków: t_PLUS = r'\+'

   • Jeśli trzeba wykonać jakąś akcję, jako funkcję można określić regułę tokenów.

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

     Uwaga: reguła jest określona jako ciąg dokumentów w funkcji. Funkcja przyjmuje jeden argument, który jest instancją LexToken , wykonuje pewne działania, a następnie zwraca argument z powrotem.

     Jeśli chcesz użyć łańcucha zewnętrznego jako reguły wyrażenia regularnego dla funkcji zamiast określać łańcuch dokumentu, rozważ następujący przykład:

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

   • Instancja obiektu LexToken (nazwijmy ten obiekt t ) ma następujące atrybuty:

     1. t.type który jest typem tokena (jako ciąg znaków) (np .: 'NUMBER' , 'PLUS' itp.). Domyślnie w t.type ustawiana jest nazwa następująca po prefiksie t_ .
     2. t.value która jest leksemem (rzeczywisty dopasowany tekst)
     3. t.lineno który jest bieżącym numerem linii (nie jest automatycznie aktualizowany, ponieważ leksyker nic nie wie o numerach linii). Zaktualizuj lineno za pomocą funkcji o nazwie t_newline .

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

     4. t.lexpos który jest pozycją tokena względem początku tekstu wejściowego.

   • Jeśli nic nie zostanie zwrócone z funkcji reguły wyrażenia regularnego, token jest odrzucany. Jeśli chcesz odrzucić token, możesz alternatywnie dodać przedrostek t_ignore_ do zmiennej reguły wyrażenia regularnego zamiast definiować funkcję dla tej samej reguły.

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

     ...Jest taki sam jak:

        t_ignore_COMMENT = r'\#.*'
     

     ^{Jest to oczywiście nieważne, jeśli wykonujesz jakieś czynności, gdy widzisz komentarz. W takim przypadku użyj funkcji, aby zdefiniować regułę wyrażeń regularnych.}

     Jeśli nie zdefiniowałeś tokena dla niektórych znaków, ale nadal chcesz go zignorować, użyj t_ignore = "<characters to ignore>" (te prefiksy są konieczne):

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

   • Podczas budowania głównego wyrażenia regularnego, lex doda wyrażenia regularne określone w pliku w następujący sposób:

     1. Tokeny zdefiniowane przez funkcje są dodawane w tej samej kolejności, w jakiej pojawiają się w pliku.
     2. Tokeny zdefiniowane przez ciągi są dodawane w kolejności malejącej długości ciągu, który określa regex dla tego tokena.

     Jeśli dopasowujesz == i = w tym samym pliku, skorzystaj z tych reguł.

   • Literały to tokeny zwracane w takiej postaci, w jakiej są. Zarówno t.type jak i t.value zostaną ustawione na samą postać. Zdefiniuj listę literałów jako taką:

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

     lub,

     literals = "+-*/"
     

     Możliwe jest pisanie funkcji tokenów, które wykonują dodatkowe akcje po dopasowaniu literałów. Musisz jednak odpowiednio ustawić typ tokena. Na przykład:

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

   • Obsługa błędów za pomocą funkcji 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)
     

     Ogólnie rzecz biorąc, t.lexer.skip(n) pomija n znaków w ciągu wejściowym.

4. Ostateczne przygotowania:

   Zbuduj lexer za pomocą lexer = lex.lex() .

   Możesz także umieścić wszystko w klasie i wywołać instancję use klasy, aby zdefiniować leksykon. Na przykład:

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

   Wprowadź dane wejściowe za pomocą lexer.input(data) gdzie dane są łańcuchem

   Aby uzyskać tokeny, użyj lexer.token() który zwraca dopasowane tokeny. Możesz iterować po Lekserze w pętli, jak w:

   for i in lexer: 
       print(i)
   

Część 2: Analiza tokenizowanych danych wejściowych za pomocą Yacc

W tej sekcji wyjaśniono, w jaki sposób przetwarzane jest tokenizowane wejście z Części 1 - odbywa się to za pomocą gramatyki bezkontekstowej (CFG). Gramatyka musi zostać określona, a tokeny są przetwarzane zgodnie z gramatyką. Pod maską analizator używa analizatora składni 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)

Awaria

• Każda reguła gramatyczna jest zdefiniowana przez funkcję, w której docstring do tej funkcji zawiera odpowiednią bezkontekstową specyfikację gramatyczną. Instrukcje składające się na ciało funkcji implementują działania semantyczne reguły. Każda funkcja przyjmuje pojedynczy argument p, który jest sekwencją zawierającą wartości każdego symbolu gramatyki w odpowiedniej regule. Wartości p[i] są odwzorowane na symbole gramatyczne, jak pokazano tutaj:

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

• W przypadku tokenów „wartość” odpowiedniego p[i] jest taka sama, jak atrybut p.value przypisany w module lexer. Tak więc PLUS będzie miał wartość + .

• Dla nieterminalnych wartość jest określana przez cokolwiek umieszczone w p[0] . Jeśli nic nie zostanie umieszczone, wartością jest None. Również p[-1] nie jest tym samym co p[3] , ponieważ p nie jest prostą listą ( p[-1] może określać działania osadzone (nie omówione tutaj)).

Zauważ, że funkcja może mieć dowolną nazwę, o ile poprzedza ją p_ .

• p_error(p) jest zdefiniowana w celu p_error(p) błędów składniowych (tak samo jak yyerror w yacc / bison).

• Wiele reguł gramatycznych można połączyć w jedną funkcję, co jest dobrym pomysłem, jeśli produkcje mają podobną strukturę.

    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] 
  

• Zamiast żetonów można używać literałów znakowych.

    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]
  

  Oczywiście literały muszą być określone w module leksykalnym.

• Puste produkcje mają '''symbol : '''

• Aby jawnie ustawić symbol początkowy, użyj start = 'foo' , gdzie foo jest nieterminalne.

• Ustawienie pierwszeństwa i powiązania można wykonać za pomocą zmiennej pierwszeństwa.

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

  Tokeny są uporządkowane od najniższego do najwyższego priorytetu. nonassoc oznacza, że te tokeny nie są powiązane. Oznacza to, że coś takiego jak a < b < c jest nielegalne, podczas a < b jest nadal legalne.

• parser.out to plik debugujący, który jest tworzony, gdy program yacc jest uruchamiany po raz pierwszy. Ilekroć występuje konflikt przesunięcia / zmniejszenia, analizator składni zawsze się zmienia.