今回の目標
前回はparse treeの作成に必要なpyparsingの機能を理解しました。今回は3番の抽象構文木(AST)生成を行います。
- パーサーでトークンに分解する。
- トークンから構文木をつくる方法、式の構文木の作成
- setParseAction()を使って抽象構文木(AST)を生成 <- 今ココ
- 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から呼ばれる関数で、トークンの２番目に入っている変数名のリストをループで処理しながら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