Parser.py

#-------------------------------------------------------------------------
#Parser.py -- ATG file parser
#Compiler Generator Coco/R,
#Copyright (c) 1990, 2004 Hanspeter Moessenboeck, University of Linz
#extended by M. Loeberbauer & A. Woess, Univ. of Linz
#ported from Java to Python by Ronald Longo
#
#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, 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.,
#59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
#
#As an exception, it is allowed to write an extension of Coco/R that is
#used as a plugin in non-free software.
#
#If not otherwise stated, any source code generated by Coco/R (other than
#Coco/R itself) does not fall under the GNU General Public License.
#-------------------------------------------------------------------------*/

from Errors import Errors
from CharClass import CharClass
from Core import Node
from Core import DFA
from Core import Graph
from Core import Symbol
from Core import Tab
from Core import Comment
from DriverGen import DriverGen
from ParserGen import ParserGen


import sys

from Scanner import Token
from Scanner import Scanner
from Scanner import Position

class Parser( object ):
   _EOF = 0
   _ident = 1
   _number = 2
   _string = 3
   _badString = 4
   # terminals
   EOF_SYM = 0
   ident_Sym = 1
   number_Sym = 2
   string_Sym = 3
   badString_Sym = 4
   COMPILER_Sym = 5
   IGNORECASE_Sym = 6
   CHARACTERS_Sym = 7
   TOKENS_Sym = 8
   NAMES_Sym = 9
   PRAGMAS_Sym = 10
   COMMENTS_Sym = 11
   FROM_Sym = 12
   TO_Sym = 13
   NESTED_Sym = 14
   IGNORE_Sym = 15
   PRODUCTIONS_Sym = 16
   equal_Sym = 17
   point_Sym = 18
   END_Sym = 19
   plus_Sym = 20
   minus_Sym = 21
   pointpoint_Sym = 22
   ANY_Sym = 23
   CHR_Sym = 24
   lparen_Sym = 25
   rparen_Sym = 26
   less_Sym = 27
   uparrow_Sym = 28
   out_Sym = 29
   greater_Sym = 30
   comma_Sym = 31
   lesspoint_Sym = 32
   pointgreater_Sym = 33
   bar_Sym = 34
   WEAK_Sym = 35
   lbrack_Sym = 36
   rbrack_Sym = 37
   lbrace_Sym = 38
   rbrace_Sym = 39
   SYNC_Sym = 40
   IF_Sym = 41
   CONTEXT_Sym = 42
   lparenpoint_Sym = 43
   pointrparen_Sym = 44
   from_Sym = 45
   import_Sym = 46
   star_Sym = 47
   NOT_SYM = 48
   # pragmas
   ddtSym_Sym = 49

   maxT = 48
   _ddtSym = 49

   T          = True
   x          = False
   minErrDist = 2

   id          = 0
   str         = 1

#-------------------------------------------------------------------------


   def __init__( self ):
      self.scanner     = None
      self.token       = None           # last recognized token
      self.la          = None           # lookahead token
      self.genScanner  = False
      self.tokenString = ''             # used in declarations of literal tokens
      self.noString    = '-none-'       # used in declarations of literal tokens
      self.errDist     = Parser.minErrDist

   def getParsingPos( self ):
      return self.la.line, self.la.col

   def SynErr( self, errNum ):
      if self.errDist >= Parser.minErrDist:
         Errors.SynErr( errNum )

      self.errDist = 0

   def SemErr( self, msg ):
      if self.errDist >= Parser.minErrDist:
         Errors.SemErr( msg )

      self.errDist = 0

   def Warning( self, msg ):
      if self.errDist >= Parser.minErrDist:
         Errors.Warn( msg )

      self.errDist = 0

   def Successful( self ):
      return Errors.count == 0;

   def LexString( self ):
      return self.token.val

   def LookAheadString( self ):
      return self.la.val

   def Get( self ):
      while True:
         self.token = self.la
         self.la = self.scanner.Scan( )
         if self.la.kind <= Parser.maxT:
            self.errDist += 1
            break
         if self.la.kind == Scanner.ddtSym_Sym:
            self.la.val = '-' + str(self.la.val[1:])
            Tab.parseArgs( [ self.la.val, 'filler1', 'filler2' ] ) 

         self.la = self.token

   def Expect( self, n ):
      if self.la.kind == n:
         self.Get( )
      else:
         self.SynErr( n )

   def StartOf( self, s ):
      return self.set[s][self.la.kind]

   def ExpectWeak( self, n, follow ):
      if self.la.kind == n:
         self.Get( )
      else:
         self.SynErr( n )
         while not self.StartOf(follow):
            self.Get( )

   def WeakSeparator( self, n, syFol, repFol ):
      s = [ False for i in xrange( Parser.maxT+1 ) ]
      if self.la.kind == n:
         self.Get( )
         return True
      elif self.StartOf(repFol):
         return False
      else:
         for i in xrange( Parser.maxT ):
            s[i] = self.set[syFol][i] or self.set[repFol][i] or self.set[0][i]
         self.SynErr( n )
         while not s[self.la.kind]:
            self.Get( )
         return self.StartOf( syFol )

   def Coco( self ):
      g    = Graph( )
      g1   = Graph( )
      g2   = Graph( )
      s    = set( )    
      if (self.la.kind == Scanner.from_Sym or self.la.kind == Scanner.import_Sym):
         ParserGen.usingPos = self.Imports()
      self.Expect(Scanner.COMPILER_Sym)
      self.genScanner = True
      Tab.ignored = set( )       
      self.Expect(Scanner.ident_Sym)
      gramName = self.token.val
      beg = self.la.pos 
      while self.StartOf(1):
         self.Get()

      Tab.semDeclPos = Position(self.scanner.buffer, beg, self.la.pos - beg, 0) 
      if (self.la.kind == Scanner.IGNORECASE_Sym):
         self.Get( )
         DFA.ignoreCase = True 
      if (self.la.kind == Scanner.CHARACTERS_Sym):
         self.Get( )
         while self.la.kind == Scanner.ident_Sym:
            self.SetDecl()

      if (self.la.kind == Scanner.TOKENS_Sym):
         self.Get( )
         while self.la.kind == Scanner.ident_Sym or self.la.kind == Scanner.string_Sym:
            self.TokenDecl(Node.t)

      if (self.la.kind == Scanner.NAMES_Sym):
         self.Get( )
         while self.la.kind == Scanner.ident_Sym:
            self.NameDecl()

      if (self.la.kind == Scanner.PRAGMAS_Sym):
         self.Get( )
         while self.la.kind == Scanner.ident_Sym or self.la.kind == Scanner.string_Sym:
            self.TokenDecl(Node.pr)

      while self.la.kind == Scanner.COMMENTS_Sym:
         self.Get( )
         nested = False 
         self.Expect(Scanner.FROM_Sym)
         g1 = self.TokenExpr()
         self.Expect(Scanner.TO_Sym)
         g2 = self.TokenExpr()
         if (self.la.kind == Scanner.NESTED_Sym):
            self.Get( )
            nested = True 
         Comment(g1.l, g2.l, nested) 

      while self.la.kind == Scanner.IGNORE_Sym:
         self.Get( )
         s = self.Set()
         Tab.ignored |= s # set union 

      while not (self.la.kind == Scanner.EOF_SYM or self.la.kind == Scanner.PRODUCTIONS_Sym):
         self.SynErr(49)
         self.Get()
      self.Expect(Scanner.PRODUCTIONS_Sym)
      if self.genScanner:
         DFA.MakeDeterministic()
      Graph.DeleteNodes()          
      while self.la.kind == Scanner.ident_Sym:
         self.Get( )
         sym = Symbol.Find(self.token.val)
         undef = (sym is None)
         if undef:
            sym = Symbol(Node.nt, self.token.val, self.token.line)
         else:
            if sym.typ == Node.nt:
               if sym.graph is not None:
                  self.SemErr("name declared twice")
            else:
               self.SemErr("this symbol kind not allowed on left side of production")
            sym.line = self.token.line
         noAttrs = (sym.attrPos is None)
         sym.attrPos = None
         noRet = (sym.retVar is None)
         sym.retVar = None 
         if (self.la.kind == Scanner.less_Sym or self.la.kind == Scanner.lesspoint_Sym):
            self.AttrDecl(sym)
         if not undef:
            if noAttrs != (sym.attrPos is None) or (noRet != (sym.retVar is None)):
               self.SemErr("attribute mismatch between declaration and use of this symbol") 
         if (self.la.kind == Scanner.lparenpoint_Sym):
            sym.semPos = self.SemText()
         self.ExpectWeak(Scanner.equal_Sym, 2)
         g = self.Expression()
         sym.graph = g.l
         Graph.Finish(g) 
         self.ExpectWeak(Scanner.point_Sym, 3)

      self.Expect(Scanner.END_Sym)
      self.Expect(Scanner.ident_Sym)
      if gramName != self.token.val:
         self.SemErr("name does not match grammar name")
      Tab.gramSy = Symbol.Find(gramName)
      if Tab.gramSy is None:
         self.SemErr("missing production for grammar name")
      else:
         sym = Tab.gramSy
         if sym.attrPos is not None:
            self.SemErr("grammar symbol must not have attributes")
      Tab.noSym = Symbol(Node.t, "???", 0) #noSym gets highest number
      Tab.SetupAnys()
      Tab.RenumberPragmas()
      if Tab.ddt[2]:
         Node.PrintNodes()
      if Errors.count == 0:
         sys.stdout.write( "checking\n" )
         Tab.CompSymbolSets()
         if Tab.ddt[7]:
            Tab.XRef()
         if Tab.GrammarOk():
            if not Tab.ddt[9]:
               sys.stdout.write( "parser" )
               ParserGen.WriteParser(Tab.ddt[10])
               if self.genScanner:
                  sys.stdout.write( " + scanner" )
                  DFA.WriteScanner(Tab.ddt[10])
                  if Tab.ddt[0]:
                     DFA.PrintStates()
               if Tab.ddt[11]:
                  sys.stdout.write( " + driver" )
                  DriverGen.WriteDriver()
               sys.stdout.write( " generated\n" )
            if Tab.ddt[8]:
               ParserGen.WriteStatistics()
      if Tab.ddt[6]:
         Tab.PrintSymbolTable()      
      self.Expect(Scanner.point_Sym)

   def Imports( self ):
      beg = None
      pos = None 
      if (self.la.kind == Scanner.from_Sym):
         self.Get( )
         beg = self.token.pos 
         self.Expect(Scanner.ident_Sym)
         while self.la.kind == Scanner.point_Sym:
            self.Get( )
            self.Expect(Scanner.ident_Sym)

      self.Expect(Scanner.import_Sym)
      if beg == None:
         beg = self.token.pos 
      if self.la.kind == Scanner.ident_Sym:
         self.Get( )
         while self.la.kind == Scanner.point_Sym:
            self.Get( )
            self.Expect(Scanner.ident_Sym)

         while self.la.kind == Scanner.comma_Sym:
            self.Get( )
            self.Expect(Scanner.ident_Sym)
            while self.la.kind == Scanner.point_Sym:
               self.Get( )
               self.Expect(Scanner.ident_Sym)


      elif self.la.kind == Scanner.lparen_Sym:
         self.Get( )
         self.Expect(Scanner.ident_Sym)
         while self.la.kind == Scanner.point_Sym:
            self.Get( )
            self.Expect(Scanner.ident_Sym)

         while self.la.kind == Scanner.comma_Sym:
            self.Get( )
            self.Expect(Scanner.ident_Sym)
            while self.la.kind == Scanner.point_Sym:
               self.Get( )
               self.Expect(Scanner.ident_Sym)


         self.Expect(Scanner.rparen_Sym)
      elif self.la.kind == Scanner.star_Sym:
         self.Get( )
      else:
         self.SynErr(50)
      while self.la.kind == Scanner.from_Sym or self.la.kind == Scanner.import_Sym:
         if (self.la.kind == Scanner.from_Sym):
            self.Get( )
            self.Expect(Scanner.ident_Sym)
            while self.la.kind == Scanner.point_Sym:
               self.Get( )
               self.Expect(Scanner.ident_Sym)

         self.Get( )
         if self.la.kind == Scanner.ident_Sym:
            self.Get( )
            while self.la.kind == Scanner.point_Sym:
               self.Get( )
               self.Expect(Scanner.ident_Sym)

            while self.la.kind == Scanner.comma_Sym:
               self.Get( )
               self.Expect(Scanner.ident_Sym)
               while self.la.kind == Scanner.point_Sym:
                  self.Get( )
                  self.Expect(Scanner.ident_Sym)


         elif self.la.kind == Scanner.lparen_Sym:
            self.Get( )
            self.Expect(Scanner.ident_Sym)
            while self.la.kind == Scanner.point_Sym:
               self.Get( )
               self.Expect(Scanner.ident_Sym)

            while self.la.kind == Scanner.comma_Sym:
               self.Get( )
               self.Expect(Scanner.ident_Sym)
               while self.la.kind == Scanner.point_Sym:
                  self.Get( )
                  self.Expect(Scanner.ident_Sym)


            self.Expect(Scanner.rparen_Sym)
         else:
            self.SynErr(51)

      end = self.la.pos
      pos = Position( self.scanner.buffer, beg, end - beg, 0 ) 
      return pos

   def SetDecl( self ):
      self.Expect(Scanner.ident_Sym)
      name = self.token.val
      c = CharClass.Find(name)
      if c is not None:
         self.SemErr("name declared twice") 
      self.Expect(Scanner.equal_Sym)
      s = self.Set()
      if len(s) == 0:
         self.SemErr("character set must not be empty")
      c = CharClass(name, s) 
      self.Expect(Scanner.point_Sym)

   def TokenDecl( self, typ ):
      s = self.Sym()
      name,kind = s
      sym = Symbol.Find(name)
      if sym is not None:
         self.SemErr("name declared twice")
      else:
         sym = Symbol(typ, name, self.token.line)
         sym.tokenKind = Symbol.fixedToken
      self.tokenString = None 
      while not (self.StartOf(4)):
         self.SynErr(52)
         self.Get()
      if self.la.kind == Scanner.equal_Sym:
         self.Get( )
         g = self.TokenExpr()
         self.Expect(Scanner.point_Sym)
         if kind == self.str:
            self.SemErr("a literal must not be declared with a structure")
         Graph.Finish(g)
         if (self.tokenString is None) or (self.tokenString == self.noString):
            DFA.ConvertToStates(g.l, sym)
         else:   # TokenExpr is a single string
            if Tab.literals.get(self.tokenString) is not None:
               self.SemErr("token string declared twice")
            Tab.literals[self.tokenString] = sym
            DFA.MatchLiteral(self.tokenString, sym)
            
      elif self.StartOf(5):
         if kind == self.id:
            genScanner = False
         else:
            DFA.MatchLiteral(sym.name, sym) 
      else:
         self.SynErr(53)
      if (self.la.kind == Scanner.lparenpoint_Sym):
         sym.semPos = self.SemText()
         if typ != Node.pr:
            self.SemErr("semantic action not allowed here") 

   def NameDecl( self ):
      self.Expect(Scanner.ident_Sym)
      alias = self.token.val 
      self.Expect(Scanner.equal_Sym)
      if self.la.kind == Scanner.ident_Sym:
         self.Get( )
      elif self.la.kind == Scanner.string_Sym:
         self.Get( )
      else:
         self.SynErr(54)
      Tab.NewName(alias, self.token.val) 
      self.Expect(Scanner.point_Sym)

   def TokenExpr( self ):
      g = self.TokenTerm()
      first = True 
      while self.WeakSeparator(Scanner.bar_Sym, 6, 7):
         g2 = self.TokenTerm()
         if first:
            Graph.MakeFirstAlt(g)
            first = False
         Graph.MakeAlternative(g, g2) 

      return g

   def Set( self ):
      s = self.SimSet()
      while self.la.kind == Scanner.plus_Sym or self.la.kind == Scanner.minus_Sym:
         if self.la.kind == Scanner.plus_Sym:
            self.Get( )
            s2 = self.SimSet()
            s |= s2 
         else:
            self.Get( )
            s2 = self.SimSet()
            s -= s2 

      return s

   def AttrDecl( self, sym ):
      if self.la.kind == Scanner.less_Sym:
         self.Get( )
         if self.la.kind == Scanner.uparrow_Sym or self.la.kind == Scanner.out_Sym:
            if self.la.kind == Scanner.uparrow_Sym:
               self.Get( )
            elif self.la.kind == Scanner.out_Sym:
               self.Get( )
            else:
               self.SynErr(55)
            self.Expect(Scanner.ident_Sym)
            sym.retVar = self.token.val     
            if self.la.kind == Scanner.greater_Sym:
               self.Get( )
            elif self.la.kind == Scanner.comma_Sym:
               self.Get( )
               beg = self.la.pos
               col = self.la.col               
               while self.StartOf(8):
                  if self.StartOf(9):
                     self.Get()
                  else:
                     self.Get( )
                     self.SemErr("bad string in attributes") 

               self.Expect(Scanner.greater_Sym)
               if self.token.pos > beg:
                  sym.attrPos = Position( self.scanner.buffer, beg, self.token.pos - beg, col )   
            else:
               self.SynErr(56)
         elif self.StartOf(10):
            beg = self.la.pos
            col = self.la.col 
            while self.StartOf(11):
               if self.StartOf(12):
                  self.Get()
               else:
                  self.Get( )
                  self.SemErr("bad string in attributes") 

            self.Expect(Scanner.greater_Sym)
            if self.token.pos > beg:
               sym.attrPos = Position( self.scanner.buffer, beg, self.token.pos - beg, col )   
         else:
            self.SynErr(57)
      elif self.la.kind == Scanner.lesspoint_Sym:
         self.Get( )
         if self.la.kind == Scanner.uparrow_Sym or self.la.kind == Scanner.out_Sym:
            if self.la.kind == Scanner.uparrow_Sym:
               self.Get( )
            elif self.la.kind == Scanner.out_Sym:
               self.Get( )
            else:
               self.SynErr(58)
            self.Expect(Scanner.ident_Sym)
            sym.retVar = self.token.val     
            if self.la.kind == Scanner.pointgreater_Sym:
               self.Get( )
            elif self.la.kind == Scanner.comma_Sym:
               self.Get( )
               beg = self.la.pos
               col = self.la.col               
               while self.StartOf(13):
                  if self.StartOf(14):
                     self.Get()
                  else:
                     self.Get( )
                     self.SemErr("bad string in attributes") 

               self.Expect(Scanner.pointgreater_Sym)
               if self.token.pos > beg:
                  sym.attrPos = Position( self.scanner.buffer, beg, self.token.pos - beg, col )   
            else:
               self.SynErr(59)
         elif self.StartOf(10):
            beg = self.la.pos
            col = self.la.col 
            while self.StartOf(15):
               if self.StartOf(16):
                  self.Get()
               else:
                  self.Get( )
                  self.SemErr("bad string in attributes") 

            self.Expect(Scanner.pointgreater_Sym)
            if self.token.pos > beg:
               sym.attrPos = Position( self.scanner.buffer, beg, self.token.pos - beg, col )   
         else:
            self.SynErr(60)
      else:
         self.SynErr(61)

   def SemText( self ):
      self.Expect(Scanner.lparenpoint_Sym)
      beg = self.la.pos
      col = self.la.col 
      while self.StartOf(17):
         if self.StartOf(18):
            self.Get()
         elif self.la.kind == Scanner.badString_Sym:
            self.Get( )
            self.SemErr( "bad string in semantic action" ) 
         else:
            self.Get( )
            self.SemErr( "missing end of previous semantic action") 

      self.Expect(Scanner.pointrparen_Sym)
      pos = Position(self.scanner.buffer, beg, self.token.pos - beg, col) 
      return pos

   def Expression( self ):
      g = self.Term()
      first = True   
      while self.WeakSeparator(Scanner.bar_Sym, 19, 20):
         g2 = self.Term()
         if first:
            Graph.MakeFirstAlt(g)
            first = False
         Graph.MakeAlternative(g, g2) 

      return g

   def SimSet( self ):
      n1 = 0
      n2 = 0
      name = '' 
      s = set( )
      mx = CharClass.charSetSize      
      if self.la.kind == Scanner.ident_Sym:
         self.Get( )
         c = CharClass.Find(self.token.val)
         if c is None:
            self.SemErr("undefined name")
         else:
            s |= c.set      
      elif self.la.kind == Scanner.string_Sym:
         name = self.String()
         if self.StartOf(21):
            for i in xrange( 0, len(name) ):
               if DFA.ignoreCase:
                  s.add(ord(name[i].lower()))
               else:
                  s.add(ord(name[i])) 
         elif self.la.kind == Scanner.pointpoint_Sym:
            if (len(name) != 1) or (ord(name[0]) > mx-1):
               self.SemErr("unacceptable character value")
            else:
               n1 = ord(name[0]) % mx
            if DFA.ignoreCase and (n1 >= ord('A')) and (n1 <= ord('Z')):
               n1 += 32 
            self.Get( )
            if self.la.kind == Scanner.string_Sym:
               name = self.String()
               if (len(name) != 1) or (ord(name[0]) > mx-1):
                  self.SemErr("unacceptable character value")
               else:
                  n2 = ord(name[0]) % mx
               if DFA.ignoreCase and ((n2 >= ord('A')) and (n2 <= ord('Z'))):
                  n2 += 32 
            elif self.la.kind == Scanner.CHR_Sym:
               n2 = self.SingleChar(mx)
            else:
               self.SynErr(62)
            for i in xrange( n1, n2+1 ):
               s.add(i)    
         else:
            self.SynErr(63)
      elif self.la.kind == Scanner.CHR_Sym:
         n1 = self.SingleChar(mx)
         s.add(n1) 
         if (self.la.kind == Scanner.pointpoint_Sym):
            self.Get( )
            if self.la.kind == Scanner.string_Sym:
               name = self.String()
               if (len(name) != 1) or (ord(name[0]) > mx-1):
                  self.SemErr("unacceptable character value")
               else:
                  n2 = ord(name[0]) % mx
               if DFA.ignoreCase and ((n2 >= ord('A')) and (n2 <= ord('Z'))):
                  n2 += 32  
            elif self.la.kind == Scanner.CHR_Sym:
               n2 = self.SingleChar(mx)
            else:
               self.SynErr(64)
            for i in xrange( n1, n2 ):
               s.add(i)                 
      elif self.la.kind == Scanner.ANY_Sym:
         self.Get( )
         s = set( )
         for num in xrange( 0, CharClass.charSetSize ):
            s.add(num)
         s.add('ANYCHAR')              
      else:
         self.SynErr(65)
      return s

   def String( self ):
      self.Expect(Scanner.string_Sym)
      name = self.token.val
      name = DFA.Unescape( name[ 1 : -1 ] ) 
      return name

   def SingleChar( self, mx ):
      n = 0 
      self.Expect(Scanner.CHR_Sym)
      self.Expect(Scanner.lparen_Sym)
      self.Expect(Scanner.number_Sym)
      n = int( self.token.val )
      if n > (mx - 1):
         self.SemErr("unacceptable character value")
      if DFA.ignoreCase and ((n >= ord('A')) and (n <= ord('Z'))):
         n += 32
      n %= mx                 
      self.Expect(Scanner.rparen_Sym)
      return n

   def Sym( self ):
      name = "???"
      kind = self.id 
      if self.la.kind == Scanner.ident_Sym:
         self.Get( )
         kind = self.id
         name = self.token.val 
      elif self.la.kind == Scanner.string_Sym:
         self.Get( )
         kind = self.str
         name = "\"" + self.token.val[ 1 : -1 ] + "\""
         if DFA.ignoreCase:
            name = name.lower()
         if name.find(' ') >= 0:
            self.SemErr("literal tokens must not contain blanks") 
      else:
         self.SynErr(66)
      s = name, kind  
      return s

   def Term( self ):
      rslv = None
      g = None          
      if self.StartOf(22):
         if (self.la.kind == Scanner.IF_Sym):
            rslv = Node(Node.rslv, None, self.la.line) 
            rslv.pos = self.Resolver()
            g = Graph(rslv) 
         g2 = self.Factor()
         if rslv is not None:
            Graph.MakeSequence(g, g2)
         else:
            g = g2 
         while self.StartOf(23):
            g2 = self.Factor()
            Graph.MakeSequence(g, g2) 

      elif self.StartOf(24):
         g = Graph(Node(Node.eps, None, 0)) 
      else:
         self.SynErr(67)
      if g is None:   # invalid start of Term
         g = Graph(Node(Node.eps, None, 0)) 
      return g

   def Resolver( self ):
      self.Expect(Scanner.IF_Sym)
      self.Expect(Scanner.lparen_Sym)
      beg = self.la.pos
      col = self.la.col 
      self.Condition()
      pos = Position(self.scanner.buffer, beg, self.token.pos - beg, col) 
      return pos

   def Factor( self ):
      weak = False
      g = None      
      if self.la.kind == Scanner.ident_Sym or self.la.kind == Scanner.string_Sym or self.la.kind == Scanner.WEAK_Sym:
         if (self.la.kind == Scanner.WEAK_Sym):
            self.Get( )
            weak = True   
         s = self.Sym()
         name,kind = s
         sym = Symbol.Find(name)
         if (sym is None) and (kind == self.str):
            sym = Tab.literals.get(name)
         undef = (sym is None)
         if undef:
            if kind == self.id:
               sym = Symbol(Node.nt, name, 0)  # forward nt
            elif self.genScanner:
               sym = Symbol(Node.t, name, self.token.line)
               DFA.MatchLiteral(sym.name, sym)
            else:  # undefined string in production
               self.SemErr("undefined string in production")
               sym = Tab.eofSy  # dummy
         typ = sym.typ
         if (typ != Node.t) and (typ != Node.nt):
            self.SemErr("this symbol kind is not allowed in a production")
         if weak:
            if typ == Node.t:
               typ = Node.wt
            else:
               self.SemErr("only terminals may be weak")
         p = Node(typ, sym, self.token.line)
         g = Graph(p) 
         if (self.la.kind == Scanner.less_Sym or self.la.kind == Scanner.lesspoint_Sym):
            self.Attribs(p)
            if kind != self.id:
               self.SemErr("a literal must not have attributes") 
         if undef:
            sym.attrPos = p.pos    # dummy
            sym.retVar = p.retVar  # AH - dummy
         elif ((p.pos is None) != (sym.attrPos is None)) or ((p.retVar is None) != (sym.retVar is None)):
            self.SemErr("attribute mismatch between declaration and use of this symbol") 
      elif self.la.kind == Scanner.lparen_Sym:
         self.Get( )
         g = self.Expression()
         self.Expect(Scanner.rparen_Sym)
      elif self.la.kind == Scanner.lbrack_Sym:
         self.Get( )
         g = self.Expression()
         self.Expect(Scanner.rbrack_Sym)
         Graph.MakeOption(g) 
      elif self.la.kind == Scanner.lbrace_Sym:
         self.Get( )
         g = self.Expression()
         self.Expect(Scanner.rbrace_Sym)
         Graph.MakeIteration(g) 
      elif self.la.kind == Scanner.lparenpoint_Sym:
         pos = self.SemText()
         p = Node(Node.sem, None, 0)
         p.pos = pos
         g = Graph(p) 
      elif self.la.kind == Scanner.ANY_Sym:
         self.Get( )
         p = Node(Node.any, None, 0)  # p.set is set in Tab.SetupAnys
         g = Graph(p) 
      elif self.la.kind == Scanner.SYNC_Sym:
         self.Get( )
         p = Node(Node.sync, None, 0)
         g = Graph(p) 
      else:
         self.SynErr(68)
      if g is None:   # invalid start of Factor
         g = Graph(Node(Node.eps, None, 0)) 
      return g

   def Attribs( self, n ):
      if self.la.kind == Scanner.less_Sym:
         self.Get( )
         if self.la.kind == Scanner.uparrow_Sym or self.la.kind == Scanner.out_Sym:
            if self.la.kind == Scanner.uparrow_Sym:
               self.Get( )
            elif self.la.kind == Scanner.out_Sym:
               self.Get( )
            else:
               self.SynErr(69)
            beg = self.la.pos 
            while self.StartOf(25):
               if self.StartOf(26):
                  self.Get()
               else:
                  self.Get( )
                  self.SemErr("bad string in attributes") 

            n.retVar = self.scanner.buffer.getString(beg, self.la.pos) 
            if self.la.kind == Scanner.greater_Sym:
               self.Get( )
            elif self.la.kind == Scanner.comma_Sym:
               self.Get( )
               beg = self.la.pos
               col = self.la.col 
               while self.StartOf(8):
                  if self.StartOf(9):
                     self.Get()
                  else:
                     self.Get( )
                     self.SemErr("bad string in attributes") 

               self.Expect(Scanner.greater_Sym)
               if self.token.pos > beg:
                  n.pos = Position(self.scanner.buffer, beg, self.token.pos - beg, col) 
            else:
               self.SynErr(70)
         elif self.StartOf(10):
            beg = self.la.pos
            col = self.la.col 
            while self.StartOf(11):
               if self.StartOf(12):
                  self.Get()
               else:
                  self.Get( )
                  self.SemErr("bad string in attributes") 

            self.Expect(Scanner.greater_Sym)
            if self.token.pos > beg:
               n.pos = Position(self.scanner.buffer, beg, self.token.pos - beg, col) 
         else:
            self.SynErr(71)
      elif self.la.kind == Scanner.lesspoint_Sym:
         self.Get( )
         if self.la.kind == Scanner.uparrow_Sym or self.la.kind == Scanner.out_Sym:
            if self.la.kind == Scanner.uparrow_Sym:
               self.Get( )
            elif self.la.kind == Scanner.out_Sym:
               self.Get( )
            else:
               self.SynErr(72)
            beg = self.la.pos 
            while self.StartOf(27):
               if self.StartOf(28):
                  self.Get()
               else:
                  self.Get( )
                  self.SemErr("bad string in attributes") 

            n.retVar = self.scanner.buffer.getString(beg, self.la.pos) 
            if self.la.kind == Scanner.pointgreater_Sym:
               self.Get( )
            elif self.la.kind == Scanner.comma_Sym:
               self.Get( )
               beg = self.la.pos
               col = self.la.col 
               while self.StartOf(13):
                  if self.StartOf(14):
                     self.Get()
                  else:
                     self.Get( )
                     self.SemErr("bad string in attributes") 

               self.Expect(Scanner.pointgreater_Sym)
               if self.token.pos > beg:
                  n.pos = Position(self.scanner.buffer, beg, self.token.pos - beg, col) 
            else:
               self.SynErr(73)
         elif self.StartOf(10):
            beg = self.la.pos
            col = self.la.col 
            while self.StartOf(15):
               if self.StartOf(16):
                  self.Get()
               else:
                  self.Get( )
                  self.SemErr("bad string in attributes") 

            self.Expect(Scanner.pointgreater_Sym)
            if self.token.pos > beg:
               n.pos = Position(self.scanner.buffer, beg, self.token.pos - beg, col) 
         else:
            self.SynErr(74)
      else:
         self.SynErr(75)

   def Condition( self ):
      while self.StartOf(29):
         if self.la.kind == Scanner.lparen_Sym:
            self.Get( )
            self.Condition()
         else:
            self.Get()

      self.Expect(Scanner.rparen_Sym)

   def TokenTerm( self ):
      g = self.TokenFactor()
      while self.StartOf(6):
         g2 = self.TokenFactor()
         Graph.MakeSequence(g, g2) 

      if (self.la.kind == Scanner.CONTEXT_Sym):
         self.Get( )
         self.Expect(Scanner.lparen_Sym)
         g2 = self.TokenExpr()
         Graph.SetContextTrans(g2.l)
         Graph.MakeSequence(g, g2) 
         self.Expect(Scanner.rparen_Sym)
      return g

   def TokenFactor( self ):
      g = None
      if self.la.kind == Scanner.ident_Sym or self.la.kind == Scanner.string_Sym:
         s = self.Sym()
         name,kind = s
         if kind == self.id:
            c = CharClass.Find(name)
            if c is None:
               self.SemErr("undefined name")
               c = CharClass(s.name, set( ) )
            p = Node(Node.clas, None, 0)
            p.val = c.n
            g = Graph(p)
            self.tokenString = self.noString
         else:    # str
            g = Graph.StrToGraph(name)
            if self.tokenString is None:
               self.tokenString = name
            else:
               self.tokenString = self.noString 
      elif self.la.kind == Scanner.lparen_Sym:
         self.Get( )
         g = self.TokenExpr()
         self.Expect(Scanner.rparen_Sym)
      elif self.la.kind == Scanner.lbrack_Sym:
         self.Get( )
         g = self.TokenExpr()
         self.Expect(Scanner.rbrack_Sym)
         Graph.MakeOption(g) 
      elif self.la.kind == Scanner.lbrace_Sym:
         self.Get( )
         g = self.TokenExpr()
         self.Expect(Scanner.rbrace_Sym)
         Graph.MakeIteration(g) 
      else:
         self.SynErr(76)
      if g is None:    # invalid start of TokenFactor
         g = Graph(Node(Node.eps, None, 0)) 
      return g



   def Parse( self, scanner ):
      self.scanner = scanner
      self.la = Token( )
      self.la.val = u''
      self.Get( )
      self.Coco()
      self.Expect(Scanner.EOF_SYM)


   set = [
      [T,T,x,T, x,x,x,x, x,T,T,T, x,x,x,T, T,T,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,T, x,x,x,x, x,x],
      [x,T,T,T, T,T,x,x, x,x,x,x, T,T,T,x, x,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,x],
      [T,T,x,T, x,x,x,x, x,T,T,T, x,x,x,T, T,T,T,x, x,x,x,T, x,T,x,x, x,x,x,x, x,x,T,T, T,x,T,x, T,T,x,T, x,x,x,x, x,x],
      [T,T,x,T, x,x,x,x, x,T,T,T, x,x,x,T, T,T,x,T, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,T, x,x,x,x, x,x],
      [T,T,x,T, x,x,x,x, x,T,T,T, x,x,x,T, T,T,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,T, x,x,x,x, x,x],
      [x,T,x,T, x,x,x,x, x,T,T,T, x,x,x,T, T,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,T, x,x,x,x, x,x],
      [x,T,x,T, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,T,x,x, x,x,x,x, x,x,x,x, T,x,T,x, x,x,x,x, x,x,x,x, x,x],
      [x,x,x,x, x,x,x,x, x,x,x,T, x,T,T,T, T,x,T,x, x,x,x,x, x,x,T,x, x,x,x,x, x,x,x,x, x,T,x,T, x,x,x,x, x,x,x,x, x,x],
      [x,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,x,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,x],
      [x,T,T,T, x,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,x,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,x],
      [x,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, x,x,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,x],
      [x,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, x,x,x,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,x],
      [x,T,T,T, x,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, x,x,x,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,x],
      [x,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,x,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,x],
      [x,T,T,T, x,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,x,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,x],
      [x,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, x,x,T,T, T,x,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,x],
      [x,T,T,T, x,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, x,x,T,T, T,x,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,x],
      [x,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, x,T,T,T, T,x],
      [x,T,T,T, x,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,x, x,T,T,T, T,x],
      [x,T,x,T, x,x,x,x, x,x,x,x, x,x,x,x, x,x,T,x, x,x,x,T, x,T,T,x, x,x,x,x, x,x,T,T, T,T,T,T, T,T,x,T, x,x,x,x, x,x],
      [x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,T,x, x,x,x,x, x,x,T,x, x,x,x,x, x,x,x,x, x,T,x,T, x,x,x,x, x,x,x,x, x,x],
      [x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,T, T,x,T,x, T,T,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x],
      [x,T,x,T, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,T, x,T,x,x, x,x,x,x, x,x,x,T, T,x,T,x, T,T,x,T, x,x,x,x, x,x],
      [x,T,x,T, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,T, x,T,x,x, x,x,x,x, x,x,x,T, T,x,T,x, T,x,x,T, x,x,x,x, x,x],
      [x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,T,x, x,x,x,x, x,x,T,x, x,x,x,x, x,x,T,x, x,T,x,T, x,x,x,x, x,x,x,x, x,x],
      [x,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,x,x, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,x],
      [x,T,T,T, x,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,x,x, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,x],
      [x,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,x, T,x,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,x],
      [x,T,T,T, x,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,x, T,x,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,x],
      [x,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,x,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,x]

      ]

   errorMessages = {
      
      0 : "EOF expected",
      1 : "ident expected",
      2 : "number expected",
      3 : "string expected",
      4 : "badString expected",
      5 : "\"COMPILER\" expected",
      6 : "\"IGNORECASE\" expected",
      7 : "\"CHARACTERS\" expected",
      8 : "\"TOKENS\" expected",
      9 : "\"NAMES\" expected",
      10 : "\"PRAGMAS\" expected",
      11 : "\"COMMENTS\" expected",
      12 : "\"FROM\" expected",
      13 : "\"TO\" expected",
      14 : "\"NESTED\" expected",
      15 : "\"IGNORE\" expected",
      16 : "\"PRODUCTIONS\" expected",
      17 : "\"=\" expected",
      18 : "\".\" expected",
      19 : "\"END\" expected",
      20 : "\"+\" expected",
      21 : "\"-\" expected",
      22 : "\"..\" expected",
      23 : "\"ANY\" expected",
      24 : "\"CHR\" expected",
      25 : "\"(\" expected",
      26 : "\")\" expected",
      27 : "\"<\" expected",
      28 : "\"^\" expected",
      29 : "\"out\" expected",
      30 : "\">\" expected",
      31 : "\",\" expected",
      32 : "\"<.\" expected",
      33 : "\".>\" expected",
      34 : "\"|\" expected",
      35 : "\"WEAK\" expected",
      36 : "\"[\" expected",
      37 : "\"]\" expected",
      38 : "\"{\" expected",
      39 : "\"}\" expected",
      40 : "\"SYNC\" expected",
      41 : "\"IF\" expected",
      42 : "\"CONTEXT\" expected",
      43 : "\"(.\" expected",
      44 : "\".)\" expected",
      45 : "\"from\" expected",
      46 : "\"import\" expected",
      47 : "\"*\" expected",
      48 : "??? expected",
      49 : "this symbol not expected in Coco",
      50 : "invalid Imports",
      51 : "invalid Imports",
      52 : "this symbol not expected in TokenDecl",
      53 : "invalid TokenDecl",
      54 : "invalid NameDecl",
      55 : "invalid AttrDecl",
      56 : "invalid AttrDecl",
      57 : "invalid AttrDecl",
      58 : "invalid AttrDecl",
      59 : "invalid AttrDecl",
      60 : "invalid AttrDecl",
      61 : "invalid AttrDecl",
      62 : "invalid SimSet",
      63 : "invalid SimSet",
      64 : "invalid SimSet",
      65 : "invalid SimSet",
      66 : "invalid Sym",
      67 : "invalid Term",
      68 : "invalid Factor",
      69 : "invalid Attribs",
      70 : "invalid Attribs",
      71 : "invalid Attribs",
      72 : "invalid Attribs",
      73 : "invalid Attribs",
      74 : "invalid Attribs",
      75 : "invalid Attribs",
      76 : "invalid TokenFactor",
      }