Python Language
Python Lex-Yacc

Einführung

Bemerkungen

Erste Schritte mit PLY

Um PLY auf Ihrem Rechner für Python2 / 3 zu installieren, führen Sie die folgenden Schritte aus:

1. Laden Sie den Quellcode hier herunter.
2. Entpacken Sie die heruntergeladene ZIP-Datei
3. Navigieren Sie in den entpackten Ordner ply-3.10
4. Führen Sie den folgenden Befehl in Ihrem Terminal aus: python setup.py install

Wenn Sie alle oben genannten Schritte ausgeführt haben, sollten Sie jetzt das PLY-Modul verwenden können. Sie können es testen, indem Sie einen Python-Interpreter öffnen und import ply.lex .

Hinweis: Verwenden Sie keine pip PLY zu installieren, wird es eine gebrochene Verteilung auf Ihrem Rechner installieren.

Das "Hallo, Welt!" of PLY - Ein einfacher Rechner

Lassen Sie uns die Leistungsfähigkeit von PLY anhand eines einfachen Beispiels demonstrieren: Dieses Programm nimmt einen arithmetischen Ausdruck als Zeichenfolgeingabe und versucht, ihn zu lösen.

Öffnen Sie Ihren bevorzugten Editor und kopieren Sie den folgenden Code:

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)

Speichern Sie diese Datei als calc.py und führen Sie sie aus.

Ausgabe:

-8

Welches ist die richtige Antwort für -4 * - (3 - 5) .

Teil 1: Tokenisierung mit Lex

Es gibt zwei Schritte, die der Code aus Beispiel 1 ausführte: Erstens wurde die Eingabe mit einem Token versehen , das heißt, es wurde nach Symbolen gesucht, die den arithmetischen Ausdruck bilden, und der zweite Schritt war das Parsing , bei dem die extrahierten Token analysiert und das Ergebnis bewertet werden.

Dieser Abschnitt enthält ein einfaches Beispiel für die Tokensierung von Benutzereingaben und unterteilt sie dann Zeile für Zeile.

    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)

Speichern Sie diese Datei als calclex.py . Wir werden dies beim Bau unseres Yacc-Parsers verwenden.

Nervenzusammenbruch

1. Importieren Sie das Modul mit import ply.lex

2. Alle Lexer müssen eine Liste namens tokens bereitstellen, die alle möglichen Token-Namen definiert, die vom Lexer erzeugt werden können. Diese Liste ist immer erforderlich.

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

tokens können auch ein Tupel von Strings (und nicht ein String) sein, wobei jeder String ein Token wie zuvor bezeichnet.

3. Die Regex-Regel für jeden String kann entweder als String oder als Funktion definiert werden. In beiden Fällen sollte dem Variablennamen t_ vorangestellt werden, um anzugeben, dass dies eine Regel für übereinstimmende Token ist.

   • Für einfache Token kann der reguläre Ausdruck als Zeichenfolge angegeben werden: t_PLUS = r'\+'

   • Wenn eine Aktion ausgeführt werden muss, kann eine Tokenregel als Funktion angegeben werden.

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

     Beachten Sie, dass die Regel als Dokumentzeichenfolge innerhalb der Funktion angegeben wird. Die Funktion akzeptiert ein Argument, das eine Instanz von LexToken , führt eine Aktion aus und gibt das Argument zurück.

     Wenn Sie einen externen String als Regex-Regel für die Funktion verwenden möchten, anstatt einen Doc-String anzugeben, betrachten Sie das folgende Beispiel:

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

   • Eine Instanz des LexToken Objekts (nennen wir dieses Objekt t ) hat die folgenden Attribute:

     1. t.type ist der Token-Typ (als Zeichenfolge) (z. B. 'NUMBER' , 'PLUS' usw.). Standardmäßig ist t.type nach dem Präfix t_ auf den Namen gesetzt.
     2. t.value was das Lexem ist (der tatsächliche Text, der angeglichen wird)
     3. t.lineno ist die aktuelle Zeilennummer (diese wird nicht automatisch aktualisiert, da der Lexer nichts von Zeilennummern weiß). Aktualisieren Sie Leineno mit einer Funktion namens t_newline .

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

     4. t.lexpos ist die Position des Tokens relativ zum Anfang des Eingabetextes.

   • Wenn von einer Regex-Regelfunktion nichts zurückgegeben wird, wird das Token verworfen. Wenn Sie ein Token verwerfen möchten, können Sie alternativ zu einer Regex-Regelvariablen das Präfix t_ignore_ hinzufügen, anstatt eine Funktion für dieselbe Regel zu definieren.

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

     ...Ist das gleiche wie:

        t_ignore_COMMENT = r'\#.*'
     

     ^{Dies ist natürlich ungültig, wenn Sie eine Aktion ausführen, wenn Sie einen Kommentar sehen. Verwenden Sie in diesem Fall eine Funktion, um die Regex-Regel zu definieren.}

     Wenn Sie für einige Zeichen kein Token definiert haben, es aber dennoch ignorieren möchten, verwenden Sie t_ignore = "<characters to ignore>" (diese Präfixe sind erforderlich):

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

   • Beim Erstellen des Master-Regex fügt lex die in der Datei angegebenen Regexes wie folgt hinzu:

     1. Von Funktionen definierte Token werden in derselben Reihenfolge hinzugefügt, in der sie in der Datei angezeigt werden.
     2. Von Zeichenfolgen definierte Token werden in abnehmender Reihenfolge der Zeichenfolgenlänge der Zeichenfolge hinzugefügt, die den regulären Ausdruck für dieses Token definiert.

     Wenn Sie == und = in derselben Datei finden, nutzen Sie diese Regeln.

   • Literale sind Marken, die zurückgegeben werden, wie sie sind. Sowohl t.type als auch t.value werden auf das Zeichen selbst gesetzt. Definieren Sie eine Liste von Literalen als solche:

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

     oder,

     literals = "+-*/"
     

     Es ist möglich, Token-Funktionen zu schreiben, die zusätzliche Aktionen ausführen, wenn Literale abgeglichen werden. Sie müssen jedoch den Tokentyp entsprechend festlegen. Zum Beispiel:

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

   • Behandeln Sie Fehler mit der Funktion 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)
     

     Im Allgemeinen überspringt t.lexer.skip(n) n Zeichen in der Eingabezeichenfolge.

4. Letzte Vorbereitungen:

   Erstellen Sie den Lexer mit lexer = lex.lex() .

   Sie können auch alles in eine Klasse einfügen und die use-Instanz der Klasse aufrufen, um den Lexer zu definieren. Z.B:

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

   Geben Sie die Eingabe mithilfe von lexer.input(data) wobei data eine Zeichenfolge ist

   Um die Token zu erhalten, verwenden Sie lexer.token() das übereinstimmende Token zurückgibt. Sie können in einer Schleife über Lexer iterieren wie in:

   for i in lexer: 
       print(i)
   

Teil 2: Analyse von getakteten Eingaben mit Yacc

In diesem Abschnitt wird erläutert, wie die mit Token versehenen Eingaben aus Teil 1 verarbeitet werden. Dies geschieht mithilfe von Context Free Grammars (CFGs). Die Grammatik muss angegeben werden und die Token werden gemäß der Grammatik verarbeitet. Unter der Haube verwendet der Parser einen LALR-Parser.

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

Nervenzusammenbruch

• Jede Grammatikregel wird durch eine Funktion definiert, bei der der Docstring für diese Funktion die entsprechende kontextfreie Grammatikspezifikation enthält. Die Anweisungen, aus denen der Funktionskörper besteht, implementieren die semantischen Aktionen der Regel. Jede Funktion akzeptiert ein einzelnes Argument p, das eine Folge ist, die die Werte jedes Grammatiksymbols in der entsprechenden Regel enthält. Die Werte von p[i] werden wie hier gezeigt auf Grammatiksymbole abgebildet:

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

• Bei Tokens entspricht der "Wert" des entsprechenden p[i] dem im Lexer-Modul zugewiesenen p.value Attribut. PLUS hat also den Wert + .

• Für Nichtterminals wird der Wert durch das bestimmt, was in p[0] . Wenn nichts platziert wird, lautet der Wert None. Außerdem ist p[-1] nicht dasselbe wie p[3] , da p keine einfache Liste ist ( p[-1] kann eingebettete Aktionen angeben (hier nicht erläutert)).

Beachten Sie, dass die Funktion einen beliebigen Namen haben kann, solange p_ vorangestellt ist.

• Die p_error(p) -Regel wird definiert, um Syntaxfehler yyerror (wie yyerror in yacc / bison).

• Mehrere Grammatikregeln können zu einer einzigen Funktion kombiniert werden. Dies ist eine gute Idee, wenn Produktionen eine ähnliche Struktur haben.

    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] 
  

• Zeichenliterale können anstelle von Token verwendet werden.

    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]
  

  Natürlich müssen die Literale im Lexer-Modul angegeben werden.

• Leere Produktionen haben das '''symbol : '''

• Um das Startsymbol explizit zu setzen, verwenden Sie start = 'foo' , wobei foo ein Nicht-Terminal ist.

• Das Festlegen von Priorität und Assoziativität kann mithilfe der Prioritätsvariablen erfolgen.

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

  Token werden vom niedrigsten bis zum höchsten Rang angeordnet. nonassoc bedeutet, dass diese Tokens nicht assoziieren. Dies bedeutet, dass so etwas wie a < b < c illegal ist, während a < b noch legal ist.

• parser.out ist eine Debugging-Datei, die erstellt wird, wenn das Programm yacc zum ersten Mal ausgeführt wird. Immer wenn ein Verschiebungs- / Reduzierungskonflikt auftritt, verschiebt sich der Parser immer.