Skip to content

Instantly share code, notes, and snippets.

@knoguchi
Last active August 29, 2015 14:15
Show Gist options
  • Save knoguchi/a91396442e350c56d6c2 to your computer and use it in GitHub Desktop.
Save knoguchi/a91396442e350c56d6c2 to your computer and use it in GitHub Desktop.
Pythonでコンパイラ: PL/0抽象構文木(AST) ref: http://qiita.com/knoguchi/items/96fa352ff0db60ee2eee
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.
class Variables(ASTNode):
_fields = ('variables',)
def __init__(self, variables):
self.variables = variables
class Var(ASTNode):
_fields = ('id',)
def __init__(self, id):
self.id = id
$ python pl0_parser3.py ex1.pl0
['VAR', [Name(id=x), 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']]
[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
$ python pl0_parser.py ex1.pl0
['VAR', [Name(id=x), 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'])]
[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
['VAR', [Name(id=x), 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'])]
x = Var('x')
y = Var('y')
variables = Variables([x, y])
print variables
>>> print if_statement.parseString('IF a = b THEN call c')
[If(condition=[Name(id=a), '=', Name(id=b)], body=Call(procedure=Name(id=c)))]
class While(ASTNode):
_fields = ('condition', 'body')
def __init__(self, condition, body):
self.condition = condition
self.body = body
>>> print if_statement.parseString('IF a = b THEN call c')
[If(condition=[Name(id=a), '=', Name(id=b)], body=Call(procedure=Name(id=c)))]
class While(ASTNode):
_fields = ('condition', 'body')
def __init__(self, condition, body):
self.condition = condition
self.body = body
[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
['VAR', [Name(id=x), 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)))]
[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
constants.setParseAction(ast.make_constants)
variables.setParseAction(ast.make_variables)
procedures.setParseAction(ast.make_procedures)
Variables(variables=[Var(id=x), Var(id=y)])
[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
const.setParseAction(ast.make_const)
var.setParseAction(ast.make_vardef)
procedures.setParseAction(ast.make_procedures)
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
[Program(
block=Block(
const=None,
var=VarDef(
variables=[
Variable(id=Name(id=x)),
Variable(id=Name(id=squ))
]),
procedures=Procedures(
procedures=[Procedure(
id=Name(id=square),
body=Block(
const=None,
var=None,
procedure=None,
statement=MultiStatements(
statements=[
Assign(
left=Name(id=squ),
right=[Name(id=x), '*', Name(id=x)]
)
]
)
)
)
]),
statement=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'])
]
)
)
]
)
)
)
]
[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
[Program(block=Block(const=None, var=VarDef(variables=[Variable(id=Name(id=x)), Variable(id=Name(id=squ))]), procedure=Procedure(id=Name(id=square), body=Block(const=None, var=None, procedure=None, statement=MultiStatements(statements=[Assign(left=Name(id=squ), right=Mult(left=Name(id=x), right=Name(id=x)))]))), statement=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))]))])))]
[Program(block=Block(const=None, var=VarDef(variables=[Variable(id=Name(id=x)), Variable(id=Name(id=squ))]), procedures=Procedures(proceduers=[Procedure(id=Name(id=square), body=Block(const=None, var=None, procedure=None, statement=MultiStatements(statements=[Assign(left=Name(id=squ), right=Mult(left=Name(id=x), right=Name(id=x)))]))), statement=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))]))])]))]
print "== symbol table =="
for k, v in ast.symbol_table.items():
print "%10s %10s" % (k, v.__class__.__name__)
[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
[Program(block=Block(const=ConstDef(constants=[Const(id=Name(id=m), value=7), Const(id=Name(id=n), value=85)]), var=VarDef(variables=[Variable(id=Name(id=x)), Variable(id=Name(id=y)), Variable(id=Name(id=z)), Variable(id=Name(id=q)), Variable(id=Name(id=r))]), procedure=Procedure(id=Name(id=gcd), body=Block(const=None, var=VarDef(variables=[Variable(id=Name(id=f)), Variable(id=Name(id=g))]), procedure=None, statement=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))]))), statement=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 Variable
b Variable
divide Procedure
g Variable
f Variable
m Const
n Const
q Variable
multiply Procedure
r Variable
w Variable
y Variable
x Variable
z Variable
gcd Procedure
[Program(block=Block(const=ConstDef(constants=[Const(id=Name(id=m), value=7), Const(id=Name(id=n), value=85)]), var=VarDef(variables=[Variable(id=Name(id=x)), Variable(id=Name(id=y)), Variable(id=Name(id=z)), Variable(id=Name(id=q)), Variable(id=Name(id=r))]), procedure=Procedures(procedures=[Procedure(id=Name(id=multiply), body=Block(const=None, var=VarDef(variables=[Variable(id=Name(id=a)), Variable(id=Name(id=b))]), procedure=None, statement=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(const=None, var=VarDef(variables=[Variable(id=Name(id=w))]), procedure=None, statement=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(const=None, var=VarDef(variables=[Variable(id=Name(id=f)), Variable(id=Name(id=g))]), procedure=None, statement=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))])))]), statement=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 Variable
b Variable
divide Procedure
g Variable
f Variable
m Const
n Const
q Variable
multiply Procedure
r Variable
w Variable
y Variable
x Variable
z Variable
gcd Procedure
[Program(block=Block(const=ConstDef(constants=[Const(id=Name(id=m), value=7), Const(id=Name(id=n), value=85)]), var=VarDef(variables=[Variable(id=Name(id=x)), Variable(id=Name(id=y)), Variable(id=Name(id=z)), Variable(id=Name(id=q)), Variable(id=Name(id=r))]), procedure=Procedure(id=Name(id=gcd), body=Block(const=None, var=VarDef(variables=[Variable(id=Name(id=f)), Variable(id=Name(id=g))]), procedure=None, statement=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))]))), statement=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 Variable
b Variable
divide Procedure
g Variable
f Variable
m Const
n Const
q Variable
multiply Procedure
r Variable
w Variable
y Variable
x Variable
z Variable
gcd Procedure
>>> 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))}
print "== symbol table =="
for k, v in ast.symbol_table.items():
print "%10s %10s" % (k, v.__class__.__name__)
[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
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)
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),
]
)
expression = infixNotation(
factor,
[
(oneOf("+ -"), UNARY, opAssoc.RIGHT),
(oneOf("* /"), BINARY, opAssoc.LEFT),
(oneOf("+ -"), BINARY, opAssoc.LEFT),
]
)
# 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
# -*- 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__)
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),
]
)
expression = infixNotation(
factor,
[
(oneOf("+ -"), UNARY, opAssoc.RIGHT),
(oneOf("* /"), BINARY, opAssoc.LEFT),
(oneOf("+ -"), BINARY, opAssoc.LEFT),
]
)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment