# -*- coding: UTF-8 -*- """ This is part of Yappy parser.py -- Yet another parser for python... A LR parser generator, based on Aho and al. 1986, C{Compilers} (aho86:_compil). It currently builds C{SLR}, C{LR(1)} and C{LALR(1)} parsing tables. Copyright (C) 2000-2003 Rogério Reis & Nelma Moreira {rvr,nam}@ncc.up.pt Version: $Id: parser.py,v 1.9 2004/12/02 10:17:50 nam Exp $ This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. @author: Rogério Reis & Nelma Moreira {rvr,nam}@ncc.up.pt @var _DEBUG: if nonzero, display information during parser generation or parsing. @type _DEBUG: integer """ from types import * import pcre, re, exceptions import sys, string, copy, time, operator import shelve import osets #Globals _DEBUG = 0 _Version = 1.2 class Lexer: """Class for lexical analyser to use with the parser @ivar rules: lexical rules @ivar operators: precedence and associativity for operators @type operators: dictionary """ def __init__(self,rules_list): """ By now lexer is kept as simple as possible, so order is really essential: i.e. if a keyword is substring of another its rule must appear after the larger keyword for the obvious reasons... @param rules_list: contains pairs C{(re,funct,op?)} where: C{re}: is an uncompiled python regular expression C{funct}: the name of a funcion that returns the pair C{(TOKEN, SPECIAL_VALUE)}, where C{TOKEN} is the token to be used by the parser and C{SPECIAL_VALUE} an eventual associated value. The argument is the matched string. If C{funct} equals C{""} the token is ignored. This can be used for delimiters. C{op}: if present, is a tuple with operador information: C{(TOKEN,PRECEDENCE,ASSOC)} where C{PRECEDENCE} is an integer and C{ASSOC} the string 'left' or 'right'. """ self.rules = [] rnumber = 1 for r in rules_list: rex = r[0] funct = r[1] try: rec = re.compile(rex) except pcre.error: raise LexicalRulesErrorRE(rex,rnumber) try: op,prec,assoc = r[2] if not self.__dict__.has_key("operators"): self.operators={} if not self.operators.has_key(op): self.operators[op]=(prec,assoc) except IndexError: pass self.rules.append((rec,funct)) rnumber = rnumber + 1 if _DEBUG and self.__dict__.has_key("operators"): print "operators %s" %self.operators def scan(self,string): """Performs the lexical analysis on C{string} @return: a list of tokens (pairs C{(TOKEN , SPEcial_VALUE )}), for recognized elements and C{("@UNK", string )} for the others""" st = string for r in self.rules: st = self.scanOneRule(r,st) st = self.scanUnknown(st) return self.rebuild(st) def scanOneRule(self,rule,st): """Scans space C{st} according only one rule @param rule: one rule C{(re,fun,op)} @param st: can be a string or a more complex structure product of previous scans steps ( an tuple C{(match, left, right)}) """ #re, fun = rule re = rule[0] fun = rule[1] if isinstance(st, StringType): if st == "": return st m = re.search(st) if not m: return st else: if m.start() == 0: left = "" else: left = st[0:m.start()] if m.end() == len(st): right = "" else: right = st[m.end():] if fun == "": return ("",left, self.scanOneRule(rule,right)) return (apply(fun,[st[m.start():m.end()]]),left, self.scanOneRule(rule,right)) else: # OK so this is already a tuple (match,left,right) (match, left, right) = st return (match, self.scanOneRule(rule,left), self.scanOneRule(rule,right)) def scanUnknown(self,st): """Scans the resulting structure making Unknown strings Unknown parts will be of the form ("@UNK", string ) """ f = lambda x: ("@UNK",x) return self.scanOneRule((re.compile(".*"),f),st) def rebuild(self,st): """Re-assembles the structure resulting from scanning as a list. @return: a list of tokens (pairs of token-value).""" if isinstance(st, StringType): # then st is "" assert st == "", "A non-empty string appears as a branch!" return [] else: (s, left, right) = st if s != "": return self.rebuild(left) + [s] + self.rebuild(right) else: return self.rebuild(left) + self.rebuild(right) def readscan(self): """Scans a string read from stdin """ st = raw_input() if not st: raise IOError if isinstance(st, StringType): s = self.scan(st) return s class YappyError(Exception): """Class for all Yappy exceptions""" pass class LexicalError(YappyError): """Class for all Yappy Lexical analyser exceptions""" pass class LexicalRulesErrorRE(YappyError): """An error occured parsing the RE part of a lexical rule""" def __init__(self,re,no=0): self.message = 'Error in RE "%s" at rule n.%d'%(re,no) self.rule = no self.re = re class GrammarError(YappyError): """Class for input grammar errors """ def __init__(self,rule): self.message = 'Error in rule "%s" '%rule class SLRConflictError(YappyError): """Confliting actions in building SLR parsing table. Grammar is not SLR(0)""" def __init__(self,i,a): self.message = 'Confliting action[%d,%s] in SLR parsing table ' %(i,a) self.item = i self.symbol = a class LRConflictError(YappyError): """Conflicting actions in building LR parsing table. Grammar is not LR(1)""" def __init__(self,i,a): self.message = 'Confliting action[%d,%s] in LR(1) parsing table ' %(i,a) self.item = i self.symbol = a def __str__(self): return "%s" % (self.message) class LRConflicts(YappyError): """Confliting actions in building LR parsing table. Grammar is not LR(1)""" def __init__(self): self.message = """Warning>>> Several confliting actions. Please consult self.Log for details""" def __str__(self): return "%s" % (self.message) class LRParserError(YappyError): """An error occured in LR parsing program""" def __init__(self,s,a): self.item = s self.symbol = a self.message = 'Error in LR: (%s,%s) not found' %(s,a) def __str__(self): return "%s" % (self.message) class SemanticError(YappyError): """An error occured in the application of a semantic action""" def __init__(self,m): self.message = m def __str__(self): return "%s" % (self.message) class TableError(YappyError): """Mismatch table version """ def __init__(self,t): self.message = """A new table must be built. Please remove table shelve %s or set no_table to 0""" %t def __str__(self): return "%s" % (self.message) class CFGrammar: """ Class for context-free grammars @ivar rules: grammar rules @ivar terminals: terminals symbols @ivar nonterminals: nonterminals symbols @ivar start: start symbol @type start: string @ivar ntr: dictionary of rules for each nonterminal """ def __init__(self,grammar): """ @param grammar: is a list for productions; each production is a tuple C{(LeftHandside,RightHandside,SemFunc,Prec?)} with C{LeftHandside} nonterminal, C{RightHandside} list of symbols, C{SemFunc} syntax-direct semantics, if present C{Prec (PRECEDENCE,ASSOC)} for ambiguous rules First production is for start symbol Special symbols: C{@S}, C{$}, C{#} """ """ MUST BE IN THIS ORDER""" self.rules = grammar self.makenonterminals() self.maketerminals() self.start = self.rules[0][0] self.aug_start = "@S" self.rules.append((self.aug_start,[self.start],DefaultSemRule)) self.endmark = '$' self.dummy = '#' self.terminals.append(self.endmark) self.terminals.append(self.dummy) self.nonterminals.append(self.aug_start) """ ritems are only for control ... not needed """ self.ritems = [] """ ntr[A] is the set of rules which has A as left side""" self.ntr = {} i = 0 for r in self.rules: if not self.ntr.has_key(r[0]): self.ntr[r[0]] = [i] else: self.ntr[r[0]].append(i) for j in range(len(r[1]) + 1): self.ritems.append((i,j)) i = i + 1 def __str__(self): """Grammar rules @return: a string representing the grammar rules """ s = "" for n in range(len(self.rules)): lhs = self.rules[n][0] rhs = self.rules[n][1] s = s + "%s | %s -> %s \n" %(n, lhs, string.join(rhs," ")) return "Grammar Rules:\n\n%s" % s def makeFFN(self): self.NULLABLE() self.FIRST_ONE() self.FOLLOW() def maketerminals(self): """Extracts C{terminals} from the rules. C{nonterminals} must already exist""" self.terminals = [] for r in self.rules: for s in r[1]: if s not in self.nonterminals and s not in self.terminals: self.terminals.append(s) def makenonterminals(self): """Extracts C{nonterminals} from grammar rules.""" self.nonterminals = [] for r in self.rules: if r[0] not in self.nonterminals: self.nonterminals.append(r[0]) def NULLABLE(self): """Determines which nonterminals C{X ->* []} """ self.nullable = {} for s in self.terminals: self.nullable[s] = 0 for s in self.nonterminals: self.nullable[s] = 0 if self.ntr.has_key(s): for i in self.ntr[s]: if not self.rules[i][1]: self.nullable[s] = 1 break k = 1 while k == 1: k = 0 for r in self.rules: e = 0 for i in r[1]: if not self.nullable[i]: e = 1 break if e == 0 and not self.nullable[r[0]]: self.nullable[r[0]] = 1 k = 1 def FIRST(self,s): """C{FIRST(s)} is the set of terminals that begin the strings derived from s """ first = osets.Set([]) e = 0 for i in range(len(s)): first.s_extend(self.first[s[i]]) if not self.nullable[s[i]]: e = 1 break if e == 0: self.nullable[string.join(s)] = 1 else: self.nullable[string.join(s)] = 0 return first def FIRST_ONE(self): """Determines C{FIRST(s)}, for every symbol s, that is the set of terminals that begin the strings derived from s """ self.first = {} self.nd = {} self.ms =Stack() for s in self.terminals: self.first[s] = osets.Set([s]) for s in self.nonterminals: if self.ntr.has_key(s) and not self.first.has_key(s): # self.FIRST_NT(s) self.FIRST_TRA(s,1) def FIRST_TRA(self,s,d): """Transitiv closure of C{FIRST(X)} """ self.ms.push(s) self.nd[s] = d """ calculating F1(s)""" self.first[s] = osets.Set([]) for i in self.ntr[s]: for y in self.rules[i][1]: if self.nullable[y]: continue else: if y in self.terminals: self.first[s].append(y) break """transitive closure""" for i in self.ntr[s]: for y in self.rules[i][1]: if y in self.nonterminals: if not self.first.has_key(y): self.FIRST_TRA(y,d+1) if self.nd.has_key(y) and self.nd[y] != -1: self.nd[s] = min(self.nd[s],self.nd[y]) self.first[s].s_extend(self.first[y]) if self.nullable[y]: continue else: break else: break if self.nd[s] == d: while 1: y = self.ms.pop() if y == s: break self.first[y] = self.first[s].copy() self.nd[y] = -1 def FIRST_NT(self,s): """ Recursivelly computes C{FIRST(X)} for a nonterminal X""" if not self.ntr.has_key(s): return self.first[s] = osets.Set([]) for i in self.ntr[s]: r = self.rules[i][1] if r == []: self.nullable[s] = 1 else: e = 1 for y in r: if not self.first.has_key(y): self.FIRST_NT(y) self.first[s].s_extend(self.first[y]) if not self.nullable[y]: e = 0 break if e == 1: self.nullable[s] = 1 def FOLLOW(self): """computes C{FOLLOW(A)} for all nonterminals: the set of terminals a that can appear immediately to the right of A in some sentential form.""" self.follow = {} self.follow[self.start] = osets.Set([self.endmark]) for rule in self.rules: r = rule[1] for i in range(len(r)): if r[i] in self.nonterminals: if not self.follow.has_key(r[i]): self.follow[r[i]] = osets.Set([]) j = i + 1 self.follow[r[i]].s_extend(self.FIRST(r[j:])) e = 1 while e: e = 0 for s in self.nonterminals: for i in self.ntr[s]: r = self.rules[i][1] try: b = r[len(r)-1] if b in self.nonterminals and self.follow[b].s_extend(self.follow[s]): e = 1 except IndexError: pass except KeyError: pass for k in range(len(r)-1): j = k + 1 if r[k] in self.nonterminals and self.nullable[string.join(r[j:])]: if self.follow[r[k]].s_extend(self.follow[s]): e = 1 break def TransClose(self): """For each nonterminal C{s} determines the set of nonterminals a such that C{s ->* ar}, for some C{r}""" self.close_nt = {} self.nd = {} self.ms =Stack() for s in self.nonterminals: if self.ntr.has_key(s) and not self.close_nt.has_key(s): self.TRAVERSE(s,1) def TRAVERSE(self,s,d): """ """ self.ms.push(s) self.nd[s] = d """ calculating F1(s)""" self.close_nt[s] = {s:osets.Set([[]])} for i in self.ntr[s]: if not self.rules[i][1]: continue else: r = self.rules[i][1] for j in range(len(r)): if r[j+1:]: f = self.FIRST(r[j+1:]) ns = self.nullable[string.join(r[j+1:])] else: f = [] ns = 1 if r[j] in self.nonterminals: if not self.close_nt[s].has_key(r[j]): self.close_nt[s][r[j]] = osets.Set([[]]) if r[j+1:]: self.close_nt[s][r[j]].append((f,ns)) if not self.nullable[r[j]]: break else: break """reflexive tansitive closure""" for i in self.ntr[s]: if not self.rules[i][1]: continue else: r = self.rules[i][1] for j in range(len(r)): f = self.FIRST(r[j+1:]) ns = self.nullable[string.join(r[j+1:])] if r[j] in self.nonterminals: if not self.close_nt.has_key(r[j]): self.TRAVERSE(r[j],d+1) if self.nd.has_key(r[j]) and self.nd[r[j]] != -1: self.nd[s] = min(self.nd[s],self.nd[r[j]]) for k in self.close_nt[r[j]].keys(): if not self.close_nt[s].has_key(k): self.close_nt[s][k] = osets.Set([[]]) else: for v in self.close_nt[s][k]: if not v: self.close_nt[s][k].append((f,ns)) else: p, n = v if n: self.close_nt[s][k].append((p+f,ns)) else: self.close_nt[s][k].append((p,n)) if not self.nullable[r[j]]: break else: break if self.nd[s] == d: while 1: y = self.ms.pop() if y == s: break self.close_nt[y] = self.close_nt[s].copy() self.nd[y] = -1 def DERIVE_NT(self): """For each nonterminal C{s} determines the set of nonterminals a such that C{s ->* ar}, for some C{r}""" self.derive_nt = {} for s in self.nonterminals: if self.ntr.has_key(s) and not self.derive_nt.has_key(s): self.DERIVE_ONE_NT(s) def DERIVE_ONE_NT(self,s): """For nonterminal C{s} determines the set of nonterminals a such that C{s -> ar}, for some C{r} """ if not self.ntr.has_key(s): return self.derive_nt[s] = {s:osets.Set([None])} for i in self.ntr[s]: if not self.rules[i][1]: continue else: r = self.rules[i][1] for j in range(len(r)): if r[j] in self.nonterminals: if not self.derive_nt.has_key(r[j]): self.DERIVE_ONE_NT(r[j]) for k in self.derive_nt[r[j]].keys(): if not self.derive_nt[s].has_key(k): self.derive_nt[s][k] = osets.Set([]) for p in self.derive_nt[r[j]][k]: if not p : self.derive_nt[s][k].append(r[j+1:]) else: self.derive_nt[s][k].append(r[j+1:].append(p)) if not self.nullable[r[j]]: break else: break def DERIVE_T(self): """ """ self.derive_ter = {} for s in self.terminals: self.derive_ter[s] = osets.Set([s]) e = 1 while e: e = 0 for s in self.nonterminals: for i in self.ntr[s]: r = self.rules[i][1] if r == []: continue for i in range(len(r)): if r[i] in self.terminals: if i < len(r) -1: if self.derive_ter.has_key(r[i+1]): if not self.derive_ter.has_key(s): self.derive_ter[s] = osets.Set([]) if self.derive_ter[s].s_append(r[i]): e = 1 break else: if not self.derive_ter.has_key(s): self.derive_ter[s] = osets.Set([]) if self.derive_ter[s].s_append(r[i]): e = 1 break else: """ non-terminal""" if self.derive_ter.has_key(r[i]): if not self.derive_ter.has_key(s): self.derive_ter[s] = osets.Set([]) if self.derive_ter[s].s_extend(self.derive_ter[r[i]]) == 1: e = 1 if i > 0 and self.nullable[r[i]]: continue else: break class LRtable: """Class for construction of a C{LR} table @ivar gr: a context-free grammar @ivar operators: operators @ivar Log: Log report for LR table construction """ def __init__(self,cfgr,operators=None,noconflicts=1,expect=0): """ @param cfgr: a context-free grammar @param operators: operators @param noconflicts: if 0 LRtable conflicts are not resolved, unless for spcecial operator rules @type noconflicts: integer @param expect: exact number of expected LR shift/reduce conflicts @type expect: integer """ self.gr = cfgr self.gr.makeFFN() self.operators = operators self.precedence = None if self.operators: self.rules_precedence() self.Log=LogLR(noconflicts,expect) self.make_action_goto() def make_action_goto(self): """ make C{action[i,X]} and C{goto[i,X]} All pairs C{(i,s)} not in action and goto dictionaries are 'error' """ c = self.items() if _DEBUG: print self.print_items(c) self.ACTION = {} self.GOTO = {} #shelve not working with osets #self.Log.items = c for i in range(len(c)): for item in c[i]: a = self.NextToDot(item) if a in self.gr.terminals: state = self.goto(c[i],a) try: j = c.index(state) self.add_action(i,a,'shift',j) except IndexError: if _DEBUG: print "no state" elif a == "": """ Dot at right end """ l = self.gr.rules[item[0]][0] if l != self.gr.aug_start : self.dotatend(item,i) else: """ last rule """ self.add_action(i,self.gr.endmark,'accept',[]) for s in self.gr.nonterminals: state = self.goto(c[i],s) try: j = c.index(state) self.GOTO[(i,s)] = j except ValueError: pass def rules_precedence(self): """Rule precedence obtained as the precedende of the right most terminal. """ self.precedence={} for i in range(len(self.gr.rules)): if len(self.gr.rules[i]) == 4: self.precedence[i] = self.gr.rules[i][3] else: self.gr.rules[i][1].reverse() for s in self.gr.rules[i][1]: if self.operators.has_key(s): self.precedence[i] = self.operators[s] break self.gr.rules[i][1].reverse() if _DEBUG: print "Precedence %s" %self.precedence def add_action(self,i,a,action,j): """Set C{(action,j)} for state C{i} and symbol C{a} or raise conflict error. Conficts are resolved using the following rules: - shift/reduce: if precedence/assoc information is available try to use it; otherwise conflict is resolved in favor of shift - reduce/reduce: choosing the production rule listed first """ if self.ACTION.has_key((i,a)) and self.ACTION[(i,a)] != (action,j): action1 , j1 = self.ACTION[(i,a)] if _DEBUG: print "LRconflit %s %s %s %s %s %s" %(action,j,action1,j1, i,a) if action1 == 'shift' and action == 'reduce': self.resolve_shift_reduce(i,a,j1,j) elif action == 'shift' and action1 == 'reduce': self.resolve_shift_reduce(i,a,j,j1) elif action == 'reduce' and action1 == 'reduce': if self.Log.noconflicts: # RESOLVED by choosing first rule if j > j1: self.ACTION[(i,a)] = (action,j1) else: self.ACTION[(i,a)] = (action,j) self.Log.add_conflict('rr',i,a,j1,j) else: raise LRConflictError(i,a) else: self.ACTION[(i,a)] = (action,j) def resolve_shift_reduce(self,i,a,s,r): """Operators precedence resolution or standard option: shift C{s}: rule for shift C{r}: rule for reduce """ try: if self.operators.has_key(a): prec_op, assoc_op = self.operators[a] else: prec_op, assoc_op = (0,'DUMMY') if self.precedence.has_key(r): if (self.precedence[r][0] > prec_op) or (self.precedence[r][0] == prec_op and self.precedence[r][1] =='left'): self.ACTION[(i,a)] = ('reduce',r) if _DEBUG: print "solved reduce %s" %r else: self.ACTION[(i,a)] = ('shift',s) if _DEBUG: print "solved shift %s" %s except: if self.Log.noconflicts: # choose to shift self.ACTION[(i,a)] = ('shift',s) if _DEBUG: print "choose shift %s for action (%s,%s)" %(s,i,a) self.Log.add_conflict('sr',i,a,s,r) if _DEBUG: print " %s for action (%s,%s)" %(self.Log.conflicts,i,a) else: raise LRConflictError(i,a) class SLRtable(LRtable): """Class for construction of a C{SLR} table C{SLR} items represented by a pair of integers C{(number of rule,position of dot)} (aho86:_compil page 221) """ def dotatend(self,item,i): n, k = item l = self.gr.rules[item[0]][0] for a in self.gr.follow[l]: self.add_action(i,a,'reduce',n) def closure(self,items): """The closure of a set of C{LR(0)} items C{I} is the set of items constructed from C{I} by the two rules: - every item of I is in closure(I) - If A -> s.Bt in closure(I) and B -> r, then add B ->.r to closure(I) (aho86:_compil page 223) """ added = {} for l in self.gr.nonterminals: added[l] = 0 close = items[:] e = 1 while e: e = 0 for i in close: s = self.NextToDot(i) if s in self.gr.nonterminals and added[s]==0 and self.gr.ntr.has_key(s): for n in self.gr.ntr[s]: close.append((n,0)) added[s] = 1 e = 1 return close def goto(self,items,s): """ goto(I,X) where I is a set of items and X a grammar symbol is the closure of the set of all items A -> sX.r such that A -> s.Xr is in I""" valid = osets.Set([]) for item in items: if self.NextToDot(item) == s: n, i = item valid.append((n, i + 1)) return self.closure(valid) def items(self): """ An LR(0) item of a grammar G is a production of G with a dot at some position on the right hand side. It is represented by the rule number and the position of the dot @return: a set of sets of items """ c = osets.Set([self.closure(osets.Set([(len(self.gr.rules) - 1,0)]))]) symbols = self.gr.terminals + self.gr.nonterminals e = 1 while e: e = 0 for i in c: for s in symbols: valid = self.goto(i,s) if valid != [] and valid not in c: c.append(valid) e = 1 return c def print_items(self,c): """Print SLR items """ s = "" j = 0 for i in c: s = s+ "I_%d: \n" %j for item in i: r, p = item lhs = self.gr.rules[r][0] rhs = self.gr.rules[r][1] s = s + "\t %s -> %s . %s \n" %(lhs, string.join(rhs[:p]," "), string.join(rhs[p:]," ")) j += 1 return s def NextToDot(self,item): """ returns symbol next to te dot or empty string""" n, i = item try: s = self.gr.rules[n][1][i] except IndexError: s = "" return s class LR1table(LRtable): """ Class for construction of a LR1 table Items are represented by a pair of integers (number of rule, position of dot) """ def closure(self,items): """The closure of a set of C{LR(1)} items C{I} is the set of items construted from I by the two rules: - every item of C{I} is in C{closure(I)} - If C{[A -> s.Bt,a]} in C{closure(I)},for C{B ->r} and each terminal C{b} in C{first(ta)}, add C{[B ->.r,b]} to C{closure(I)} """ close = items e = 1 while e: e = 0 for i in close: s = self.NextToDot(i) sa = self.gr.FIRST(self.AfterDot(i)) if s in self.gr.nonterminals and self.gr.ntr.has_key(s): for n in self.gr.ntr[s]: for b in sa: e = close.append((n,0,b)) return close def goto(self,items,s): """ goto(I,X) where I is a set of items and X a grammar symbol is the closure of the set of all items (A -> sX.r,a) such that (A -> s.Xr,a) in I""" valid = osets.Set([]) for item in items: if self.NextToDot(item) == s: n, i, t = item valid.append((n, i + 1,t)) return self.closure(valid) def items(self): """ An LR(1) item of a grammar G is a production of G with a dot at some position of the right hand side and a terminal: (rule_number,dot_position,terminal) (aho86:_compil page 231) """ c = osets.Set([ self.closure(osets.Set([(len(self.gr.rules) - 1,0,self.gr.endmark)]))]) symbols = self.gr.terminals + self.gr.nonterminals e = 1 while e: e = 0 for i in c: for s in symbols: valid=self.goto(i,s) if valid != [] : if c.s_append(valid): e = 1 return c def print_items(self,c): """Print C{LR(1)} items """ s = "" j = 0 for i in c: s = s+ "I_%d: \n" %j for item in i: r, p, t = item lhs = self.gr.rules[r][0] rhs = self.gr.rules[r][1] s = s + "\t %s -> %s . %s , %s\n" %(lhs, string.join(rhs[:p]," "), string.join(rhs[p:]," "),t) j += 1 print s return s def NextToDot(self,item): """ returns symbol next to the dot or empty string""" n, i, t = item try: s = self.gr.rules[n][1][i] except IndexError: s = "" return s def AfterDot(self,item): """ returns symbol next to the dot or empty string""" n, i, t = item try: s = self.gr.rules[n][1][i+1:] except IndexError: s = [] s.append(t) return s def dotatend(self,item,i): n, k, t = item self.add_action(i,t,'reduce',n) class LALRtable1(LRtable): """Class for construction of C{LALR(1)} tables""" def make_action_goto(self): """ Make C{action[i,X]} and C{goto[i,X]} all pairs C{(i,s)} not in action and goto dictionaries are 'error' """ self.gr.DERIVE_NT() c = self.items() if _DEBUG: print self.print_items(c) self.ACTION = {} self.GOTO = {} #shelve not working with osets #self.Log.items = c for i in range(len(c)): for item in c[i].keys(): a = self.NextToDot(item) if a in self.gr.terminals: state =self.goto(c[i],a) j = self.get_union(c,state) if j != -1: self.add_action(i,a,'shift',j) elif a == "": """ Dot at right end """ l = self.gr.rules[item[0]][0] if l != self.gr.aug_start : self.dotatend(item,c,i) else: """ last rule """ self.add_action(i,self.gr.endmark,'accept',[]) for s in self.gr.nonterminals: state = self.goto(c[i],s) j = self.get_union(c,state) if j != -1: self.GOTO[(i,s)] = j def items(self): """ An C{LALR(1)} item of a grammar C{G} is a production of C{G}with a dot at some position of the right hand side and a list of terminals: is coded as a dictonary with key C{(rule_number,dot_position)} and value a set of terminals """ i0 = {} i0[(len(self.gr.rules) - 1,0)] = osets.Set([self.gr.endmark]) c = osets.Set([self.closure(i0)]) symbols = self.gr.terminals + self.gr.nonterminals e = 1 while e: e = 0 for i in c: for s in symbols: if self.core_merge(c,self.goto(i,s)) == 1: e = 1 return c def print_items(self,c): """Print C{LALR(1)} items """ s = "" j = 0 for i in range(len(c)): s = s+ "I_%d: \n" %i for item in c[i].keys(): r, p = item lhs = self.gr.rules[r][0] rhs = self.gr.rules[r][1] s = s + "\t %s -> %s . %s, %s \n" %(lhs, string.join(rhs[:p]," "), string.join(rhs[p:]," "),c[i][item]) print s return s def goto(self,items,s): """ C{goto(I,X)} where C{I} is a set of items and C{X} a grammar symbol is the closure of the set of all items C{(A -> sX.r,a)} such that C{(A -> s.Xr,a)} in C{I}""" valid = {} for (n,i) in items.keys(): if self.NextToDot((n,i)) == s: if not valid.has_key((n,i+1)): valid[(n,i + 1)] = osets.Set([]) for t in items[(n,i)]: valid[(n, i + 1)].append(t) return self.closure(valid) def closure(self,items): """The closure of a set of C{LR(1)} items I is the set of items construted from I by the two rules: - every item of I is in closure(I) - If [A -> s.Bt,a] in closure(I),for B ->r and each terminal b in first(ta), add [B ->.r,b] to closure(I) """ e = 1 while e: e = 0 for i in items.keys(): s = self.NextToDot(i) if s in self.gr.nonterminals and self.gr.ntr.has_key(s): l = self.AfterDot(i,items) for n in self.gr.ntr[s]: if not items.has_key((n,0)): items[(n,0)] = osets.Set([]) if items[(n,0)].s_extend(l) == 1 : e = 1 return items def get_union(self,c,j): """ """ for i in c: if i.keys() == j.keys(): return c.index(i) return -1 def core_merge(self,c,j): """ """ if j == {} or j in c : return 0 e = 2 for i in c: if i.keys() == j.keys(): e = 0 for k in j.keys(): if i[k].s_extend(j[k]) == 1: e = 1 break if e == 2: e = c.s_append(j) return e def NextToDot(self,item): """ returns symbol next to the dot or empty string""" n, i = item try: s = self.gr.rules[n][1][i] except IndexError: s = "" return s def AfterDot(self,item,items): """ returns FIRST of strings after the dot concatenated with lookahead""" n, i = item try: s = self.gr.rules[n][1][i+1:] except IndexError: s = [] sa = osets.Set([]) for a in items[item]: s.append(a) sa.s_extend(self.gr.FIRST(s)) del s[len(s)-1] return sa def dotatend(self,item,c,i): n, k = item for a in c[i][item]: self.add_action(i,a,'reduce',n) class LALRtable(LALRtable1): """Class for construction of LALR tables """ def make_action_goto(self): """ collection of LR(0) items """ self.gr.DERIVE_T() self.gr.TransClose() c = self.items() if _DEBUG: print self.print_items(c) """ make action[i,X] and goto[i,X] all pairs (i,s) not in action and goto dictionaries are 'error' """ self.ACTION = {} self.GOTO = {} #shelve not working with osets #self.Log.items = c for i in range(len(c)): for item in c[i].keys(): C = self.NextToDot(item) if C in self.gr.nonterminals: if self.gr.derive_ter.has_key(C): for a in self.gr.derive_ter[C]: if self.goto_ref.has_key((i,a)): j = self.goto_ref[(i,a)] self.add_action(i,a,'shift',j) if self.gr.close_nt.has_key(C): for A in self.gr.close_nt[C].keys(): """Error: ignores end string s in C->*As""" for p in self.gr.close_nt[C][A]: r = self.AfterDotTer(item,c[i],p) if self.gr.ntr.has_key(A): for k in self.gr.ntr[A]: if self.gr.rules[k][1] == []: for a in r: self.add_action(i,a,'reduce',k) elif C in self.gr.terminals: if self.goto_ref.has_key((i,C)): j = self.goto_ref[(i,C)] self.add_action(i,C,'shift',j) else: """ Dot at right end """ l = self.gr.rules[item[0]][0] if l != self.gr.aug_start: self.dotatend(item,c,i) else: """ last rule """ self.add_action(i,self.gr.endmark,'accept',[]) for s in self.gr.nonterminals: state = self.goto(c[i],s) j = self.get_union(c,state) if j != -1: self.GOTO[(i,s)] = j def items(self): """ An C{LALR(1)} kernel item of a grammar C{G} is a production of C{G} with a dot at some position of the right hand side (except the first) and a list of terminals: is coded as a dictionary with key C{(rule_number,dot_position)} and value a set of terminals. """ i0 = {} i0[(len(self.gr.rules) - 1,0)] = osets.Set([self.gr.endmark]) c= osets.Set([i0]) symbols = self.gr.terminals + self.gr.nonterminals """ kernel LR(0) items """ self.goto_ref = {} e = 1 while e: e = 0 for i in c: for s in symbols: valid = self.goto(i,s) if valid != {}: if c.s_append(valid): e = 1 self.goto_ref[(c.index(i),s)] = c.index(valid) """ Discovering propagated and spontaneous lookaheads for kernel items k and grammar symbol s""" lh={} for k in c: nk = c.index(k) lh[nk] = {} #osets.Set([]) for (n,i) in k.keys(): lh[nk][(n,i)] = osets.Set([]) j = {} j[(n,i)]=osets.Set([(self.gr.dummy)]) j = self.closure(j) for s in symbols: for (m1,j1) in j.keys(): if self.NextToDot((m1,j1)) == s: for a in j[(m1,j1)]: if a == self.gr.dummy: lh[nk][(n,i)].append((self.goto_ref[(nk,s)],m1,j1+1)) else: c[self.goto_ref[(nk,s)]][(m1,j1+1)].append(a) del j """ Propagate lookaheads """ # c[0][(len(self.gr.rules) - 1,0)].s_append(self.gr.endmark) e = 1 while e: e = 0 for k in c: nk = c.index(k) for (n,i) in k.keys(): for (m,n1,i1) in lh[nk][(n,i)]: if c[m][(n1,i1)].s_extend(k[(n,i)]) == 1: e = 1 return c def goto(self,items,s): """ C{goto(I,X)} where I is a set of kernel items and X a grammar symbol is the closure of the set of all items (A -> sX.r,a) such that (A -> s.Xr,a) is in I""" valid = {} for (n,i) in items.keys(): x = self.NextToDot((n,i)) if x == s: if not valid.has_key((n,i+1)): valid[(n,i + 1)] = osets.Set([]) if self.gr.close_nt.has_key(x): for a in self.gr.close_nt[x].keys(): if self.gr.ntr.has_key(a): for k in self.gr.ntr[a]: if self.gr.rules[k][1] != [] and self.gr.rules[k][1][0] == s: valid[(k,1)] = osets.Set([]) return valid def NextToDot(self,item): """ returns symbol next to the dot or empty string""" n, i = item try: s = self.gr.rules[n][1][i] except IndexError: s = "" return s def AfterDotTer(self,item,items,path): """ returns FIRST of strings after the dot concatenated with lookahead""" if path: p, n = path if not n: return p l, i = item try: f= self.gr.FIRST(self.gr.rules[l][1][i+1:]) ns = self.gr.nullable[string.join(self.gr.rules[l][1][i+1:])] except IndexError: f = [] ns = 1 if ns: return items[item] else: return f class LogLR: """Class for LR table construction report: @ivar expect: number of shit/reduce conflicts expected @type expect: integer @ivar items: set of LR items @ivar conflicts: dictionary of conflicts occurred in LR table construction: 'rr' and 'sr' """ def __init__(self,noconflicts,expect): self.noconflicts = noconflicts self.expect = expect self.conflicts = {} self.items = None def add_conflict(self,type,i,a,value1,value2): try: self.conflicts[type].append((i,a,value1,value2)) except KeyError: self.conflicts[type] = [(i,a,value1,value2)] class LRparser: """Class for LR parser @ivar cfgr: context free grammar @ivar rules: grammar rules @ivar terminals: grammar terminals @ivar nonterminals: grammar nonterminals @ivar table: LR parsing table @ivar ACTION: Action function @ivar GOTO: Goto function @ivar tokens: tokens to be parsed @ivar context: computational context @ivar output: list of grammar rules used for parsing C{tokens} (right derivation in reverse) @ivar stack: LR stack with pairs C{(state,token)} """ def __init__(self,grammar,table_shelve,no_table=1,tabletype=LALRtable,operators=None,noconflicts=1,expect=0,**args): """ @param grammar: is a list for productions; each production is a tuple C{(LeftHandside,RightHandside,SemFunc,Prec?)} with C{LeftHandside} nonterminal, C{RightHandside} list of symbols, C{SemFunc} syntax-direct semantics, if present C{Prec (PRECEDENCE,ASSOC)} for ambiguous rules First production is for start symbol @param table_shelve: file where parser is saved @type table_shelve: string @param tabletype: type of LR table: C{SLR}, C{LR1}, C{LALR} @type tabletype: LRtable class @param no_table: if 0 table_shelve is created anyway @type no_table: integer @param operators: precedence and associativity for operators @type operators: dictionary @param noconflicts: if 0 LRtable conflicts are not resolved, unless spcecial operator rules @type noconflicts: integer @param expect: exact number of expected LR shift/reduce conflicts @type expect: integer """ self.cfgr = CFGrammar(grammar) self.rules = self.cfgr.rules self.terminals = self.cfgr.terminals self.nonterminals = self.cfgr.nonterminals self.endmark = self.cfgr.endmark d = shelve.open(table_shelve) if d and no_table: self.ACTION = d['action'] self.GOTO = d['goto'] if d.has_key('version'): if d['version'] < _Version: raise TableError(table_shelve) try: self.Log = d['log'] except: raise TableError(table_shelve) else: self.table = tabletype(self.cfgr,operators,noconflicts,expect) d['version'] = _Version d['action'] = self. ACTION = self.table.ACTION d['goto'] = self.GOTO = self.table.GOTO d['log'] = self.Log = self.table.Log d.close() def __str__(self): """@return: the LR parsing table showing for each state the action and goto function """ l = (map(lambda x: x[0],self.ACTION.keys())) l.sort() a1="\nState\n" if len(self.terminals) < 20: for a in self.terminals: a1=a1+" \t%s" %a for i in osets.Set(l): a3="\n%s" % i for a in self.terminals: if self.ACTION.has_key((i,a)): if self.ACTION[i,a][0]=="shift": x="s" else: x="r" a2="\t%s%s" %(x,self.ACTION[i,a][1]) else: a2="\t" a3=a3+a2 a1="%s%s" %(a1,a3) ac=a1 else: for i in osets.Set(l): a3="%s\n" % i for a in self.terminals: if self.ACTION.has_key((i,a)): if self.ACTION[i,a][0]=="shift": x="s" else: x="r" a3= a3+"%s = %s%s\n" %(a,x,self.ACTION[i,a][1]) a1="%s%s" %(a1,a3) ac=a1 l = (map(lambda x: x[0],self.GOTO.keys())) l.sort() a1 = "\nState\n" if len(self.nonterminals) < 20: for a in self.nonterminals: a1 = a1 + " \t%s" %a for i in osets.Set(l): a3 = "\n%s" % i for a in self.nonterminals: if self.GOTO.has_key((i,a)): a2 = "\t%s" %self.GOTO[(i,a)] else: a2 = "\t" a3 = a3 + a2 a1 = "%s%s" %(a1,a3) else: for i in osets.Set(l): a3 = "%s\n" % i for a in self.nonterminals: if self.GOTO.has_key((i,a)): a3 = a3 + "%s = %s\n" %(a,self.GOTO[(i,a)]) a1 = "%s%s" %(a1,a3) go = a1 return "Action table:\n %s\n Goto table:%s\n" % (ac,go) def parsing(self,tokens,context = None): """LR Parsing Algorithm (aho86:_compil, page 218) @param tokens: pairs (TOKEN, SPECIAL_VALUE) @param context: a computational context for semantic actions @return: parsed result """ self.stack = Stack() self.stack.push((0,[])) self.tokens = tokens self.tokens.append((self.endmark,self.endmark)) self.context = context self.output = [] ip = 0 while 1: s = self.stack.top()[0] a = self.tokens[ip][0] if _DEBUG: print "Input: %s\nState: %s" %(map(lambda x:x[0],self.tokens[ip:]),s) print "Stack: %s" %self.stack try: if self.ACTION[s,a][0] == 'shift': if _DEBUG: print "Action: shift\n" self.stack.push((self.ACTION[s,a][1], self.tokens[ip][1])) ip = ip + 1 elif self.ACTION[s,a][0] == 'reduce': n = self.ACTION[s,a][1] if _DEBUG: print "Action: reduce %s %s\n" %(n,str(self.rules[n])) semargs = [self.stack.pop()[1] for i in range(len(self.rules[n][1]))] semargs.reverse() reduce = Reduction(self.rules[n][2],semargs,self.context) del semargs s1 = self.stack.top()[0] a = self.rules[n][0] self.stack.push((self.GOTO[s1,a],reduce)) self.output.append(n) elif self.ACTION[s,a] == ('accept', []): break else: raise LRParserError(s,a) except: if _DEBUG: print "Error in action: %s" %self.ACTION raise LRParserError(s,a) return self.stack.top()[1] def parse_grammar(self,st,context): """ Transforms a string into a grammar description @param st: is a string representing the grammar rules, with default symbols as below. Fisrt rule for start. I{Example}:: reg -> reg + reg E{lb}E{lb} self.OrSemRule // (priority,'left') E{rb}E{rb} | ( reg ) E{lb}E{lb}self.ParSemRuleE{rb}E{rb} ; where: - rulesym="->" production symbol - rhssep='' RHS symbols separator - opsym='//' operator definition separator - semsym=E{lb}E{lb} semantic rule start marker - csemsym=E{rb}E{rb} semantic rule end marker - rulesep='|' separator for multiple rules for a LHS - ruleend=';' end marker for one LHS rule""" self.pg=Yappy_grammar() self.pg.input(st,context) return self.pg.context['rules'] def gsrules(self,rulestr, **sym): """ Transforms a string in a grammar description @param rulestr: is a string representing the grammar rules, with default symbols as below. @param sym: Dictionary with symbols used. Default ones: - rulesym="->" production symbol - rhssep='' RHS symbols separator - opsym='//' operator definition separator - semsym=E{lb}E{lb} semantic rule start marker - csemsym=E{rb}E{rb} semantic rule end marker - rulesep='|' separator for multiple rules for a LHS - ruleend=';' end marker for one LHS rule Example: reg -> reg + reg E{lb}E{lb} self.OrSemRule // (priority,'left') E{rb}E{rb} | ( reg ) E{lb}E{lb}self.ParSemRuleE{rb}E{rb} ; """ if not sym: sym = Dict(rulesym="->", rhssep='', opsym='//', semsym='{{', csemsym='}}', rulesep='|', ruleend=';') gr = [] rl = string.split(rulestr,sym['ruleend']) for l in rl: m = re.compile(sym['rulesym']).search(l) if not m: continue else: if m.start() == 0: raise GrammarError(l) else: lhs = l[0:m.start()].strip() if m.end() == len(l): raise GrammarError(l) else: rhss = string.strip(l[m.end():]) if rhss == "[]": rhs = [] sem = EmptySemRule op = None else: rhss = string.split(l[m.end():],sym['rulesep']) for rest in rhss: rest=string.strip(rest) if rhss == "[]": rhs = [] sem = EmptySemRule op = None else: m=re.search(sym['semsym']+'(?P.*)'+sym['csemsym'],rest) if not m: rhs = string.split(rest,None) sem = DefaultSemRule op = None else: if m.start() == 0: raise GrammarError(rest) else: rhs = string.split(rest[0:m.start()].strip()) if m.group('opsem'): opsem = string.split(m.group('opsem'),sym['opsym']) if len(opsem) == 1: sem = string.strip(opsem[0]) op = None elif len(opsem) == 2: sem = string.strip(opsem[0]) op = string.strip(opsem[1]) else: raise GrammarError(rest) else: sem = DefaultSemRule op = None if op == None: gr.append((lhs,rhs,eval(sem))) else: gr.append((lhs,rhs,eval(sem),eval(op))) return gr class LRBuildparser: """Class for LR parser: without shelve and semantic rules(obsolete) """ def __init__(self,grammar): """ """ self.table = LALRtable(grammar) def parsing(self,tokens): """LR Parsing Algorithm """ self.stack = Stack() self.stack.push(0) self.input = tokens self.input.append(self.table.gr.endmark) self.output = [] ip = 0 while 1: s = self.stack.top() a = self.input[ip] if not self.table.ACTION.has_key((s,a)): raise LRParserError() elif self.table.ACTION[s,a][0] == 'shift': # self.stack.push(a) self.stack.push(self.table.ACTION[s,a][1]) ip = ip + 1 elif self.table.ACTION[s,a][0] == 'reduce': n = self.table.ACTION[s,a][1] for i in range(len(self.table.gr.rules[n][1])): self.stack.pop() s1 = self.stack.top() a = self.table.gr.rules[n][0] # self.stack.push(a) if not self.table.GOTO.has_key((s1,a)): raise LRParserError() else: self.stack.push(self.table.GOTO[s1,a]) self.output.append(n) elif self.table.ACTION[s,a] == ('accept', []): break else: raise LRParserError() ############# Auxiliares ################## def Dict(**entries): """Create a dict out of the argument=value arguments""" return entries def grules(rules_list,rulesym="->",rhssep=None): """ Transforms a list of rules in a grammar description @param rules_list: is a list of pairs (rule,sem) where rule is a string of the form: - Word rulesym Word1 ... Word2 - Word rulesym [] @param rulesym: LHS and RHS rule separator @param rhssep: RHS values separator (None for white chars) @return: a grammar description """ gr = [] sep = re.compile(rulesym) for r in rules_list: rule = r[0] m = sep.search(rule) if not m: continue else: if m.start() == 0: raise GrammarError(rule) else: lhs = rule[0:m.start()].strip() if m.end() == len(rule): raise GrammarError(rule) else: rest=string.strip(rule[m.end():]) if rest == "[]": rhs = [] else: rhs = string.split(rest,rhssep) if len(r)==3: gr.append((lhs,rhs,r[1],r[2])) else: gr.append((lhs,rhs,r[1])) return gr ####################################################### class Yappy(LRparser): """ A basic class for parsing. @ivar lex: a Lexer object """ def __init__(self,tokenize,grammar, table='YappyTab', no_table=1, tabletype=LALRtable,noconflicts=1,expect=0): """ @param tokenize: same as for L{Lexer} @param grammar: if a string C{parse_grammar} is called @param table: and no_table, tabletype same as for L{LRparser} """ self.lex = Lexer(tokenize) operators = None if self.lex.__dict__.has_key("operators"): operators = self.lex.operators if type(grammar) is StringType: grammar = self.parse_grammar(grammar,{'locals':locals()}) LRparser.__init__(self,grammar,table,no_table,tabletype,operators,noconflicts,expect) if (self.Log.noconflicts and ((self.Log.conflicts.has_key('sr') and len(self.Log.conflicts['sr'])!= self.Log.expect) or self.Log.conflicts.has_key('rr'))): print "LR conflicts %s" %self.Log.conflicts print """If it is Ok, set expect to the number of conflicts and build table again""" def input(self,str=None,context=None): """ Reads from stdin or string and retuns parsed result @param str: String to be parsed. If not given, reads from C{stdin}. @param context: some initial computational context @return: a tuple C{(parsed result,context)} or only the C{parsed result} """ if str: self.tokens = self.lex.scan(str) else: print "Input: ", self.tokens = self.lex.readscan() self.context = context return self.parsing(self.tokens,self.context) def inputfile(self,FileName,context=None): """Reads input from file """ try: file = open(FileName,"r") except IOError: raise YappyError() return self.input(file.read(),context) def parse_tree(self): """To be defined using output""" pass def test(self): """A test for each class""" pass ######### Semantic Grammar Rules ############## def Reduction(fun,list,context=None): """Reduction function for semantic rules""" return apply(fun,[list,context]) def DefaultSemRule(list,context=None): """Default semantic rule""" return list[0] def EmptySemRule(list,context=None): return [] ######Parser for grammars ################## class Yappy_grammar(Yappy): """ A parser for grammar rules. See C{test()} for an example. """ def __init__(self,no_table=1, table='yappypar.tab'): grammar= grules([ ("G -> RULE G",self.GRule), ("G -> []",EmptySemRule), ("RULE -> ID rulesym MULTI ruleend",self.RULERule) , ("MULTI -> RHS rulesep MULTI",self.MULTIRule), ("MULTI -> RHS",self.MULTIRule), ("RHS -> []",EmptySemRule), #RHS->OPSEM not allowed; epsilon-rule ("RHS -> RH OPSEM",self.RHSRule), ("RH -> ID RH",self.RHRule), ("RH -> ID",self.RHRule), ("OPSEM -> []",self.OPSEMRule), ("OPSEM -> semsym ID csemsym",self.OPSEMRule),#OPSEM->OP not allowed ("OPSEM -> semsym ID OP csemsym",self.OPSEMRule), ("OP -> opsym OPV",self.OPRule), ("OPV -> ID ID ", self.OPVRule) ]) tokenize = [("\s+",""), ("->",lambda x: ("rulesym",x)), ("\|",lambda x: ("rulesep",x)), (";",lambda x: ("ruleend",x)), ("}}",lambda x: ("csemsym",x)), ("{{",lambda x: ("semsym",x)), ("//",lambda x: ("opsym",x)), (".*",lambda x: ("ID",x))] Yappy.__init__(self,tokenize,grammar,table,no_table) def OPVRule(self,arg,context): """ """ try: int(arg[0]) except ValueError: raise SemanticError("Precedence must be an integer: %s given" %arg[0]) if arg[1]!= 'left' and arg[1]!= 'right' and arg[1]!= 'noassoc': raise SemanticError("Associativity must be 'left' or 'right' or 'noassoc': %s\ given" %arg[1]) return (int(arg[0]),arg[1]) def OPRule(self,arg,context): return arg[1] def OPSEMRule(self,arg,context): if len(arg) == 4: return (arg[1],arg[2]) if len(arg) == 3: return arg[1] if len(arg) == 0: return 'DefaultSemRule' def RHRule(self,arg,context): if len(arg) == 1: return [arg[0]] if len(arg) == 2: return [arg[0]]+arg[1] def RHSRule(self,arg,context): return (arg[0],arg[1]) def MULTIRule(self,arg,context): if len(arg) == 1: return [arg[0]] else: return [arg[0]]+arg[2] def RULERule(self,arg,context): lhs=arg[0] def grule(self,l): if l == []: return (lhs,[],EmptySemRule) if type(l[1]) is TupleType: return (lhs,l[0],eval(l[1][0],globals(),context['locals']),l[1][1]) else: return (lhs,l[0],eval(l[1],globals(),context['locals'])) return map(lambda l:grule(self,l) ,arg[2]) def GRule(self,args,context): if context.has_key('rules'): context['rules']= args[0]+context['rules'] else: context['rules'] = args[0] return [] def test(self): st = """ reg -> reg + reg {{ DefaultSemRule// 200 left }} | reg reg {{ DefaultSemRule // 200 left }} | reg * {{ DefaultSemRule }} | ( reg ) {{DefaultSemRule}} | id {{DefaultSemRule}} ; reg -> ; a -> reg | reg ; """ self.input(st,{'locals':locals()}) return self.context['rules'] class Stack: """ A simple class to implement stacks""" def __init__(self, start=[]): """Reverse initial stack objects""" self.stack = [] for x in start: self.push(x) self.stack.reverse() def push(self, object): self.stack = [object] + self.stack def pop(self): if not self.stack: raise 'stack underflow' top, self.stack = self.stack[0], self.stack[1:] return top def top(self): """ Returns top of stack (not poping it)""" if not self.stack: raise 'stack underflow' return self.stack[0] def empty(self): """ Tests if stack is empty""" return not self.stack def popall(self): """ Empties stack""" self.stack=[] def __repr__(self): return '[Stack:%s]' % self.stack def __cmp__(self, other): return cmp(self.stack, other.stack) def __len__(self): return len(self.stack) def __add__(self, other): return Stack(self.stack + other.stack) def __mul__(self, reps): return Stack(self.stack * reps) def __getitem__(self, offset): return self.stack[offset] def __getslice__(self, low, high): return Stack(self.stack[low : high]) def __getattr__(self, name): return getattr(self.stack, name)