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)
|
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.
-
|