Core.py

#-------------------------------------------------------------------------
#Core.py -- the computation routines
#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 coe generated by Coco/R (other than
#Coco/R itself) does not fall under the GNU General Public License.
#-------------------------------------------------------------------------*/

import os.path
import sys
import copy
from optparse import OptionParser

from Trace import Trace
from Errors import Errors
from CharClass import CharClass

class Comment( object ):
   ''' info about comment syntax'''
   first = None   # list of comments

   def __init__( self, frm,  to,  nested):
      assert isinstance(frm,Node)
      assert isinstance(to,Node)
      assert isinstance(nested,bool)
      self.start = self.Str(frm)
      self.stop = self.Str(to)
      self.nested = nested
      self.next = Comment.first
      Comment.first = self

   def Str(self, p):
      assert isinstance(p,Node)
      s = ''    # StringBuffer
      while p is not None:
         if p.typ == Node.chr:
            s += chr(p.val)
         elif p.typ == Node.clas:
            st = CharClass.Set(p.val)   # BitSet
            if len(st) != 1:
               Errors.SemErr("character set contains more than 1 character")
            s += chr(min(st))
            #s += chr(st.First())
         else:
            Errors.SemErr("comment delimiters may not be structured")
         p = p.next
      if len(s) == 0 or len(s) > 2:
         Errors.SemErr("comment delimiters must be 1 or 2 characters long")
         s = '?'
      return s

class Symbol( object ):
   terminals     = [ ]    # of Symbol
   pragmas       = [ ]
   nonterminals  = [ ]

   # token kinds
   fixedToken    = 0   # e.g. 'a' ('b' | 'c') (structure of literals)
   classToken    = 1   # e.g. digit {digit}   (at least one char class)
   litToken      = 2   # e.g. "while"
   classLitToken = 3   # e.g. letter {letter} but without literals that have the same structure


   def __init__( self, typ, name, line ):
      assert isinstance( typ, int )
      assert isinstance( name, (str,unicode) )
      assert isinstance( line, int )
      self.n             = 0       # symbol number
      self.typ           = 0       # t, nt, pr, unknown, rslv
      self.name          = 0       # symbol name
      self.graph         = None    # Node,  nt: to first node of syntax graph
      self.tokenKind     = 0       # t:  token kind (fixedToken, classToken, ...)
      self.deletable     = False   # nt: true if nonterminal is deletable
      self.firstReady    = False   # nt: true if terminal start symbols have already been computed
      self.first         = None    # set,   nt: terminal start symbols
      self.follow        = None    # set,   nt: terminal followers
      self.nts           = None    # set,   nt: nonterminals whose followers have to be added to this sym
      self.line          = 0       # source text line number of item in this node
      self.attrPos       = None    # Position,   nt: position of attributes in source text (or None)
      self.semPos        = None    # Position,   pr: pos of semantic action in source text (or None)
                                   #             nt: pos of local declarations in source text (or None)
      self.retType       = ''      # AH - nt: Type of output attribute (or None)
      self.retVar        = None    # str - AH - nt: Name of output attribute (or None)
      self.symName       = None    # str,   symbolic name /* pdt */

      if len(name) == 2 and name[0] == '"':
         Errors.SemErr( 'empty token not allowed' )
         name = '???'

      self.typ = typ
      self.name = name
      self.line = line

      if typ == Node.t:
         self.n = len(Symbol.terminals)
         Symbol.terminals.append( self )
      elif typ == Node.pr:
         Symbol.pragmas.append( self )
      elif typ == Node.nt:
         self.n = len(Symbol.nonterminals)
         Symbol.nonterminals.append( self )

   @staticmethod
   def Find( name ):
      assert isinstance( name, ( str, unicode ) )

      for s in Symbol.terminals:
         if s.name == name:
            return s

      for s in Symbol.nonterminals:
         if s.name == name:
            return s

      return None

   def compareTo( self, x ):
      assert isinstance( x, Symbol )
      return self.name.__cmp__( x.name )

class Target( object ):
   ''' set of states that are reached by an action'''
   def __init__( self, s ):
      assert isinstance( s, State )
      self.state = s      # target state
      self.next  = None   # Target instance

class Node( object ):
   nodes = [ ]
   nTyp  = ["    ", "t   ", "pr  ", "nt  ", "clas", "chr ", "wt  ", "any ", "eps ",
            "sync", "sem ", "alt ", "iter", "opt ", "rslv"]

   # constants for node kinds
   t    =  1  # terminal symbol
   pr   =  2  # pragma
   nt   =  3  # nonterminal symbol
   clas =  4  # character class
   chr  =  5  # character
   wt   =  6  # weak terminal symbol
   any  =  7  #
   eps  =  8  # empty
   sync =  9  # synchronization symbol
   sem  = 10  # semantic action: (. .)
   alt  = 11  # alternative: |
   iter = 12  # iteration: { }
   opt  = 13  # option: [ ]
   rslv = 14  # resolver expr  /* ML */ /* AW 03-01-13 renamed slv --> rslv */

   normalTrans  = 0  # transition codes
   contextTrans = 1

   def __init__( self, typ, symOrNodeOrInt, line=None ):
      assert isinstance( typ, int )
      assert isinstance( symOrNodeOrInt, Symbol ) or isinstance( symOrNodeOrInt, Node ) or isinstance( symOrNodeOrInt, int ) or (symOrNodeOrInt is None)
      assert isinstance( line, int ) or (line is None)

      self.n     =  0    # node number
      self.typ   =  0    # t, nt, wt, chr, clas, any, eps, sem, sync, alt, iter, opt, rslv
      self.next  = None  # Node,   to successor node
      self.down  = None  # Node,   alt: to next alternative
      self.sub   = None  # Node,   alt, iter, opt: to first node of substructure
      self.up    = False # true: "next" leads to successor in enclosing structure
      self.sym   = None  # Symbol,   nt, t, wt: symbol represented by this node
      self.val   =  0    # chr:  ordinal character value
                         # clas: index of character class
      self.code  =  0    # chr, clas: transition code
      self.set   = None  # set,   any, sync: the set represented by this node
      self.pos   = None  # Position,   nt, t, wt: pos of actual attributes
                         #             sem:       pos of semantic action in source text
      self.line  = 0     # source text line number of item in this node
      self.state = None  # State,   DFA state corresponding to this node
                         #          (only used in DFA.ConvertToStates)
      self.retVar= None  # str, nt: name of output attribute (or None)

      if isinstance(symOrNodeOrInt, int) and isinstance(line, int):
         self.typ = typ
         self.sym = None
         self.line = line
         self.n    = len(Node.nodes)
         Node.nodes.append( self )
         self.val = symOrNodeOrInt
      elif line is None:
         self.typ = typ
         self.sym = None
         self.line = 0
         self.n    = len(Node.nodes)
         Node.nodes.append( self )
         self.sub = symOrNodeOrInt
      else:
         self.typ = typ
         self.sym = symOrNodeOrInt
         self.line = line
         self.n    = len(Node.nodes)
         Node.nodes.append( self )

   @staticmethod
   def DelGraph( p ):
      return (p is None) or Node.DelNode(p) and Node.DelGraph(p.next)

   @staticmethod
   def DelSubGraph( p ):
      return p is None or Node.DelNode(p) and (p.up or Node.DelSubGraph(p.next))

   @staticmethod
   def DelAlt( p ):
      return p is None or Node.DelNode(p) and (p.up or Node.DelAlt(p.next))

   @staticmethod
   def DelNode( p ):
      if p.typ == Node.nt:
         return p.sym.deletable
      elif p.typ == Node.alt:
         return Node.DelAlt( p.sub ) or p.down != None and Node.DelAlt(p.down)
      else:
         return p.typ in ( Node.eps, Node.iter, Node.opt, Node.sem, Node.sync, Node.rslv )

#----------------- for printing ----------------------

   @staticmethod
   def Ptr( p, up ):
      assert isinstance( p, Node ) or ( p is None )
      assert isinstance( up, bool )
      if p is None:
         return 0
      elif up:
         return -p.n
      else:
         return p.n

   @staticmethod
   def Pos( pos ):
      if pos is None:
         return '     '
      else:
         return Trace.formatString( str(pos.beg), 5 )

   @staticmethod
   def Name( name ):
      assert isinstance( name, (str,unicode) )
      return (name + '           ')[0:12]
      # found no simpler way to get the first 12 characters of the name
      # padded with blanks on the right

   @staticmethod
   def PrintNodes( ):
      Trace.WriteLine("Graph nodes:")
      Trace.WriteLine("----------------------------------------------------")
      Trace.WriteLine("   n type name          next  down   sub   pos  line")
      Trace.WriteLine("                               val  code")
      Trace.WriteLine("----------------------------------------------------")

      for p in Node.nodes:
         Trace.Write(str(p.n), 4)
         Trace.Write(" " + Node.nTyp[p.typ] + " ")
         if p.sym is not None:
            Trace.Write(Node.Name(p.sym.name), 12)
            Trace.Write(" ")
         elif p.typ == Node.clas:
            c = CharClass.classes[ p.val ]
            Trace.Write(Node.Name(c.name), 12)
            Trace.Write(" ")
         else:
            Trace.Write("             ")

         Trace.Write(str(Node.Ptr(p.next, p.up)), 5)
         Trace.Write(" ")

         if p.typ in ( Node.t, Node.nt, Node.wt ):
            Trace.Write("             ")
            Trace.Write(Node.Pos(p.pos), 5)
         elif p.typ == Node.chr:
            Trace.Write(str(p.val), 5)
            Trace.Write(" ")
            Trace.Write(str(p.code), 5)
            Trace.Write("       ")
         elif p.typ == Node.clas:
            Trace.Write("      ")
            Trace.Write(str(p.code), 5)
            Trace.Write("       ")
         elif p.typ in ( Node.alt, Node.iter, Node.opt ):
            Trace.Write(str(Node.Ptr(p.down, False)), 5)
            Trace.Write(" ")
            Trace.Write(str(Node.Ptr(p.sub, False)), 5)
            Trace.Write("       ")
         elif p.typ == Node.sem:
            Trace.Write("             ")
            Trace.Write(Node.Pos(p.pos), 5)
         elif p.typ in ( Node.eps, Node.any, Node.sync ):
            Trace.Write("                  ")

         Trace.WriteLine(str(p.line), 5);

      Trace.WriteLine();

class State( object ):
   ''' state of finite automaton'''
   lastNr = 0  # highest state number

   def __init__( self ):
      self.nr = 0             # state number
      self.firstAction = None # Action,  to first action of this state
      self.endOf = None       # Symbol,  recognized token if state is final
      self.ctx = False        # true if state is reached via contextTrans
      self.next = None        # State

      State.lastNr += 1
      self.nr = State.lastNr

   def AddAction(self, act):
      assert isinstance(act,Action)
      lasta = None     # Action
      a = self.firstAction  # Action
      while (a is not None) and (act.typ >= a.typ):
         lasta = a
         a = a.next
      # collecting classes at the beginning gives better performance
      act.next = a
      if a == self.firstAction:
         self.firstAction = act
      else:
         lasta.next = act

   def DetachAction(self, act):
      assert isinstance(act,Action)
      lasta = None   # Action
      a = self.firstAction   # Action
      while (a is not None) and a != act:
         lasta = a
         a = a.next
      if a is not None:
         if a == self.firstAction:
            self.firstAction = a.next
         else:
            lasta.next = a.next

   def TheAction(self, ch):
      assert isinstance(ch,(str,unicode))
      if isinstance( ch, (str,unicode) ):
         ch = ord(ch)
      a = self.firstAction
      while a is not None:
         if a.typ == Node.chr and ch == a.sym:
            return a
         elif a.typ == Node.clas:
            s = CharClass.Set(a.sym)
            if ch in s:
               return a
         a = a.next
      return None

   def MeltWith(self, s):
      '''copy actions of s to state'''
      assert isinstance( s, State )
      action = s.firstAction
      while action is not None:
         a = Action(action.typ, action.sym, action.tc)
         a.AddTargets(action)
         self.AddAction(a)
         action = action.next

class Action( object ):
   ''' action of finite automaton'''
   def __init__( self, typ, sym, tc):
      assert isinstance(typ,int)
      assert isinstance(sym,int)
      assert isinstance(tc,int)
      self.typ = typ        # type of action symbol: clas, chr
      self.sym = sym        # action symbol
      self.tc = tc          # transition code: normalTrans, contextTrans
      self.target = None    # Target    # states reached from this action
      self.next = None      # Action

   def AddTarget(self,t):
      ''' add t to the action.targets'''
      assert isinstance( t, Target )
      last = None   # Target
      p = self.target   # Target
      while (p is not None) and (t.state.nr >= p.state.nr):
         if t.state == p.state:
            return
         last = p
         p = p.next
      t.next = p
      if (p == self.target):
         self.target = t
      else:
         last.next = t

   def AddTargets(self, a):
      '''add copy of a.targets to action.targets'''
      assert isinstance( a, Action )
      p = a.target
      while p is not None:
         t = Target(p.state)
         self.AddTarget(t)
         p = p.next
      if a.tc == Node.contextTrans:
         self.tc = Node.contextTrans

   def Symbols(self):
      if self.typ == Node.clas:
         s = copy.copy(CharClass.Set(self.sym))
      else:
         s = set( )
         s.add(self.sym)
      return s

   def ShiftWith(self,s):
      if len(s) == 1:
         self.typ = Node.chr
         self.sym = min(s) #.First()
      else:
         c = CharClass.Find(s)
         if c is None:
            c = CharClass("#", s) # class with dummy name
         self.typ = Node.clas
         self.sym = c.n

   def GetTargetStates(self,param):
      assert isinstance( param, list ) # Object[]
      # compute the set of target states
      targets = set( )   # BitSet
      endOf = None   # Symbol
      ctx = False   # boolean
      t = self.target
      while t is not None:
         stateNr = t.state.nr   # int
         if stateNr <= DFA.lastSimState:
            targets.add(stateNr)
         else:
            try:
               targets |= Melted.Set(stateNr)
            except:
               print sys.exc_info()[1]
               Errors.count += 1
         if t.state.endOf is not None:
            if (endOf is None) or (endOf == t.state.endOf):
               endOf = t.state.endOf
            else:
               print "Tokens " + endOf.name + " and " + t.state.endOf.name + " cannot be distinguished"
               Errors.count += 1
         if t.state.ctx:
            ctx = True
         t = t.next
      param[0] = targets
      param[1] = endOf
      return ctx

class Melted( object ):     # info about melted states
   first    = None   # Melted instance,   head of melted state list

   def __init__( self, st, state ):
      assert isinstance( st, set )
      assert isinstance( state, State )
      self.set     = st            # set of old states
      self.state   = state         # new state
      self.next    = Melted.first  # Melted instance
      Melted.first = self

   @staticmethod
   def Set( nr ):
      assert isinstance( nr, int )
      m = Melted.first
      while m is not None:
         if m.state.nr == nr:
            return m.set
         else:
            m = m.next
      raise RuntimeError( '-- compiler error in Melted.Set()' )

   @staticmethod
   def StateWithSet( s ):
      assert isinstance( s, set )
      m = Melted.first
      while m is not None:
         if s == m.set: #s.equals( m.set ):
            return m
         m = m.next
      return None

class Graph( object ):
   dummyNode = Node( Node.eps, None, 0 )

   def __init__( self, p=None ):
      assert isinstance(p, Node) or (p is None)

      self.l  = p   #Node,  left end of graph = head
      self.r  = p   #Node,  right end of graph = list of nodes to be linked to successor graph

   @staticmethod
   def MakeFirstAlt( g ):
      assert isinstance( g, Graph )
      g.l = Node(Node.alt, g.l)
      g.l.line = g.l.sub.line       # make line available for error handling */
      g.l.next = g.r
      g.r = g.l

   @staticmethod
   def MakeAlternative( g1, g2 ):
      assert isinstance( g1, Graph )
      assert isinstance( g2, Graph )
      g2.l = Node(Node.alt, g2.l)
      g2.l.line = g2.l.sub.line
      p = g1.l
      while p.down is not None:
         p = p.down
      p.down = g2.l
      p = g1.r
      while p.next is not None:
         p = p.next
      p.next = g2.r

   @staticmethod
   def MakeSequence( g1, g2 ):
      assert isinstance( g1, Graph)
      assert isinstance( g2, Graph)
      p = g1.r.next
      g1.r.next = g2.l    # link head node
      while p is not None:    # link substructure
         q = p.next
         p.next = g2.l
         p.up = True
         p = q
      g1.r = g2.r

   @staticmethod
   def MakeIteration( g ):
      assert isinstance(g, Graph)
      g.l = Node(Node.iter, g.l)
      p = g.r
      g.r = g.l
      while p is not None:
         q = p.next
         p.next = g.l
         p.up = True
         p = q

   @staticmethod
   def MakeOption( g ):
      assert isinstance( g, Graph)
      g.l = Node(Node.opt, g.l)
      g.l.next = g.r
      g.r = g.l

   @staticmethod
   def Finish( g ):
      assert isinstance( g, Graph)
      p = g.r
      while p is not None:
         q = p.next
         p.next = None
         p = q

   @staticmethod
   def SetContextTrans( p ):
      '''set transition code in the graph rooted at p'''
      assert isinstance(p, Node) or (p is None)
      DFA.hasCtxMoves = True
      while p is not None:
         if p.typ == Node.chr or p.typ == Node.clas:
            p.code = Node.contextTrans
         elif p.typ == Node.opt or p.typ == Node.iter:
            Graph.SetContextTrans(p.sub)
         elif p.typ == Node.alt:
            Graph.SetContextTrans(p.sub)
            Graph.SetContextTrans(p.down)
         if p.up:
            break
         p = p.next

   @staticmethod
   def DeleteNodes( ):
      Node.nodes = [ ]
      Graph.dummyNode = Node(Node.eps, None, 0)

   @staticmethod
   def StrToGraph( st ):
      assert isinstance(st,(str,unicode))
      s = DFA.Unescape(st[1:-1])
      if len(s) == 0:
         Errors.SemErr("empty token not allowed")
      g = Graph()
      g.r = Graph.dummyNode
      for i in xrange(0, len(s)):
         p = Node(Node.chr, ord(s[i]), 0)
         g.r.next = p
         g.r = p
      g.l = Graph.dummyNode.next
      Graph.dummyNode.next = None
      return g

class UserDefinedTokenName(object):
   NameTab = [ ]
   alias   = ''
   name    = ''

   def __init__(self, alias, name):
      assert isinstance(alias, str)
      assert isinstance(name, str)
      self.alias = alias
      self.name  = name
      UserDefinedTokenName.NameTab.append(self)

class Tab:
   semDeclPos     = None           #Position,   position of global semantic declarations
   ignored        = None           #Set,   characters ignored by the scanner
   ddt            = [ False ] * 20 # boolean[20],  debug and test switches
   gramSy         = None           #Symbol,   root nonterminal; filled by ATG
   eofSy          = None           #Symbol,   end of file symbol
   noSym          = None           #Symbol,   used in case of an error
   allSyncSets    = None           #set,   union of all synchronisation sets
   nsName         = ''             #namespace for generated files
   frameDir       = None           #directory containing the frame files
   literals       = { }            #Hashtable,   symbols that are used as literals

   visited        = None           #set,   mark list for graph traversals
   curSy          = None           #Symbol,   current symbol in computation of sets

   @staticmethod
   def parseArgs( argv, testArgCt=False ):
      usage = 'usage: %prog [options] filename.atg'
      optParser = OptionParser( usage )
      optParser.add_option( '-a', '-A', dest='traceAutomaton',
                         action='store_true', default=False,
                         help='Include automaton tracing in the trace file.' )
      optParser.add_option( '-c', '-C', dest='generateDriver',
                         action='store_true', default=False,
                         help='Generate a main compiler source file.' )
      optParser.add_option( '-f', '-F', dest='firstAndFollow',
                         action='store_true', default=False,
                         help='Include first & follow sets in the trace file.' )
      optParser.add_option( '-g', '-G', dest='syntaxGraph',
                         action='store_true', default=False,
                         help='Include syntax graph in the trace file.' )
      optParser.add_option( '-i', '-I', dest='traceComputations',
                         action='store_true', default=False,
                         help='Include a trace of the computations for first sets in the trace file.' )
      optParser.add_option( '-j', '-J', dest='listAnyAndSync',
                         action='store_true', default=False,
                         help='Inclue a listing of the ANY and SYNC sets in the trace file.' )
      optParser.add_option( '-m', '-M', dest='mergeErrors',
                         action='store_true', default=False,
                         help='Merge error messages in the source listing.' )
      optParser.add_option( '-n', '-N', dest='tokenNames',
                         action='store_true', default=False,
                         help='Generate token names in the source listing.' )
      optParser.add_option( '-p', '-P', dest='statistics',
                         action='store_true', default=False,
                         help='Include a listing of statistics in the trace file.' )
      optParser.add_option( '-r', '-R', dest='frameFileDir',
                            default=None,
                         help='Use scanner.frame and parser.frame in directory DIR.', metavar='DIR' )
      optParser.add_option( '-s', '-S', dest='symbolTable',
                         action='store_true', default=False,
                         help='Include the symbol table listing in the trace file.' )
      optParser.add_option( '-t', '-T', dest='testOnly',
                         action='store_true', default=False,
                         help='Test the grammar only, don\'t generate any files.' )
      optParser.add_option( '-x', '-X', dest='crossReferences',
                         action='store_true', default=False,
                         help='Include a cross reference listing in the trace file.' )

      if argv is None:
         options, args = optParser.parse_args( )
      else:
         options, args = optParser.parse_args( argv )

      Tab.SetDDT( options )

      if testArgCt:
         if len(args) != 2:
            optParser.print_help( )
            sys.exit( )

      return options,args

   #---------------------------------------------------------------------
   #  Symbol set computations
   #---------------------------------------------------------------------

   @staticmethod
   def First0( p, mark ):
      '''Computes the first set for the given Node.'''
      assert isinstance( p, Node ) or (p is None)
      assert isinstance( mark, set )
      fs = set( )
      while (p is not None) and not (p.n in mark):
         mark.add(p.n)
         if p.typ == Node.nt:
            if p.sym.firstReady:
               fs |= p.sym.first
            else:
               fs |= Tab.First0( p.sym.graph, mark )
         elif p.typ in ( Node.t, Node.wt ):
            fs.add(p.sym.n)
         elif p.typ == Node.any:
            fs |= p.set
         elif p.typ == Node.alt:
            fs |= Tab.First0(p.sub, mark)
            fs |= Tab.First0(p.down, mark)
         elif p.typ in ( Node.iter, Node.opt ):
            fs |= Tab.First0(p.sub, mark)
         if not Node.DelNode(p):
            break
         p = p.next
      return fs

   @staticmethod
   def First( p ):
      assert isinstance( p, Node) or (p is None)
      fs = Tab.First0(p, set( ) )
      if Tab.ddt[3]:
         Trace.WriteLine( )
         if p is not None:
            Trace.WriteLine("First: node = " + str(p.n) )
         else:
            Trace.WriteLine("First: node = None");
         Tab.PrintSet(fs,0)
      return fs

   @staticmethod
   def CompFirstSets( ):
      assert isinstance( Symbol.nonterminals, list)
      nt = Symbol.nonterminals
      for sym in nt:
         sym.first = set( )
         sym.firstReady = False
      for sym in nt:
         sym.first = Tab.First(sym.graph)
         sym.firstReady = True

   @staticmethod
   def CompFollow( p ):
      assert isinstance(p, Node) or (p is None)
      assert isinstance(Tab.visited, set)
      while (p is not None) and (p.n not in Tab.visited):
         Tab.visited.add(p.n)
         if p.typ == Node.nt:
            s = Tab.First(p.next)
            p.sym.follow |= s
            if Node.DelGraph(p.next):
               p.sym.nts.add(Tab.curSy.n)
         elif p.typ == Node.opt or p.typ == Node.iter:
            Tab.CompFollow(p.sub)
         elif p.typ == Node.alt:
            Tab.CompFollow(p.sub)
            Tab.CompFollow(p.down)
         p = p.next

   @staticmethod
   def Complete( sym ):
      assert isinstance( sym, Symbol )
      if sym.n not in Tab.visited:
         Tab.visited.add(sym.n)
         nt = Symbol.nonterminals
         for s in nt:
            if s.n in sym.nts:
               Tab.Complete(s)
               sym.follow |= s.follow
               if sym == Tab.curSy:
                  sym.nts.discard(s.n)

   @staticmethod
   def CompFollowSets():
      nt = Symbol.nonterminals;
      for sym in nt:
         sym.follow = set()
         sym.nts = set()
      Tab.gramSy.follow.add(Tab.eofSy.n)
      Tab.visited = set( )
      for sym in nt:
         Tab.curSy = sym
         Tab.CompFollow(sym.graph)
      for sym in nt:
         Tab.visited = set()
         Tab.curSy = sym
         Tab.Complete(sym)

   @staticmethod
   def LeadingAny( p ):
      assert isinstance( p, Node) or (p is None)
      if p is None:
         return None
      a = None
      if p.typ == Node.any:
         a = p
      elif p.typ == Node.alt:
         a = Tab.LeadingAny(p.sub)
         if a is None:
            a = Tab.LeadingAny(p.down)
      elif p.typ == Node.opt or p.typ == Node.iter:
         a = Tab.LeadingAny(p.sub)
      elif Node.DelNode(p) and not p.up:
         a = Tab.LeadingAny(p.next)
      return a

   @staticmethod
   def FindAS( p ):
      '''find ANY sets'''
      assert isinstance( p, Node ) or ( p is None )
      while p is not None:
         if p.typ == Node.opt or p.typ == Node.iter:
            Tab.FindAS(p.sub)
            a = Tab.LeadingAny(p.sub)
            if a is not None:
               a.set -= Tab.First(p.next)
         elif p.typ == Node.alt:
            s1 = set( )
            q = p
            while q is not None:
               Tab.FindAS(q.sub)
               a = Tab.LeadingAny(q.sub)
               if a is not None:
                  h = Tab.First(q.down)
                  h |= s1
                  a.set -= h
               else:
                  s1 |= Tab.First(q.sub)
               q = q.down
         if p.up:
            break
         p = p.next;

   @staticmethod
   def CompAnySets():
      nt = Symbol.nonterminals
      for sym in nt:
         Tab.FindAS(sym.graph)

   @staticmethod
   def Expected( p, curSy):
      assert isinstance( p, Node ) or (p is None)
      assert isinstance( curSy, Symbol )
      s = Tab.First(p)
      if Node.DelGraph(p):
         s |= curSy.follow
      return s

   @staticmethod
   # does not look behind resolvers; only called during LL(1) test and in CheckRes
   def Expected0( p, curSy ):
      assert isinstance( p, Node)
      assert isinstance(curSy,Symbol)
      if p.typ == Node.rslv:
         return set( )
      else:
         return Tab.Expected(p, curSy)

   @staticmethod
   def CompSync(p):
      assert isinstance( p, Node) or (p is None)
      while (p is not None) and (p.n not in Tab.visited):
         Tab.visited.add(p.n)
         if p.typ == Node.sync:
            s = Tab.Expected(p.next, Tab.curSy)
            s.add(Tab.eofSy.n)
            Tab.allSyncSets |= s
            p.set = s
         elif p.typ == Node.alt:
            Tab.CompSync(p.sub)
            Tab.CompSync(p.down)
         elif p.typ == Node.opt or p.typ == Node.iter:
            Tab.CompSync(p.sub)
         p = p.next

   @staticmethod
   def CompSyncSets():
      nt = Symbol.nonterminals
      Tab.allSyncSets = set( )
      Tab.allSyncSets.add(Tab.eofSy.n)
      Tab.visited = set( )
      for sym in nt:
         Tab.curSy = sym
         Tab.CompSync(Tab.curSy.graph)

   @staticmethod
   def SetupAnys():
      for p in Node.nodes:
         if p.typ == Node.any:
            p.set = set( )
            for j in xrange(0,len(Symbol.terminals)):
               p.set.add(j)
            p.set.discard(Tab.eofSy.n)

   @staticmethod
   def CompDeletableSymbols():
      nt = Symbol.nonterminals

      changed = False
      for sym in nt:
         if (not sym.deletable) and (sym.graph is not None) and Node.DelGraph(sym.graph):
            sym.deletable = True
            changed = True
      while changed:
         changed = False
         for sym in nt:
            if (not sym.deletable) and (sym.graph is not None) and Node.DelGraph(sym.graph):
               sym.deletable = True
               changed = True
      for sym in nt:
         if sym.deletable:
            print "  " + sym.name + " deletable"

   @staticmethod
   def RenumberPragmas():
      n = len(Symbol.terminals)
      for sym in Symbol.pragmas:
         sym.n = n
         n += 1

   @staticmethod
   def CompSymbolSets():
      Tab.CompDeletableSymbols()
      Tab.CompFirstSets()
      Tab.CompFollowSets()
      Tab.CompAnySets()
      Tab.CompSyncSets()
      if Tab.ddt[1]:
         Trace.WriteLine()
         Trace.WriteLine("First & follow symbols:")
         Trace.WriteLine("----------------------")
         Trace.WriteLine()
         nt = Symbol.nonterminals
         for sym in nt:
            Trace.WriteLine(sym.name)
            Trace.Write("first:   ")
            Tab.PrintSet(sym.first, 10)
            Trace.Write("follow:  ")
            Tab.PrintSet(sym.follow,10)
            Trace.WriteLine()
      if Tab.ddt[4]:
         Trace.WriteLine()
         Trace.WriteLine("ANY and SYNC sets:")
         Trace.WriteLine("-----------------")
         for p in Node.nodes:
            if p.typ == Node.any or p.typ == Node.sync:
               Trace.Write(str(p.n), 4)
               Trace.Write(" ")
               Trace.Write(Node.nTyp[p.typ], 4)
               Trace.Write(": ")
               Tab.PrintSet(p.set,12)
               Trace.WriteLine()

   #---------------------------------------------------------------------
   #  Grammar checks
   #---------------------------------------------------------------------

   @staticmethod
   def GrammarOk():
      ok = (     Tab.NtsComplete()
             and Tab.AllNtReached()
             and Tab.NoCircularProductions()
             and Tab.AllNtToTerm()
             and Tab.ResolversOk() )
      assert isinstance(ok,bool)
      if ok:
         Tab.CheckLL1()
      return ok

   #--------------- check for circular productions ----------------------

   @staticmethod
   def GetSingles(p, singles):
      assert isinstance(p,Node) or (p is None)
      assert isinstance(singles,list)
      if p is None:
         return       # end of graph
      if p.typ == Node.nt:
         if p.up or Node.DelGraph(p.next):
            singles.append(p.sym)
      elif p.typ == Node.alt or p.typ == Node.iter or p.typ == Node.opt:
         if p.up or Node.DelGraph(p.next):
            Tab.GetSingles(p.sub, singles)
            if p.typ == Node.alt:
               Tab.GetSingles(p.down, singles)
      if (not p.up) and Node.DelNode(p):
         Tab.GetSingles(p.next, singles)

   @staticmethod
   def NoCircularProductions():
      class CNode(object):
         '''node of list for finding circular productions'''
         def __init__( self, l, r ):
            self.left  = l
            self.right = r

      lst = [ ]
      for sym in Symbol.nonterminals:
         singles = [ ]
         Tab.GetSingles(sym.graph, singles) # get nonterminals s such that sym-->s
         for j in xrange( 0, len(singles) ):
            s = singles[j]
            lst.append( CNode(sym, s) )

      changed = False
      i = 0
      while i < len(lst):
         n = lst[i]
         onLeftSide = False
         onRightSide = False
         for m in lst:
            if n.left == m.right:
               onRightSide = True
            if n.right == m.left:
               onLeftSide = True
         if (not onLeftSide) or (not onRightSide):
            lst.remove(n)
            i -= 1
            changed = True
         i += 1

      while changed:
         changed = False
         i = 0
         while i < len(lst):
            n = lst[i]
            onLeftSide = False
            onRightSide = False
            for m in lst:
               if n.left == m.right:
                  onRightSide = True
               if n.right == m.left:
                  onLeftSide = True
            if (not onLeftSide) or (not onRightSide):
               lst.remove(n)
               i -= 1
               changed = True
            i += 1

      ok = True
      for n in lst:
         ok = False;
         Errors.count += 1
         print "  " + n.left.name + " --> " + n.right.name
      return ok

   #--------------- check for LL(1) errors ----------------------

   @staticmethod
   def LL1Error( cond, sym):
      assert isinstance(cond,int)
      assert isinstance(sym,Symbol) or (sym is None)
      print "  LL(1) warning in " + Tab.curSy.name + ":",
      if sym is not None:
         print sym.name + " is",
      if cond == 1:
         print "the start of several alternatives"
      elif cond == 2:
         print "the start & successor of a deletable structure"
      elif cond == 3:
         print "an ANY node that matches no symbol"
      elif cond == 4:
         print "contents of [...] or {...} must not be deletable"

   @staticmethod
   def CheckOverlap( s1, s2, cond ):
      assert isinstance( s1, set )
      assert isinstance( s2, set )
      assert isinstance( cond, int )
      for sym in Symbol.terminals:
         if (sym.n in s1) and (sym.n in s2):
            Tab.LL1Error(cond, sym)

   @staticmethod
   def CheckAlts(p):
      assert isinstance(p,Node)
      while p is not None:
         if p.typ == Node.alt:
            q = p
            s1 = set( )
            while q is not None:    # for all alternatives
               s2 = Tab.Expected0(q.sub, Tab.curSy)
               Tab.CheckOverlap(s1, s2, 1)
               s1 |= s2
               Tab.CheckAlts(q.sub)
               q = q.down
         elif p.typ == Node.opt or p.typ == Node.iter:
            if Node.DelSubGraph(p.sub):
               Tab.LL1Error(4, None)    # e.g. [[...]]
            else:
               s1 = Tab.Expected0(p.sub, Tab.curSy)
               s2 = Tab.Expected(p.next, Tab.curSy)
               Tab.CheckOverlap(s1, s2, 2)
            Tab.CheckAlts(p.sub)
         elif p.typ == Node.any:
            if len(p.set) == 0:
               Tab.LL1Error(3, None)
            # e.g. {ANY} ANY or [ANY] ANY
         if p.up:
            break
         p = p.next

   @staticmethod
   def CheckLL1():
      for sym in Symbol.nonterminals:
         Tab.curSy = sym
         Tab.CheckAlts(Tab.curSy.graph)

   #------------- check if resolvers are legal  --------------------

   resOk = False

   @staticmethod
   def ResErr( p, msg):
      assert isinstance(p,Node)
      assert isinstance(msg, str)
      Errors.SemErr(msg, (p.line, p.pos.col) )
      Tab.resOk = False

   @staticmethod
   def CheckRes(p, rslvAllowed):
      assert isinstance(p, Node)
      assert isinstance(rslvAllowed, bool)
      while p is not None:
         if p.typ == Node.alt:
            expected = set( )
            q = p
            while q is not None:
               expected |= Tab.Expected0(q.sub, Tab.curSy)
               q = q.down
            soFar = set( )
            q = p
            while q is not None:
               if q.sub.typ == Node.rslv:
                  fs = Tab.Expected(q.sub.next,Tab.curSy)
                  if fs.intersection(soFar):
                     Tab.ResErr( q.sub, "Resolver will never be evaluated. "
                                        "Place it at previous conflicting alternative." )
                  if not fs.intersection(expected):
                     Tab.ResErr(q.sub, "Misplaced resolver: no LL(1) conflict." )
               else:
                  soFar |= Tab.Expected(q.sub,Tab.curSy)
               Tab.CheckRes(q.sub, True)

               q=q.down
         elif p.typ in ( Node.iter, Node.opt ):
            if p.sub.typ == Node.rslv:
               fs = Tab.First(p.sub.next)
               fsNext = Tab.Expected(p.next, Tab.curSy)
               if not fs.intersection(fsNext):
                  Tab.ResErr(p.sub, "Misplaced resolver: no LL(1) conflict.")
            Tab.CheckRes(p.sub, True)
         elif p.typ == Node.rslv:
            if not rslvAllowed:
               Tab.ResErr(p, "Misplaced resolver: no alternative.")
         if p.up:
            break
         p = p.next
         rslvAllowed = False

   @staticmethod
   def ResolversOk():
      Tab.resOk = True
      for sym in Symbol.nonterminals:
         Tab.curSy = sym;
         Tab.CheckRes(Tab.curSy.graph, False)
      return Tab.resOk

   #------------- check if every nts has a production --------------------

   @staticmethod
   def NtsComplete():
      complete = True
      for sym in Symbol.nonterminals:
         if sym.graph is None:
            complete = False
            Errors.count += 1
            print "  No production for " + sym.name
      return complete

   #-------------- check if every nts can be reached  -----------------

   @staticmethod
   def MarkReachedNts(p):
      assert isinstance( p, Node ) or (p is None)
      while p is not None:
         if p.typ == Node.nt and (p.sym.n not in Tab.visited):  # new nt reached
            Tab.visited.add(p.sym.n)
            Tab.MarkReachedNts(p.sym.graph)
         elif p.typ == Node.alt or p.typ == Node.iter or p.typ == Node.opt:
            Tab.MarkReachedNts(p.sub)
            if p.typ == Node.alt:
               Tab.MarkReachedNts(p.down)
         if p.up:
            break
         p = p.next

   @staticmethod
   def AllNtReached():
      ok = True
      Tab.visited = set( )
      Tab.visited.add(Tab.gramSy.n)
      Tab.MarkReachedNts(Tab.gramSy.graph)
      for sym in Symbol.nonterminals:
         if sym.n not in Tab.visited:
            ok = False
            Errors.count += 1
            print "  " + sym.name + " cannot be reached"
      return ok

   #--------- check if every nts can be derived to terminals  ------------

   @staticmethod
   def IsTerm( p, mark):
      '''true if graph can be derived to terminals'''
      assert isinstance( p,Node)
      assert isinstance(mark,set)
      while p is not None:
         if p.typ == Node.nt and (p.sym.n not in mark):
            return False
         if ( p.typ == Node.alt and not Tab.IsTerm(p.sub, mark)
              and ((p.down is None) or not Tab.IsTerm(p.down, mark))):
            return False
         if p.up:
            break
         p = p.next
      return True

   @staticmethod
   def AllNtToTerm():
      ok = True
      mark = set( )
      #a nonterminal is marked if it can be derived to terminal symbols

      changed = False
      for sym in Symbol.nonterminals:
         if (sym.n not in mark) and Tab.IsTerm(sym.graph, mark):
            mark.add(sym.n)
            changed = True

      while changed:
         changed = False
         for sym in Symbol.nonterminals:
            if (sym.n not in mark) and Tab.IsTerm(sym.graph, mark):
               mark.add(sym.n)
               changed = True

      for sym in Symbol.nonterminals:
         if sym.n not in mark:
            ok = False
            Errors.count += 1
            print "  " + sym.name + " cannot be derived to terminals"
      return ok

   #---------------------------------------------------------------------
   #  Utility functions
   #---------------------------------------------------------------------

   @staticmethod
   def Num(p):
      if p is None:
         return 0
      else:
         return p.n

   @staticmethod
   def PrintSet( aSet, indent ):
      assert isinstance( indent, int )

      col = indent

      for sym in Symbol.terminals:
         if sym.n in aSet:
            ln = len(sym.name)
            if col + ln >= 80:
               Trace.WriteLine( )
               col = 1
               while col < indent:
                  Trace.Write(' ')
                  col += 1
            Trace.Write(sym.name + " ")
            col += ln + 1
      if col == indent:
         Trace.Write("-- empty set --")
      Trace.WriteLine( )

   tKind = ["fixedToken   ", "classToken   ", "litToken     ", "classLitToken"]

   @staticmethod
   def PrintSym(sym):
      assert isinstance(sym,Symbol)
      Trace.Write(str(sym.n), 3)
      Trace.Write(" ")
      Trace.Write(Node.Name(sym.name), -14)
      Trace.Write(" ")
      Trace.Write(Node.nTyp[sym.typ], 2)
      if sym.attrPos is None:
         Trace.Write(" false ")
      else:
         Trace.Write(" true  ")
      if sym.typ == Node.nt:
         Trace.Write(str(Tab.Num(sym.graph)), 5)
         if sym.deletable:
            Trace.Write(" true  ")
         else:
            Trace.Write(" false ")
      else:
         Trace.Write("            ")
      Trace.Write(str(sym.line), 5)
      Trace.Write(" " + Tab.tKind[sym.tokenKind].strip());
      if (sym.typ == Node.pr or sym.typ == Node.t) and (sym.symName is not None):
         Trace.Write("   " + sym.symName)
      Trace.WriteLine()

   @staticmethod
   def PrintSymbolTable():
      Trace.WriteLine("Symbol Table:")
      Trace.WriteLine("------------")
      Trace.WriteLine()
      Trace.WriteLine(" nr name          typ  hasAt graph  del    line tokenKind")
      for sym in Symbol.terminals:
         Tab.PrintSym(sym)
      for sym in Symbol.pragmas:
         Tab.PrintSym(sym)
      for sym in Symbol.nonterminals:
         Tab.PrintSym(sym)
      Trace.WriteLine()
      Trace.WriteLine("Literal Tokens:")
      Trace.WriteLine("--------------")
      for me_key, me_value in Tab.literals.iteritems():
         Trace.WriteLine("_" + me_value.name + " = " + me_key + ".");
      Trace.WriteLine()

   @staticmethod
   def XRef():
      tab = { }
      for sym in Symbol.nonterminals:
         if sym in tab:
            lst = tab[ sym ]
         else:
            lst = [ ]
            tab[sym] = lst
         lst.append( -sym.line )

      # collect lines where symbols have been referenced
      for n in Node.nodes:
         if n.typ in (Node.t, Node.wt, Node.nt):
            if n.sym in tab:
               lst = tab[ n.sym ]
            else:
               lst = [ ]
               tab[n.sym] = lst
            lst.append(n.line)

      # print cross reference list
      Trace.WriteLine("Cross reference list:")
      Trace.WriteLine("--------------------")
      Trace.WriteLine( )
      keyList = [ x.name for x in tab.keys() ]
      keyList.sort( )
      for key in keyList:
         for k in tab.keys( ):
            if k.name == key:
               sym = k
               break

         Trace.Write("  ")
         Trace.Write(Node.Name(sym.name), -12)
         lst = tab[sym]
         col = 14
         for line in lst:
            if col + 5 > 80:
               Trace.WriteLine()
               for col in xrange(1,15):
                  Trace.Write(" ");
            Trace.Write(str(line), 5)
            col += 5
         Trace.WriteLine()
      Trace.WriteLine()
      Trace.WriteLine()

   @staticmethod
   def SetDDT(s):
      options = { 'traceAutomaton':     0,
                  'generateDriver':    11,
                  'firstAndFollow':     1,
                  'syntaxGraph':        2,
                  'traceComputations':  3,
                  'listAnyAndSync':     4,
                  'mergeErrors':        5,
                  'tokenNames':        10,
                  'statistics':         8,
                  'symbolTable':        6,
                  'testOnly':           9,
                  'crossReferences':    7 }
      for key,value in options.iteritems( ):
         if s.__dict__[ key ]:
            Tab.ddt[ value ] = True

   @staticmethod
   def Init():
      Tab.eofSy = Symbol( Node.t, 'EOF', 0 )
      Tab.literals  = { }

   # considerable extension from here on to handle name generation

   @staticmethod
   def NewName(alias,name):
      assert isinstance( alias, str )
      assert isinstance( name, str )
      if name.find(' ') >= 0:
         Errors.SemErr("tokens must not contain blanks")
      u = UserDefinedTokenName(alias, name)

   @staticmethod
   def Ascii(ch):
      assert isinstance(ch, (str,unicode))
      name = {
          chr( 0) : "nul",
          chr( 1) : "soh",
          chr( 2) : "stx",
          chr( 3) : "etx",
          chr( 4) : "eot",
          chr( 5) : "enq",
          chr( 6) : "ack",
          chr( 7) : "bel",
          chr( 8) : "bs",
          chr( 9) : "ht",
          chr(10) : "lf",
          chr(11) : "vt",
          chr(12) : "ff",
          chr(13) : "cr",
          chr(14) : "so",
          chr(15) : "si",
          chr(16) : "dle",
          chr(17) : "dc1",
          chr(18) : "dc2",
          chr(19) : "dc3",
          chr(20) : "dc4",
          chr(21) : "nak",
          chr(22) : "syn",
          chr(23) : "etb",
          chr(24) : "can",
          chr(25) : "em",
          chr(26) : "sub",
          chr(27) : "esc",
          chr(28) : "fs",
          chr(29) : "gs",
          chr(30) : "rs",
          chr(31) : "us",
             ' '  : "_",
             '!'  : "bang",
             '\"' : "dquote",
             '#'  : "hash",
             '$'  : "dollar",
             '%'  : "percent",
             '&'  : "and",
             '\'' : "squote",
             '('  : "lparen",
             ')'  : "rparen",
             '*'  : "star",
             '+'  : "plus",
             ','  : "comma",
             '-'  : "minus",
             '.'  : "point",
             '/'  : "slash",
             '0'  : "d0",
             '1'  : "d1",
             '2'  : "d2",
             '3'  : "d3",
             '4'  : "d4",
             '5'  : "d5",
             '6'  : "d6",
             '7'  : "d7",
             '8'  : "d8",
             '9'  : "d9",
             ':'  : "colon",
             ';'  : "semicolon",
             '<'  : "less",
             '='  : "equal",
             '>'  : "greater",
             '?'  : "query",
             '@'  : "at",
             '['  : "lbrack",
             '\\' : "backslash",
             ']'  : "rbrack",
             '^'  : "uparrow",
             '_'  : "underscore",
             '`'  : "accent",
             '{'  : "lbrace",
             '|'  : "bar",
             '}'  : "rbrace",
             '~'  : "tilde",
         chr(127) : "delete" }
      if ch in name:
         return name[ch]
      else:
         return "ASC" + str(ch)

   @staticmethod
   def SymName(name):
      assert isinstance( name, (str,unicode) )
      name = str(name)
      for u in UserDefinedTokenName.NameTab:
         if name == u.name:
            return u.alias
      if name[0] == '"':
         name = DFA.Unescape(name[1:-1])
      S = ''
      for i in xrange(0,len(name)):
         ch = name[i]
         if ('a' <= ch <= 'z' or 'A' <= ch <= 'Z'
               or '0' <= ch <= '9' and i > 0):
            S += ch
         else:
            S += Tab.Ascii(ch)
      S += '_Sym'
      return S

   @staticmethod
   def AssignNames():
      for sym in Symbol.terminals:
         sym.symName = Tab.SymName( sym.name )
      for sym in Symbol.pragmas:
         sym.symName = Tab.SymName(sym.name);
      Symbol.terminals[0].symName = 'EOF_SYM'
      Symbol.terminals[ len(Symbol.terminals)-1 ].symName = 'NOT_SYM'
      sys.stdout.write( " (Names assigned)" )

class DFA( object ):
   maxStates = 0
   EOF = -1
   CR  = '\r'
   LF  = '\n'

   firstState = None   # State
   lastState = None    # State,  last allocated state
   lastSimState = 0    # last non melted state
   fram = None         # Reader, scanner frame input
   gen = None          # PrintWriter,  generated scanner file
   curSy = None        # Symbol, current token to be recognized (in FindTrans)
   curGraph = None     # Node, start of graph for current token (in FindTrans)
   ignoreCase = False  # true if input should be treated case-insensitively
   dirtyDFA = False    # DFA may become nondeterministic in MatchedDFA
   hasCtxMoves = False # DFA has context transitions
   srcName = ''        # name of the attributed grammar file
   srcDir = ''         # directory of attributed grammar file

   @staticmethod
   def framRead():
      try:
         return DFA.fram.read(1)
      except:
         raise RuntimeError("-- error reading Scanner.frame")
      return DFA.EOF

        #---------- Output primitives
   @staticmethod
   def Ch(ch):
      if isinstance(ch, int):
         ch = str( ch )
      if ch < ' ' or ch >= str(127) or ch == '\'' or ch == '\\':
         return ch
      else:
         return "ord('" + ch + "')"
      #if isinstance(ch, (str,unicode)):
         #ch = ord(ch)
      #if (ch < ord(' ') or ch >= 127 or ch == ord('\'') or ch == ord('\\')):
         #return str(ch)
      #else:
         #return "ord('" + chr(ch) + "')"

   @staticmethod
   def ReportCh(ch):
      if isinstance(ch, (str,unicode)):
         ch = ord(ch)
      if (ch < ord(' ') or ch >= 127 or ch == ord('\'') or ch == ord('\\')):
         return str(ch)
      else:
         return ''.join( [ "'", chr(ch), "'" ] )

   @staticmethod
   def ChCond(ch, relOpStr='=='):
      if isinstance(ch, (str,unicode)):
         ch = ord(ch)

      if (ch < ord(' ') or ch >= 127 or ch == ord('\'') or ch == ord('\\')):
         return ''.join( [ 'ord(self.ch) ', relOpStr, " ", str(ch) ] )
      else:
         return ''.join( [ 'self.ch ', relOpStr, " '", chr(ch), "'" ] )

   @staticmethod
   def PutRange(s):
      assert isinstance(s, set)
      lo = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
      hi = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
      # fill lo and hi
      mx = CharClass.charSetSize
      top = -1
      i = 0
      while i < mx:
         if i in s:
            top += 1
            lo[top] = i
            i += 1
            while i < mx and (i in s):
               i += 1
            hi[top] = i-1
         else:
            i += 1
      # print ranges
      if top == 1 and lo[0] == 0 and hi[1] == mx-1 and hi[0]+2 == lo[1]:
         s1 = set( )
         s1.add(hi[0]+1)
         DFA.gen.write("not ")
         DFA.PutRange(s1)
         DFA.gen.write(" and Scanner.ch != Scanner.buffer.EOF")
      else:
         DFA.gen.write("(")

         for i in xrange( 0, top+1 ):
            if hi[i] == lo[i]:
               DFA.gen.write( DFA.ChCond( lo[i] ) )
            elif (lo[i] == 0):
               DFA.gen.write( DFA.ChCond( hi[i], '<=' ) )
            else:
               DFA.gen.write( DFA.ChCond( lo[i], '>=' ) )
               DFA.gen.write( ' and ' + DFA.ChCond( hi[i], '<=' ) )
            if i < top:
               DFA.gen.write('\n')
               DFA.gen.write("                 or ")
         if 'ANYCHAR' in s:
            DFA.gen.write(' or ord(self.ch) > %d' % CharClass.charSetSize)
         DFA.gen.write(")")

        #---------- String handling
   @staticmethod
   def Hex2Char(s):
      assert isinstance( s, (str,unicode) )
      val = 0   # int
      for i in xrange(0,len(s)):
         ch = s[i]               # char
         if '0' <= ch <= '9':
            val = 16 * val + (ord(ch) - ord('0'))
         elif 'a' <= ch <= 'f':
            val = 16 * val + (10 + ord(ch) - ord('a'))
         elif 'A' <= ch <= 'F':
            val = 16 * val + (10 + ord(ch) - ord('A'))
         else:
            Errors.SemErr("bad escape sequence in string or character")
      if val > CharClass.charSetSize:
         Errors.SemErr("bad escape sequence in string or character")
      return chr(val % CharClass.charSetSize)

   @staticmethod
   def Char2Hex( ch):
      assert isinstance(ch,(str,unicode))
      hx = hex(ord(ch))
      for i in xrange(len(hx), 4):
         hx = '0' + hx;
      return "\\u" + hx;

   @staticmethod
   def Unescape (s):
      # replaces escape sequences in s by their Unicode values.
      assert isinstance( s, (str,unicode) )
      buf = ''
      i = 0
      while i < len(s):
         if s[i] == '\\':
            ch = s[i+1]
            if ch in ( 'u', 'x' ):
               if i + 4 <= len(s):
                  buf += DFA.Hex2Char(s[i+2: i+6])
                  i += 6
               else:
                  Errors.SemErr("bad escape sequence in string or character")
                  i = len(s)
            elif ch in ( '\\', '\'', '\"', 'r', 'n', 't', '0', 'a', 'b', 'f'):
               buf += { '\\': '\\',
                        '\'': '\'',
                        '\"': '\"',
                        'r' : '\r',
                        'n' : '\n',
                        't' : '\t',
                        '0' : '\0',
			'a' : '\a',
                        'b' : '\b',
                        'f' : '\f' } [ s[i+1] ]
               i += 2
            else:
               Errors.SemErr("bad escape sequence in string or character")
               i += 2
         else:
            buf += s[i]
            i += 1
      return buf

   @staticmethod
   def Escape(s):
      assert isinstance(s, (str,unicode))
      buf = ''
      for ch in s:
         if ch in ('\\', '\'', '\"', '\t', '\r', '\n'):
            buf += { '\\': "\\\\",
                     '\'': "\\'",
                     '\"': "\\\"",
                     '\t': "\\t",
                     '\r': "\\r",
                     '\n': "\\n" }[ ch ]
         elif ch < ' ' or ch > chr(127): #'\x7f'
            buf += DFA.Char2Hex(ch)
         else:
            buf += ch
      return buf

#---------- State handling
   @staticmethod
   def NewState():
      s = State()   # State
      if DFA.firstState is None:
         DFA.firstState = s
      else:
         DFA.lastState.next = s
      DFA.lastState = s
      return s

   @staticmethod
   def NewTransition( frm,  to,  typ,  sym,  tc):
      assert isinstance(frm,State)
      assert isinstance(to,State)
      assert isinstance(typ,int)
      assert isinstance(sym,(int,str,unicode))
      assert isinstance(tc,int)
      if to == DFA.firstState:
         Errors.SemErr("token must not start with an iteration")
      if isinstance(sym, (str,unicode)):
         sym = ord(sym)
      t = Target(to)
      a = Action(typ, sym, tc)
      a.target = t
      frm.AddAction(a)
      if typ == Node.clas:
         DFA.curSy.tokenKind = Symbol.classToken

   @staticmethod
   def CombineShifts():
      state = DFA.firstState
      while state is not None:
         a = state.firstAction
         while a is not None:
            b = a.next;
            while b is not None:
               if a.target.state == b.target.state and a.tc == b.tc:
                  seta = a.Symbols()
                  setb = b.Symbols()
                  seta |= setb
                  a.ShiftWith(seta)
                  c = b
                  b = b.next
                  state.DetachAction(c)
               else:
                  b = b.next
            a = a.next
         state = state.next

   @staticmethod
   def FindUsedStates( state,  used):
      assert isinstance(state,State)
      assert isinstance(used,set)
      if state.nr in used:
         return
      used.add(state.nr)
      a = state.firstAction
      while a is not None:
         DFA.FindUsedStates(a.target.state, used)
         a = a.next

   @staticmethod
   def DeleteRedundantStates():
      newState = [ None for x in xrange(State.lastNr + 1) ]
      used = set( )
      DFA.FindUsedStates(DFA.firstState, used)
      # combine equal final states
      s1 = DFA.firstState.next
      while s1 is not None:
         # DFA.firstState cannot be final
         if ((s1.nr in used) and (s1.endOf is not None)
              and (s1.firstAction is None) and not s1.ctx):
            s2 = s1.next
            while s2 is not None:
               nots2_ctx = 1 if not s2.ctx else 0
               if ((s2.nr in used) and s1.endOf == s2.endOf and (s2.firstAction is None) & nots2_ctx):
                  used.discard(s2.nr)
                  newState[s2.nr] = s1
               s2 = s2.next
         s1 = s1.next

      state = DFA.firstState
      while state is not None:
         if state.nr in used:
            a = state.firstAction
            while a is not None:
               if a.target.state.nr not in used:
                  a.target.state = newState[a.target.state.nr]
               a = a.next
         state = state.next

      # delete unused states
      DFA.lastState = DFA.firstState
      State.lastNr = 0     # DFA.firstState has number 0
      state = DFA.firstState.next
      while state is not None:
         if state.nr in used:
            State.lastNr += 1
            state.nr = State.lastNr
            DFA.lastState = state
         else:
            DFA.lastState.next = state.next
         state = state.next

   @staticmethod
   def TheState(p):
      assert isinstance(p, Node) or (p is None)
      if p is None:
         state = DFA.NewState()
         state.endOf = DFA.curSy
         return state
      else:
         return p.state

   @staticmethod
   def Step( frm, p, stepped):
      assert isinstance(frm,State)
      assert isinstance(p,Node) or (p is None)
      assert isinstance(stepped,set)
      if p is None:
         return
      stepped.add(p.n)
      if p.typ in (Node.clas, Node.chr):
         DFA.NewTransition(frm, DFA.TheState(p.next), p.typ, p.val, p.code)
      elif p.typ == Node.alt:
         DFA.Step(frm, p.sub, stepped)
         DFA.Step(frm, p.down, stepped)
      elif p.typ in (Node.iter, Node.opt):
         if (p.next is not None) and (p.next.n not in stepped):
            DFA.Step(frm, p.next, stepped)
         DFA.Step(frm, p.sub, stepped)

   @staticmethod
   def NumberNodes(p, state):
      '''Assigns a state n.state to every node n. There will be a transition
      from n.state to n.next.state triggered by n.val. All nodes in an
      alternative chain are represented by the same state.'''
      assert isinstance(p, Node) or (p is None)
      assert isinstance(state,State) or (state is None)
      if p is None:
         return
      if p.state is not None:
         return
      if state is None:
         state = DFA.NewState()
      p.state = state
      if Node.DelGraph(p):
         state.endOf = DFA.curSy
      if p.typ in (Node.clas, Node.chr):
         DFA.NumberNodes(p.next, None)
      elif p.typ == Node.opt:
         DFA.NumberNodes(p.next, None)
         DFA.NumberNodes(p.sub, state)
      elif p.typ == Node.iter:
         DFA.NumberNodes(p.next, state)
         DFA.NumberNodes(p.sub, state)
      elif p.typ == Node.alt:
         DFA.NumberNodes(p.sub, state)
         DFA.NumberNodes(p.down, state)

   @staticmethod
   def FindTrans (p, start, marked):
      assert isinstance(p,Node) or (p is None)
      assert isinstance(start,bool)
      assert isinstance(marked,set)
      if (p is None) or (p.n in marked):
         return
      marked.add(p.n)
      if start:
         DFA.Step(p.state, p, set( )) #/ start of group of equally numbered nodes
      if p.typ in (Node.clas, Node.chr):
         DFA.FindTrans(p.next, True, marked)
      elif p.typ == Node.opt:
         DFA.FindTrans(p.next, True, marked)
         DFA.FindTrans(p.sub, False, marked)
      elif p.typ == Node.iter:
         DFA.FindTrans(p.next, False, marked)
         DFA.FindTrans(p.sub, False, marked)
      elif p.typ == Node.alt:
         DFA.FindTrans(p.sub, False, marked)
         DFA.FindTrans(p.down, False, marked)

   @staticmethod
   def ConvertToStates(p, sym):
      assert isinstance(p,Node)
      assert isinstance(sym,Symbol)
      DFA.curGraph = p
      DFA.curSy = sym
      if Node.DelGraph(DFA.curGraph):
         Errors.SemErr("token might be empty")
      DFA.NumberNodes(DFA.curGraph, DFA.firstState)
      DFA.FindTrans(DFA.curGraph, True, set( ))

   @staticmethod
   def MatchLiteral(s, sym):
      assert isinstance(sym,Symbol)
      assert isinstance(s,(str,unicode))
      '''match string against current automaton; store it either as a
      fixedToken or as a litToken'''
      s = DFA.Unescape(s[1:-1])
      ln = len(s)
      state = DFA.firstState   # State
      a = None
      endedPrematurely = False
      for i in xrange(0, ln):    # try to match s against existing DFA
         a = state.TheAction(s[i])
         if a is None:
            endedPrematurely = True
            break
         state = a.target.state
      if not endedPrematurely:
         i = ln
      # if s was not totally consumed or leads to a non-final state => make new DFA from it
      if  (i != ln) or (state.endOf is None):
         state = DFA.firstState
         i = 0
         a = None
         DFA.dirtyDFA = True
      while i < ln:      # make new DFA for s[i..len-1]
         to = DFA.NewState()   # State
         DFA.NewTransition(state, to, Node.chr, s[i], Node.normalTrans)
         state = to
         i += 1
      matchedSym = state.endOf   # Symbol
      if state.endOf is None:
         state.endOf = sym
      elif (matchedSym.tokenKind == Symbol.fixedToken) or (a is not None) and (a.tc == Node.contextTrans):
         # s matched a token with a fixed definition or a token with an appendix that will be cut off
         Errors.SemErr("tokens " + sym.name + " and " + matchedSym.name + " cannot be distinguished");
      else:
         # matchedSym == classToken or classLitToken
         matchedSym.tokenKind = Symbol.classLitToken
         sym.tokenKind = Symbol.litToken

   @staticmethod
   def SplitActions( state, a, b):
      assert isinstance(state,State)
      assert isinstance(a, Action)
      assert isinstance(b, Action)
      seta = a.Symbols()
      setb = b.Symbols()
      if seta == setb: #seta.equals(setb):
         a.AddTargets(b)
         state.DetachAction(b)
      elif seta >= setb:
         setc = copy.copy(seta)
         setc -= setb
         b.AddTargets(a)
         a.ShiftWith(setc)
      elif setb >= seta:
         setc = copy.copy(setb)
         setc -= seta
         a.AddTargets(b)
         b.ShiftWith(setc)
      else:
         setc = copy.copy(seta)
         setc &= setb
         seta -= setc
         setb -= setc
         a.ShiftWith(seta)
         b.ShiftWith(setb)
         c = Action(0, 0, Node.normalTrans)  # typ and sym are set in ShiftWith
         c.AddTargets(a)
         c.AddTargets(b)
         c.ShiftWith(setc)
         state.AddAction(c)

   @staticmethod
   def Overlap(a, b):
      assert isinstance(a, Action)
      assert isinstance(b, Action)
      if a.typ == Node.chr:
         if (b.typ == Node.chr):
            return a.sym == b.sym
         else:
            setb = CharClass.Set(b.sym)
            return a.sym in setb
      else:
         seta = CharClass.Set(a.sym)
         if b.typ == Node.chr:
            return b.sym in seta
         else:
            setb = CharClass.Set(b.sym)
            return len(seta & setb) > 0
            #return seta.intersects( setb )

   @staticmethod
   def MakeUnique( state):
      assert isinstance(state,State)
      # return True if actions were split
      changed = False   # boolean
      a = state.firstAction
      while a is not None:
         b = a.next
         while b is not None:
            if DFA.Overlap(a, b):
               DFA.SplitActions(state, a, b)
               changed = True
            b = b.next
         a = a.next
      return changed

   @staticmethod
   def MeltStates( state):
      assert isinstance(state,State)
      action = state.firstAction
      while action is not None:
         if action.target.next is not None:
            param = [None,None]
            ctx = action.GetTargetStates(param)
            targets = param[0]
            endOf = param[1]
            melt = Melted.StateWithSet(targets)   # Melted
            if melt is None:
               s = DFA.NewState()
               s.endOf = endOf
               s.ctx = ctx
               targ = action.target
               while targ is not None:
                  s.MeltWith(targ.state)
                  targ = targ.next
               changed = DFA.MakeUnique(s)
               while changed:
                  changed = DFA.MakeUnique(s)
               melt = Melted(targets, s)
            action.target.next = None
            action.target.state = melt.state
         action = action.next

   @staticmethod
   def FindCtxStates():
      state = DFA.firstState
      while state is not None:
         a = state.firstAction
         while a is not None:
            if a.tc == Node.contextTrans:
               a.target.state.ctx = True
            a = a.next
         state = state.next

   @staticmethod
   def MakeDeterministic():
      DFA.lastSimState = DFA.lastState.nr
      DFA.maxStates = 2 * DFA.lastSimState     # heuristic for set size in Melted.set
      DFA.FindCtxStates()
      state = DFA.firstState
      while state is not None:
         changed = DFA.MakeUnique(state)
         while changed:
            changed = DFA.MakeUnique(state)
         state = state.next

      state = DFA.firstState
      while state is not None:
         DFA.MeltStates(state)
         state = state.next
      DFA.DeleteRedundantStates()
      DFA.CombineShifts()

   @staticmethod
   def PrintStates( ):
      Trace.WriteLine( )
      Trace.WriteLine("Automaton Trace:")
      Trace.WriteLine("---------------")
      Trace.WriteLine( )
      Trace.WriteLine("---------- states ----------")
      state = DFA.firstState
      while state is not None:
         first = True   # boolean
         if state.endOf is None:
            Trace.Write("               ")
         else:
            Trace.Write("E(" + Node.Name(state.endOf.name) + ")", 12)
         Trace.Write(str(state.nr) + ":", 4)
         if state.firstAction is None:
            Trace.WriteLine()
         action = state.firstAction
         while action is not None:
            if first:
               Trace.Write(" ")
               first = False
            else:
               Trace.Write("                    ")
            if (action.typ == Node.clas):
               Trace.Write(CharClass.classes[action.sym].name)
            else:
               Trace.Write(DFA.ReportCh(action.sym), 3)
            targ = action.target
            while targ is not None:
               Trace.Write(str(targ.state.nr), 4)
               targ = targ.next
            if action.tc == Node.contextTrans:
               Trace.WriteLine(" context")
            else:
               Trace.WriteLine( )
            action = action.next
         state = state.next
      Trace.WriteLine( )
      Trace.WriteLine("---------- character classes ----------")
      CharClass.WriteClasses( )

   @staticmethod
   def GenComBody2( com ):
      assert isinstance(com,Comment)
      DFA.gen.write      ("      while True:\n")
      DFA.gen.write      ("         if " + DFA.ChCond(com.stop[0]) + ":\n")
      if len(com.stop) == 1:
         DFA.gen.write   ("            level -= 1\n")
         DFA.gen.write   ("            if level == 0:\n")
         DFA.gen.write   ("               self.oldEols = self.line - line0\n")
         DFA.gen.write   ("               self.NextCh()\n")
         DFA.gen.write   ("               return True\n")
         DFA.gen.write   ("            self.NextCh()\n")
      else:
         DFA.gen.write   ("            self.NextCh()\n")
         DFA.gen.write   ("            if " + DFA.ChCond(com.stop[1]) + ":\n")
         DFA.gen.write   ("               level -= 1\n")
         DFA.gen.write   ("               if level == 0:\n")
         DFA.gen.write   ("                  self.oldEols = self.line - line0\n")
         DFA.gen.write   ("                  self.NextCh()\n")
         DFA.gen.write   ("                  return True\n")
         DFA.gen.write   ("               self.NextCh()\n")
      if com.nested:
         DFA.gen.write   ("         elif " + DFA.ChCond(com.start[0]) + ":\n")
         if (len(com.start) == 1):
            DFA.gen.write("            level += 1\n")
            DFA.gen.write("            self.NextCh()\n")
         else:
            DFA.gen.write("            self.NextCh()\n")
            DFA.gen.write("            if " + DFA.ChCond(com.start[1]) + ":\n")
            DFA.gen.write("               level += 1\n")
            DFA.gen.write("               self.NextCh()\n")
      DFA.gen.write      ("         elif self.ch == Buffer.EOF:\n")
      DFA.gen.write      ("            return False\n")
      DFA.gen.write      ("         else:\n")
      DFA.gen.write      ("            self.NextCh()\n")

   @staticmethod
   def GenComBody3( com):
      assert isinstance(com,Comment)
      DFA.gen.write      ("         while True:\n")
      DFA.gen.write      ("            if " + DFA.ChCond(com.stop[0]) + ":\n")
      if len(com.stop) == 1:
         DFA.gen.write   ("               level -= 1\n")
         DFA.gen.write   ("               if level == 0:\n")
         DFA.gen.write   ("                  self.oldEols = self.line - line0\n")
         DFA.gen.write   ("                  self.NextCh()\n")
         DFA.gen.write   ("                  return True\n")
         DFA.gen.write   ("               self.NextCh()\n")
      else:
         DFA.gen.write   ("               self.NextCh()\n")
         DFA.gen.write   ("               if " + DFA.ChCond(com.stop[1]) + ":\n")
         DFA.gen.write   ("                  level -= 1\n")
         DFA.gen.write   ("                  if level == 0:\n")
         DFA.gen.write   ("                     self.oldEols = self.line - line0\n")
         DFA.gen.write   ("                     self.NextCh()\n")
         DFA.gen.write   ("                     return True\n")
         DFA.gen.write   ("                  self.NextCh()\n")
      if com.nested:
         DFA.gen.write   ("            elif " + DFA.ChCond(com.start[0]) + ":\n")
         if (len(com.start) == 1):
            DFA.gen.write("               level += 1")
            DFA.gen.write("               self.NextCh()")
         else:
            DFA.gen.write("               self.NextCh()\n")
            DFA.gen.write("               if " + DFA.ChCond(com.start[1]) + ":\n")
            DFA.gen.write("                  level += 1\n")
            DFA.gen.write("                  self.NextCh()\n")
      DFA.gen.write      ("            elif self.ch == Buffer.EOF:\n")
      DFA.gen.write      ("               return False\n")
      DFA.gen.write      ("            else:\n")
      DFA.gen.write      ("               self.NextCh()\n")

   @staticmethod
   def GenComment( com, i):
      assert isinstance(com,Comment)
      assert isinstance(i, int)
      DFA.gen.write   ( '\n' )
      DFA.gen.write   ("   def Comment" + str(i) + "( self ):\n")
      DFA.gen.write   ("      level = 1\n")
      DFA.gen.write   ("      line0 = self.line\n")
      DFA.gen.write   ("      lineStart0 = self.lineStart\n")
      if len(com.start) == 1:
         DFA.gen.write("      self.NextCh()\n")
         DFA.GenComBody2(com)
      else:
         DFA.gen.write("      self.NextCh()\n")
         DFA.gen.write("      if " + DFA.ChCond(com.start[1]) + ":\n")
         DFA.gen.write("         self.NextCh()\n")
         DFA.GenComBody3(com)
         DFA.gen.write("      else:\n")
         DFA.gen.write("         if self.ch == Scanner.EOL:\n")
         DFA.gen.write("            self.line -= 1\n")
         DFA.gen.write("            self.lineStart = lineStart0\n")
         DFA.gen.write("         self.pos = self.pos - 2\n")
         DFA.gen.write("         self.buffer.setPos(self.pos+1)\n")
         DFA.gen.write("         self.NextCh()\n")
         DFA.gen.write("      return False\n")

   @staticmethod
   def CopyFramePart(stop):
      assert isinstance(stop,(str,unicode))
      last = 0;   # int
      startCh = stop[0]
      endOfStopString = len(stop) - 1
      ch = DFA.framRead()   # int

      while ch != DFA.EOF:
         if ch == startCh:
            i = 0
            if i == endOfStopString:
               return       # stop[0..i] found
            ch = DFA.framRead()
            i += 1
            while ch == stop[i]:
               if (i == endOfStopString):
                  return    # stop[0..i] found
               ch = DFA.framRead()
               i += 1
            # stop
            DFA.gen.write(stop[0:1])
         elif ch == DFA.LF:
            if last != DFA.CR:
               DFA.gen.write('\n')
            last = ch
            ch = DFA.framRead()
         elif (ch == DFA.CR):
            DFA.gen.write('\n')
            last = ch
            ch = DFA.framRead()
         else:
            if isinstance(chr, int):
               DFA.gen.write(chr(ch))
            else:
               DFA.gen.write(ch)
            last = ch
            ch = DFA.framRead()
      raise RuntimeError(" -- incomplete or corrupt scanner frame file")

   @staticmethod
   def SymName( sym):
      assert isinstance(sym,Symbol)
      if sym.name[0].isalpha( ):
         # real name value is stored in Tab.literals
         for me_key, me_value in Tab.literals.iteritems( ):
            if me_value == sym:
               return me_key
      return sym.name

   @staticmethod
   def GenLiterals( ):
      DFA.gen.write("lit = self.t.val")
      if (DFA.ignoreCase):
         DFA.gen.write(".lower()")
      DFA.gen.write( '\n' )
      first = True   # boolean
      for sym in Symbol.terminals:
         if (sym.tokenKind == Symbol.litToken):
            name = DFA.SymName(sym)   # String
            if DFA.ignoreCase:
               name = name.lower()
            # sym.name stores literals with quotes, e.g. "\"Literal\"",
            if (first):
               DFA.gen.write("      if ")
               first = False
            else:
               DFA.gen.write("      elif ")
            DFA.gen.write  ("lit == " + name + ":\n")
            DFA.gen.write  ("         self.t.kind = ")
            DFA.PrintTermName(sym)
            DFA.gen.write  ( '\n' )

   @staticmethod
   def WriteState( state):
      assert isinstance(state,State)
      endOf = state.endOf   # Symbol
      DFA.gen.write(str(state.nr) + ":\n")
      ctxEnd = state.ctx    # boolean
      action = state.firstAction
      while action is not None:
         if action == state.firstAction:
            DFA.gen.write  ("            if ")
         else:
            DFA.gen.write  ("            elif ")
         if (action.typ == Node.chr):
            DFA.gen.write  (DFA.ChCond(action.sym))
         else:
            DFA.PutRange(CharClass.Set(action.sym))
         DFA.gen.write     (":\n")
         if action.tc == Node.contextTrans:
            DFA.gen.write  ("               apx += 1\n")
            ctxEnd = False
         elif (state.ctx):
            DFA.gen.write  ("               apx = 0\n")
         if DFA.ignoreCase:
            DFA.gen.write  ("               buf += unicode(self.ch)\n")
         else:
            DFA.gen.write  ("               buf += unicode(self.ch)\n")
         DFA.gen.write     ("               self.NextCh()\n")
         DFA.gen.write     ("               state = " + str(action.target.state.nr) + '\n')
         action = action.next
      if state.firstAction is not None:
         DFA.gen.write     ("            else:\n")
      if ctxEnd:       # final context state: cut appendix
         DFA.gen.write('\n')
         DFA.gen.write("            self.pos = self.pos - apx - 1\n")
         DFA.gen.write("            self.line = self.t.line\n")
         DFA.gen.write("            self.buffer.setPos(self.pos+1)\n")
         DFA.gen.write("            self.NextCh()\n")
         #DFA.gen.write("            ")
      if state.firstAction is not None:
         if endOf is None:
            DFA.gen.write("               self.t.kind = Scanner.noSym\n");
            DFA.gen.write("               done = True\n")
         else:
            DFA.gen.write("               self.t.kind = ")
            DFA.PrintTermName(endOf)
            DFA.gen.write( '\n' )
            if endOf.tokenKind == Symbol.classLitToken:
               DFA.gen.write("               self.t.val = buf\n")
               DFA.gen.write("               self.CheckLiteral()\n");
               DFA.gen.write("               return self.t\n");
            else:
               DFA.gen.write("               done = True\n")
      else:
         if endOf is None:
            DFA.gen.write("            self.t.kind = Scanner.noSym\n")
            DFA.gen.write("            done = True\n")
         else:
            DFA.gen.write("            self.t.kind = ")
            DFA.PrintTermName(endOf)
            DFA.gen.write('\n')
            if endOf.tokenKind == Symbol.classLitToken:
               DFA.gen.write("            self.t.val = buf")
               DFA.gen.write("            self.CheckLiteral()\n")
               DFA.gen.write("            return self.t\n")
            else:
               DFA.gen.write("            done = True\n")

   @staticmethod
   def FillStartTab(startTab):
      assert isinstance( startTab, list )
      action = DFA.firstState.firstAction
      while action is not None:
         targetState = action.target.state.nr;   # int
         if action.typ == Node.chr:
            startTab[action.sym] = targetState
         else:
            s = CharClass.Set(action.sym)   # BitSet
            for i in xrange( 0, CharClass.charSetSize ):
               if i in s:
                  startTab[i] = targetState
         action = action.next

   @staticmethod
   def OpenGen(backUp):
      assert isinstance(backUp,bool)
      try:
         fn = DFA.srcDir + "Scanner.py"   # String
         if backUp and os.path.exists(fn):
            if os.path.exists(fn + '.old'):
               os.remove( fn + '.old' )
            os.rename( fn, fn + '.old' )
         DFA.gen = file( fn, 'w' )
      except:
         raise RuntimeError("-- Compiler Error: Cannot generate scanner file.")

   @staticmethod
   def WriteScanner( withNames):
      assert isinstance(withNames,bool)
      startTab = [ 0 for i in xrange(CharClass.charSetSize) ]
      fr = DFA.srcDir + "Scanner.frame"   # String
      if not os.path.exists( fr ):
         if Tab.frameDir is not None:
            fr = os.path.join( Tab.frameDir.strip(), "Scanner.frame" )
         if not os.path.exists(fr):
            raise RuntimeError("-- Compiler Error: Cannot find Scanner.frame")
      try:
         DFA.fram = file( fr, 'r' )
      except:
         raise RuntimeError("-- Compiler Error: Cannot open Scanner.frame.")
      DFA.OpenGen(True)
      if DFA.dirtyDFA:
         DFA.MakeDeterministic( )
      DFA.FillStartTab(startTab)
      DFA.CopyFramePart( "-->begin" )
      if not DFA.srcName.lower( ).endswith( 'coco.atg' ):
         DFA.gen.close()
         DFA.OpenGen(False)

      DFA.CopyFramePart("-->declarations")
      DFA.gen.write("   charSetSize = " + str(CharClass.charSetSize) + '\n')
      DFA.gen.write("   maxT = "        + str(len(Symbol.terminals) - 1) + '\n')
      DFA.gen.write("   noSym = "       + str(Tab.noSym.n) + '\n')
      if withNames:
         DFA.gen.write("   # terminals\n")
         for sym in Symbol.terminals:
            DFA.gen.write("   " + sym.symName + " = " + str(sym.n) + '\n')
         DFA.gen.write("   # pragmas\n")
         for sym in Symbol.pragmas:
            DFA.gen.write("   " + sym.symName + " = " + str(sym.n) + '\n')
         DFA.gen.write( '\n' )
      DFA.gen.write("   start = [\n")
      for i in xrange(0,CharClass.charSetSize / 16):
         DFA.gen.write("   ")
         for j in xrange(0,16):
            DFA.gen.write(Trace.formatString(str(startTab[16*i+j]), 3))
            DFA.gen.write(",")
         DFA.gen.write( '\n' )
      DFA.gen.write("     -1]\n")

      if DFA.ignoreCase:
         DFA.gen.write("   valCh = u''       # current input character (for token.val)")

      DFA.CopyFramePart("-->initialization")
      j = 0
      for i in Tab.ignored:
         DFA.gen.write("      self.ignore.add(" + str(i) + ") \n")

      DFA.CopyFramePart("-->casing")
      if DFA.ignoreCase:
         DFA.gen.write("      valCh = self.ch\n")
         DFA.gen.write("      if self.ch != Buffer.EOF:\n")
         DFA.gen.write("         self.ch = self.ch.lower()\n");

      DFA.CopyFramePart("-->comments")
      com = Comment.first   # Comment
      i = 0
      while com is not None:
         DFA.GenComment(com, i)
         com = com.next
         i += 1

      DFA.CopyFramePart("-->literals")
      DFA.GenLiterals()

      DFA.CopyFramePart("-->scan1")
      if Comment.first!=None:
         DFA.gen.write("if (")
         com = Comment.first
         i = 0
         while com is not None:
            DFA.gen.write(DFA.ChCond(com.start[0]))
            DFA.gen.write(" and self.Comment" + str(i) + "()")
            if com.next is not None:
               DFA.gen.write(" or ")
            com = com.next
            i += 1
         DFA.gen.write("):\n")
         DFA.gen.write("         return self.NextToken()\n")
      if DFA.hasCtxMoves:
         DFA.gen.write('\n')
         DFA.gen.write("      apx = 0")

      DFA.CopyFramePart("-->scan2")
      if DFA.ignoreCase:
         DFA.gen.write("buf += unicode(self.ch)\n")
         DFA.gen.write("      self.NextCh()\n")
      else:
         DFA.gen.write("buf += unicode(self.ch)\n")
         DFA.gen.write("      self.NextCh()\n")

      DFA.CopyFramePart("-->scan3")
      state = DFA.firstState.next
      while state is not None:
         DFA.gen.write("         elif state == ")
         DFA.WriteState(state)
         state = state.next
      DFA.CopyFramePart("$$$")
      DFA.gen.close()

   @staticmethod
   def Init ( file,  dir):
      assert isinstance(file,str)
      assert isinstance(dir,str)
      DFA.srcName = file
      DFA.srcDir = dir
      DFA.firstState = None
      DFA.lastState = None
      State.lastNr = -1;
      DFA.firstState = DFA.NewState()
      Melted.first = None
      Comment.first = None
      DFA.ignoreCase = False
      DFA.dirtyDFA = False
      DFA.hasCtxMoves = False

   @staticmethod
   def PrintTermName( sym):
      assert isinstance(sym,Symbol)
      if sym.symName is None:
         DFA.gen.write(str(sym.n))
      else:
         DFA.gen.write("Scanner.")
         DFA.gen.write(str(sym.symName))