001: package fri.patterns.interpreter.parsergenerator.parsertables;
002:
003: import fri.patterns.interpreter.parsergenerator.syntax.Syntax;
004:
005: /**
006: Parser table generator for LALR interpretation.
007:
008: @see fri.patterns.interpreter.parsergenerator.parsertables.LRParserTables
009: @author (c) 2000, Fritz Ritzberger
010: */
011:
012: public class LALRParserTables extends LRParserTables {
013: /** Calls super. */
014: public LALRParserTables(Syntax syntax) throws ParserBuildException {
015: super (syntax);
016: }
017:
018: /** Factory method: constructing a root node for LALR syntax nodes. */
019: protected LRSyntaxNode createStartNode(Nullable nullable,
020: FirstSets firstSets) {
021: return new LALRSyntaxNode(nullable, firstSets);
022: }
023:
024: /** Test main dumping parser tables. */
025: public static void main(String[] args) {
026: /*
027: String [][] syntax = {
028: { "EXPR", "TERM" },
029: { "EXPR", "EXPR", "'+'", "TERM" },
030: { "EXPR", "EXPR", "'-'", "TERM" },
031: { "TERM", "FAKT", },
032: { "TERM", "TERM", "'*'", "FAKT" },
033: { "TERM", "TERM", "'/'", "FAKT" },
034: { "FAKT", "\"[0-9]+\"", },
035: { "FAKT", "'('", "EXPR", "')'" },
036: };
037: */
038: String[][] syntax = { { "S", "L", "'='", "R" }, { "S", "R" },
039: { "L", "'*'", "R" }, { "L", "'id'" }, { "R", "L", }, };
040:
041: try {
042: LALRParserTables p = new LALRParserTables(
043: new Syntax(syntax));
044: p.dump(System.err);
045: } catch (Exception e) {
046: e.printStackTrace();
047: }
048: }
049:
050: }
051:
052: /*
053: (Rule 0) <START> :
054: (Rule 1) S : '=' R
055: (Rule 2) S :
056: (Rule 3) L : R
057: (Rule 4) L :
058: (Rule 5) R :
059:
060: FIRST(L) = ['*', 'id']
061: FIRST(S) = ['*', 'id']
062: FIRST(R) = ['*', 'id']
063: FIRST(<START>) = ['*', 'id']
064:
065: State 0
066: (Rule 0) <START> : .S LOOKAHEAD["EoI"] -> State 5
067: (Rule 1) S : .L '=' R LOOKAHEAD["EoI"] -> State 4
068: (Rule 2) S : .R LOOKAHEAD["EoI"] -> State 3
069: (Rule 3) L : .'*' R LOOKAHEAD['=', "EoI"] -> State 2
070: (Rule 4) L : .'id' LOOKAHEAD['=', "EoI"] -> State 1
071: (Rule 5) R : .L LOOKAHEAD["EoI"] -> State 4
072:
073: State 1
074: (Rule 4) L : 'id' . ['=', "EoI"]
075:
076: State 2
077: (Rule 3) L : '*' .R LOOKAHEAD['=', "EoI"] -> State 6
078: (Rule 3) L : .'*' R LOOKAHEAD['=', "EoI"] -> State 2
079: (Rule 4) L : .'id' LOOKAHEAD['=', "EoI"] -> State 1
080: (Rule 5) R : .L LOOKAHEAD['=', "EoI"] -> State 7
081:
082: State 3
083: (Rule 2) S : R . ["EoI"]
084:
085: State 4
086: (Rule 1) S : L .'=' R LOOKAHEAD["EoI"] -> State 8
087: (Rule 5) R : L . ["EoI"]
088:
089: State 5
090: (Rule 0) <START> : S . ["EoI"]
091:
092: State 6
093: (Rule 3) L : '*' R . ['=', "EoI"]
094:
095: State 7
096: (Rule 5) R : L . ['=', "EoI"]
097:
098: State 8
099: (Rule 1) S : L '=' .R LOOKAHEAD["EoI"] -> State 9
100: (Rule 3) L : .'*' R LOOKAHEAD["EoI"] -> State 2
101: (Rule 4) L : .'id' LOOKAHEAD["EoI"] -> State 1
102: (Rule 5) R : .L LOOKAHEAD["EoI"] -> State 7
103:
104: State 9
105: (Rule 1) S : L '=' R . ["EoI"]
106:
107:
108: GOTO TABLE
109: ==========
110: | <START> S L R '=' '*' 'id'
111: ________________________________________________________________
112: 0 | - 5 4 3 - 2 1
113: 1 | - - - - - - -
114: 2 | - - 7 6 - 2 1
115: 3 | - - - - - - -
116: 4 | - - - - 8 - -
117: 5 | - - - - - - -
118: 6 | - - - - - - -
119: 7 | - - - - - - -
120: 8 | - - 7 9 - 2 1
121: 9 | - - - - - - -
122:
123: PARSE-ACTION TABLE
124: ==================
125: | '=' '*' 'id' <EOF>
126: ________________________________________
127: 0 | - SH SH -
128: 1 | 4 - - 4
129: 2 | - SH SH -
130: 3 | - - - 2
131: 4 | SH - - 5
132: 5 | - - - AC
133: 6 | 3 - - 3
134: 7 | 5 - - 5
135: 8 | - SH SH -
136: 9 | - - - 1
137:
138: */
139:
140: /*
141: (Rule 0) <START> : EXPR
142: (Rule 1) EXPR : TERM
143: (Rule 2) EXPR : EXPR '+' TERM
144: (Rule 3) EXPR : EXPR '-' TERM
145: (Rule 4) TERM : FAKT
146: (Rule 5) TERM : TERM '*' FAKT
147: (Rule 6) TERM : TERM '/' FAKT
148: (Rule 7) FAKT : "[0-9]+"
149: (Rule 8) FAKT : '(' EXPR ')'
150:
151: FIRST(EXPR) = ["[0-9]+", '(']
152: FIRST(FAKT) = ["[0-9]+", '(']
153: FIRST(<START>) = ["[0-9]+", '(']
154: FIRST(TERM) = ["[0-9]+", '(']
155:
156: State 0
157: (Rule 0) <START> : .EXPR LOOKAHEAD["EoI"] -> State 2
158: (Rule 1) EXPR : .TERM LOOKAHEAD['+', '-', "EoI"] -> State 1
159: (Rule 2) EXPR : .EXPR '+' TERM LOOKAHEAD['+', '-', "EoI"] -> State 2
160: (Rule 3) EXPR : .EXPR '-' TERM LOOKAHEAD['+', '-', "EoI"] -> State 2
161: (Rule 4) TERM : .FAKT LOOKAHEAD['+', '-', '/', '*', "EoI"] -> State 4
162: (Rule 5) TERM : .TERM '*' FAKT LOOKAHEAD['+', '-', '/', '*', "EoI"] -> State 1
163: (Rule 6) TERM : .TERM '/' FAKT LOOKAHEAD['+', '-', '/', '*', "EoI"] -> State 1
164: (Rule 7) FAKT : ."[0-9]+" LOOKAHEAD['+', '-', '/', '*', "EoI"] -> State 5
165: (Rule 8) FAKT : .'(' EXPR ')' LOOKAHEAD['+', '-', '/', '*', "EoI"] -> State 3
166:
167: State 1
168: (Rule 1) EXPR : TERM . ['+', '-', ')', "EoI"]
169: (Rule 5) TERM : TERM .'*' FAKT LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 7
170: (Rule 6) TERM : TERM .'/' FAKT LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 6
171:
172: State 2
173: (Rule 0) <START> : EXPR . ["EoI"]
174: (Rule 2) EXPR : EXPR .'+' TERM LOOKAHEAD['+', '-', "EoI"] -> State 9
175: (Rule 3) EXPR : EXPR .'-' TERM LOOKAHEAD['+', '-', "EoI"] -> State 8
176:
177: State 3
178: (Rule 1) EXPR : .TERM LOOKAHEAD['+', '-', ')'] -> State 1
179: (Rule 2) EXPR : .EXPR '+' TERM LOOKAHEAD['+', '-', ')'] -> State 10
180: (Rule 3) EXPR : .EXPR '-' TERM LOOKAHEAD['+', '-', ')'] -> State 10
181: (Rule 4) TERM : .FAKT LOOKAHEAD['+', '-', ')', '/', '*'] -> State 4
182: (Rule 5) TERM : .TERM '*' FAKT LOOKAHEAD['+', '-', ')', '/', '*'] -> State 1
183: (Rule 6) TERM : .TERM '/' FAKT LOOKAHEAD['+', '-', ')', '/', '*'] -> State 1
184: (Rule 7) FAKT : ."[0-9]+" LOOKAHEAD['+', '-', ')', '/', '*'] -> State 5
185: (Rule 8) FAKT : '(' .EXPR ')' LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 10
186: (Rule 8) FAKT : .'(' EXPR ')' LOOKAHEAD['+', '-', ')', '/', '*'] -> State 3
187:
188: State 4
189: (Rule 4) TERM : FAKT . ['+', '-', ')', '/', '*', "EoI"]
190:
191: State 5
192: (Rule 7) FAKT : "[0-9]+" . ['+', '-', ')', '/', '*', "EoI"]
193:
194: State 6
195: (Rule 6) TERM : TERM '/' .FAKT LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 11
196: (Rule 7) FAKT : ."[0-9]+" LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 5
197: (Rule 8) FAKT : .'(' EXPR ')' LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 3
198:
199: State 7
200: (Rule 5) TERM : TERM '*' .FAKT LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 12
201: (Rule 7) FAKT : ."[0-9]+" LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 5
202: (Rule 8) FAKT : .'(' EXPR ')' LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 3
203:
204: State 8
205: (Rule 3) EXPR : EXPR '-' .TERM LOOKAHEAD['+', '-', ')', "EoI"] -> State 13
206: (Rule 4) TERM : .FAKT LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 4
207: (Rule 5) TERM : .TERM '*' FAKT LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 13
208: (Rule 6) TERM : .TERM '/' FAKT LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 13
209: (Rule 7) FAKT : ."[0-9]+" LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 5
210: (Rule 8) FAKT : .'(' EXPR ')' LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 3
211:
212: State 9
213: (Rule 2) EXPR : EXPR '+' .TERM LOOKAHEAD['+', '-', ')', "EoI"] -> State 14
214: (Rule 4) TERM : .FAKT LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 4
215: (Rule 5) TERM : .TERM '*' FAKT LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 14
216: (Rule 6) TERM : .TERM '/' FAKT LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 14
217: (Rule 7) FAKT : ."[0-9]+" LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 5
218: (Rule 8) FAKT : .'(' EXPR ')' LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 3
219:
220: State 10
221: (Rule 2) EXPR : EXPR .'+' TERM LOOKAHEAD['+', '-', ')'] -> State 9
222: (Rule 3) EXPR : EXPR .'-' TERM LOOKAHEAD['+', '-', ')'] -> State 8
223: (Rule 8) FAKT : '(' EXPR .')' LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 15
224:
225: State 11
226: (Rule 6) TERM : TERM '/' FAKT . ['+', '-', ')', '/', '*', "EoI"]
227:
228: State 12
229: (Rule 5) TERM : TERM '*' FAKT . ['+', '-', ')', '/', '*', "EoI"]
230:
231: State 13
232: (Rule 3) EXPR : EXPR '-' TERM . ['+', '-', ')', "EoI"]
233: (Rule 5) TERM : TERM .'*' FAKT LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 7
234: (Rule 6) TERM : TERM .'/' FAKT LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 6
235:
236: State 14
237: (Rule 2) EXPR : EXPR '+' TERM . ['+', '-', ')', "EoI"]
238: (Rule 5) TERM : TERM .'*' FAKT LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 7
239: (Rule 6) TERM : TERM .'/' FAKT LOOKAHEAD['+', '-', ')', '/', '*', "EoI"] -> State 6
240:
241: State 15
242: (Rule 8) FAKT : '(' EXPR ')' . ['+', '-', ')', '/', '*', "EoI"]
243:
244:
245: GOTO TABLE
246: ==========
247: | <START> EXPR TERM FAKT '+' '-' '*' '/' "[0-9]+ '(' ')'
248: ________________________________________________________________________________________________
249: 0 | - 2 1 4 - - - - 5 3 -
250: 1 | - - - - - - 7 6 - - -
251: 2 | - - - - 9 8 - - - - -
252: 3 | - 10 1 4 - - - - 5 3 -
253: 4 | - - - - - - - - - - -
254: 5 | - - - - - - - - - - -
255: 6 | - - - 11 - - - - 5 3 -
256: 7 | - - - 12 - - - - 5 3 -
257: 8 | - - 13 4 - - - - 5 3 -
258: 9 | - - 14 4 - - - - 5 3 -
259: 10 | - - - - 9 8 - - - - 15
260: 11 | - - - - - - - - - - -
261: 12 | - - - - - - - - - - -
262: 13 | - - - - - - 7 6 - - -
263: 14 | - - - - - - 7 6 - - -
264: 15 | - - - - - - - - - - -
265:
266: PARSE-ACTION TABLE
267: ==================
268: | '+' '-' '*' '/' "[0-9]+ '(' ')' <EOF>
269: ________________________________________________________________________
270: 0 | - - - - SH SH - -
271: 1 | 1 1 SH SH - - 1 1
272: 2 | SH SH - - - - - AC
273: 3 | - - - - SH SH - -
274: 4 | 4 4 4 4 - - 4 4
275: 5 | 7 7 7 7 - - 7 7
276: 6 | - - - - SH SH - -
277: 7 | - - - - SH SH - -
278: 8 | - - - - SH SH - -
279: 9 | - - - - SH SH - -
280: 10 | SH SH - - - - SH -
281: 11 | 6 6 6 6 - - 6 6
282: 12 | 5 5 5 5 - - 5 5
283: 13 | 3 3 SH SH - - 3 3
284: 14 | 2 2 SH SH - - 2 2
285: 15 | 8 8 8 8 - - 8 8
286:
287: */
|