Python Language
Python Lex-Yacc
Zoeken…
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 objectt
noemen) heeft de volgende kenmerken:-
t.type
dat hett.type
is (als een tekenreeks) (bijvoorbeeld:'NUMBER'
,'PLUS'
, enz.). Standaard ist.type
ingesteld op de naam na hett_
voorvoegsel. -
t.value
die het lexeme is (de werkelijke overeenkomende tekst) -
t.lineno
wat het huidige regelnummer is (dit wordt niet automatisch bijgewerkt, omdat de lexer niets van regelnummers weet). Werk linneno bij met de functiet_newline
.
def t_newline(t): r'\n+' t.lexer.lineno += len(t.value)
-
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:
- Tokens gedefinieerd door functies worden toegevoegd in dezelfde volgorde als ze in het bestand verschijnen.
- 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
alst.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 isGebruik
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 kenmerkp.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 isp[-1]
niet hetzelfde alsp[3]
, omdatp
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 alsyyerror
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'
, waarbijfoo
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 alsa < b < c
illegaal is, terwijla < 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.