Help us understand the problem. What is going on with this article?

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

More than 3 years have passed since last update.

今回の目標

前回はparse treeの作成に必要なpyparsingの機能を理解しました。今回は3番の抽象構文木(AST)生成を行います。

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

ASTノード

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

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

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

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ジェネレータ

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

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

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をセットします。

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それぞれが変数であることもわかりますね!

>>> 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 - 代入文

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

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

astジェネレータ

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

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

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に拡張すれば関数も実装できますね。

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)

テスト結果。

[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文は条件式と実行する本体をとります。

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

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

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)

テスト...と思ったら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
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)

テスト

[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がセットできないので、括り出しました。

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)

テスト結果。

[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クラスに変更します。

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)

テスト結果。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と同等のことができます。

現状はこちら。

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

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

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

ソースコード

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

おまけ

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

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
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした