001: package fri.patterns.interpreter.parsergenerator.parsertables;
002:
003: import java.util.Hashtable;
004: import fri.patterns.interpreter.parsergenerator.syntax.Syntax;
005:
006: /**
007: Parser table generator for LR interpretation.
008: <p>
009: The init() method is overridden, as LR parsing does not need
010: FOLLOW-sets, and it needs nullability before building syntax nodes.
011:
012: @see fri.patterns.interpreter.parsergenerator.parsertables.SLRParserTables
013: @author (c) 2000, Fritz Ritzberger
014: */
015:
016: public class LRParserTables extends SLRParserTables {
017: /** Calls super. */
018: public LRParserTables(Syntax syntax) throws ParserBuildException {
019: super (syntax);
020: }
021:
022: /** Factory method: constructing a root node for LR syntax nodes. */
023: protected LRSyntaxNode createStartNode(Nullable nullable,
024: FirstSets firstSets) {
025: return new LRSyntaxNode(nullable, firstSets);
026: }
027:
028: /**
029: Modifiying the SLR-generation as FIRST-sets and Nullable are needed
030: before building syntax nodes, FOLLOW-sets are not needed at all.
031: */
032: protected void init() throws ParserBuildException {
033: Nullable nullable = new Nullable(syntax, nonterminals);
034: firstSets = new FirstSets(syntax, nullable, nonterminals);
035:
036: syntaxNodes = createStartNode(nullable, firstSets).build(
037: syntax, syntaxNodes, new Hashtable());
038:
039: gotoTable = generateGoto(syntaxNodes);
040:
041: parseTable = generateParseAction(syntaxNodes);
042: }
043:
044: /** Test main dumping parser tables. */
045: public static void main(String[] args) {
046: String[][] syntax = { { "S", "L", "'='", "R" }, { "S", "R" },
047: { "L", "'*'", "R" }, { "L", "'id'" }, { "R", "L", }, };
048:
049: try {
050: LRParserTables p = new LRParserTables(new Syntax(syntax));
051: p.dump(System.err);
052: } catch (Exception e) {
053: e.printStackTrace();
054: }
055: }
056:
057: }
058:
059: /*
060: (Rule 0) <START> :
061: (Rule 1) S : '=' R
062: (Rule 2) S :
063: (Rule 3) L : R
064: (Rule 4) L :
065: (Rule 5) R :
066:
067: FIRST(L) = ['*', 'id']
068: FIRST(S) = ['*', 'id']
069: FIRST(R) = ['*', 'id']
070: FIRST(<START>) = ['*', 'id']
071:
072: State 0
073: (Rule 0) <START> : .S LOOKAHEAD["EoI"] -> State 5
074: (Rule 1) S : .L '=' R LOOKAHEAD["EoI"] -> State 4
075: (Rule 2) S : .R LOOKAHEAD["EoI"] -> State 3
076: (Rule 3) L : .'*' R LOOKAHEAD["EoI"] -> State 2
077: (Rule 3) L : .'*' R LOOKAHEAD['='] -> State 2
078: (Rule 4) L : .'id' LOOKAHEAD["EoI"] -> State 1
079: (Rule 4) L : .'id' LOOKAHEAD['='] -> State 1
080: (Rule 5) R : .L LOOKAHEAD["EoI"] -> State 4
081:
082: State 1
083: (Rule 4) L : 'id' . ['=']
084: (Rule 4) L : 'id' . ["EoI"]
085:
086: State 2
087: (Rule 3) L : '*' .R LOOKAHEAD['='] -> State 6
088: (Rule 3) L : '*' .R LOOKAHEAD["EoI"] -> State 6
089: (Rule 3) L : .'*' R LOOKAHEAD["EoI"] -> State 2
090: (Rule 3) L : .'*' R LOOKAHEAD['='] -> State 2
091: (Rule 4) L : .'id' LOOKAHEAD["EoI"] -> State 1
092: (Rule 4) L : .'id' LOOKAHEAD['='] -> State 1
093: (Rule 5) R : .L LOOKAHEAD['='] -> State 7
094: (Rule 5) R : .L LOOKAHEAD["EoI"] -> State 7
095:
096: State 3
097: (Rule 2) S : R . ["EoI"]
098:
099: State 4
100: (Rule 1) S : L .'=' R LOOKAHEAD["EoI"] -> State 8
101: (Rule 5) R : L . ["EoI"]
102:
103: State 5
104: (Rule 0) <START> : S . ["EoI"]
105:
106: State 6
107: (Rule 3) L : '*' R . ['=']
108: (Rule 3) L : '*' R . ["EoI"]
109:
110: State 7
111: (Rule 5) R : L . ["EoI"]
112: (Rule 5) R : L . ['=']
113:
114: State 8
115: (Rule 1) S : L '=' .R LOOKAHEAD["EoI"] -> State 11
116: (Rule 3) L : .'*' R LOOKAHEAD["EoI"] -> State 10
117: (Rule 4) L : .'id' LOOKAHEAD["EoI"] -> State 9
118: (Rule 5) R : .L LOOKAHEAD["EoI"] -> State 12
119:
120: State 9
121: (Rule 4) L : 'id' . ["EoI"]
122:
123: State 10
124: (Rule 3) L : '*' .R LOOKAHEAD["EoI"] -> State 13
125: (Rule 3) L : .'*' R LOOKAHEAD["EoI"] -> State 10
126: (Rule 4) L : .'id' LOOKAHEAD["EoI"] -> State 9
127: (Rule 5) R : .L LOOKAHEAD["EoI"] -> State 12
128:
129: State 11
130: (Rule 1) S : L '=' R . ["EoI"]
131:
132: State 12
133: (Rule 5) R : L . ["EoI"]
134:
135: State 13
136: (Rule 3) L : '*' R . ["EoI"]
137:
138:
139: GOTO TABLE
140: ==========
141: | <START> S L R '=' '*' 'id'
142: ________________________________________________________________
143: 0 | - 5 4 3 - 2 1
144: 1 | - - - - - - -
145: 2 | - - 7 6 - 2 1
146: 3 | - - - - - - -
147: 4 | - - - - 8 - -
148: 5 | - - - - - - -
149: 6 | - - - - - - -
150: 7 | - - - - - - -
151: 8 | - - 12 11 - 10 9
152: 9 | - - - - - - -
153: 10 | - - 12 13 - 10 9
154: 11 | - - - - - - -
155: 12 | - - - - - - -
156: 13 | - - - - - - -
157:
158: PARSE-ACTION TABLE
159: ==================
160: | '=' '*' 'id' <EOF>
161: ________________________________________
162: 0 | - SH SH -
163: 1 | 4 - - 4
164: 2 | - SH SH -
165: 3 | - - - 2
166: 4 | SH - - 5
167: 5 | - - - AC
168: 6 | 3 - - 3
169: 7 | 5 - - 5
170: 8 | - SH SH -
171: 9 | - - - 4
172: 10 | - SH SH -
173: 11 | - - - 1
174: 12 | - - - 5
175: 13 | - - - 3
176:
177: */
|