Python Language => Python Lex-Yacc

Invoering

PLY is een pure Python-implementatie van de populaire compileerconstructietools lex en yacc.

Opmerkingen

Aanvullende links:

Aan de slag met PLY

Volg de onderstaande stappen om PLY op uw machine voor python2 / 3 te installeren:

Download de broncode van hier .
Pak het gedownloade zipbestand uit
Navigeer naar de uitgepakte map ply-3.10
Voer de volgende opdracht in uw terminal uit: python setup.py install

Als u al het bovenstaande hebt voltooid, zou u nu de PLY-module moeten kunnen gebruiken. Je kunt het testen door een python-interpreter te openen en import ply.lex typen.

Opmerking: Gebruik geen pip om PLY installeert, zal het een gebroken distributie op uw computer te installeren.

De "Hallo wereld!" van PLY - Een eenvoudige rekenmachine

Laten we de kracht van PLY demonstreren met een eenvoudig voorbeeld: dit programma neemt een rekenkundige uitdrukking als een stringinvoer en probeert het op te lossen.

Open je favoriete editor en kopieer de volgende 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)

Sla dit bestand op als calc.py en voer het uit.

Output:

-8

Dat is het juiste antwoord voor -4 * - (3 - 5) .

Deel 1: Tokeniserende invoer met Lex

Er zijn twee stappen die de code uit voorbeeld 1 heeft uitgevoerd: een tokeniseren van de invoer, wat betekent dat het symbolen zocht die de rekenkundige uitdrukking vormen, en de tweede stap was parseren , waarbij de geëxtraheerde tokens werden geanalyseerd en het resultaat werd geëvalueerd.

Deze sectie biedt een eenvoudig voorbeeld van het tokeniseren van gebruikersinvoer en splitst het vervolgens regel voor regel op.

    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)

Sla dit bestand op als calclex.py . We zullen dit gebruiken bij het bouwen van onze Yacc-parser.

Afbreken

Importeer de module met import ply.lex
Alle lexers moeten een lijst bieden met de naam tokens die alle mogelijke tokennamen definieert die door de lexer kunnen worden geproduceerd. Deze lijst is altijd verplicht.
```
 tokens = [
    'NUMBER',
    'PLUS',
    'MINUS',
    'TIMES',
    'DIVIDE',
    'LPAREN',
    'RPAREN',
 ]
```

tokens kunnen ook een tuple van strings zijn (in plaats van een string), waarbij elke string een token als eerder aangeeft.

De regex-regel voor elke string kan worden gedefinieerd als een string of als een functie. In beide gevallen moet de variabelenaam worden voorafgegaan door t_ om aan te geven dat het een regel is voor het matchen van tokens.
- Voor eenvoudige tokens kan de reguliere expressie worden opgegeven als tekenreeksen: t_PLUS = r'\+'
- Als een bepaalde actie moet worden uitgevoerd, kan een tokenregel worden opgegeven als een functie.
```
   def t_NUMBER(t):
       r'\d+'
       t.value = int(t.value)
       return t
```
  Let op, de regel is gespecificeerd als een doc-string binnen de functie. De functie accepteert een argument dat een instantie van LexToken , voert een actie uit en retourneert het argument vervolgens.
  Als u een externe string wilt gebruiken als regexregel voor de functie in plaats van een doc-string op te geven, overweeg dan het volgende voorbeeld:
```
   @TOKEN(identifier)         # identifier is a string holding the regex
   def t_ID(t):
       ...      # actions
```
- Een exemplaar van het LexToken object (laten we dit object t noemen) heeft de volgende kenmerken:
  1. t.type dat het t.type is (als een tekenreeks) (bijvoorbeeld: 'NUMBER' , 'PLUS' , enz.). Standaard is t.type ingesteld op de naam na het t_ voorvoegsel.
  2. t.value die het lexeme is (de werkelijke overeenkomende tekst)
  3. t.lineno wat het huidige regelnummer is (dit wordt niet automatisch bijgewerkt, omdat de lexer niets van regelnummers weet). Werk linneno bij met de functie t_newline .
```
  def t_newline(t):
      r'\n+'
      t.lexer.lineno += len(t.value)
```
  1. t.lexpos dat is de positie van het token ten opzichte van het begin van de invoertekst.
- Als er niets wordt geretourneerd vanuit een regexregelfunctie, wordt het token verwijderd. Als u een token wilt verwijderen, kunt u ook het voorvoegsel t_ignore_ toevoegen aan een variabele van de regex-regel in plaats van een functie voor dezelfde regel te definiëren.
```
   def t_COMMENT(t):
       r'\#.*'
       pass
       # No return value. Token discarded
```
  ...Is hetzelfde als:
```
   t_ignore_COMMENT = r'\#.*'
```
  ^{Dit is natuurlijk ongeldig als u een actie uitvoert wanneer u een opmerking ziet. Gebruik in dat geval een functie om de regex-regel te definiëren.}
  Als u voor sommige tekens geen token hebt gedefinieerd, maar deze toch wilt negeren, gebruikt u t_ignore = "<characters to ignore>" (deze voorvoegsels zijn nodig):
```
   t_ignore_COMMENT = r'\#.*'
   t_ignore  = ' \t'    # ignores spaces and tabs
```
- Bij het bouwen van de hoofdregex voegt lex de regexen die in het bestand zijn gespecificeerd als volgt toe:
  1. Tokens gedefinieerd door functies worden toegevoegd in dezelfde volgorde als ze in het bestand verschijnen.
  2. Tokens gedefinieerd door strings worden toegevoegd in afnemende volgorde van de stringlengte van de string die de regex voor dat token definieert.
  Als u == en = in hetzelfde bestand vindt, profiteer dan van deze regels.
- Letterlijke tekens zijn tokens die worden geretourneerd zoals ze zijn. Zowel t.type als t.value worden ingesteld op het teken zelf. Definieer een lijst met letterlijke teksten als zodanig:
```
literals = [ '+', '-', '*', '/' ]
```
  of,
```
literals = "+-*/"
```
  Het is mogelijk om tokenfuncties te schrijven die extra acties uitvoeren wanneer literalen worden vergeleken. U moet echter het tokentype correct instellen. Bijvoorbeeld:
```
literals = [ '{', '}' ]

def t_lbrace(t):
    r'\{'
    t.type = '{'  # Set token type to the expected literal (ABSOLUTE MUST if this is a literal)
    return t
```
- Fouten verwerken met de functie 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)
```
  Over het algemeen slaat t.lexer.skip(n) n tekens in de invoertekenreeks over.

Laatste voorbereidingen:

Bouw de lexer met behulp van lexer = lex.lex() .

U kunt ook alles in een klasse plaatsen en use use van de klasse aanroepen om de lexer te definiëren. bv:

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

Lever input met lexer.input(data) waarbij data een string is

Gebruik lexer.token() om de tokens te verkrijgen die overeenkomen met tokens. Je kunt in een lus over lexer itereren zoals in:

for i in lexer: 
    print(i)

Deel 2: Tokenized invoer parseren met Yacc

In deze sectie wordt uitgelegd hoe de tokenized invoer uit Deel 1 wordt verwerkt - dit gebeurt met Context Free Grammars (CFG's). De grammatica moet worden opgegeven en de tokens worden verwerkt volgens de grammatica. Onder de motorkap gebruikt de parser een 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)

Afbreken

Elke grammaticaregel wordt gedefinieerd door een functie waarbij de docstring naar die functie de juiste contextvrije grammatica-specificatie bevat. De verklaringen waaruit het functielichaam bestaat, implementeren de semantische acties van de regel. Elke functie accepteert een enkel argument p dat een reeks is die de waarden van elk grammaticasymbool in de overeenkomstige regel bevat. De waarden van p[i] worden toegewezen aan grammaticasymbolen zoals hier weergegeven:
```
  def p_expression_plus(p):
      'expression : expression PLUS term'
      #   ^            ^        ^    ^
      #  p[0]         p[1]     p[2] p[3]

      p[0] = p[1] + p[3]
```

Voor tokens is de "waarde" van de overeenkomstige p[i] hetzelfde als het kenmerk p.value dat is toegewezen in de lexer-module. PLUS heeft dus de waarde + .
Voor niet-terminals wordt de waarde bepaald door wat er in p[0] wordt geplaatst. Als er niets wordt geplaatst, is de waarde Geen. Ook is p[-1] niet hetzelfde als p[3] , omdat p geen eenvoudige lijst is ( p[-1] kan ingesloten acties opgeven (hier niet besproken)).

Merk op dat de functie elke naam kan hebben, zolang deze wordt voorafgegaan door p_ .

De p_error(p) -regel is gedefinieerd om syntaxisfouten te vangen (hetzelfde als yyerror in yacc / bison).

Meerdere grammaticaregels kunnen worden gecombineerd tot een enkele functie, wat een goed idee is als producties een vergelijkbare structuur hebben.

  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]

Letterlijke tekens kunnen worden gebruikt in plaats van tokens.

  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]

Natuurlijk moeten de letterlijke waarden worden opgegeven in de lexermodule.

Lege producties hebben de vorm '''symbol : '''
Om het startsymbool expliciet in te stellen, gebruikt u start = 'foo' , waarbij foo een niet-terminal is.
Voorrang en associativiteit instellen kan worden gedaan met behulp van de prioriteitsvariabele.
```
  precedence = (
      ('nonassoc', 'LESSTHAN', 'GREATERTHAN'),  # Nonassociative operators
      ('left', 'PLUS', 'MINUS'),
      ('left', 'TIMES', 'DIVIDE'),
      ('right', 'UMINUS'),            # Unary minus operator
  )
```
Tokens zijn geordend van laagste naar hoogste prioriteit. nonassoc betekent dat die tokens niet associëren. Dit betekent dat zoiets als a < b < c illegaal is, terwijl a < b nog steeds legaal is.
parser.out is een foutopsporingsbestand dat wordt gemaakt wanneer het yacc-programma voor de eerste keer wordt uitgevoerd. Wanneer een shift / verminder conflict optreedt, verschuift de parser altijd.

Modified text is an extract of the original Stack Overflow Documentation

Licentie onder CC BY-SA 3.0

Niet aangesloten bij Stack Overflow

Python Language
Python Lex-Yacc

Zoeken…

Invoering

Opmerkingen

Aan de slag met PLY

De "Hallo wereld!" van PLY - Een eenvoudige rekenmachine

Deel 1: Tokeniserende invoer met Lex

Afbreken

Deel 2: Tokenized invoer parseren met Yacc

Afbreken