Au travail, je devais passer d'un DSL à un autre, j'ai donc décidé d'écrire un compilateur en utilisant pyparsing. Tout d'abord, pour comprendre le pyparsing, implémentons un analyseur utilisant PL / 0 comme exemple.
PL / 0 est un langage avec une grammaire similaire à Pascal. Il s'agit d'une très petite spécification linguistique à des fins éducatives. En fait, je l'ai également utilisé comme matériel pédagogique pour la formation des compilateurs lorsque j'étais en troisième année d'université.
Vous trouverez ci-dessous un exemple de 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.
Pour écrire un analyseur, vous avez besoin d'une définition de grammaire. L'une des notations grammaticales est [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). Le (E) BNF de PL / 0 ci-dessous a été obtenu à partir du lien Wikipedia. BNF se compose de symboles de terminaison et de règles de production.
Le PL / 0 BNF dans Wikipedia ne contenait pas d'identifiant, alors je l'ai ajouté.
Les mots réservés sont en lettres minuscules, mais vous devrez les prendre en charge en majuscules pour analyser l'exemple précédent.
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 ")".
Il est difficile d'écrire soudainement un analyseur qui satisfait complètement la grammaire. Que devrais-je faire? C'est une bonne idée de commencer près du symbole de fin, d'implémenter et de tester chaque bloc de construction minimum, puis de les combiner et de les empiler.
Plus précisément, l'ordre est réservé par mot-clé, identificateur, expression, instruction, bloc, déclaration et programme. Étonnamment, les bases telles que la déclaration de variable seront implémentées vers la fin.
** Il est très important d'élaborer d'abord une politique. ** Mettre en œuvre une règle de production Si vous trouvez une règle de production non implémentée pendant que vous la faites, vous risquez de rester coincé dans les profondeurs des références imbriquées et récursives si vous l'implémentez et que vous faites des allers-retours.
Implémentons-le dans l'ordre suivant.
Les mots réservés pour PL / 0 sont const, var, procedure, call, begin, end, if, then, while, do, impair dans la mesure où ils sont lus à partir de BNF. Dans pyparsing, vous pouvez déclarer un mot réservé avec Keyword (). CaselessKeyword () est utilisé pour déclarer des mots réservés sans casse.
CONST = CaselessKeyword('CONST')
VAR = CaselessKeyword('VAR')
:
Au lieu d'écrire, il semble qu'il soit recommandé d'écrire comme suit. N'y a-t-il pas une façon d'écrire plus SÈCHE ...
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))
Le résultat a été reconnu comme CONST quel que soit le cas.
>>> print keyword.parseString('CONST')
['CONST']
>>> print keyword.parseString('const')
['CONST']
La définition d'un identifiant est généralement un alphabet, suivi d'un alphabet ou d'un nombre et _, nous allons donc suivre cela. De plus, puisque les mots réservés ne peuvent pas être des identificateurs, écrivez «~ mot-clé» au début.
from pyparsing import Word, alphas, alphanums
ident = ~keyword + Word(alphas, alphanums+"_")
Suite à l'analyse des identifiants valides, des identifiants non valides et des mots réservés, seuls les identifiants valides ont réussi.
>>> 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)
La formule PL / 0 est complétée par le BNF suivant.
expression = [ "+"|"-"] term { ("+"|"-") term}.
term = factor {("*"|"/") factor}.
factor = ident | number | "(" expression ")"
La mise en œuvre de pyparsing ressemble à ceci: Lorsque la règle de production est référencée de manière récursive, utilisez Forward pour préparer la boîte en premier. Utilisez «<<» pour définir la règle de production ultérieurement. Utiliser oneOf signifie que les opérateurs ont la même priorité.
<<Par inadvertance avec la colle habituelle=Si vous utilisez, vous obtiendrez une erreur de cause inconnue et vous serez perturbé par le débogage. Aussi<<Lors de l'utilisation du côté droit()Concluons avec.x << y | zQuandx << (y | z)は演算子の優先順位に起因して計算結果がこQuandななるため。当然利用したいのは後者です。これもパース時に原因不明のエラーQuandなり、デバッグに悩まされます。pyparsingの仕様なので、そういうものだQuand思って気をつけるしかないです。
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 + ")"
Testons-le. Il semble qu'il soit correctement analysé.
>>> expression.parseString('123')
(['123'], {})
>>> expression.parseString('123+456')
(['123', '+', '456'], {})
>>> expression.parseString('(x+y)*z')
(['(', 'x', '+', 'y', ')', '*', 'z'], {})
PL / 0 a un opérateur de terme unique appelé "impair" pour une raison quelconque. En dehors de cela, ce ne sont que des opérateurs binaires ordinaires. pyparsing a un mécanisme pour générer un analyseur d'expressions conditionnelles appelé infixNotation, mais ici nous allons l'implémenter fidèlement à BNF.
condition = "odd" expression |
expression ("="|"#"|"<"|"<="|">"|">=") expression .
La mise en œuvre est la suivante:
condition = ODD + expression | expression + oneOf('= # < <= > >=') + expression
tester
>>> condition.parseString('odd 1')
(['ODD', '1'], {})
>>> condition.parseString('3 <= 1')
(['3', '<=', '1'], {})
Le BNF de l'affectation est ʻident ": =" expression`. C'est facile car l'ident et l'expression sont déjà implémentés.
assign_statement = ident + ":=" + expression
Puisque la même chose est répétée, nous ne la mettrons en œuvre qu'à partir d'ici.
call_statement = CALL + ident
Définissez l'instruction IF. La déclaration qui représente la phrase entière n'est pas encore apparue, je vais donc la déclarer dans Forward.
statement = Forward()
if_statement = IF + condition + THEN + statement
while_statement = WHILE + condition + DO + statement
Maintenant que nous avons toutes les parties, définissons enfin les règles de génération d'instructions. Le BNF est le suivant.
statement = [ ident ":=" expression | "call" ident |
"begin" statement {";" statement } "end" |
"if" condition "then" statement |
"while" condition "do" statement ].
Implémentez avec pyparsing tel quel.
statement = Optional(assign_statement
| call_statement
| BEGIN + statement + ZeroOrMore(";" + statement) + END
| if_statement
| while_statement
)
Je suis fatigué, alors je viens de le mettre en œuvre.
const = CONST + ident + "=" + number + ZeroOrMore("," + ident + "=" + number) + ";"
var = VAR + ident + ZeroOrMore("," + ident) + ";"
Concentrez-vous uniquement sur cette partie de la BNF "procédure" ident ";" bloc ";" La répétition externe est effectuée lorsque le bloc est monté.
block = Forward()
procedure = PROCEDURE + ident + ";" + block + ";"
block
block << Optional(const) + Optional(var) + ZeroOrMore(procedure) + statement
program Il s'agit de la règle de production de premier niveau. Je vous remercie pour votre travail acharné.
program = block + "."
Analysons l'exemple de programme affiché au début.
$ 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)
Ça ne passe pas. Pourquoi? Puisqu'il dit line: 8, col: 1, BEGIN-END ne peut pas être analysé, et il semble qu'il attend un "." À la fin du programme. Tu ne peux pas avoir une erreur un peu plus gentille ici? Je vais le tester uniquement avec l'analyseur d'instructions pour confirmation.
>>> statement.parseString('''\
... BEGIN
... x := 1;
... WHILE x <= 10 DO
... BEGIN
... CALL square;
... ! squ;
... x := x + 1;
... END
... END
... ''')
([], {})
Le résultat est vide et échoue certainement. Les échecs qui ne se bloquent pas sont difficiles à déboguer. Si vous regardez attentivement, vous trouverez une phrase inconnue, «! Squ;». Il s'agit d'une syntaxe PL / 0 étendue et n'est pas définie dans le BNF de cette implémentation. Supprimez-le et réexécutez-le.
$ 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', '.']
Ça s'est bien passé!
La prochaine fois, j'aimerais vraiment créer un arbre de syntaxe (AST) et générer du code.
Enfin, je posterai la source de l'analyseur que j'ai implémenté jusqu'à présent.
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