Python Language
Python Lex-Yacc

Introduktion

Anmärkningar

Komma igång med PLY

För att installera PLY på din maskin för python2 / 3, följ stegen nedan:

1. Ladda ner källkoden härifrån .
2. Packa upp den nedladdade zip-filen
3. Navigera i den opackade ply-3.10 mappen
4. Kör följande kommando i din terminal: python setup.py install

Om du har slutfört alla ovanstående bör du nu kunna använda PLY-modulen. Du kan testa det genom att öppna en python-tolk och skriva import ply.lex .

Obs: Använd inte pip att installera PLY, det kommer att installera en trasig distribution på din maskin.

"Hej, världen!" av PLY - En enkel kalkylator

Låt oss visa kraften hos PLY med ett enkelt exempel: det här programmet kommer att ta ett aritmetiskt uttryck som en stränginmatning och försöka lösa det.

Öppna din favoritredigerare och kopiera följande 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)

Spara den här filen som calc.py och kör den.

Produktion:

-8

Vilket är det rätta svaret för -4 * - (3 - 5) .

Del 1: Tokenizing Input med Lex

Det finns två steg som koden från exempel 1 utförde: ett tokeniserade ingången, vilket betyder att den letade efter symboler som utgör det aritmetiska uttrycket, och det andra steget analyserades , vilket innebär att analysera de extraherade token och utvärdera resultatet.

Det här avsnittet ger ett enkelt exempel på hur man markerar användarinmatning och bryter sedan ned rad för rad.

    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)

Spara den här filen som calclex.py . Vi kommer att använda detta när vi bygger vår Yacc-parser.

Bryta ner

1. Importera modulen med import ply.lex

2. Alla lexers måste tillhandahålla en lista som heter tokens som definierar alla möjliga tokenamn som kan produceras av lexern. Denna lista krävs alltid.

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

tokens kan också vara en tupel av strängar (snarare än en sträng), där varje sträng betecknar ett symbol som tidigare.

3. Regex-regeln för varje sträng kan definieras antingen som en sträng eller som en funktion. I båda fallen bör variabelnamnet förinställas av t_ för att beteckna att det är en regel för matchande token.

   • För enkla tokens kan det reguljära uttrycket anges som strängar: t_PLUS = r'\+'

   • Om någon typ av åtgärd behöver utföras kan en tokenregel anges som en funktion.

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

     Observera att regeln anges som en doc-sträng i funktionen. Funktionen accepterar ett argument som är ett exempel på LexToken , utför en viss åtgärd och returnerar sedan argumentet.

     Om du vill använda en extern sträng som regex-regel för funktionen istället för att ange en doc-sträng, överväg följande exempel:

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

   • En instans av LexToken objekt (låt oss kalla det här objektet t ) har följande attribut:

     1. t.type som är tokenstypen (som en sträng) (t.ex.: 'NUMBER' , 'PLUS' , etc). Som standard är t.type inställt på namnet efter prefixet t_ .
     2. t.value som är lexemet (den faktiska matchade texten)
     3. t.lineno som är det aktuella t.lineno (detta uppdateras inte automatiskt, eftersom lexern inte vet något om radnumren). Uppdatera linan med en funktion som heter t_newline .

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

     4. t.lexpos som är symbolens position relativt början på inmatningstexten.

   • Om ingenting returneras från en regex-regelfunktion kastas tokenet. Om du vill kassera ett token kan du alternativt lägga till t_ignore_-prefixet till en regex-variabel istället för att definiera en funktion för samma regel.

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

     ...Är det samma som:

        t_ignore_COMMENT = r'\#.*'
     

     ^{Detta är naturligtvis ogiltigt om du gör några åtgärder när du ser en kommentar. I vilket fall använder du en funktion för att definiera regex-regeln.}

     Om du inte har definierat ett symbol för vissa tecken men ändå vill ignorera det, använd t_ignore = "<characters to ignore>" (dessa prefix är nödvändiga):

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

   • När man bygger masterregex lägger lex till de regexer som anges i filen enligt följande:

     1. Tokens definierade av funktioner läggs till i samma ordning som de visas i filen.
     2. Tokens definierade av strängar läggs till i minskande ordning för stränglängden på strängen som definierar regexet för det symbolet.

     Om du matchar == och = i samma fil, dra fördel av dessa regler.

   • Bokstäver är symboler som returneras som de är. Både t.type och t.value kommer att ställas in på själva karaktären. Definiera en lista med bokstäver som sådan:

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

     eller,

     literals = "+-*/"
     

     Det är möjligt att skriva tokenfunktioner som utför ytterligare åtgärder när bokstäver matchas. Du måste dock ställa in tokenstypen på lämpligt sätt. Till exempel:

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

   • Hantera fel med t_error-funktionen.

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

     I allmänhet t.lexer.skip(n) över n tecken i inmatningssträngen.

4. Slutliga förberedelser:

   Bygg lexern med lexer = lex.lex() .

   Du kan också placera allt i en klass och ringa instans för klassen för att definiera lexern. T.ex:

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

   Ge inmatning med lexer.input(data) där data är en sträng

   För att få tokens använder du lexer.token() som returnerar matchade token. Du kan iterera över lexer i en slinga som i:

   for i in lexer: 
       print(i)
   

Del 2: Analysera inmatad inmatning med Yacc

Detta avsnitt förklarar hur den tokeniserade ingången från del 1 bearbetas - den görs med hjälp av Context Free Grammars (CFG). Grammatiken måste anges och tokens behandlas enligt grammatiken. Under huven använder tolkaren en LALR-tolkare.

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

Bryta ner

• Varje grammatikregel definieras av en funktion där doktringen till den funktionen innehåller lämplig kontextfri grammatikspecifikation. Uttalelserna som utgör funktionsorganet genomför de semantiska handlingarna i regeln. Varje funktion accepterar ett enda argument p som är en sekvens som innehåller värdena för varje grammarsymbol i motsvarande regel. Värdena på p[i] mappas till grammatikssymboler som visas här:

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

• För symboler är "värdet" för motsvarande p[i] detsamma som attributet p.value tilldelats i lexer-modulen. Så PLUS kommer att ha värdet + .

• För icke-terminaler bestäms värdet av vad som är placerat i p[0] . Om ingenting placeras är värdet Inget. Dessutom är p[-1] inte samma sak som p[3] , eftersom p inte är en enkel lista ( p[-1] kan ange inbäddade åtgärder (diskuteras inte här)).

Observera att funktionen kan ha valfritt namn, så länge den föregås av p_ .

• p_error(p) definieras för att fånga syntaxfel (samma som yyerror i yacc / bison).

• Flera grammatikregler kan kombineras till en enda funktion, vilket är en bra idé om produktioner har en liknande 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] 
  

• Teckenbokstäver kan användas istället för symboler.

    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]
  

  Naturligtvis måste bokstäverna anges i lexer-modulen.

• Tomma produktioner har formen '''symbol : '''

• För att uttryckligen ställa in startsymbolen, använd start = 'foo' , där foo är någon icke-terminal.

• Inställning av företräde och associativitet kan göras med hjälp av företrädesvariabeln.

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

  Tokens beställs från lägsta till högsta prioritet. nonassoc betyder att dessa symboler inte associerar. Detta innebär att något som a < b < c är olagligt medan a < b fortfarande är lagligt.

• parser.out är en felsökningsfil som skapas när yacc-programmet körs för första gången. När en skiftning / minskning av konflikt inträffar växlar tolkaren alltid.