001: package fri.patterns.interpreter.parsergenerator.parsertables;
002:
003: import java.util.*;
004: import java.io.*;
005: import java.lang.reflect.*;
006: import fri.patterns.interpreter.parsergenerator.ParserTables;
007: import fri.patterns.interpreter.parsergenerator.Token;
008: import fri.patterns.interpreter.parsergenerator.syntax.*;
009:
010: /**
011: Base class for all parser tables. Default implementations.
012: <p>
013: Source generation method: <i>toSourceFile()</i>. Needed by <i>CompiledTables</i>,
014: used for buffering compiled table classes at runtime.
015: <p>
016: Dump methods to print human readable table contents. Dumping does not work on
017: buffered table objects (needs scratch build by constructor).
018:
019: @author (c) 2000, 2001, 2002 Fritz Ritzberger
020: */
021:
022: public abstract class AbstractParserTables implements ParserTables,
023: Serializable {
024: /** The raw syntax to apply on parsing. */
025: protected Syntax syntax;
026:
027: /** The GOTO-table with all possible follow states. As much lines as states and columns as terminals and nonterminals are present. */
028: protected List gotoTable;
029:
030: /** The PARSE-ACTION table with SHIFT and REDUCE entries. As much lines as states and as much columns as terminals are present. */
031: protected List parseTable;
032:
033: /** Non-terminals and terminals, without EPSILON, with START-symbol: column header of GOTO-table. */
034: protected transient List symbols = new ArrayList();
035:
036: /** Terminals, with EPSILON: column header of PARSE-ACTION table. */
037: protected transient List terminals = new ArrayList();
038:
039: /** Terminals, without EPSILON: tokens for the Lexer. */
040: protected List terminalsWithoutEpsilon = new ArrayList();
041:
042: /** Non-terminals, with START-symbol. */
043: protected transient List nonterminals = new ArrayList();
044:
045: /** Helper for the cell width of printed tables. Can be set manually if automatic result does not fit. */
046: public transient static int CELLWIDTH = 0;
047:
048: /** Serializable constructor. */
049: protected AbstractParserTables() {
050: }
051:
052: /**
053: Implements ParserTables: returns the next state from GOTO-table.
054: @param currentState curent state
055: @param symbol current terminal or nonterminal
056: @return new state
057: */
058: public Integer getGotoState(Integer currentState, String symbol) {
059: Integer state = null;
060: Map map = (Map) gotoTable.get(currentState.intValue());
061: if (map != null)
062: state = (Integer) map.get(symbol);
063: return state == null ? ParserTables.ERROR : state;
064: }
065:
066: /**
067: Implements ParserTables: returns the next action from PARSE-ACTION-table.
068: @param currentState curent state
069: @param symbol current terminal
070: @return new action
071: */
072: public Integer getParseAction(Integer currentState, String terminal) {
073: Integer action = null;
074: Map map = (Map) parseTable.get(currentState.intValue());
075: if (map != null)
076: action = (Integer) map.get(terminal);
077: return action == null ? ParserTables.ERROR : action;
078: }
079:
080: /** Implements ParserTables: returns String List of terminals, without EPSILON. */
081: public List getTerminals() {
082: return terminalsWithoutEpsilon;
083: }
084:
085: /** Implements ParserTables: returns Syntax. */
086: public Syntax getSyntax() {
087: return syntax;
088: }
089:
090: /** Implements ParserTables: Returns a Map of the expected tokens for current state, contained in keySet iterator. */
091: public Map getExpected(Integer state) {
092: return (Map) parseTable.get(state.intValue());
093: }
094:
095: /**
096: Factory to build precompiled parser tables, or construct them from scratch.
097: Used by <i>CompiledTables</i> and <i>SerializedTables</i>.
098: @param parserType LALRParserTables, SLRParserTables, LRParserTables class.
099: @param syntax can be null for precompiled tables, else the syntax to build.
100: */
101: public static AbstractParserTables construct(Class parserType,
102: Syntax syntax) throws Exception {
103: Constructor constr;
104: if (syntax == null) { // load compiled table
105: constr = parserType.getConstructor(new Class[0]);
106: return (AbstractParserTables) constr
107: .newInstance(new Object[0]);
108: } else { // build tables from scratch
109: try { // if this fails
110: constr = parserType.getConstructor(new Class[] { syntax
111: .getClass() });
112: } catch (Exception e) { // try Object as parameter for Constructor
113: constr = parserType
114: .getConstructor(new Class[] { Object.class });
115: }
116: return (AbstractParserTables) constr
117: .newInstance(new Object[] { syntax });
118: }
119: }
120:
121: // dump methods, display rules and tables
122:
123: /** Implements ParserTables: prints rules, FIRST/FOLLOW sets, syntax nodes (states), GOTO-table, PARSE-ACTION-table. */
124: public void dump(PrintStream out) {
125: dumpSyntax(out);
126: dumpTables(out);
127: }
128:
129: public void dumpTables(PrintStream out) {
130: dumpGoto(out);
131: dumpParseAction(out);
132: }
133:
134: public void dumpSyntax(PrintStream out) {
135: for (int i = 0; i < syntax.size(); i++)
136: out.println(dumpRule(syntax.getRule(i), i));
137: out.println();
138: }
139:
140: protected String dumpRule(Rule rule, int i) {
141: StringBuffer sb = new StringBuffer("(Rule " + i + ") "
142: + rule.getNonterminal() + " : ");
143: for (int j = 0; j < rule.rightSize(); j++)
144: sb.append(rule.getRightSymbol(j) + " ");
145: return sb.toString();
146: }
147:
148: protected void dumpGoto(PrintStream out) {
149: if (symbols.size() > 0)
150: dumpTable("GOTO TABLE", symbols, gotoTable, out);
151: }
152:
153: protected void dumpParseAction(PrintStream out) {
154: if (terminals.size() > 0)
155: dumpTable("PARSE-ACTION TABLE", terminals, parseTable, out);
156: }
157:
158: protected void dumpTable(String title, List head, List table,
159: PrintStream out) {
160: out.println(title);
161: out.println(dummy(title.length(), "="));
162:
163: // if no CELLWIDTH is set, estimate maximum cell width
164: if (CELLWIDTH <= 0) {
165: for (Iterator it = head.iterator(); it.hasNext();) {
166: String s = (String) it.next();
167: if (s.length() > CELLWIDTH && it.hasNext()) // not last
168: CELLWIDTH = s.length() + 1;
169: }
170: }
171:
172: // print table header
173: dumpCell(" | ", CELLWIDTH, false, out);
174: for (Iterator it = head.iterator(); it.hasNext();) {
175: String s = (String) it.next();
176: if (Token.isEpsilon(s))
177: s = "<EOF>";
178: dumpCell(s, CELLWIDTH, !it.hasNext(), out);
179: }
180:
181: out.println();
182: out.println(dummy(CELLWIDTH * (head.size() + 1), "_"));
183:
184: int i = 0;
185: for (Iterator it = table.iterator(); it.hasNext(); i++) {
186: Map h = (Map) it.next();
187:
188: dumpCell(Integer.toString(i) + " | ", CELLWIDTH, false, out);
189: for (Iterator it2 = head.iterator(); it2.hasNext();) {
190: String symbol = (String) it2.next();
191:
192: Integer intg = h != null ? (Integer) h.get(symbol)
193: : null;
194: String digit = intg == null ? "-" : intg
195: .equals(ParserTables.SHIFT) ? "SH" : intg
196: .equals(ParserTables.ACCEPT) ? "AC" : intg
197: .toString();
198:
199: dumpCell(digit, CELLWIDTH, !it2.hasNext(), out);
200: }
201: out.println();
202: }
203:
204: out.println();
205: }
206:
207: private void dumpCell(String digit, int width, boolean isLast,
208: PrintStream out) {
209: StringBuffer tab = new StringBuffer(" ");
210: for (int i = 0; i < width - 1 - digit.length(); i++)
211: tab.append(' ');
212:
213: String s = tab + digit;
214: if (!isLast && s.length() > width && width > 2)
215: s = s.substring(0, width);
216:
217: out.print(s);
218: }
219:
220: private String dummy(int width, String ch) {
221: StringBuffer sb = new StringBuffer();
222: for (int i = 0; i < width; i++)
223: sb.append(ch);
224: return sb.toString();
225: }
226:
227: /** Reports count of rules, ternminals and nonterminals. */
228: public void report(PrintStream out) {
229: out.println("rules: " + syntax.size());
230: out.println("terminals: " + terminals.size());
231: out.println("nonterminals: " + nonterminals.size());
232: }
233:
234: // Java source generation methods
235:
236: private transient Writer f = null;
237:
238: private void fwrite(String line) throws IOException {
239: f.write(line, 0, line.length());
240: }
241:
242: /**
243: Generates a compilable source file "parserClassName.java".
244: If the class name contains package path, the file will be generated
245: within the corresponding directory, else within working directory.
246: @param parserClassName name of class to generate:
247: "Java" will generate "Java.java" in current directory,
248: "my.pkg.PT" will generate "my/pkg/PT.java" in current directory.
249: @return fileName if File could be written, else null.
250: */
251: public String toSourceFile(String parserClassName)
252: throws IOException {
253: if (parserClassName.endsWith("ParserTables") == false)
254: parserClassName = parserClassName + "ParserTables";
255:
256: String fileName = parserClassName.replace('.',
257: File.separatorChar)
258: + ".java";
259: System.err.println("Writing Java Source to " + fileName);
260:
261: File file = new File(fileName);
262: String path = file.getParent();
263: if (path != null && new File(path).exists() == false)
264: new File(path).mkdirs();
265:
266: // begin file writing
267: f = new BufferedWriter(new FileWriter(file));
268:
269: // header of Java source
270: if (path != null) {
271: if (path.endsWith(File.separator))
272: path = path.substring(0, path.length() - 1);
273:
274: fwrite("package " + path.replace(File.separatorChar, '.')
275: + ";\n\n");
276:
277: parserClassName = parserClassName.substring(parserClassName
278: .lastIndexOf(".") + 1);
279: }
280:
281: fwrite("import java.util.*;\n");
282: fwrite("import fri.patterns.interpreter.parsergenerator.syntax.*;\n");
283: fwrite("import fri.patterns.interpreter.parsergenerator.parsertables.AbstractParserTables;\n\n");
284: fwrite("/**\n");
285: fwrite(" * DO NOT EDIT - ParserTables generated\n");
286: fwrite(" * at " + new Date() + "\n");
287: fwrite(" * by fri.patterns.interpreter.parsergenerator.parsertables.AbstractParserTables.\n");
288: fwrite(" */\n\n");
289: fwrite("public final class " + parserClassName
290: + " extends AbstractParserTables\n");
291: fwrite("{\n");
292:
293: // begin constructor
294: fwrite(" public " + parserClassName + "() {\n");
295:
296: fwrite(" syntax = new Syntax(" + syntax.size() + ");\n");
297: fwrite(" Rule s;\n");
298: fwrite("\n");
299: for (int i = 0; i < syntax.size(); i++) {
300: Rule s = syntax.getRule(i);
301: fwrite(" syntax.addRule(s = new Rule(\""
302: + s.getNonterminal() + "\", " + s.rightSize()
303: + ")); // rule " + i + "\n");
304: for (int j = 0; j < s.rightSize(); j++)
305: fwrite(" s.addRightSymbol(\""
306: + sub(s.getRightSymbol(j)) + "\");\n");
307: fwrite("\n");
308: }
309: fwrite("\n");
310:
311: // call methods to build tables
312: fwrite(" loadGotoTable();\n");
313: fwrite(" loadParseActionTable();\n");
314: fwrite("\n");
315:
316: // load terminal list that gets passed to Lexer
317: fwrite(" terminalsWithoutEpsilon = new ArrayList("
318: + terminalsWithoutEpsilon.size() + ");\n");
319: for (int i = 0; i < terminalsWithoutEpsilon.size(); i++)
320: fwrite(" terminalsWithoutEpsilon.add(\""
321: + sub(terminalsWithoutEpsilon.get(i)) + "\");\n");
322:
323: fwrite(" }\n");
324: // end constructor
325:
326: // method to load Goto table
327: fwrite(" private void loadGotoTable() {\n");
328: fwrite(" gotoTable = new ArrayList(" + gotoTable.size()
329: + ");\n");
330: fwrite("\n");
331: for (int i = 0; i < gotoTable.size(); i++) {
332: Map g = (Map) gotoTable.get(i);
333: if (g == null)
334: fwrite(" gotoTable.add(null); // state " + i);
335: else
336: fwrite(" loadGoto_" + i + "();");
337: fwrite("\n");
338: }
339: fwrite(" }\n");
340:
341: // every goto state is a method as Java can not load methods bigger than 65563 Bytes
342: for (int i = 0; i < gotoTable.size(); i++) {
343: Map g = (Map) gotoTable.get(i);
344: if (g != null) {
345: fwrite(" private void loadGoto_" + i + "() {\n");
346: fwrite(" Hashtable g = new Hashtable(" + g.size()
347: + ", 1);\n");
348: fwrite(" gotoTable.add(g);\n");
349: for (Iterator it = g.keySet().iterator(); it.hasNext();) {
350: String key = (String) it.next();
351: Object value = g.get(key);
352: fwrite(" g.put(\"" + sub(key) + "\", new Integer("
353: + value + "));\n");
354: }
355: fwrite(" }\n");
356: }
357: }
358:
359: // method to load Parse-Action table
360: fwrite(" private void loadParseActionTable() {\n");
361: fwrite(" parseTable = new ArrayList(" + parseTable.size()
362: + ");\n");
363: fwrite("\n");
364: for (int i = 0; i < parseTable.size(); i++) {
365: Map p = (Map) parseTable.get(i);
366: if (p == null)
367: fwrite(" parseTable.add(null); // state " + i);
368: else
369: fwrite(" loadParseAction_" + i + "();");
370: fwrite("\n");
371: }
372: fwrite(" }\n");
373:
374: // every action state is a method as Java can not load methods bigger than 65563 Bytes
375: for (int i = 0; i < parseTable.size(); i++) {
376: Map p = (Map) parseTable.get(i);
377: if (p != null) {
378: fwrite(" private void loadParseAction_" + i + "() {\n");
379: fwrite(" Hashtable p = new Hashtable(" + p.size()
380: + ", 1);\n");
381: fwrite(" parseTable.add(p);\n");
382: for (Iterator it = p.keySet().iterator(); it.hasNext();) {
383: String key = (String) it.next();
384: Object value = p.get(key);
385: fwrite(" p.put(\"" + sub(key) + "\", new Integer("
386: + value + "));\n");
387: }
388: fwrite(" }\n");
389: }
390: }
391:
392: fwrite("}");
393:
394: // end file writing
395: f.flush();
396: f.close();
397: f = null;
398:
399: return fileName;
400: }
401:
402: private String sub(Object o) {
403: return SyntaxUtil.maskQuoteAndBackslash((String) o);
404: }
405:
406: }
|