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