Source code: com/voytechs/jnetstream/npl/ExpressionParser.java
1 /*
2 * File: ExpressionParser.java
3 * Auth: Mark Bednarczyk
4 * Date: DATE
5 * Id: $Id: ExpressionParser.java,v 1.1.1.1 2003/09/22 16:32:17 voytechs Exp $
6 ********************************************
7 Copyright (C) 2003 Mark Bednarczyk
8
9 This program is free software; you can redistribute it and/or
10 modify it under the terms of the GNU General Public License
11 as published by the Free Software Foundation; either version 2
12 of the License, or (at your option) any later version.
13
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
22 ********************************************
23 * $Log: ExpressionParser.java,v $
24 * Revision 1.1.1.1 2003/09/22 16:32:17 voytechs
25 * Initial import.
26 *
27 */
28 package com.voytechs.jnetstream.npl;
29
30 import java.lang.*;
31 import java.util.*;
32 import java.io.*;
33
34 /**
35 * Express parser.
36 * A standard C-Like expression will be parsed into an expression tree.
37 * The expression tree then can be traversed and evaluated via a number of methods.
38 * The expression parser is called using the parseExpression() method and passing it a String
39 * containing the expression to be parsed.
40 * The parser has the following operators defined:<BR><BR>
41 * <OL>
42 * <L> "+" - class PlusOpNode - NORMAL/BINARY
43 * <L> "-" - class MinusOpNode - NORMAL/BINARY
44 * <L> "*" - class MultiplyOpNode - HIGH/BINARY
45 * <L> "/" - class DivideOpNode - HIGH/BINARY
46 * <L> "&" - class AndOpNode - HIGH/BINARY
47 * <L> "|" - class OrOpNode - HIGH/BINARY
48 * <L> "%" - class ModOpNode - NORMAL/BINARY
49 * <L> "^" - class PowOpNode - NORMAL/BINARY
50 * <L> "~" - class InverseOpNode - LOW/UNARY
51 * <L> "&&" - class LogicalAndOpNode - NORMAL/BINARY
52 * <L> "||" - class LogicalOrOpNode - NORMAL/BINARY
53 * <L> "!" - class LogicalNotOpNode - LOW/UNARY
54 * <L> "==" - class LogicalEqualOpNode - NORMAL/BINARY
55 * <L> "!=" - class LogicalNotEqualOpNode - NORMAL/BINARY
56 * <L> "<" - class LessThanOpNode - NORMAL/BINARY
57 * <L> "<=" - class LessEqualsOpNode - NORMAL/BINARY
58 * <L> "<=" - class GreaterThanOpNode - NORMAL/BINARY
59 * <L> "<=" - class GreaterEqualsThanOpNode - NORMAL/BINARY
60 * </OL>
61 */
62 public class ExpressionParser {
63 /* Internal attributes */
64 private static final boolean debug = false;
65
66 protected Stack s1 = new Stack(); // Operators
67 protected Stack s2 = new Stack(); // Operands
68
69 protected String expression;
70
71 public static Hashtable context = new Hashtable();
72
73 /**
74 * Initialize the parser.
75 */
76 public ExpressionParser() {
77 }
78
79 /**
80 * Returns the root node of the parse tree or Glyths.
81 * @param exp Expression string to be parsed into the expression tree.
82 * @return Root node of the parsed tree.
83 */
84 public Node parse(String exp)
85 throws SyntaxError {
86
87 return(parse(new StringReader(exp)));
88
89 }
90
91 /**
92 * Returns the root node of the parse tree or Glyths.
93 * @param exp Input Reader stream to be parsed into the expression tree.
94 * @return Root node of the parsed tree.
95 */
96 public Node parse(Reader input)
97 throws SyntaxError {
98
99 ExpTokenizer tokenizer = new ExpTokenizer(input);
100
101 return(parseExpression(tokenizer));
102
103 }
104
105 /**
106 * Returns the root node of the parsed tree or Glyths.
107 * @param tokens Tokenizer object initialized with the express string or stream.
108 */
109 protected Node parseExpression(ExpTokenizer tokens)
110 throws SyntaxError {
111
112 ExpToken token = null;
113 ExpToken peek = null;
114
115 if(debug)
116 System.out.println("parseExpression()");
117
118 Stack s1 = this.s1;
119 Stack s2 = this.s2;
120
121 while(tokens.hasMoreTokens()) {
122
123 token = (ExpToken)tokens.nextToken();
124 peek = (ExpToken)tokens.lookAhead();
125
126 if(debug)
127 System.out.println( "1-token=" + token
128 + " peek=" + peek
129 + " s1=" + s1.toString()
130 + " s2=" + s2.toString() );
131
132 if( token.getTokenType() == ExpToken.TYPE_OP) {
133 s1.push((OpNode)token.objectValue());
134 }
135
136 else if( token.getTokenType() == ExpToken.TYPE_CLOSE_PAREN) {
137 tokens.pushBack();
138 break;
139 }
140
141 else if( token.getTokenType() == ExpToken.TYPE_OPEN_PAREN) {
142
143 /**
144 * Parse subexpression in its own separate parser.
145 */
146 ExpressionParser np = new ExpressionParser();
147 Node subExpr = np.parseExpression(tokens);
148
149 if( (token = (ExpToken)tokens.nextToken()).getTokenType() != Token.TYPE_CLOSE_PAREN)
150 throw new SyntaxError("unmatched close parenthesis ')'", token);
151
152 s2.push(subExpr); // Put result on s2.
153
154 /**
155 * Now fetch the peek value again so that we can check presedence at the end of the loop
156 */
157 peek = (ExpToken)tokens.lookAhead();
158
159 }
160
161 else if(token.getTokenType() == Token.TYPE_NUMBER) {
162 s2.push(new IntNodeImpl(token.intValue()));
163
164 }
165
166 else if(token.getTokenType() == Token.TYPE_WORD) {
167 s2.push(new MutableReferenceNode(token.stringValue()));
168
169 }
170
171 else if(token.getTokenType() == Token.TYPE_DOUBLE_QUOTE)
172 s2.push(new StringNodeImpl(token.stringValue()));
173
174 else {
175 // if(debug)
176 // System.out.println("parseExpression() - unknown token=" + token);
177
178 tokens.pushBack();
179 break;
180 }
181
182
183 if( token.getTokenType() == ExpToken.TYPE_OP)
184 continue;
185
186 /**
187 * Check for presendence of operators. If the next operator (we do a peek) has equal or higher
188 * presedence the put them on the stack to get the right order of syntax execution (right tree.)
189 */
190 OpNode lastOp = null;
191 OpNode nextOp = null;
192
193 if(s1.empty() == false) lastOp = (OpNode)s1.peek();
194 if(peek != null && (peek.objectValue() instanceof OpNode)) nextOp = (OpNode)peek.objectValue();
195
196 if(lastOp != null && nextOp != null && lastOp.getPresedence() < nextOp.getPresedence())
197 s2.push(parseExpression(tokens));
198
199 processOpNodes();
200
201 if(debug)
202 System.out.println( "2-token=" + token
203 + " peek=" + peek
204 + " s1=" + s1.toString()
205 + " s2=" + s2.toString() );
206
207 }
208
209 processOpNodes();
210
211 if(s2.empty())
212 return(null);
213
214 return((Node)s2.pop());
215 }
216
217
218 /**
219 * Processes tokens that are builtin statement or variables.
220 */
221 protected void processBuiltinStatement(ExpTokenizer tokens, Token token, Token peek) {
222
223
224 }
225
226
227
228 /**
229 * Processes all of the OP nodes found on the stack until the stack is emptied.
230 * The two stacks are s1 for operators and s2 for operands (parameters)
231 */
232 protected void processOpNodes() {
233 OpNode op;
234
235 if(debug && false)
236 System.out.println("processOpNodes() s1=" + s1 + " s2=" + s2);
237
238 while(s1.empty() == false) {
239
240 op = (OpNode)s1.pop();
241
242 if(debug && false)
243 System.out.println("processOpNodes() BINARY(" + op + ")");
244
245 /**
246 * Each operator pops off as many operands as it requires.
247 */
248 try {
249 s2.push(op.createOpNode(s2));
250 }
251 catch(ExpInternalException internal) {
252 System.out.println("FATAL Internal ERROR" + internal);
253 }
254 catch(OperandException oe) {
255 System.out.println("Syntax error: " + oe);
256 }
257 }
258 }
259
260
261 /**
262 * Test function for ExpressionParser
263 * @param args command line arguments
264 */
265 public static void main(String [] args) {
266
267 String exp = "1 + 2";
268
269 if(args.length != 0) {
270 exp = args[0];
271 }
272
273 context.put("a", new Integer(100));
274 context.put("b", new Integer(200));
275 context.put("length", new Integer(20));
276 context.put("i", new Integer(3));
277 context.put("ver", new Integer(4));
278
279
280 ExpressionParser parser = new ExpressionParser();
281
282 Node node;
283
284 try {
285 if(exp.equals("-")) {
286 node = parser.parse(new InputStreamReader(System.in));
287 }
288 else {
289 node = parser.parse(exp);
290 }
291
292 // node = node.optimize();
293
294 System.out.print(exp + "::=" + node.toString());
295 // System.out.println("getBoolean()=::=" + ((BooleanNode)node).getBoolean());
296 // System.out.println("getString()=::=" + ((StringNode)node).getString());
297 System.out.println(" context=" + context);
298 }
299 catch(SyntaxError se) {
300 System.err.println(se);
301 }
302 }
303
304 } /* END OF: ExpressionParser */