Package lemon :: Package external :: Package gadfly :: Module kjParseBuild :: Class Ruleset
[show private | hide private]
[frames | no frames]

Class Ruleset


Ruleset class, used to compute NFA and then DFA for parsing based on
a list of rules.

Method Summary
  __init__(self, StartNonterm, Rulelist)
  compDFA(self)
compute DFA for ruleset by computing the E-closure of the NFA...
  compFirst(self)
method to compute prefixes and First sets for nonterminals...
  compFollow(self)
computing the Follow set for the ruleset the good news: I think it's correct.
  compFollowRule(self, Follow, R)
  compFollowRules(self, Follow)
  compSLRNFA(self)
compute an SLR NFA for the ruleset with states for each SLR "item" and transitions, eg: X > .AB on A maps to X > A.B on epsilon maps to A > .ZC and A > .WK an item is a pair (rulenumber, bodyposition) where body position 0 is interpreted to point before the beginning of the body.
  DoSLRGeneration(self)
do complete SLR DFA creation starting after initialization...
  DumpDFAsets(self)
  DumpFirstFollow(self)
  DumpItemSet(self, State)
  DumpSLRNFA(self)
dump the NFA...
  FirstOfTail(self, Rule, TailIndex, Token)
computing the "first" of the tail of a rule followed by an optional terminal.
  ItemDump(self, item)
dump an item...
  SLRFixDFA(self)
this function completes the computation of an SLR DFA by adding reduction states for each DFA state S containing item H > B.
  SLRItemIsFinal(self, item)
utility function -- returns true if an item is a final item...

Method Details

compDFA(self)

compute DFA for ruleset by computing the E-closure of the NFA

compFirst(self)

method to compute prefixes and First sets for nonterminals

compFollow(self)

computing the Follow set for the ruleset
the good news: I think it's correct.
the bad news: It's slower than it needs to be for epsilon cases.

compSLRNFA(self)

compute an SLR NFA for the ruleset with states for each SLR "item"
and transitions, eg:
    X > .AB
  on A maps to X > A.B
  on epsilon maps to A > .ZC
                 and A > .WK
an item is a pair (rulenumber, bodyposition)
where body position 0 is interpreted to point before the
beginning of the body.

SLR = "simple LR" in Aho+Ullman terminology

DoSLRGeneration(self)

do complete SLR DFA creation starting after initialization

DumpSLRNFA(self)

dump the NFA

FirstOfTail(self, Rule, TailIndex, Token=None)

computing the "first" of the tail of a rule followed by an optional
terminal.

doesn't include NULLTOKEN
requires self.First to be computed

ItemDump(self, item)

dump an item

SLRFixDFA(self)

this function completes the computation of an SLR DFA
by adding reduction states for each DFA state S containing
item   H > B.
which reduces rule H > B
for each token T in Follow of H.
if S already has a transition for T then there is a conflict!

assumes DFA and SLRNFA and Follow have been computed.

SLRItemIsFinal(self, item)

utility function -- returns true if an item is a final item

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