Package lemon :: Package external :: Package gadfly :: Module kjParser :: Class ParserObj
[show private | hide private]
[frames | no frames]

Class ParserObj


the parse class:
  Based loosely on Aho+Ullman, Principles of Compiler Design, Ch.6.
   except that they don't describe how to handle boundary
   conditions, I made them up myself.

  Note: This could be implemented using just functions; it's implemented
   as a class to facilitate diagnostics and debugging in case of
   failures of various sorts.

a parse accepts
  a rule list

  a lexically analysed stream with methods
    stream.getmember()  returns the current token on the stream
    stream.next()  moves on to next token
    stream.more()     returns false if current token is the last token

  and a FSM (finite state machine) with methods
    FSM.root_nonTerminal
      the nonterminal at which to start parsing
    FSM.initial_state
      the initial state to start at
    FSM.successful_final_state
      the final state to go to upon successful parse
    FSM.map(Current_State,Current_Token)
      returns either
         (TERMFLAG, 0)
            if Current_State is terminal (final or reduction).
         (NOMATCHFLAG, 0)
            if Current_State is nonterminal, but the Current_Token
            and Next_Token do not lead to a valid state in the FSM
         (MOVETOFLAG, Next_State)
            if Current_State is nonterminal and Current_Token,
            Next_token map to Next_State from Current_State.
         (REDUCEFLAG, Rulenum)
            if Current_State indicates a reduction at Current_Token
            for rule Rule number Rule

   and a Stack with methods (replaced with dictionary)
         (init: {-1:0} )
      Stack.Top() returns top of stack (no pop)
         ( Stack[Stack[-1]] )
      Stack.Push(Object)
         ( Stack[-1]=Stack[-1]+1; Stack[Stack[-1]]=Object )
      Stack.MakeEmpty()
         ( Stack[-1]=0 )
      Stack.IsEmpty()
         ( Stack[-1] == 0 )
      Stack.Pop()
         ( Stack[-1] = Stack[-1]-1 )
      stack contents created by Parser will be of form (State,Value)
      where Value was inserted at FSM state State.
      Value of form either (KEYFLAG, Name)
                           (NontermName, reductionvalue)
                        or (TerminalName, value)

   and an optional parameter Evaluate which if 0 indicates that
      rules should be evaluated, otherwise indicates that rules
      should just be reduced and the reduction structure should
      be used as the result of the rule

rule objects must support methods
   Rule.reduce(Stack)
      pops off the elements corresponding to the body of the Rule
      from the stack and returns (NewStack,Red) where NewStack is
      the stack minus the body and Red is the result of evaluating the
      reduction function on this instance of the rule.
   Rule.Nonterm
      the nonterminal at the head of the rule

Method Summary
  __init__(self, Rulelist, Stream, FSM, Stack, Evaluate, Context)
  DoOneReduction(self)
DoOneReduction accepts tokens from the stream and pushes them onto the stack until a reduction state is reached.
  GO(self)
execute parsing until done...
  GotoState(self, rule)
compute the state to goto after a reduction is performed on a rule.
  ParseError(self, State, Token, *rest)
  StackDump(self, N)

Method Details

DoOneReduction(self)

DoOneReduction accepts tokens from the stream and pushes
them onto the stack until a reduction state is reached.

Resolve the reduction

GO(self)

execute parsing until done

GotoState(self, rule)

compute the state to goto after a reduction is performed on a rule.
Algorithm: determine the state at beginning of reduction
 and the next state indicated by the head nonterminal of the rule.
 special case: empty stack and root nonterminal > success.

Generated by Epydoc 2.0 on Mon Nov 10 15:07:47 2003 http://epydoc.sf.net