Compilateur en Python: arborescence de syntaxe PL / 0

L'objectif de cette fois

Le flux général de création d'un compilateur est le suivant, et précédent était jusqu'au numéro 1. Cette fois, nous allons créer le deuxième arbre de syntaxe (une partie seulement).

  1. Décomposez-le en jetons avec un analyseur.
  2. Analysez la structure du jeton pour créer une arborescence d'analyse.
  3. Supprimez les discussions inutiles et créez un arbre de syntaxe abstraite (AST).
  4. Suivez le nœud AST pour générer du code.

Suppression des jetons inutiles

Avec pyparsing, vous n'êtes pas obligé de conserver des symboles tels que «;» dans le résultat de l'analyse en raison de la fonction de structuration qui vient plus tard. Si vous utilisez Suppress (), le jeton ne sera pas inclus dans le résultat. Si vous ne le supprimez pas d'abord, il sera difficile de voir le résultat, alors commençons par ce sujet.

Je republierai les résultats de l'analyse jusqu'à la dernière fois.

['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', '.']

Supprimons (),;. Et vérifions l'effet.

#Ajouter au début. 
LPAR, RPAR, COMMA, SEMICOLON, DOT = map(Suppress, "(),;.")

#Remplacer la chaîne par une constante
# before
# factor << (ident | number | "(" + expression + ")")
# after
factor << (ident | number | LPAR + expression + RPAR)

#De même, ; .Remplacer par une constante

Analysons l'exemple de programme comme précédemment. Le symbole a disparu.

$ 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']

Arborescence utilisant Group ()

Les résultats de perspective que nous avons vus jusqu'à présent sont des tableaux unidimensionnels et n'ont aucune structure. Créons une structure en ajoutant des informations de groupe à l'analyseur.

Pour donner une structure statique, utilisez Group () pour combiner des jetons en un seul. Regardons un exemple concret. Pour regrouper la liste des variables, apportez les modifications suivantes:

# 11. var
var = VAR + Group(ident + ZeroOrMore(COMMA + ident)) + SEMICOLON

C'est le résultat d'une nouvelle analyse. La liste des variables au début est entre parenthèses!

['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']

Ensuite, on peut dire qu'il devrait être encapsulé dans Group (), mais dans pyparsing, il existe une autre façon conventionnelle d'utiliser .setParseAction.

Comment utiliser .setParseAction ()

Avec pyparsing, il est possible d'appeler un rappel lorsque l'analyseur réussit à analyser. Une liste de jetons est transmise à ce rappel et vous pouvez remplacer les jetons par la valeur de retour. Mettons la déclaration de variable dans [] de la même manière qu'avant.

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

Quand je l'ai analysé, j'ai obtenu le même résultat qu'avant.

['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']

Un peu d'utilisation avancée.

Au lieu d'appeler une fonction, essayez d'appeler le constructeur de classe. Si vous prétraitez avec Group (), vous pouvez écrire la classe proprement.

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

résultat. Oh! L'objet est entré. Cela vous permet de ** générer un AST directement lorsque vous exécutez l'analyseur **.

[<__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']

Le rappel peut être une fonction ou une classe tant qu'il peut être appelé. Attention, la signification des arguments varie en fonction du nombre d'arguments.

original_string = Chaîne originale en cours d'analyse location = emplacement de la chaîne correspondante tokens = un tableau de jetons correspondants. Le jeton est un objet ParseResults

Arborescence de formules

Les expressions ont une séquence complexe de calculs, mais au final, ce sont essentiellement des termes et des opérateurs. L'imbrication est obligatoire compte tenu de la priorité des opérateurs. C'est un problème à écrire par vous-même, mais pyparsing a un utilitaire appelé ʻinfixNotation`, qui crée automatiquement un analyseur juste en définissant l'ordre des opérateurs. Supprimez l'analyseur basé sur le BNF d'origine.

Le signe devant le terme est l'opérateur unaire, et l'opération habituelle à quatre règles est l'opérateur binaire. L'opérateur de comparaison (<< = >> = = #) est également un compagnon de l'opérateur binaire. Définissons-le réellement.

L'utilisation de oneOf signifie que les opérateurs sont les mêmes. Notez que si vous écrivez par inadvertance ceci sur deux lignes, le résultat violera la règle selon laquelle «les mêmes opérateurs sont calculés à partir de la gauche».

opAssoc.RIGHT et LEFT indiquent si l'opérateur est lié au côté droit ou gauche. L'opérateur # signifie! = En 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 définit la priorité des opérateurs.
#Écrivez le même opérateur sur une seule ligne.
UNARY, BINARY, TERNARY = 1, 2, 3
factor = ident | number
expression = infixNotation(
    factor,
    [
        (oneOf("+ -"), UNARY, opAssoc.RIGHT),  #Le code a la priorité la plus élevée.
        (oneOf("* /"), BINARY, opAssoc.LEFT),  #La multiplication et la division ont priorité sur l'addition et la soustraction
        (oneOf("+ -"), BINARY, opAssoc.LEFT),
    ]
)

Réécrivez la condition de la même manière.

# 4. condition
#condition = ODD + expression | expression + oneOf('= # < <= > >=') + expression
condition = infixNotation(
    expression,
    [
        (ODD, UNARY, opAssoc.RIGHT),
        (oneOf("< <= > >="), BINARY, opAssoc.LEFT),
        (oneOf("= #"), BINARY, opAssoc.LEFT),
    ]
)

Résultat de l'exécution. Vous pouvez voir que l'expression est entre [].

['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']

En passant, les quatre règles peuvent être analysées correctement.

>>> print expression.parseString('1 + 2 * 3 + 4')
[['1', '+', ['2', '*', '3'], '+', '4']]
>>> print expression.parseString('1 + 2 / 3 * 4 - -5')
[['1', '+', ['2', '/', '3', '*', '4'], '-', ['-', '5']]]

Résumé

J'ai créé un arbre de syntaxe à partir d'une liste de jetons. Nous avons également généré un arbre de syntaxe pour les expressions qui prend en compte une partie de la syntaxe définie dans BNF et les priorités des opérateurs. Je n'en ai implémenté qu'une partie car il existe une méthode pour générer directement AST dans pyparsing, et même si elle est implémentée, elle sera rejetée. La prochaine fois, générez un AST qui prend en charge toutes les grammaires.

La source

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),  #Le code a la priorité la plus élevée
        (oneOf("* /"), BINARY, opAssoc.LEFT),  #La multiplication et la division ont priorité sur l'addition et la soustraction
        (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

Compilateur en Python: arborescence de syntaxe PL / 0
Compilateur en Python: Arbre de syntaxe abstraite PL / 0 (AST)
Compilateur en Python: analyseur PL / 0
Algorithme (arborescence de segments) en Python (s'entraîner)
Arborescence de sortie des fichiers en Python
Différences entre la syntaxe Python et Java
Dessinez une structure arborescente en Python 3 à l'aide de graphviz
Arborescence de segments retardée en Python (demande de débogage)
Manipuler XML avec des espaces de noms en Python (arbre des éléments)
Quadtree en Python --2
Python en optimisation
Métaprogrammation avec Python
Python 3.3 avec Anaconda
Géocodage en python
SendKeys en Python
Méta-analyse en Python
Unittest en Python
Époque en Python
Discord en Python
Allemand en Python
nCr en python
N-Gram en Python
Programmation avec Python
Plink en Python
Constante en Python
avec syntaxe (Python)
FizzBuzz en Python
Sqlite en Python
Étape AIC en Python
LINE-Bot [0] en Python
CSV en Python
Assemblage inversé avec Python
Réflexion en Python
Constante en Python
nCr en Python.
format en python
Scons en Python 3
Puyopuyo en python
python dans virtualenv
PPAP en Python
Quad-tree en Python
Syntaxe de contrôle de la syntaxe Python
Réflexion en Python
Chimie avec Python
Hashable en Python
DirectLiNGAM en Python
LiNGAM en Python
Aplatir en Python
Aplatir en python
Liste triée en Python
AtCoder # 36 quotidien avec Python
AtCoder # 2 tous les jours avec Python
Daily AtCoder # 32 en Python
Daily AtCoder # 18 en Python
Motif singleton en Python
Opérations sur les fichiers en Python
Séquence de touches en Python
Daily AtCoder # 33 en Python