Der allgemeine Ablauf beim Erstellen eines Compilers ist wie folgt, und vorherige war bis zur Nummer 1. Dieses Mal erstellen wir den zweiten Syntaxbaum (nur einen Teil).
Beim Pyparsing müssen Sie aufgrund der späteren Strukturierungsfunktion keine Symbole wie ';' im Analyseergebnis behalten. Wenn Sie Suppress () verwenden, wird das Token nicht in das Ergebnis aufgenommen. Wenn Sie es nicht zuerst unterdrücken, ist es schwierig, das Ergebnis zu sehen. Beginnen wir also mit diesem Thema.
Ich werde die Analyseergebnisse bis zum letzten Mal erneut veröffentlichen.
['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', '.']
Lassen Sie uns unterdrücken (),;. Und überprüfen Sie den Effekt.
#Zum Anfang hinzufügen.
LPAR, RPAR, COMMA, SEMICOLON, DOT = map(Suppress, "(),;.")
#Ersetzen Sie die Zeichenfolge durch eine Konstante
# before
# factor << (ident | number | "(" + expression + ")")
# after
factor << (ident | number | LPAR + expression + RPAR)
#Ähnlich, ; .Durch eine Konstante ersetzen
Lassen Sie uns das Beispielprogramm wie zuvor analysieren. Das Symbol ist verschwunden.
$ 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']
Die perspektivischen Ergebnisse, die wir bisher gesehen haben, sind eindimensionale Arrays und haben keine Struktur. Erstellen wir eine Struktur, indem wir dem Parser Gruppeninformationen hinzufügen.
Um eine statische Struktur zu erhalten, verwenden Sie Group (), um Token zu einem zu kombinieren. Schauen wir uns ein konkretes Beispiel an. Nehmen Sie die folgenden Änderungen vor, um die Liste der Variablen zu gruppieren:
# 11. var
var = VAR + Group(ident + ZeroOrMore(COMMA + ident)) + SEMICOLON
Dies ist das Ergebnis einer erneuten Analyse. Die Liste der Variablen am Anfang steht in Klammern!
['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']
Dann kann gesagt werden, dass es in Group () eingeschlossen werden sollte, aber beim Pyparsing gibt es eine andere konventionelle Möglichkeit, .setParseAction zu verwenden.
Mit Pyparsing ist es möglich, einen Rückruf aufzurufen, wenn der Parser erfolgreich analysiert wurde. Eine Liste von Token wird an diesen Rückruf übergeben, und Sie können die Token durch den Rückgabewert ersetzen. Lassen Sie uns die Variablendeklaration auf die gleiche Weise wie zuvor in [] einfügen.
# 11. var
def var_list(tokens):
tokens = tokens.asList()
return [tokens[0], tokens[1:]]
var = VAR + ident + ZeroOrMore(COMMA + ident) + SEMICOLON
var.setParseAction(var_list)
Als ich es analysierte, erhielt ich das gleiche Ergebnis wie zuvor.
['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']
Versuchen Sie, anstatt eine Funktion aufzurufen, den Klassenkonstruktor aufzurufen. Wenn Sie mit Group () vorverarbeiten, können Sie die Klasse ordentlich schreiben.
# 11. var
class Var(object):
def __init__(self, tokens):
tokens = tokens.asList()
self.variables = tokens[1]
var = VAR + Group(ident + ZeroOrMore(COMMA + ident)) + SEMICOLON
var.setParseAction(Var)
Ergebnis. Oh! Das Objekt wurde eingegeben. Auf diese Weise können Sie ** direkt beim Ausführen des Parsers ** einen AST generieren **.
[<__main__.Var object at 0x10d418710>, 'PROCEDURE', 'square', 'BEGIN', 'squ', ':=', 'x', '*', 'x', 'END', 'BEGIN', 'x', ':=', '1', 'WHILE', 'x', '<=', '10', 'DO', 'BEGIN', 'CALL', 'square', 'x', ':=', 'x', '+', '1', 'END', 'END']
Der Rückruf kann eine Funktion oder eine Klasse sein, solange er aufgerufen werden kann. Seien Sie vorsichtig, da die Bedeutung der Argumente je nach Anzahl der Argumente unterschiedlich ist.
original_string = Originalstring, der gerade analysiert wird location = location der übereinstimmenden Zeichenfolge Token = ein Array übereinstimmender Token. Das Token ist ein ParseResults-Objekt
Ausdrücke haben eine komplexe Abfolge von Berechnungen, aber am Ende sind sie im Grunde genommen Begriffe und Operatoren. Die Verschachtelung ist unter Berücksichtigung der Priorität der Bediener obligatorisch. Es ist mühsam, selbst zu schreiben, aber Pyparsing verfügt über ein Dienstprogramm namens "infixNotation", das automatisch einen Parser erstellt, indem nur die Reihenfolge der Operatoren definiert wird. Löschen Sie den Parser basierend auf dem ursprünglichen BNF.
Das Vorzeichen vor dem Begriff ist der unäre Operator, und die übliche Operation mit vier Regeln ist der binäre Operator. Der Vergleichsoperator (<< = >> = = #) ist auch ein Begleiter des Binäroperators. Lassen Sie es uns tatsächlich definieren.
Die Verwendung von oneOf bedeutet, dass die Operatoren identisch sind. Beachten Sie, dass das Ergebnis gegen die Regel verstößt, dass "dieselben Operatoren von links berechnet werden", wenn Sie dies versehentlich in zwei Zeilen schreiben.
opAssoc.RIGHT und LEFT geben an, ob der Bediener an die rechte oder linke Seite gebunden ist. Der Operator # bedeutet! = In PL / 0.
# term = Forward()
# factor = Forward()
# expression = Optional(oneOf("+ -")) + term + ZeroOrMore(oneOf("+ -") + term)
# term << (factor + ZeroOrMore(oneOf("* /") + factor))
# factor << (ident | number | LPAR + expression + RPAR)
#infixNotation definiert die Priorität von Operatoren.
#Schreiben Sie denselben Operator in eine Zeile.
UNARY, BINARY, TERNARY = 1, 2, 3
factor = ident | number
expression = infixNotation(
factor,
[
(oneOf("+ -"), UNARY, opAssoc.RIGHT), #Der Code hat die höchste Priorität.
(oneOf("* /"), BINARY, opAssoc.LEFT), #Multiplikation und Division haben Vorrang vor Addition und Subtraktion
(oneOf("+ -"), BINARY, opAssoc.LEFT),
]
)
Schreiben Sie den Zustand auf die gleiche Weise neu.
# 4. condition
#condition = ODD + expression | expression + oneOf('= # < <= > >=') + expression
condition = infixNotation(
expression,
[
(ODD, UNARY, opAssoc.RIGHT),
(oneOf("< <= > >="), BINARY, opAssoc.LEFT),
(oneOf("= #"), BINARY, opAssoc.LEFT),
]
)
Ausführungsergebnis. Sie können sehen, dass der Ausdruck in [] eingeschlossen ist.
['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']
Übrigens können die vier Regeln korrekt analysiert werden.
>>> print expression.parseString('1 + 2 * 3 + 4')
[['1', '+', ['2', '*', '3'], '+', '4']]
>>> print expression.parseString('1 + 2 / 3 * 4 - -5')
[['1', '+', ['2', '/', '3', '*', '4'], '-', ['-', '5']]]
Ich habe einen Syntaxbaum aus einer Liste von Token erstellt. Wir haben auch einen Syntaxbaum für Ausdrücke generiert, der einige der in BNF- und Operatorprioritäten definierten Syntax berücksichtigt. Ich habe nur einen Teil implementiert, da es eine Methode gibt, um AST direkt in Pyparsing zu generieren, und selbst wenn es implementiert ist, wird es verworfen. Generieren Sie beim nächsten Mal einen AST, der alle Grammatiken unterstützt.
pl0_parser.py
# -*- coding: utf-8 -*-
from pyparsing import *
LPAR, RPAR, COMMA, SEMICOLON, DOT = map(Suppress, "(),;.")
# 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+)?")
UNARY, BINARY, TERNARY = 1, 2, 3
factor = ident | number
expression = infixNotation(
factor,
[
(oneOf("+ -"), UNARY, opAssoc.RIGHT), #Code hat die höchste Priorität
(oneOf("* /"), BINARY, opAssoc.LEFT), #Multiplikation und Division haben Vorrang vor Addition und Subtraktion
(oneOf("+ -"), BINARY, opAssoc.LEFT),
]
)
# 4. condition
#condition = ODD + expression | expression + oneOf('= # < <= > >=') + expression
condition = infixNotation(
expression,
[
(ODD, UNARY, opAssoc.RIGHT),
(oneOf("< <= > >="), BINARY, opAssoc.LEFT),
(oneOf("= #"), BINARY, opAssoc.LEFT),
]
)
# 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(SEMICOLON + statement) + END
| if_statement
| while_statement
)
# 10. const
const = CONST + Group(Group(ident + "=" + number) + ZeroOrMore(COMMA + ident + "=" + number)) + SEMICOLON
# 11. var
var = VAR + Group(ident + ZeroOrMore(COMMA + ident)) + SEMICOLON
# 12. procedure
block = Forward()
procedure = PROCEDURE + ident + SEMICOLON + block + SEMICOLON
# 13. block
block << Optional(const) + Optional(var) + ZeroOrMore(procedure) + statement
# 14. program
program = block + DOT
if __name__ == '__main__':
import sys
with open(sys.argv[1], 'r') as fp:
txt = fp.read()
print program.parseString(txt)
Recommended Posts