Bei der Arbeit musste ich von einem DSL zu einem anderen konvertieren, also entschied ich mich, einen Compiler mit pyparsing zu schreiben. Um Pyparsing zu verstehen, implementieren wir zunächst einen Parser am Beispiel von PL / 0.
PL / 0 ist eine Sprache mit einer Grammatik ähnlich Pascal. Es ist eine sehr kleine Sprachspezifikation für Bildungszwecke. Eigentlich habe ich es auch als Lehrmaterial für die Compilerausbildung verwendet, als ich in meinem dritten Studienjahr war.
Unten finden Sie ein Beispiel aus Wikipedia.
ex1.pl0
VAR x, squ;
PROCEDURE square;
BEGIN
squ := x * x
END;
BEGIN
x := 1;
WHILE x <= 10 DO
BEGIN
CALL square;
! squ;
x := x + 1;
END
END.
Um einen Parser zu schreiben, benötigen Sie eine Grammatikdefinition. Eine der grammatikalischen Notationen ist [BNF](http://ja.wikipedia.org/wiki/%E3%83%90%E3%83%83%E3%82%AB%E3%82%B9%E3 % 83% BB% E3% 83% 8A% E3% 82% A6% E3% 82% A2% E8% A8% 98% E6% B3% 95). Das (E) BNF von PL / 0 unten wurde von der verlinkten Wikipedia erhalten. BNF besteht aus Terminierungssymbolen und Produktionsregeln.
Das PL / 0 BNF in Wikipedia enthielt keine Identität, also habe ich es hinzugefügt.
Die reservierten Wörter sind in Kleinbuchstaben geschrieben, aber Sie müssen sie in Großbuchstaben unterstützen, um das vorherige Beispiel zu analysieren.
pl0_bnf.txt
ident = alpha { alpha | number | '_' } .
program = block "." .
block = [ "const" ident "=" number {"," ident "=" number} ";"]
[ "var" ident {"," ident} ";"]
{ "procedure" ident ";" block ";" } statement .
statement = [ ident ":=" expression | "call" ident |
"begin" statement {";" statement } "end" |
"if" condition "then" statement |
"while" condition "do" statement ].
condition = "odd" expression |
expression ("="|"#"|"<"|"<="|">"|">=") expression .
expression = [ "+"|"-"] term { ("+"|"-") term}.
term = factor {("*"|"/") factor}.
factor = ident | number | "(" expression ")".
Es ist schwierig, plötzlich einen Parser zu schreiben, der die Grammatik vollständig erfüllt. Was soll ich machen? Es ist eine gute Idee, in der Nähe des Endsymbols zu beginnen, jeden minimalen Baustein zu implementieren und zu testen und sie dann zu kombinieren und zu stapeln.
Insbesondere ist die Reihenfolge reserviertes Schlüsselwort, Bezeichner, Ausdruck, Anweisung, Block, Deklaration und Programm. Überraschenderweise werden die Grundlagen wie die Variablendeklaration gegen Ende implementiert.
** Es ist sehr wichtig, zuerst eine Richtlinie zu erstellen. ** Implementieren Sie eine Produktionsregel Wenn Sie dabei eine nicht implementierte Produktionsregel finden, bleiben Sie wahrscheinlich in den Tiefen verschachtelter und rekursiver Referenzen stecken, wenn Sie sie implementieren und zurückkehren.
Lassen Sie es uns in der folgenden Reihenfolge implementieren.
Die reservierten Wörter für PL / 0 sind const, var, procedure, call, begin, end, wenn, dann, while, ungerade, soweit sie von BNF gelesen werden. Mit Pyparsing können Sie reservierte Wörter mit "Keyword ()" deklarieren. CaselessKeyword () wird verwendet, um caseless reservierte Wörter zu deklarieren.
CONST = CaselessKeyword('CONST')
VAR = CaselessKeyword('VAR')
:
Anstatt zu schreiben, wird empfohlen, wie folgt zu schreiben. Gibt es nicht eine trockenere Art zu schreiben ...
from pyparsing import CaselessKeyword, MatchFirst
(CONST, VAR, PROCEDURE, CALL, BEGIN, END, IF, THEN, WHILE, DO, ODD) = map(CaselessKeyword,
"CONST, VAR, PROCEDURE, CALL, BEGIN, END, IF, THEN, WHILE, DO, ODD".replace(",","").split())
keyword = MatchFirst((CONST, VAR, PROCEDURE, CALL, BEGIN, END, IF, THEN, WHILE, DO, ODD))
Das Ergebnis wurde unabhängig vom Fall als CONST erkannt.
>>> print keyword.parseString('CONST')
['CONST']
>>> print keyword.parseString('const')
['CONST']
Die Definition eines Bezeichners ist im Allgemeinen ein Alphabet, gefolgt von einem Alphabet oder einer Zahl und _, also folgen wir dem. Außerdem können reservierte Wörter keine Bezeichner sein. Schreiben Sie daher am Anfang das Schlüsselwort ~.
from pyparsing import Word, alphas, alphanums
ident = ~keyword + Word(alphas, alphanums+"_")
Durch das Parsen gültiger Bezeichner, ungültiger Bezeichner und reservierter Wörter waren nur gültige Bezeichner erfolgreich.
>>> print repr(ident.parseString('valid_id'))
(['valid_id'], {})
>>> print repr(ident.parseString('0123bad_id'))
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/usr/lib/python2.7/dist-packages/pyparsing.py", line 1041, in parseString
raise exc
pyparsing.ParseException: Expected W:(abcd...,abcd...) (at char 0), (line:1, col:1)
>>> print repr(ident.parseString('CONST'))
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/usr/lib/python2.7/dist-packages/pyparsing.py", line 1041, in parseString
raise exc
pyparsing.ParseException: Found unwanted token, {"CONST" | "VAR" | "PROCEDURE" | "CALL" | "BEGIN" | "END" | "IF" | "THEN" | "WHILE" | "DO" | "ODD"} (at char 0), (line:1, col:1)
Die PL / 0-Formel wird mit dem folgenden BNF vervollständigt.
expression = [ "+"|"-"] term { ("+"|"-") term}.
term = factor {("*"|"/") factor}.
factor = ident | number | "(" expression ")"
Die Implementierung von Pyparsing sieht folgendermaßen aus: Wenn auf die Produktionsregel rekursiv verwiesen wird, bereiten Sie die Box zuerst mit "Weiterleiten" vor. Verwenden Sie <<, um die Produktionsregel später festzulegen. Die Verwendung von oneOf bedeutet, dass die Operatoren dieselbe Priorität haben.
<<Versehentlich mit dem üblichen Kleber=Wenn Sie verwenden, erhalten Sie einen Fehler unbekannter Ursache und Sie werden durch das Debuggen beunruhigt. Ebenfalls<<Bei Verwendung der rechten Seite()Lassen Sie es uns abschließen.x << y | zWannx << (y | z)は演算子の優先順位に起因して計算結果がこWannななるため。当然利用したいのは後者です。これもパース時に原因不明のエラーWannなり、デバッグに悩まされます。pyparsingの仕様なので、そういうものだWann思って気をつけるしかないです。
number = Regex(r"\d+(\.\d*)?([eE][+-]?\d+)?")
term = Forward()
factor = Forward()
expression = Optional(oneOf("+ -")) + term + ZeroOrMore( oneOf("+ -") + term)
term << factor + ZeroOrMore(oneOf("* /") + factor)
factor << ident | number | "(" + expression + ")"
Lass es uns testen. Es scheint, dass es richtig analysiert wird.
>>> expression.parseString('123')
(['123'], {})
>>> expression.parseString('123+456')
(['123', '+', '456'], {})
>>> expression.parseString('(x+y)*z')
(['(', 'x', '+', 'y', ')', '*', 'z'], {})
PL / 0 hat aus irgendeinem Grund einen einzelnen Termoperator namens "odd". Davon abgesehen sind es nur gewöhnliche Binäroperatoren. Pyparsing hat einen Mechanismus zum Generieren eines Parsers für bedingte Ausdrücke namens infixNotation, aber hier werden wir ihn BNF treu implementieren.
condition = "odd" expression |
expression ("="|"#"|"<"|"<="|">"|">=") expression .
Die Implementierung ist wie folgt:
condition = ODD + expression | expression + oneOf('= # < <= > >=') + expression
Prüfung
>>> condition.parseString('odd 1')
(['ODD', '1'], {})
>>> condition.parseString('3 <= 1')
(['3', '<=', '1'], {})
Die BNF der Zuweisung lautet "ident": = "expression". Es ist einfach, da sowohl ident als auch expression bereits implementiert sind.
assign_statement = ident + ":=" + expression
Da dasselbe wiederholt wird, werden wir es nur von hier aus implementieren.
call_statement = CALL + ident
Definieren Sie die IF-Anweisung. Die Aussage, die den gesamten Satz darstellt, ist noch nicht erschienen, daher werde ich sie in Forward deklarieren.
statement = Forward()
if_statement = IF + condition + THEN + statement
while_statement = WHILE + condition + DO + statement
Nachdem wir alle Teile haben, definieren wir endlich die Regeln für die Anweisungsgenerierung. Die BNF ist wie folgt:
statement = [ ident ":=" expression | "call" ident |
"begin" statement {";" statement } "end" |
"if" condition "then" statement |
"while" condition "do" statement ].
Implementieren Sie mit Pyparsing so wie es ist.
statement = Optional(assign_statement
| call_statement
| BEGIN + statement + ZeroOrMore(";" + statement) + END
| if_statement
| while_statement
)
Ich werde müde, also habe ich es einfach umgesetzt.
const = CONST + ident + "=" + number + ZeroOrMore("," + ident + "=" + number) + ";"
var = VAR + ident + ZeroOrMore("," + ident) + ";"
Konzentrieren Sie sich nur auf diesen Teil der BNF-Prozedur "ident"; "block"; "". Die äußere Wiederholung wird ausgeführt, wenn der Block montiert ist.
block = Forward()
procedure = PROCEDURE + ident + ";" + block + ";"
block
block << Optional(const) + Optional(var) + ZeroOrMore(procedure) + statement
program Dies ist die Produktionsregel der obersten Ebene. Danke für deine harte Arbeit.
program = block + "."
Lassen Sie uns das am Anfang veröffentlichte Beispielprogramm analysieren.
$ python pl0_parser.py ex1.pl0
Traceback (most recent call last):
File "pl0_parser.py", line 64, in <module>
print program.parseString(txt)
File "/usr/lib/python2.7/dist-packages/pyparsing.py", line 1041, in parseString
raise exc
pyparsing.ParseException: Expected "." (at char 59), (line:8, col:1)
Es geht nicht vorbei. Warum? Da dort Zeile: 8, Spalte: 1 steht, kann BEGIN-END nicht analysiert werden, und es scheint, dass er am Ende des Programms ein "." Erwartet. Kannst du hier nicht ein bisschen mehr Fehler machen? Ich werde es nur mit dem Anweisungsparser zur Bestätigung testen.
>>> statement.parseString('''\
... BEGIN
... x := 1;
... WHILE x <= 10 DO
... BEGIN
... CALL square;
... ! squ;
... x := x + 1;
... END
... END
... ''')
([], {})
Das Ergebnis ist leer und schlägt mit Sicherheit fehl. Fehler, die nicht abstürzen, sind beim Debuggen umständlich. Wenn Sie genau hinschauen, finden Sie einen unbekannten Satz: "! Squ;". Dies ist eine erweiterte PL / 0-Syntax und wird im BNF dieser Implementierung nicht definiert. Löschen Sie es und führen Sie es erneut aus.
$ python pl0_parser.py ex1.pl0
['VAR', 'x', ',', 'squ', ';', 'PROCEDURE', 'square', ';', 'BEGIN', 'squ', ':=', 'x', '*', 'x', 'END', ';', 'BEGIN', 'x', ':=', '1', ';', 'WHILE', 'x', '<=', '10', 'DO', 'BEGIN', 'CALL', 'square', ';', 'x', ':=', 'x', '+', '1', ';', 'END', 'END', '.']
Es ging gut!
Das nächste Mal möchte ich ernsthaft einen Syntaxbaum (AST) erstellen und Code generieren.
Schließlich werde ich die Quelle des Parsers veröffentlichen, den ich bisher implementiert habe.
pl0_parser.py
from pyparsing import CaselessKeyword, MatchFirst, Word, alphas, alphanums, Forward, Optional, oneOf, ZeroOrMore, Regex
# 1. reserved keyword
(CONST, VAR, PROCEDURE, CALL, BEGIN, END, IF, THEN, WHILE, DO, ODD) = map(CaselessKeyword,
"CONST, VAR, PROCEDURE, CALL, BEGIN, END, IF, THEN, WHILE, DO, ODD".replace(",", "").split())
keyword = MatchFirst((CONST, VAR, PROCEDURE, CALL, BEGIN, END, IF, THEN, WHILE, DO, ODD))
# 2. identifier
ident = ~keyword + Word(alphas, alphanums + "_")
# 3. expression
number = Regex(r"\d+(\.\d*)?([eE][+-]?\d+)?")
term = Forward()
factor = Forward()
expression = Optional(oneOf("+ -")) + term + ZeroOrMore(oneOf("+ -") + term)
term << (factor + ZeroOrMore(oneOf("* /") + factor))
factor << (ident | number | "(" + expression + ")")
# 4. condition
condition = ODD + expression | expression + oneOf('= # < <= > >=') + expression
# 5. assignment
assign_statement = ident + ":=" + expression
# 6. call
call_statement = CALL + ident
# 7. if-then
statement = Forward()
if_statement = IF + condition + THEN + statement
# 8. while-do
while_statement = WHILE + condition + DO + statement
# 9. statement
statement << Optional(assign_statement
| call_statement
| BEGIN + statement + ZeroOrMore(";" + statement) + END
| if_statement
| while_statement
)
# 10. const
const = CONST + ident + "=" + number + ZeroOrMore("," + ident + "=" + number) + ";"
# 11. var
var = VAR + ident + ZeroOrMore("," + ident) + ";"
# 12. procedure
block = Forward()
procedure = PROCEDURE + ident + ";" + block + ";"
# 13. block
block << Optional(const) + Optional(var) + ZeroOrMore(procedure) + statement
# 14. program
program = block + "."
if __name__ == '__main__':
import sys
with open(sys.argv[1], 'r') as fp:
txt = fp.read()
print program.parseString(txt)
Recommended Posts