Pythonでコンパイラ: PL/0抽象構文木(AST)

# 今回の目標

[前回](http://qiita.com/knoguchi/items/6f9b7383b7252a9ebdad)はparse treeの作成に必要なpyparsingの機能を理解しました。今回は3番の抽象構文木(AST)生成を行います。

1. パーサーでトークンに分解する。
2. トークンから構文木をつくる方法、式の構文木の作成
3. setParseAction()を使って抽象構文木(AST)を生成 <- 今ココ
4. ASTノードを辿ってコードを生成する。

# ASTノード

ノードを定義するにあたっては次の点に注意します。

* ASTノードはpyparsingの実装から切り離す。
* ツリーの探索が簡単にできるようする。具体的には共通のベースクラスを持たせる。
* ノードがコード生成の最小単位であるから、一つのノードの役割を大きくしない。

では実装です。pl0_nodes.pyというファイルを新規に作成します。このファイルではpyparsingはインポートしません。ベースクラスはprintしたときに、クラス名とフィールド名と値を表示するメソッドだけです。なおこのクラスは**Pythonのast.ASTノードを真似ています。**

```py: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])
	)
```

VARを具体例に実装します。変数の宣言をVariablesとし、変数そのものは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
```

テストしてみます。

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

variables = Variables([x, y])

print variables
```

結果は次のようにVariablesを頂点とした入れ子構造のASTです。

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

# ASTジェネレータ

[前回やったように](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)VariablesクラスをsetParseActionで直接起動しても良いのですが、それではコンストラクタの引数がpyparsingのトークンになってしまい密結合になってしまうのと、宣言された識別子の追跡も行いたいので、間にASTジェネレータを導入します。

`make_variables`がsetParseActionから呼ばれる関数で、トークンの２番目に入っている変数名のリストをループで処理しながら`Var`クラスのオブジェクトを作ります。同時にシンボルテーブルに識別子を格納していきます。シンボルテーブルがあれば変数の二重定義のエラーをチェックしたり、コード生成時にメモリを確保するなどの用途に使えます。


```py: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)
```

実際にパーサーから呼んでみましょう。先頭でインスタンスを作り、variables.setParseActionをセットします。

```py: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)
```

テストしたところ、ASTが正しく生成されています。シンボルテーブルの中をみるとx, yそれぞれが変数であることもわかりますね！

```py
>>> 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))}
```

パース後にsymbol_tableをダンプするコードを追加します。

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


サンプルのex1.pl0をパースしてみます。

```
[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
```
# ひたすら実装

あとは順次最深部から実装して積み上げていきます。未実装の依存関係が最小限で済むのでテストがしやすいです。

## assign - 代入文

代入は右辺を左辺にセットするというだけです。

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

astジェネレータ

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

識別子のテスト結果をみると':='が出ていましたが、パース時の残骸なのでSuppressしましょう。

```py:pl0_parser.py
ASSIGN = Suppress(':=')

...

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

```

テスト。

```
[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
```

## call - 手続き呼び出し

callは現状procedureしかとりませんが、callableに拡張すれば関数も実装できますね。

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

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

```py:pl0_parser.py
call_statement.setParseAction(ast.make_call)
```

テスト結果。

```
[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文

IF文は条件式と実行する本体をとります。

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

tokens[2]は'THEN'が入っているので無視。予約語も全部Suppressしてもよかったですね。デバッグがしにくくなるかもしれませんが。

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

```py:pl0_parser.py
if_statement.setParseAction(ast.make_if)
```

テスト...と思ったらex1.pl0にIF文がなかったので、適当にテストします。問題なさそうです。

```
>>> 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 文

IF文と全く同じです。

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

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

```py:pl0_parser.py
while_statement.setParseAction(ast.make_while)
```

テスト

```
[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 statements - 複文
BEGIN-ENDは複数の文をひとかたまりにしています。オリジナルのBNFから書き起こしたパーサーだとsetParseActionがセットできないので、括り出しました。

```py: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)
```

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

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

テスト結果。

```
[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

同じパターンで以下を実装しました。

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

テスト

```
[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 

ブロックはOptionalのフィールドがあるので、トークンの位置だけでは何がセットされているのかわかりません。うまい方法を思いつかなかったので、isinstance()でクラスの型を判別することにしました。各statementクラスは親クラスをASTNodeからStatementクラスに変更します。

```py: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
```

```py: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)

```

テスト結果。Program()ノードを頂点とした入れ子になっています。みずらいので手作業で整形しました

```
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完成...? いや、式がトークンの羅列のままになっています。

## expression - 式

前回pyparsingのinfixNotationについてしらべましたが、引数を追加するとsetParseActionと同等のことができます。

現状はこちら。

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

コールバックを追加します。

```py: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は、演算子の記号によってインスタンス化するノードクラスを変えています。また同位の演算子が複数連続する場合、pyparsingは[ 1 + 2 + 3 ] というトークンを送ってくるので、二項演算に変換するための`convert()`という関数を書きました。これにより[[1+2]+3]という形式に変換されAdd(Add(1, 2), 3)というASTを生成することができます。

結果

```
[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
```

# ソースコード

```py: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),  # 符号は最優先
        (oneOf("* /"), BINARY, opAssoc.LEFT, ast.make_binary_op),  # 掛け算割り算は足し算引き算より優先
        (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__)
```

```py: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)
```

```py: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
```

# おまけ

WikipediaのPL/0のサンプルコード

```pas: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.
```

パース結果

```
[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
```