-
Notifications
You must be signed in to change notification settings - Fork 0
/
IntegerExpressionParser.java
141 lines (119 loc) · 5.46 KB
/
IntegerExpressionParser.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
package intexpr;
import java.io.File;
import java.io.IOException;
import java.util.List;
import edu.mit.eecs.parserlib.ParseTree;
import edu.mit.eecs.parserlib.Parser;
import edu.mit.eecs.parserlib.UnableToParseException;
import edu.mit.eecs.parserlib.Visualizer;
public class IntegerExpressionParser {
/**
* Main method. Parses and evaluates an example expression.
*
* @param args command line arguments, not used
* @throws UnableToParseException if example expression can't be parsed
*/
public static void main(final String[] args) throws UnableToParseException {
final String input = "54+(2+ 89)";
System.out.println(input);
final IntegerExpression expression = IntegerExpressionParser.parse(input);
final int value = expression.value();
System.out.println("value " + value);
}
// the nonterminals of the grammar
private enum IntegerGrammar {
EXPRESSION, SUM, PRIMARY, NUMBER, WHITESPACE,
};
private static Parser<IntegerGrammar> parser = makeParser();
/**
* Compile the grammar into a parser.
*
* @param grammarFilename <b>Must be in this class's Java package.</b>
* @return parser for the grammar
* @throws RuntimeException if grammar file can't be read or has syntax errors
*/
private static Parser<IntegerGrammar> makeParser() {
try {
// read the grammar as a file, relative to the project root.
final File grammarFile = new File("src/intexpr/IntegerExpression.g");
return Parser.compile(grammarFile, IntegerGrammar.EXPRESSION);
// A better way would read the grammar as a "classpath resource", which would allow this code
// to be packed up in a jar and still be able to find its grammar file:
//
// final InputStream grammarStream = IntegerExpression.class.openResourceAsStream("IntegerExpression.g");
// return Parser.compile(grammarStream, IntegerGrammar.EXPRESSION);
//
// See http://www.javaworld.com/article/2077352/java-se/smartly-load-your-properties.html
// for a discussion of classpath resources.
// Parser.compile() throws two checked exceptions.
// Translate these checked exceptions into unchecked RuntimeExceptions,
// because these failures indicate internal bugs rather than client errors
} catch (IOException e) {
throw new RuntimeException("can't read the grammar file", e);
} catch (UnableToParseException e) {
throw new RuntimeException("the grammar has a syntax error", e);
}
}
/**
* Parse a string into an expression.
* @param string string to parse
* @return IntegerExpression parsed from the string
* @throws UnableToParseException if the string doesn't match the IntegerExpression grammar
*/
public static IntegerExpression parse(final String string) throws UnableToParseException {
// parse the example into a parse tree
final ParseTree<IntegerGrammar> parseTree = parser.parse(string);
System.out.println("parse tree " + parseTree);
// display the parse tree in a web browser, for debugging only
Visualizer.showInBrowser(parseTree);
// make an AST from the parse tree
final IntegerExpression expression = makeAbstractSyntaxTree(parseTree);
System.out.println("AST " + expression);
return expression;
}
/**
* Convert a parse tree into an abstract syntax tree.
*
* @param parseTree constructed according to the grammar in IntegerExpression.g
* @return abstract syntax tree corresponding to parseTree
*/
private static IntegerExpression makeAbstractSyntaxTree(final ParseTree<IntegerGrammar> parseTree) {
switch (parseTree.name()) {
case EXPRESSION: // expression ::= sum;
{
final ParseTree<IntegerGrammar> child = parseTree.children().get(0);
return makeAbstractSyntaxTree(child);
}
case SUM: // sum ::= primary ('+' primary)*;
{
final List<ParseTree<IntegerGrammar>> children = parseTree.children();
IntegerExpression expression = makeAbstractSyntaxTree(children.get(0));
for (int i = 1; i < children.size(); ++i) {
expression = new Plus(expression, makeAbstractSyntaxTree(children.get(i)));
}
return expression;
}
case PRIMARY: // primary ::= number | '(' sum ')';
{
final ParseTree<IntegerGrammar> child = parseTree.children().get(0);
// check which alternative (number or sum) was actually matched
switch (child.name()) {
case NUMBER:
return makeAbstractSyntaxTree(child);
case SUM:
return makeAbstractSyntaxTree(child); // in this case, we do the
// same thing either way
default:
throw new AssertionError("should never get here");
}
}
case NUMBER: // number ::= [0-9]+;
{
final int n = Integer.parseInt(parseTree.text());
return new Number(n);
}
default:
throw new AssertionError("should never get here");
}
}
}