# picking a random grammar from Appel MCI
is_a = isinstance
import Parsing
class t_ID (Parsing.Token):
"%token ID"
def __init__(self, parser, name):
Parsing.Token.__init__(self, parser)
self.name = name
class t_WHILE (Parsing.Token):
"%token WHILE"
class t_BEGIN (Parsing.Token):
"%token BEGIN"
class t_END (Parsing.Token):
"%token END"
class t_DO (Parsing.Token):
"%token DO"
class t_IF (Parsing.Token):
"%token IF"
class t_THEN (Parsing.Token):
"%token THEN"
class t_ELSE (Parsing.Token):
"%token ELSE [p1]"
class t_SEMI (Parsing.Token):
"%token SEMI"
class t_ASSIGN (Parsing.Token):
"%token ASSIGN"
class t_EOF (Parsing.Token):
"%token EOF"
"""
prog: stmlist
stm: ID ASSIGN ID
| WHILE ID DO stm
| BEGIN stmlist END
| IF ID THEN stm
| IF ID THEN stm ELSE stm
stmlist : stm
| stmlist SEMI stm
"""
class p1 (Parsing.Precedence):
"%right p1"
class stm (Parsing.Nonterm):
"%nonterm"
def reduce_assign (self, *args):
"%reduce ID ASSIGN ID"
def reduce_while (self, *args):
"%reduce WHILE ID DO stm"
def reduce_begin (self, *args):
"%reduce BEGIN stmlist END"
def reduce_then (self, *args):
"%reduce IF ID THEN stm [p1]"
def reduce_else (self, *args):
"%reduce IF ID THEN stm ELSE stm [p1]"
class stmlist (Parsing.Nonterm):
"%nonterm"
def reduce_stm (self, *args):
"%reduce stm"
def reduce_semi (self, *args):
"%reduce stmlist SEMI stm"
class prog (Parsing.Nonterm):
"%start"
def reduce (self, *args):
"%reduce stmlist"
from pdb import set_trace as trace
from pprint import pprint as pp
class Parser (Parsing.Lr):
def scan (self, input):
syms= {
"while": t_WHILE,
"begin": t_BEGIN,
"end": t_END,
"do": t_DO,
"if": t_IF,
"then" :t_THEN,
"else" :t_ELSE,
";" :t_SEMI,
":=" :t_ASSIGN,
}
for word in input.split():
if word in syms:
token = syms[word](self)
else:
token = t_ID (self, word)
self.token (token)
self.eoi()
def make_map (l):
m = {}
for i in range (len (l)):
m[l[i]] = i
return m
def build_tables (s):
tokens = s._tokens.keys()
nonterms = s._nonterms.keys()
goto = s._goto
action = s._action
token_map = make_map (tokens)
nt_map = make_map (nonterms)
action2 = []
for i in range (len (action)):
d = {}
for k,v in action[i].iteritems():
# v is always a one-element list? GLR-related?
if is_a (v[0], Parsing.ShiftAction):
v = -1, v[0].nextState
elif is_a (v[0], Parsing.ReduceAction):
p = v[0].production
v = -2, (len(p.rhs), p.lhs.name)
else:
raise ValueError
d[token_map[k.name]] = v
action2.append (d)
goto2 = []
for i in range (len (goto)):
d = {}
for k,v in goto[i].iteritems():
d[k.name] = v
goto2.append (d)
return goto2, action2, token_map, nt_map
def get_state (stack):
if stack:
return stack[-1][1]
else:
return 0
def eval (goto, action, tmap, ntmap, stream):
stack = []
while len(stream):
kind, val = stream[0]
state = get_state (stack)
shift_reduce, n = action[state][tmap[kind]]
if shift_reduce is -1:
# shift
stream.pop (0)
stack.append ((val, n))
elif shift_reduce is -2:
# reduce
plen, nt = n
stack, args = stack[:-plen], stack[-plen:]
next_state = goto[get_state(stack)][nt]
stack.append (((nt,[x[0] for x in args]), next_state))
if stack[-1][0] == '<$>':
trace()
return stack[0][0]
else:
raise SyntaxError
def build_stream (s):
keywords = {
"while":"WHILE",
"begin":"BEGIN",
"end":"END",
"do":"DO",
"if":"IF",
"then":"THEN",
"else":"ELSE",
";":"SEMI",
":=":"ASSIGN",
}
r = []
for word in s.split():
if keywords.has_key (word):
r.append ((keywords[word], word))
else:
r.append (('ID', word))
r.append (('<$>', '<$>'))
return r
import sys
spec = Parsing.Spec (
sys.modules[__name__],
pickleFile="appel.pickle",
skinny=False,
logFile="appel.log",
graphFile="appel.dot",
verbose=True
)
p = Parser (spec)
p.verbose = True
t = "begin x := y ; z := a end"
t = "while x do begin x := y ; z := x end"
t = "if x then a := b else c := d"
t = "if x then if y then c := d else e := f"
t = """
while x do
begin
x := y ;
if z then x := y else y := z
end
"""
#p.scan (t)
goto, action, tmap, ntmap = build_tables (spec)
stream = build_stream (t)
pp (eval (goto, action, tmap, ntmap, stream))