Compiler in Python: PL / 0 Abstract Syntax Tree (AST)

Diesmal das Ziel

Letztes Mal hat die Pyparsing-Funktion verstanden, die zum Erstellen eines Analysebaums erforderlich ist. Dieses Mal generieren wir den dritten abstrakten Syntaxbaum (AST).

1. Zerlegen Sie es mit einem Parser in Token.
2. So erstellen Sie einen Syntaxbaum aus Token, erstellen Sie einen Syntaxbaum für Ausdrücke
3. Generieren Sie hier einen abstrakten Syntaxbaum (AST) mit setParseAction () <-now
4. Folgen Sie dem AST-Knoten, um Code zu generieren.

AST-Knoten

Beachten Sie beim Definieren eines Knotens Folgendes:

• Trennen Sie den AST-Knoten von der Implementierung von Pyparsing.
• Machen Sie es einfach, den Baum zu erkunden. Insbesondere haben eine gemeinsame Basisklasse.
• Da ein Knoten die kleinste Einheit der Codegenerierung ist, wird die Rolle eines Knotens nicht erhöht.

Nun zur Implementierung. Erstellen Sie eine neue Datei mit dem Namen pl0_nodes.py. Diese Datei importiert kein Pyparsing. Die Basisklasse ist nur eine Methode, die beim Drucken den Klassennamen, den Feldnamen und den Wert druckt. Beachten Sie, dass diese Klasse den Knoten ** Python ast.AST nachahmt. ** **.

pl0_nodes.py

# PL0 Abstract Syntax Tree Nodes
# This file must be free from pyparsing implementation!!

class ASTNode(object):
    _fields = ()

    def __repr__(self):
        return "{}({})".format(
            self.__class__.__name__,
            ', '.join(["%s=%s" % (field, getattr(self, field))
	               for field in self._fields])
	)

Implementieren Sie VAR als konkretes Beispiel. Die Deklaration der Variablen lautet Variables und die Variable selbst ist Var.

class Variables(ASTNode):
    _fields = ('variables',)
    def __init__(self, variables):
        self.variables = variables

class Var(ASTNode):
    _fields = ('id',)
    def __init__(self, id):
        self.id = id

Ich werde es testen.

x = Var('x')
y = Var('y')

variables = Variables([x, y])

print variables

Das Ergebnis ist ein verschachtelter AST mit Variablen als Scheitelpunkt:

Variables(variables=[Var(id=x), Var(id=y)])

AST-Generator

[Wie beim letzten Mal](http://qiita.com/knoguchi/items/6f9b7383b7252a9ebdad#%E3%81%A1%E3%82%87%E3%81%A3%E3%81%A8%E9%AB % 98% E5% BA% A6% E3% 81% AA% E4% BD% BF% E3% 81% 84% E6% 96% B9) Sie können die Variablenklasse direkt mit setParseAction starten, dann aber mit dem Konstruktor Da das Argument von ein Token für Pyparsing ist und eng miteinander verbunden wird und wir auch den deklarierten Bezeichner verfolgen möchten, werden wir dazwischen einen AST-Generator einführen.

make_variables ist eine Funktion, die von setParseAction aufgerufen wird und ein Objekt der Klasse Var erstellt, während die Liste der Variablennamen im zweiten Token in einer Schleife verarbeitet wird. Gleichzeitig wird der Bezeichner in der Symboltabelle gespeichert. Wenn Sie über eine Symboltabelle verfügen, können Sie damit nach doppelten Definitionsfehlern von Variablen suchen, Speicher beim Generieren von Code zuweisen usw.

pl0_ast.py

from pl0_nodes import Var, Variables

class AstGenerator(object):
    def __init__(self):
        self.symbol_table = {}

    def make_name(self, tokens):
        tokens = tokens.asList()
	assert len(tokens) == 1
        return Name(tokens[0])

    def make_variables(self, tokens):
        tokens = tokens.asList()
	idents = tokens[1]
	variables = []
        for ident in idents:
            node = Var(ident)
            self.symbol_table[ident.id] = node
            variables.append(node)
        return Variables(variables)

Nennen wir es tatsächlich vom Parser. Erstellen Sie am Anfang eine Instanz und setzen Sie variables.setParseAction.

pl0_parser.py

from pl0_ast import AstGenerator

ast = AstGenerator()

...

# 11. var
var_dec = ident
variables = VAR + Group(var_dec + ZeroOrMore(COMMA + var_dec)) + SEMICOLON
variables.setParseAction(ast.make_variables)

Beim Testen wird der AST korrekt generiert. Wenn Sie in die Symboltabelle schauen, können Sie auch sehen, dass x und y Variablen sind!

>>> print variables.parseString('VAR x, y;')
[Variables(variables=[Var(id=Name(id=x)), Var(id=Name(id=y))])]

>>> print ast.symbol_table
{'y': Var(id=Name(id=y)), 'x': Var(id=Name(id=x))}

Fügen Sie nach dem Parsen Code zum Dump symbol_table hinzu.

    print "== symbol table =="
    for k, v in ast.symbol_table.items():
        print "%10s  %10s" % (k, v.__class__.__name__)

Lassen Sie uns das Beispiel ex1.pl0 analysieren.

[Variables(variables=[Var(id=Name(id=x)), Var(id=Name(id=squ))]), ['PROCEDURE', Name(id=square), Name(id=squ), [Name(id=x), '*', Name(id=x)]], Name(id=x), '1', 'WHILE', [Name(id=x), '<=', '10'], 'DO', 'CALL', Name(id=square), Name(id=x), [Name(id=x), '+', '1']]
== symbol table ==
         x         Var
       squ         Var

Ernsthaft umgesetzt

Danach werden wir nacheinander vom tiefsten Teil aus montieren und stapeln. Es ist einfach zu testen, da es ein Minimum an nicht implementierten Abhängigkeiten erfordert.

zuweisen - Zuweisungsanweisung

Durch Substitution wird einfach die rechte Seite auf die linke Seite gesetzt.

pl0_nodes.py

class Assign(ASTNode):
    _fields = ('left', 'right')
    def __init__(self, left, right):
        self.left = left
        self.right = right

ast Generator

pl0_ast.py

    def make_assign(self, tokens):
        tokens = tokens.asList()
        left = tokens[0]
        right = tokens[1]
        return Assign(left, right)

Wenn Sie sich das Testergebnis des Bezeichners ansehen, wurde ': =' angezeigt. Da es sich jedoch zum Zeitpunkt des Parsens um ein Wrack handelt, unterdrücken wir.

pl0_parser.py

ASSIGN = Suppress(':=')

...

# 5. assignment
assign_statement = ident + ASSIGN + expression
assign_statement.setParseAction(ast.make_assign)

Prüfung.

[Variables(variables=[Var(id=Name(id=x)), Var(id=Name(id=squ))]), ['PROCEDURE', Name(id=square), Assign(left=Name(id=squ), right=[Name(id=x), '*', Name(id=x)])], Assign(left=Name(id=x), right=1), 'WHILE', [Name(id=x), '<=', '10'], 'DO', 'CALL', Name(id=square), Assign(left=Name(id=x), right=[Name(id=x), '+', '1'])]
== symbol table ==
         x         Var
       squ         Var

Aufruf-Prozedur-Aufruf

Derzeit dauert der Aufruf nur eine Prozedur. Wenn Sie ihn jedoch auf aufrufbar erweitern, können Sie auch Funktionen implementieren.

pl0_nodes.py

class Call(ASTNode):
    _fields = ('procedure',)
    def __init__(self, procedure):
        self.procedure = procedure

pl0_ast.py

    def make_call(self, tokens):
        tokens = tokens.asList()
        ident = tokens[1]
	return Call(ident)

pl0_parser.py

call_statement.setParseAction(ast.make_call)

Testergebnisse.

[Variables(variables=[Var(id=Name(id=x)), Var(id=Name(id=squ))]), ['PROCEDURE', Name(id=square), Assign(left=Name(id=squ), right=[Name(id=x), '*', Name(id=x)])], Assign(left=Name(id=x), right=1), 'WHILE', [Name(id=x), '<=', '10'], 'DO', Call(procedure=Name(id=square)), Assign(left=Name(id=x), right=[Name(id=x), '+', '1'])]
== symbol table ==
         x         Var
       squ         Var

if-Anweisung

Die IF-Anweisung benötigt einen bedingten Ausdruck und einen Body, um ausgeführt zu werden.

pl0_nodes.py

class If(ASTNode):
    _fields = ('condition', 'body')
    def __init__(self, condition, body):
        self.condition = test
        self.body = body

Ignoriere Token [2], da sie 'DANN' enthalten. Es wäre schön gewesen, alle reservierten Wörter zu unterdrücken. Das Debuggen kann schwierig sein.

pl0_ast.py

    def make_if(self, tokens):
        tokens = tokens.asList()
        condition = tokens[1]
        body = tokens[3]
        return If(condition, body)

pl0_parser.py

if_statement.setParseAction(ast.make_if)

Als ich über das Testen nachdachte ... gab es in ex1.pl0 keine IF-Anweisung, daher werde ich sie entsprechend testen. Es scheint kein Problem zu geben.

>>> print if_statement.parseString('IF a = b THEN call c')
[If(condition=[Name(id=a), '=', Name(id=b)], body=Call(procedure=Name(id=c)))]

while-Anweisung

Es ist genau das gleiche wie die IF-Anweisung.

class While(ASTNode):
    _fields = ('condition', 'body')
    def __init__(self, condition, body):
        self.condition = condition
        self.body = body

pl0_ast.py

    def make_while(self, tokens):
        tokens = tokens.asList()
        condition = tokens[1]
        body = tokens[3]
        return While(condition, body)

pl0_parser.py

while_statement.setParseAction(ast.make_while)

Prüfung

[Variables(variables=[Var(id=Name(id=x)), Var(id=Name(id=squ))]), ['PROCEDURE', Name(id=square), Assign(left=Name(id=squ), right=[Name(id=x), '*', Name(id=x)])], Assign(left=Name(id=x), right=1), While(condition=[Name(id=x), '<=', '10'], body=Call(procedure=Name(id=square)))]
== symbol table ==
         x         Var
       squ         Var

Multi-Anweisungen - Doppelte Anweisungen

BEGIN-END ist eine Sammlung mehrerer Sätze. Wenn es sich um einen Parser handelt, der vom ursprünglichen BNF transkribiert wurde, kann setParseAction nicht festgelegt werden, daher habe ich ihn zusammengestellt.

pl0_parser.py

# 9. statement
multi_statements = BEGIN.suppress() + statement + ZeroOrMore(SEMICOLON + statement) + END.suppress()

statement << Optional(assign_statement
                      | call_statement
                      | multi_statements
                      | if_statement
                      | while_statement
)

multi_statements.setParseAction(ast.make_multi_statements)

pl0_nodes.py

class MultiStatements(ASTNode):
    _fields = ('statements',)
    def __init__(self, statements):
        self.statements = statements

pl0_ast.py

    def make_multi_statements(self, tokens):
        tokens = tokens.asList()
        return MultiStatements(tokens)

Testergebnisse.

[Variables(variables=[Var(id=Name(id=x)), Var(id=Name(id=squ))]), ['PROCEDURE', Name(id=square), MultiStatements(statements=[Assign(left=Name(id=squ), right=[Name(id=x), '*', Name(id=x)])])], MultiStatements(statements=[Assign(left=Name(id=x), right=1), While(condition=[Name(id=x), '<=', '10'], body=MultiStatements(statements=[Call(procedure=Name(id=square)), Assign(left=Name(id=x), right=[Name(id=x), '+', '1'])]))])]
== symbol table ==
         x         Var
       squ         Var

const, var, procedure

Ich habe das Folgende mit dem gleichen Muster implementiert.

constants.setParseAction(ast.make_constants)
variables.setParseAction(ast.make_variables)
procedures.setParseAction(ast.make_procedures)

Prüfung

[Variables(variables=[Var(id=Name(id=x)), Var(id=Name(id=squ))]), Procedures(procedures=[Procedure(id=Name(id=square), body=MultiStatements(statements=[Assign(left=Name(id=squ), right=[Name(id=x), '*', Name(id=x)])]))]), MultiStatements(statements=[Assign(left=Name(id=x), right=1), While(condition=[Name(id=x), '<=', '10'], body=MultiStatements(statements=[Call(procedure=Name(id=square)), Assign(left=Name(id=x), right=[Name(id=x), '+', '1'])]))])]
== symbol table ==
         x         Var
    square   Procedure
       squ         Var

block

Da der Block ein optionales Feld hat, können Sie nicht erkennen, was nur an der Position des Tokens festgelegt ist. Ich konnte mir keinen guten Weg vorstellen, also entschied ich mich, isinstance () zu verwenden, um den Typ der Klasse zu bestimmen. Jede Anweisungsklasse ändert ihre übergeordnete Klasse von ASTNode in Anweisungsklasse.

pl0_nodes.py

class Statement(ASTNode):
    pass

class MultiStatements(Statement):
class Assign(Statement):
class If(Statement):
class While(Statement):
class Call(Statement):

class Block(ASTNode):
    _fields = ('constants', 'variables', 'procedures', 'statements')
    def __init__(self, constants, variables, procedures, statements):
        self.constants = constants
        self.variables = variables
	self.procedures = procedures
	self.statements = statements

pl0_ast.py

   def make_block(self, tokens):
        constants = None
        variables = None
        procedures = None
        statements = None
        for token in tokens.asList():
            if isinstance(token, Constants):
                const = token
            elif isinstance(token, Variables):
                var = token
            elif isinstance(token, Procedures):
                procedures = token
            elif isinstance(token, Statement):
                statements = token
            else:
                raise ValueError(token)

        return Block(constants, variables, procedures, statements)

Testergebnisse. Es ist mit dem Program () - Knoten als Apex verschachtelt. Es ist schwer zu formen, also habe ich es von Hand geformt.

Program(
 block=
  Block(
   constants=
   variables=
   procedures=
    Procedures(
     procedures=
      Procedure(
       id=
        'square'
       body=
        Block(
         constants=
         variables=
         procedures=
         statements=
          MultiStatements(
           statements=
            Assign(
             left=
              'squ'
             right=
              'x'
              *
              'x'
            )
          )
        )
      )
    )
   statements=
    MultiStatements(
     statements=
      Assign(
       left=
        'x'
       right=
        1
      )
      While(
       condition=
        'x'
        <=
        10
       body=
        MultiStatements(
         statements=
          Call(
           procedure=
            'square'
          )
          Assign(
           left=
            'x'
           right=
            'x'
            +
            1
          )
        )
      )
    )
  )
)
== symbol table ==
         x         Var
    square   Procedure
       squ         Var

AST abgeschlossen ...? Nein, die Formel ist immer noch eine Liste von Token.

Ausdruck - Ausdruck

Das letzte Mal habe ich mir die fixNotation von pyparsing angesehen, aber wenn Sie ein Argument hinzufügen, können Sie dasselbe wie setParseAction tun.

Klicken Sie hier für den aktuellen Status.

pl0_parser_before.py

expression = infixNotation(
    factor,
    [
     	(oneOf("+ -"), UNARY, opAssoc.RIGHT),
        (oneOf("* /"), BINARY, opAssoc.LEFT),
        (oneOf("+ -"), BINARY, opAssoc.LEFT),
    ]
)

Fügen Sie einen Rückruf hinzu.

pl0_parser_after.py

expression = infixNotation(
    factor,
    [
     	(oneOf("+ -"), UNARY, opAssoc.RIGHT, ast.make_unary_op),  
        (oneOf("* /"), BINARY, opAssoc.LEFT, ast.make_binary_op),
        (oneOf("+ -"), BINARY, opAssoc.LEFT, ast.make_binary_op),
    ]
)

condition = infixNotation(
    expression,
    [
        (ODD, UNARY, opAssoc.RIGHT, ast.make_unary_op),
        (oneOf("< <= > >="), BINARY, opAssoc.LEFT, ast.make_binary_op),
        (oneOf("= #"), BINARY, opAssoc.LEFT, ast.make_binary_op),
    ]
)

make_binary_op ändert die Knotenklasse so, dass sie durch das Symbol des Operators instanziiert wird. Wenn mehrere Peer-Operatoren aufeinander folgen, sendet Pyparsing ein Token [1 + 2 + 3]. Daher habe ich eine Funktion namens "convert ()" geschrieben, um es in eine binäre Operation zu konvertieren. Dadurch wird es in das Format [[1 + 2] + 3] konvertiert und ein AST mit dem Namen Add (Add (1, 2), 3) generiert.

Ergebnis

[Program(block=Block(constants=None, variables=None, procedures=Procedures(procedures=[Procedure(id=Name(id=square), body=Block(constants=None, variables=None, procedures=None, statements=MultiStatements(statements=[Assign(left=Name(id=squ), right=Mult(left=Name(id=x), right=Name(id=x)))])))]), statements=MultiStatements(statements=[Assign(left=Name(id=x), right=1), While(condition=LtE(left=Name(id=x), right=10), body=MultiStatements(statements=[Call(procedure=Name(id=square)), Assign(left=Name(id=x), right=Add(left=Name(id=x), right=1))]))])))]
== symbol table ==
         x         Var
    square   Procedure
       squ         Var

Quellcode

pl0_parser.py

# -*- coding: utf-8 -*-
from pyparsing import *
from pl0_ast import AstGenerator

ast = AstGenerator()

LPAR, RPAR, COMMA, SEMICOLON, DOT = map(Suppress, "(),;.")
ASSIGN = 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, ast.make_unary_op),  #Code hat die höchste Priorität
        (oneOf("* /"), BINARY, opAssoc.LEFT, ast.make_binary_op),  #Multiplikation und Division haben Vorrang vor Addition und Subtraktion
        (oneOf("+ -"), BINARY, opAssoc.LEFT, ast.make_binary_op),
    ]
)

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

# 5. assignment
assign_statement = ident + ASSIGN + 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
multi_statements = BEGIN.suppress() + statement + ZeroOrMore(SEMICOLON + statement) + END.suppress()

statement << Optional(assign_statement
                      | call_statement
                      | multi_statements
                      | if_statement
                      | while_statement
)

# 10. const
const_dec = Group(ident + "=" + number)
constants = CONST + Group(const_dec + ZeroOrMore(COMMA + const_dec)) + SEMICOLON

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

# 12. procedure
block = Forward()
procedure_dec = Group(PROCEDURE + ident + SEMICOLON + block + SEMICOLON)
procedures = OneOrMore(procedure_dec)

# 13. block
block << Optional(constants) + Optional(variables) + Optional(procedures) + statement

# 14. program
program = block + DOT

# set callbacks
ident.setParseAction(ast.make_name)
assign_statement.setParseAction(ast.make_assign)
call_statement.setParseAction(ast.make_call)
if_statement.setParseAction(ast.make_if)
while_statement.setParseAction(ast.make_while)
multi_statements.setParseAction(ast.make_multi_statements)
constants.setParseAction(ast.make_constants)
variables.setParseAction(ast.make_variables)
procedures.setParseAction(ast.make_procedures)
block.setParseAction(ast.make_block)
program.setParseAction(ast.make_program)

if __name__ == '__main__':
    import sys
    with open(sys.argv[1], 'r') as fp:
        txt = fp.read()
        res = program.parseString(txt)
        print res

    print "== symbol table =="
    for k, v in ast.symbol_table.items():
        print "%10s  %10s" % (k, v.__class__.__name__)

pl0_ast.py

from pl0_nodes import *

class AstGenerator(object):
    """
    Generates AST.
    This class is tightly coupled with the pl0_paser.
    """
    def __init__(self):
        self.symbol_table = {}

    def make_name(self, tokens):
        tokens = tokens.asList()
        assert len(tokens) == 1
        return Name(tokens[0])

    def make_constants(self, tokens):
        tokens = tokens.asList()
        constants = []
        for token in tokens[1]:
            lhs = token[0]
            rhs = token[2]
            node = Const(id=lhs, value=rhs)
            self.symbol_table[lhs.id] = node
            constants.append(node)
        return Constants(constants)

    def make_variables(self, tokens):
        tokens = tokens.asList()
        idents = tokens[1]
        variables = []
        for ident in idents:
            node = Var(ident)
            self.symbol_table[ident.id] = node
            variables.append(node)
        return Variables(variables)

    def make_procedures(self, tokens):
        tokens = tokens.asList()
        procedures = []
        for token in tokens:
            name, body = token[1], token[2]
            node = Procedure(name, body)
            self.symbol_table[name.id] = node
            procedures.append(node)
        return Procedures(procedures)

    # statements
    def make_multi_statements(self, tokens):
        tokens = tokens.asList()
        return MultiStatements(tokens)

    def make_if(self, tokens):
        tokens = tokens.asList()
        condition = tokens[1]
        body = tokens[3]
        return If(condition, body)

    def make_while(self, tokens):
        tokens = tokens.asList()
        condition = tokens[1]
        body = tokens[3]
        return While(condition, body)

    def make_call(self, tokens):
        tokens = tokens.asList()
        ident = tokens[1]
        return Call(ident)

    def make_assign(self, tokens):
        tokens = tokens.asList()
        left = tokens[0]
        right = tokens[1]
        return Assign(left, right)

    # unary operators
    def make_unary_op(self, tokens=None):
        tokens = tokens.asList()[0]
        op = tokens[0]
        _op_map = {
            'ODD': Odd,
            '-': Neg
            }
        cls = _op_map[op]
        return cls(op, tokens[1])

    # binary operators
    def make_binary_op(self, tokens):
        _op_map = {
            'ODD': Odd,
            '+': Add,
            '-': Sub,
            '*': Mult,
            '/': Div,
            '<': Lt,
            '<=': LtE,
            '>': Gt,
            '>=': GtE,
            '=': Eq,
            '#': Ne,
        }

        def convert(l):
            stack = []
            l = iter(l)
            for e in l:
                if e in _op_map:
                    cls = _op_map[e]
                    left = stack.pop()
                    right = next(l)
                    stack.append(cls(left, e, right))
                else:
                    stack.append(e)
            return stack.pop()

        tokens = tokens.asList()[0]
        return convert(tokens)

    # block
    def make_block(self, tokens):
        constants = None
        variables = None
        procedures = None
        statements = None
        for token in tokens.asList():
            if isinstance(token, Constants):
                const = token
            elif isinstance(token, Variables):
                var = token
            elif isinstance(token, Procedures):
                procedures = token
            elif isinstance(token, Statement):
                statements = token
            else:
                raise ValueError(token)

        return Block(constants, variables, procedures, statements)

    # program
    def make_program(self, tokens):
        tokens = tokens.asList()
        assert len(tokens) == 1, len(tokens)
        block = tokens[0]
        return Program(block)

pl0_nodes.py

# PL0 Abstract Syntax Tree Nodes
# This file must be free from pyparsing implementation!!

class ASTNode(object):
    SPACER = " "
    _fields = ()

    def __repr__(self):
        return "{}({})".format(
            self.__class__.__name__,
            ', '.join(["%s=%s" % (field, getattr(self, field))
                       for field in self._fields])
        )
    
    def _p(self, v, indent):
        print "{}{}".format(self.SPACER * indent, v)
        
    def dumps(self, indent=0):
        self._p(self.__class__.__name__ + '(', indent)
        for field in self._fields:
            self._p(field + '=', indent + 1)
            value = getattr(self, field)
            if type(value) == list:
                for value2 in value:
                    if isinstance(value2, ASTNode):
                        value2.dumps(indent + 2)
                    else:
                        self._p(value2, indent + 2)
            else:
                if value:
                    if isinstance(value, ASTNode):
                        value.dumps(indent + 2)
                    else:
                        self._p(value, indent + 2)
        self._p(')', indent)
                    

# Literals
class Num(ASTNode):
    _fields = ('n',)

    def __init__(self, n):
        self.n = n


# Variables
class Name(ASTNode):
    _fields = ('id',)

    def __init__(self, id):
        self.id = id

    def dumps(self, indent=0):
        print "{}'{}'".format(self.SPACER * indent, self.id)

        
class Const(ASTNode):
    _fields = ('id', 'value',)

    def __init__(self, id, value):
        self.id = id
        self.value = value


class Constants(ASTNode):
    _fields = ('constants',)

    def __init__(self, constants):
        self.constants = constants


# Expressions
class Expr(ASTNode):
    _fields = ('value',)

    def __init__(self, value):
        self.value = value


# unary operators
class UnaryOp(ASTNode):
    _fields = ('op', 'right')

    def __init__(self, op, right):
        self.op = op
        self.right = right


class Odd(UnaryOp):
    pass

class Neg(UnaryOp):
    pass

class Not(UnaryOp):
    pass


# binary operatos
class BinOp(ASTNode):
    _fields = ('left', 'right')
    def __init__(self, left, op, right):
        self.left = left
        self.right = right


class Add(BinOp):
    pass


class Sub(BinOp):
    pass


class Mult(BinOp):
    pass


class Div(BinOp):
    pass


class And(BinOp):
    pass


class Or(BinOp):
    pass

class Eq(BinOp):
    pass


class Ne(BinOp):
    pass


class Lt(BinOp):
    pass


class LtE(BinOp):
    pass


class Gt(BinOp):
    pass


class GtE(BinOp):
    pass


# statement
class Statement(ASTNode):
    pass


class MultiStatements(Statement):
    _fields = ('statements',)
    def __init__(self, statements):
        self.statements = statements


class Assign(Statement):
    _fields = ('left', 'right')
    def __init__(self, left, right):
        self.left = left
        self.right = right


# control flow
class If(Statement):
    _fields = ('condition', 'body')
    def __init__(self, condition, body):
        self.condition = condition
        self.body = body


class While(Statement):
    _fields = ('condition', 'body')
    def __init__(self, condition, body):
        self.condition = condition
        self.body = body


class Call(Statement):
    _fields = ('procedure',)
    def __init__(self, procedure):
        self.procedure = procedure


# Declaration
class Var(ASTNode):
    _fields = ('id',)
    def __init__(self, id):
        self.id = id


class Variables(ASTNode):
    _fields = ('variables',)

    def __init__(self, variables):
        self.variables = variables


class Procedure(ASTNode):
    _fields = ('id', 'body')
    def __init__(self, id, body):
        self.id = id
        self.body = body

class Procedures(ASTNode):
    _fields = ('procedures',)
    def __init__(self, procedures):
        self.procedures = procedures


# block
class Block(ASTNode):
    _fields = ('constants', 'variables', 'procedures', 'statements')
    def __init__(self, constants, variables, procedures, statements):
        self.constants = constants
        self.variables = variables
        self.procedures = procedures
        self.statements = statements


# Program
class Program(ASTNode):
    _fields = ('block',)
    def __init__(self, block):
        self.block = block

Bonus

Wikipedia PL / 0 Beispielcode

ex2.pl0

CONST
  m =  7,
  n = 85;

VAR
  x, y, z, q, r;

PROCEDURE multiply;
VAR a, b;

BEGIN
  a := x;
  b := y;
  z := 0;
  WHILE b > 0 DO BEGIN
    IF ODD b THEN z := z + a;
    a := 2 * a;
    b := b / 2;
  END
END;

PROCEDURE divide;
VAR w;
BEGIN
  r := x;
  q := 0;
  w := y;
  WHILE w <= r DO w := 2 * w;
  WHILE w > y DO BEGIN
    q := 2 * q;
    w := w / 2;
    IF w <= r THEN BEGIN
      r := r - w;
      q := q + 1
    END
  END
END;

PROCEDURE gcd;
VAR f, g;
BEGIN
  f := x;
  g := y;
  WHILE f # g DO BEGIN
    IF f < g THEN g := g - f;
    IF g < f THEN f := f - g;
  END;
  z := f
END;

BEGIN
  x := m;
  y := n;
  CALL multiply;
  x := 25;
  y :=  3;
  CALL divide;
  x := 84;
  y := 36;
  CALL gcd;
END.

Perspektivisches Ergebnis

[Program(block=Block(constants=None, variables=None, procedures=Procedures(procedures=[Procedure(id=Name(id=multiply), body=Block(constants=None, variables=None, procedures=None, statements=MultiStatements(statements=[Assign(left=Name(id=a), right=Name(id=x)), Assign(left=Name(id=b), right=Name(id=y)), Assign(left=Name(id=z), right=0), While(condition=Gt(left=Name(id=b), right=0), body=MultiStatements(statements=[If(condition=Odd(op=ODD, right=Name(id=b)), body=Assign(left=Name(id=z), right=Add(left=Name(id=z), right=Name(id=a)))), Assign(left=Name(id=a), right=Mult(left=2, right=Name(id=a))), Assign(left=Name(id=b), right=Div(left=Name(id=b), right=2))]))]))), Procedure(id=Name(id=divide), body=Block(constants=None, variables=None, procedures=None, statements=MultiStatements(statements=[Assign(left=Name(id=r), right=Name(id=x)), Assign(left=Name(id=q), right=0), Assign(left=Name(id=w), right=Name(id=y)), While(condition=LtE(left=Name(id=w), right=Name(id=r)), body=Assign(left=Name(id=w), right=Mult(left=2, right=Name(id=w)))), While(condition=Gt(left=Name(id=w), right=Name(id=y)), body=MultiStatements(statements=[Assign(left=Name(id=q), right=Mult(left=2, right=Name(id=q))), Assign(left=Name(id=w), right=Div(left=Name(id=w), right=2)), If(condition=LtE(left=Name(id=w), right=Name(id=r)), body=MultiStatements(statements=[Assign(left=Name(id=r), right=Sub(left=Name(id=r), right=Name(id=w))), Assign(left=Name(id=q), right=Add(left=Name(id=q), right=1))]))]))]))), Procedure(id=Name(id=gcd), body=Block(constants=None, variables=None, procedures=None, statements=MultiStatements(statements=[Assign(left=Name(id=f), right=Name(id=x)), Assign(left=Name(id=g), right=Name(id=y)), While(condition=Ne(left=Name(id=f), right=Name(id=g)), body=MultiStatements(statements=[If(condition=Lt(left=Name(id=f), right=Name(id=g)), body=Assign(left=Name(id=g), right=Sub(left=Name(id=g), right=Name(id=f)))), If(condition=Lt(left=Name(id=g), right=Name(id=f)), body=Assign(left=Name(id=f), right=Sub(left=Name(id=f), right=Name(id=g))))])), Assign(left=Name(id=z), right=Name(id=f))])))]), statements=MultiStatements(statements=[Assign(left=Name(id=x), right=Name(id=m)), Assign(left=Name(id=y), right=Name(id=n)), Call(procedure=Name(id=multiply)), Assign(left=Name(id=x), right=25), Assign(left=Name(id=y), right=3), Call(procedure=Name(id=divide)), Assign(left=Name(id=x), right=84), Assign(left=Name(id=y), right=36), Call(procedure=Name(id=gcd))])))]
== symbol table ==
         a         Var
         b         Var
    divide   Procedure
         g         Var
         f         Var
         m       Const
         n       Const
         q         Var
  multiply   Procedure
         r         Var
         w         Var
         y         Var
         x         Var
         z         Var
       gcd   Procedure