Back to index

enigmail  1.4.3
Public Member Functions | Public Attributes | Private Member Functions
ply.yacc.Grammar Class Reference

List of all members.

Public Member Functions

def __init__
def __len__
def __getitem__
def set_precedence
def add_production
def set_start
def find_unreachable
def infinite_cycles
def undefined_symbols
def unused_terminals
def unused_rules
def unused_precedence
def compute_first
def compute_follow
def build_lritems

Public Attributes

 Productions
 Prodnames
 Prodmap
 Terminals
 Nonterminals
 First
 Follow
 Precedence
 UsedPrecedence
 Start

Private Member Functions

def _first

Detailed Description

Definition at line 1314 of file yacc.py.


Constructor & Destructor Documentation

def ply.yacc.Grammar.__init__ (   self,
  terminals 
)

Definition at line 1315 of file yacc.py.

01315 
01316     def __init__(self,terminals):
01317         self.Productions  = [None]  # A list of all of the productions.  The first
01318                                     # entry is always reserved for the purpose of
01319                                     # building an augmented grammar
01320 
01321         self.Prodnames    = { }     # A dictionary mapping the names of nonterminals to a list of all
01322                                     # productions of that nonterminal.
01323 
01324         self.Prodmap      = { }     # A dictionary that is only used to detect duplicate
01325                                     # productions.
01326 
01327         self.Terminals    = { }     # A dictionary mapping the names of terminal symbols to a
01328                                     # list of the rules where they are used.
01329 
01330         for term in terminals:
01331             self.Terminals[term] = []
01332 
01333         self.Terminals['error'] = []
01334 
01335         self.Nonterminals = { }     # A dictionary mapping names of nonterminals to a list
01336                                     # of rule numbers where they are used.
01337 
01338         self.First        = { }     # A dictionary of precomputed FIRST(x) symbols
01339 
01340         self.Follow       = { }     # A dictionary of precomputed FOLLOW(x) symbols
01341 
01342         self.Precedence   = { }     # Precedence rules for each terminal. Contains tuples of the
01343                                     # form ('right',level) or ('nonassoc', level) or ('left',level)
01344 
01345         self.UsedPrecedence = { }   # Precedence rules that were actually used by the grammer.
01346                                     # This is only used to provide error checking and to generate
01347                                     # a warning about unused precedence rules.
01348 
01349         self.Start = None           # Starting symbol for the grammar
01350 


Member Function Documentation

def ply.yacc.Grammar.__getitem__ (   self,
  index 
)

Definition at line 1354 of file yacc.py.

01354 
01355     def __getitem__(self,index):
01356         return self.Productions[index]

def ply.yacc.Grammar.__len__ (   self)

Definition at line 1351 of file yacc.py.

01351 
01352     def __len__(self):
01353         return len(self.Productions)

def ply.yacc.Grammar._first (   self,
  beta 
) [private]

Definition at line 1647 of file yacc.py.

01647 
01648     def _first(self,beta):
01649 
01650         # We are computing First(x1,x2,x3,...,xn)
01651         result = [ ]
01652         for x in beta:
01653             x_produces_empty = 0
01654 
01655             # Add all the non-<empty> symbols of First[x] to the result.
01656             for f in self.First[x]:
01657                 if f == '<empty>':
01658                     x_produces_empty = 1
01659                 else:
01660                     if f not in result: result.append(f)
01661 
01662             if x_produces_empty:
01663                 # We have to consider the next x in beta,
01664                 # i.e. stay in the loop.
01665                 pass
01666             else:
01667                 # We don't have to consider any further symbols in beta.
01668                 break
01669         else:
01670             # There was no 'break' from the loop,
01671             # so x_produces_empty was true for all x in beta,
01672             # so beta produces empty as well.
01673             result.append('<empty>')
01674 
01675         return result

Here is the caller graph for this function:

def ply.yacc.Grammar.add_production (   self,
  prodname,
  syms,
  func = None,
  file = '',
  line = 0 
)

Definition at line 1390 of file yacc.py.

01390 
01391     def add_production(self,prodname,syms,func=None,file='',line=0):
01392 
01393         if prodname in self.Terminals:
01394             raise GrammarError("%s:%d: Illegal rule name '%s'. Already defined as a token" % (file,line,prodname))
01395         if prodname == 'error':
01396             raise GrammarError("%s:%d: Illegal rule name '%s'. error is a reserved word" % (file,line,prodname))
01397         if not _is_identifier.match(prodname):
01398             raise GrammarError("%s:%d: Illegal rule name '%s'" % (file,line,prodname))
01399 
01400         # Look for literal tokens 
01401         for n,s in enumerate(syms):
01402             if s[0] in "'\"":
01403                  try:
01404                      c = eval(s)
01405                      if (len(c) > 1):
01406                           raise GrammarError("%s:%d: Literal token %s in rule '%s' may only be a single character" % (file,line,s, prodname))
01407                      if not c in self.Terminals:
01408                           self.Terminals[c] = []
01409                      syms[n] = c
01410                      continue
01411                  except SyntaxError:
01412                      pass
01413             if not _is_identifier.match(s) and s != '%prec':
01414                 raise GrammarError("%s:%d: Illegal name '%s' in rule '%s'" % (file,line,s, prodname))
01415         
01416         # Determine the precedence level
01417         if '%prec' in syms:
01418             if syms[-1] == '%prec':
01419                 raise GrammarError("%s:%d: Syntax error. Nothing follows %%prec" % (file,line))
01420             if syms[-2] != '%prec':
01421                 raise GrammarError("%s:%d: Syntax error. %%prec can only appear at the end of a grammar rule" % (file,line))
01422             precname = syms[-1]
01423             prodprec = self.Precedence.get(precname,None)
01424             if not prodprec:
01425                 raise GrammarError("%s:%d: Nothing known about the precedence of '%s'" % (file,line,precname))
01426             else:
01427                 self.UsedPrecedence[precname] = 1
01428             del syms[-2:]     # Drop %prec from the rule
01429         else:
01430             # If no %prec, precedence is determined by the rightmost terminal symbol
01431             precname = rightmost_terminal(syms,self.Terminals)
01432             prodprec = self.Precedence.get(precname,('right',0)) 
01433             
01434         # See if the rule is already in the rulemap
01435         map = "%s -> %s" % (prodname,syms)
01436         if map in self.Prodmap:
01437             m = self.Prodmap[map]
01438             raise GrammarError("%s:%d: Duplicate rule %s. " % (file,line, m) +
01439                                "Previous definition at %s:%d" % (m.file, m.line))
01440 
01441         # From this point on, everything is valid.  Create a new Production instance
01442         pnumber  = len(self.Productions)
01443         if not prodname in self.Nonterminals:
01444             self.Nonterminals[prodname] = [ ]
01445 
01446         # Add the production number to Terminals and Nonterminals
01447         for t in syms:
01448             if t in self.Terminals:
01449                 self.Terminals[t].append(pnumber)
01450             else:
01451                 if not t in self.Nonterminals:
01452                     self.Nonterminals[t] = [ ]
01453                 self.Nonterminals[t].append(pnumber)
01454 
01455         # Create a production and add it to the list of productions
01456         p = Production(pnumber,prodname,syms,prodprec,func,file,line)
01457         self.Productions.append(p)
01458         self.Prodmap[map] = p
01459 
01460         # Add to the global productions list
01461         try:
01462             self.Prodnames[prodname].append(p)
01463         except KeyError:
01464             self.Prodnames[prodname] = [ p ]
01465         return 0

Here is the call graph for this function:

Definition at line 1777 of file yacc.py.

01777 
01778     def build_lritems(self):
01779         for p in self.Productions:
01780             lastlri = p
01781             i = 0
01782             lr_items = []
01783             while 1:
01784                 if i > len(p):
01785                     lri = None
01786                 else:
01787                     lri = LRItem(p,i)
01788                     # Precompute the list of productions immediately following
01789                     try:
01790                         lri.lr_after = self.Prodnames[lri.prod[i+1]]
01791                     except (IndexError,KeyError):
01792                         lri.lr_after = []
01793                     try:
01794                         lri.lr_before = lri.prod[i-1]
01795                     except IndexError:
01796                         lri.lr_before = None
01797 
01798                 lastlri.lr_next = lri
01799                 if not lri: break
01800                 lr_items.append(lri)
01801                 lastlri = lri
01802                 i += 1
01803             p.lr_items = lr_items
01804 
01805 # -----------------------------------------------------------------------------
01806 #                            == Class LRTable ==
01807 #
01808 # This basic class represents a basic table of LR parsing information.  
01809 # Methods for generating the tables are not defined here.  They are defined
01810 # in the derived class LRGeneratedTable.
01811 # -----------------------------------------------------------------------------

Definition at line 1681 of file yacc.py.

01681 
01682     def compute_first(self):
01683         if self.First:
01684             return self.First
01685 
01686         # Terminals:
01687         for t in self.Terminals:
01688             self.First[t] = [t]
01689 
01690         self.First['$end'] = ['$end']
01691 
01692         # Nonterminals:
01693 
01694         # Initialize to the empty set:
01695         for n in self.Nonterminals:
01696             self.First[n] = []
01697 
01698         # Then propagate symbols until no change:
01699         while 1:
01700             some_change = 0
01701             for n in self.Nonterminals:
01702                 for p in self.Prodnames[n]:
01703                     for f in self._first(p.prod):
01704                         if f not in self.First[n]:
01705                             self.First[n].append( f )
01706                             some_change = 1
01707             if not some_change:
01708                 break
01709         
01710         return self.First

Here is the call graph for this function:

Here is the caller graph for this function:

def ply.yacc.Grammar.compute_follow (   self,
  start = None 
)

Definition at line 1718 of file yacc.py.

01718 
01719     def compute_follow(self,start=None):
01720         # If already computed, return the result
01721         if self.Follow:
01722             return self.Follow
01723 
01724         # If first sets not computed yet, do that first.
01725         if not self.First:
01726             self.compute_first()
01727 
01728         # Add '$end' to the follow list of the start symbol
01729         for k in self.Nonterminals:
01730             self.Follow[k] = [ ]
01731 
01732         if not start:
01733             start = self.Productions[1].name
01734 
01735         self.Follow[start] = [ '$end' ]
01736 
01737         while 1:
01738             didadd = 0
01739             for p in self.Productions[1:]:
01740                 # Here is the production set
01741                 for i in range(len(p.prod)):
01742                     B = p.prod[i]
01743                     if B in self.Nonterminals:
01744                         # Okay. We got a non-terminal in a production
01745                         fst = self._first(p.prod[i+1:])
01746                         hasempty = 0
01747                         for f in fst:
01748                             if f != '<empty>' and f not in self.Follow[B]:
01749                                 self.Follow[B].append(f)
01750                                 didadd = 1
01751                             if f == '<empty>':
01752                                 hasempty = 1
01753                         if hasempty or i == (len(p.prod)-1):
01754                             # Add elements of follow(a) to follow(b)
01755                             for f in self.Follow[p.name]:
01756                                 if f not in self.Follow[B]:
01757                                     self.Follow[B].append(f)
01758                                     didadd = 1
01759             if not didadd: break
01760         return self.Follow
01761 

Here is the call graph for this function:

Definition at line 1489 of file yacc.py.

01489 
01490     def find_unreachable(self):
01491         
01492         # Mark all symbols that are reachable from a symbol s
01493         def mark_reachable_from(s):
01494             if reachable[s]:
01495                 # We've already reached symbol s.
01496                 return
01497             reachable[s] = 1
01498             for p in self.Prodnames.get(s,[]):
01499                 for r in p.prod:
01500                     mark_reachable_from(r)
01501 
01502         reachable   = { }
01503         for s in list(self.Terminals) + list(self.Nonterminals):
01504             reachable[s] = 0
01505 
01506         mark_reachable_from( self.Productions[0].prod[0] )
01507 
01508         return [s for s in list(self.Nonterminals)
01509                         if not reachable[s]]
    

Definition at line 1518 of file yacc.py.

01518 
01519     def infinite_cycles(self):
01520         terminates = {}
01521 
01522         # Terminals:
01523         for t in self.Terminals:
01524             terminates[t] = 1
01525 
01526         terminates['$end'] = 1
01527 
01528         # Nonterminals:
01529 
01530         # Initialize to false:
01531         for n in self.Nonterminals:
01532             terminates[n] = 0
01533 
01534         # Then propagate termination until no change:
01535         while 1:
01536             some_change = 0
01537             for (n,pl) in self.Prodnames.items():
01538                 # Nonterminal n terminates iff any of its productions terminates.
01539                 for p in pl:
01540                     # Production p terminates iff all of its rhs symbols terminate.
01541                     for s in p.prod:
01542                         if not terminates[s]:
01543                             # The symbol s does not terminate,
01544                             # so production p does not terminate.
01545                             p_terminates = 0
01546                             break
01547                     else:
01548                         # didn't break from the loop,
01549                         # so every symbol s terminates
01550                         # so production p terminates.
01551                         p_terminates = 1
01552 
01553                     if p_terminates:
01554                         # symbol n terminates!
01555                         if not terminates[n]:
01556                             terminates[n] = 1
01557                             some_change = 1
01558                         # Don't need to consider any more productions for this n.
01559                         break
01560 
01561             if not some_change:
01562                 break
01563 
01564         infinite = []
01565         for (s,term) in terminates.items():
01566             if not term:
01567                 if not s in self.Prodnames and not s in self.Terminals and s != 'error':
01568                     # s is used-but-not-defined, and we've already warned of that,
01569                     # so it would be overkill to say that it's also non-terminating.
01570                     pass
01571                 else:
01572                     infinite.append(s)
01573 
01574         return infinite
01575 

def ply.yacc.Grammar.set_precedence (   self,
  term,
  assoc,
  level 
)

Definition at line 1365 of file yacc.py.

01365 
01366     def set_precedence(self,term,assoc,level):
01367         assert self.Productions == [None],"Must call set_precedence() before add_production()"
01368         if term in self.Precedence:
01369             raise GrammarError("Precedence already specified for terminal '%s'" % term)
01370         if assoc not in ['left','right','nonassoc']:
01371             raise GrammarError("Associativity must be one of 'left','right', or 'nonassoc'")
01372         self.Precedence[term] = (assoc,level)
 
def ply.yacc.Grammar.set_start (   self,
  start = None 
)

Definition at line 1473 of file yacc.py.

01473 
01474     def set_start(self,start=None):
01475         if not start:
01476             start = self.Productions[1].name
01477         if start not in self.Nonterminals:
01478             raise GrammarError("start symbol %s undefined" % start)
01479         self.Productions[0] = Production(0,"S'",[start])
01480         self.Nonterminals[start].append(0)
01481         self.Start = start

Definition at line 1583 of file yacc.py.

01583 
01584     def undefined_symbols(self):
01585         result = []
01586         for p in self.Productions:
01587             if not p: continue
01588 
01589             for s in p.prod:
01590                 if not s in self.Prodnames and not s in self.Terminals and s != 'error':
01591                     result.append((s,p))
01592         return result

Definition at line 1631 of file yacc.py.

01631 
01632     def unused_precedence(self):
01633         unused = []
01634         for termname in self.Precedence:
01635             if not (termname in self.Terminals or termname in self.UsedPrecedence):
01636                 unused.append((termname,self.Precedence[termname][0]))
01637                 
01638         return unused

Definition at line 1614 of file yacc.py.

01614 
01615     def unused_rules(self):
01616         unused_prod = []
01617         for s,v in self.Nonterminals.items():
01618             if not v:
01619                 p = self.Prodnames[s][0]
01620                 unused_prod.append(p)
01621         return unused_prod

Definition at line 1599 of file yacc.py.

01599 
01600     def unused_terminals(self):
01601         unused_tok = []
01602         for s,v in self.Terminals.items():
01603             if s != 'error' and not v:
01604                 unused_tok.append(s)
01605 
01606         return unused_tok


Member Data Documentation

Definition at line 1337 of file yacc.py.

Definition at line 1339 of file yacc.py.

Definition at line 1334 of file yacc.py.

Definition at line 1341 of file yacc.py.

Definition at line 1323 of file yacc.py.

Definition at line 1320 of file yacc.py.

Definition at line 1316 of file yacc.py.

Definition at line 1348 of file yacc.py.

Definition at line 1326 of file yacc.py.

Definition at line 1344 of file yacc.py.


The documentation for this class was generated from the following file: