| java.lang.Object
 fri.patterns.interpreter.parsergenerator.parsertables.SLRSyntaxNode
All known Subclasses: fri.patterns.interpreter.parsergenerator.parsertables.LRSyntaxNode,
| SLRSyntaxNode | | class SLRSyntaxNode (Code) | | SLR bottom-up parser syntax node.
The build() method of an no-arg-constructed node is used to fill a
state node list. The empty list passed to build() will be filled
with all state nodes after.
Every syntax node provides a fill() method to populate the corresponding
line (node-index) within PARSE-ACTION and GOTO tables.
After construction the syntax node has state entries represented by
RuleStateItem instances.
The state of a rule is represented by a dot "." at start, between symbols,
or at end. To shift an item means to move the dot to left.
author:
(c) 2000, Fritz Ritzberger |
| Inner Class :protected class RuleStateItem | |
| Constructor Summary | |
| public | SLRSyntaxNode()
Do-nothing-constructor, used to call the build() method. |
| Method Summary | |
| protected void | addRulesDerivingPendingNonTerminal(RuleStateItem item, String nonterm, Syntax syntax, List todo)
Closure call for one rule state item. | | protected List | addShiftedItems(String symbol, Hashtable originatorEntries)
Adopt all rule-states from originator node, which have the passed symbol
as pending to the right of dot. | | public List | build(Syntax syntax, List syntaxNodes, Hashtable kernels)
Construction of start node and all further state nodes.
After this call the syntaxNodes list is filled with all state-bound nodes.
Parameters:
syntax - the grammar, including START rule.
Parameters:
syntaxNodes - ampty list that holds all syntax nodes after this call.
Parameters:
kernels - empty hashtable for internal buffering. | | protected void | closure(Syntax syntax)
Closure - do for all rule states:
Adopt all rules from grammar that derive one of the pending nonterminals
(right of dot) within entries list. | | protected RuleStateItem | createRuleStateItem(int ruleIndex, Rule rule)
Factory-method to create a RuleStateItem, to be overridden by other node types. | | protected SLRSyntaxNode | createSyntaxNode()
Factory-method to create a SLRSyntaxNode, to be overridden by other node types. | | public boolean | equals(Object o)
The count of kernel items must be equal. | | public Hashtable | fillGotoLine(int state)
Fill the line of GOTO table this state corresponds to. | | public Hashtable | fillParseActionLine(int state, FirstSets firstSets, FollowSets followSets)
Fill the line of PARSE-ACTION table this state corresponds to. | | protected void | generateSyntaxNodes(List syntaxNodes, Syntax syntax, Hashtable kernels)
Generates syntax nodes into passed list, whereby every node represents one possible state. | | protected void | generateSyntaxNodesFromItems(List syntaxNodes, Syntax syntax, Hashtable kernels)
Generates follower nodes from rule state items into list. | | protected List | getNontermShiftSymbols(FirstSets firstSets, String nonterm)
Returns all symbols for which SHIFT must be put into PARSE-ACTION table for a nonterminal. | | protected Iterator | getReduceSymbols(FollowSets followSets, RuleStateItem item)
Returns all symbols for which REDUCE must be put into PARSE-ACTION table. | | public int | hashCode()
Returns the hashcodes of all rule state items, associated by ^. | | protected void | linkParentItemToChild(RuleStateItem parent, int newIndex, List syntaxNodes, RuleStateItem child)
Store the follow state (node index) within rule state item. | | protected void | setParseTableLine(int state, Hashtable line, RuleStateItem item, Integer action, String terminal)
Set a position in PARSE-ACTION table. | | protected boolean | setTableLine(String table, int state, Hashtable line, RuleStateItem item, Integer action, String terminal)
Set a position in one of the tables. | | public String | toString()
Outputs this syntax node with all its rule state entries sorted. |
| SLRSyntaxNode | | public SLRSyntaxNode()(Code) | | Do-nothing-constructor, used to call the build() method.
|
| addRulesDerivingPendingNonTerminal | | protected void addRulesDerivingPendingNonTerminal(RuleStateItem item, String nonterm, Syntax syntax, List todo)(Code) | | Closure call for one rule state item. All rules in grammar that have passed
nonterm on left side get appended to todo list and put into item entries when not already in entries.
|
| addShiftedItems | | protected List addShiftedItems(String symbol, Hashtable originatorEntries)(Code) | | Adopt all rule-states from originator node, which have the passed symbol
as pending to the right of dot. This is done when a new node was generated,
which happens when the dot is moved to the right.
All adopted items together form the kernel of the syntax node.
The number of kernel items is calculated, which is important when searching
existing nodes.
Parameters:
symbol - the symbol that must be the pending symbol right of the dot within rule state item
Parameters:
originatorEntries - map containing all rule state items of the originator node (as value). a Tuple list containing pairs of original and new item, the new item is the shifted one. |
| build | | public List build(Syntax syntax, List syntaxNodes, Hashtable kernels)(Code) | | Construction of start node and all further state nodes.
After this call the syntaxNodes list is filled with all state-bound nodes.
Parameters:
syntax - the grammar, including START rule.
Parameters:
syntaxNodes - ampty list that holds all syntax nodes after this call.
Parameters:
kernels - empty hashtable for internal buffering. the syntaxNodes list, now filled. |
| closure | | protected void closure(Syntax syntax)(Code) | | Closure - do for all rule states:
Adopt all rules from grammar that derive one of the pending nonterminals
(right of dot) within entries list. This is done recursively, appending
new rules at end, so that they can adopt further rules.
The closure method calls addRulesDerivingPendingNonTerminal().
|
| createRuleStateItem | | protected RuleStateItem createRuleStateItem(int ruleIndex, Rule rule)(Code) | | Factory-method to create a RuleStateItem, to be overridden by other node types.
|
| createSyntaxNode | | protected SLRSyntaxNode createSyntaxNode()(Code) | | Factory-method to create a SLRSyntaxNode, to be overridden by other node types.
|
| equals | | public boolean equals(Object o)(Code) | | The count of kernel items must be equal. All kernel items must exist in passed node.
Parameters:
o - new node that contains only kernel items (which do not have dot at start). |
| fillGotoLine | | public Hashtable fillGotoLine(int state)(Code) | | Fill the line of GOTO table this state corresponds to.
Parameters:
state - the index of this state within list Hashtable with all terminals/nonterminals to handle, and their follower states. |
| fillParseActionLine | | public Hashtable fillParseActionLine(int state, FirstSets firstSets, FollowSets followSets)(Code) | | Fill the line of PARSE-ACTION table this state corresponds to.
Parameters:
state - the index of this state within list
Parameters:
firstSets - all FIRST-sets of all nonterminals
Parameters:
followSets - all FOLLOW-sets of all nonterminals Hashtable with all terminals to handle, and their actions. |
| generateSyntaxNodes | | protected void generateSyntaxNodes(List syntaxNodes, Syntax syntax, Hashtable kernels)(Code) | | Generates syntax nodes into passed list, whereby every node represents one possible state.
Every generated node gets appended to list and can generate new nodes by itself.
Parameters:
syntaxNodes - list of nodes
Parameters:
syntax - the grammar rules |
| generateSyntaxNodesFromItems | | protected void generateSyntaxNodesFromItems(List syntaxNodes, Syntax syntax, Hashtable kernels)(Code) | | Generates follower nodes from rule state items into list. The followers are referenced
by their originators (GOTO-references).
Parameters:
syntaxNodes - list of nodes
Parameters:
syntax - the grammar rules |
| getNontermShiftSymbols | | protected List getNontermShiftSymbols(FirstSets firstSets, String nonterm)(Code) | | Returns all symbols for which SHIFT must be put into PARSE-ACTION table for a nonterminal.
For SLR this is the FIRST set of the nonterminal.
|
| getReduceSymbols | | protected Iterator getReduceSymbols(FollowSets followSets, RuleStateItem item)(Code) | | Returns all symbols for which REDUCE must be put into PARSE-ACTION table.
For SLR this is the FOLLOW set of the nonterminal.
|
| hashCode | | public int hashCode()(Code) | | Returns the hashcodes of all rule state items, associated by ^. The result gets buffered on first call.
|
| linkParentItemToChild | | protected void linkParentItemToChild(RuleStateItem parent, int newIndex, List syntaxNodes, RuleStateItem child)(Code) | | Store the follow state (node index) within rule state item.
This is a sparate protected method as LALR nodes do further work here.
|
| setParseTableLine | | protected void setParseTableLine(int state, Hashtable line, RuleStateItem item, Integer action, String terminal)(Code) | | Set a position in PARSE-ACTION table.
This is the place where SHIFT/REDUCE and REDUCE/REDUCE conflicts are solved.
|
| setTableLine | | protected boolean setTableLine(String table, int state, Hashtable line, RuleStateItem item, Integer action, String terminal)(Code) | | Set a position in one of the tables.
Here SHIFT/SHIFT, SHIFT/REDUCE and REDUCE/REDUCE conflicts are detected.
true when no conflict was detected |
| toString | | public String toString()(Code) | | Outputs this syntax node with all its rule state entries sorted.
|
|
|