|
1 package ro.infoiasi.donald.compiler.parser;
2
3 import ro.infoiasi.donald.compiler.cfg.*;
4 import java.io.*;
5 import java.util.*;
6
7
8 class LL1Parser extends AbstractParser {
9 public LL1Parser(ParserSpec spec) {
10 super(spec);
11 }
12
13 public LL1Parser(String  parserSpecPath)
14 throws IOException, SpecParseException {
15 super(parserSpecPath);
16 }
17
18 private int[][] parseTable;
19
20 private final int PARSE_ERROR = -1;
21
22 public void precompute() {
23 g.computeNullable();
24 g.computeFirst();
25 g.computeFollow();
26
30 parseTable = new int[v.count()][];
31 for (int i = 0; i<v.count(); i++) {
32 parseTable[i] = new int[t.count()];
33 for (int j = 0; j<t.count(); j++) {
34 parseTable[i][j] = PARSE_ERROR;
35 }
36 }
37
38 for (int i = 0; i<v.count(); i++) {
39 NonTerminal var = v.find(i);
40 List prodList = p.find(var);
41 Iterator itL = prodList.iterator();
42 while (itL.hasNext()) {
43 Production prod = (Production)itL.next();
44 Set first = g.first(prod);
45 Iterator it = first.iterator();
46 if (g.nullable(prod)) {
47 Set set = new LinkedHashSet(first);
48 set.addAll(g.follow(var));
49 it = set.iterator();
50 }
51 while (it.hasNext()) {
52 Terminal a = (Terminal)it.next();
53 int j = a.getIndex();
54 if (parseTable[i][j] != PARSE_ERROR) {
55 throw new RuntimeException ("Grammar not LL1.");
56 } else {
57 parseTable[i][j] = prod.getIndex();
58 }
59 }
60 }
61 }
62 }
63
64 public Production parseTable(NonTerminal x, Terminal a) {
65 int val = parseTable[x.getIndex()][a.getIndex()];
66 if (val == PARSE_ERROR) {
67 return null;
68 } else {
69 return p.find(val);
70 }
71 }
72
73 public List parse() throws IOException, SyntaxError {
74 List pi = new LinkedList();
75 Word stack = new Word();
76 stack.addLast(t.EOF);
77 stack.addLast(s);
78 Terminal a = lexer.nextToken().getSymbol();
79
80 while (true) {
81 Symbol x = stack.removeLast();
82 if (x.isTerminal()) {
84 if (x.equals(t.EOF) && a.equals(t.EOF)) {
85 return pi; } else if (x.equals(a)) {
87 a = lexer.nextToken().getSymbol(); } else {
89 throw new SyntaxError(a); }
91 } else {
92 Production prod = parseTable((NonTerminal)x,a);
93 if (prod == null) {
94 throw new SyntaxError(a); } else {
96 pi.add(prod); Word w = prod.getRHS().mirror();
99 WordIterator it = w.iterator();
100 while (it.hasNext()) {
101 stack.addLast(it.next());
102 }
103 }
104 }
105 }
106 }
107
108 private void printParseTable() {
109 if (parseTable != null) {
110 for (int i = 0; i<v.count(); i++) {
111 for (int j = 0; j<t.count(); j++) {
112 if (parseTable[i][j] != PARSE_ERROR) {
113 System.out.print("("+v.find(i)+","+t.find(j)+"): ");
114 System.out.println(p.find(parseTable[i][j]));
115 }
116 }
117 }
118 }
119 }
120
121 public static void main(String args[]) throws Exception {
122 if (args.length != 3) {
123 System.err.println("args: <grammar_file> <lexer_class> <input_file>");
124 System.exit(1);
125 }
126
127 LL1Parser parser = new LL1Parser(args[0]);
128 System.out.println(parser.getGrammar());
129
130 parser.precompute();
131
132 CFG g = parser.getGrammar();
133 g.printNullable();
134 g.printFirst();
135 g.printFollow();
136 parser.printParseTable();
137
138 parser.setLexer(args[1], args[2]);
139 List pi = parser.parse();
140 Iterator it = pi.iterator();
141 while (it.hasNext()) {
142 System.out.println(it.next()+";");
143 }
144 }
145 }
146
147 |
Popular Tags |
Java API By Example, From Geeks To Geeks.