001: /*
002: * Copyright 2006, 2007 Odysseus Software GmbH
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: package de.odysseus.el.tree.impl;
017:
018: import java.util.ArrayList;
019: import java.util.Collections;
020: import java.util.LinkedList;
021: import java.util.List;
022:
023: import de.odysseus.el.misc.LocalMessages;
024: import de.odysseus.el.tree.FunctionNode;
025: import de.odysseus.el.tree.IdentifierNode;
026: import de.odysseus.el.tree.Tree;
027:
028: import de.odysseus.el.tree.impl.Scanner.ScanException;
029: import de.odysseus.el.tree.impl.Scanner.Symbol;
030: import de.odysseus.el.tree.impl.ast.*;
031:
032: import static de.odysseus.el.tree.impl.Scanner.Symbol.*;
033:
034: /**
035: * Handcrafted top-down parser.
036: *
037: * @author Christoph Beck
038: */
039: final class Parser {
040: /**
041: * Parse exception type
042: */
043: @SuppressWarnings("serial")
044: static class ParseException extends Exception {
045: ParseException(int position, String encountered, String expected) {
046: super (LocalMessages.get("error.parse", position,
047: encountered, expected));
048: }
049: }
050:
051: /**
052: * Token type (used to store lookahead)
053: */
054: private static final class LookaheadToken {
055: final Symbol symbol;
056: final String image;
057: final int position;
058:
059: LookaheadToken(Symbol symbol, String image, int position) {
060: this .symbol = symbol;
061: this .image = image;
062: this .position = position;
063: }
064: }
065:
066: private static final String EXPR_FIRST = IDENTIFIER + "|" + STRING
067: + "|" + FLOAT + "|" + INTEGER + "|" + TRUE + "|" + FALSE
068: + "|" + NULL + "|" + MINUS + "|" + NOT + "|" + EMPTY + "|"
069: + LPAREN;
070:
071: private final Builder context;
072: private final Scanner scanner;
073:
074: private List<IdentifierNode> identifiers = Collections.emptyList();
075: private List<FunctionNode> functions = Collections.emptyList();
076: private List<LookaheadToken> lookahead = Collections.emptyList();
077:
078: public Parser(Builder context, String input) {
079: this .context = context;
080: this .scanner = new Scanner(input);
081: }
082:
083: private Symbol symbol; // current token symbol
084: private String image; // current token text
085: private int position; // current token position
086:
087: private Number parseInteger(String string) throws ParseException {
088: try {
089: return context.parseInteger(string);
090: } catch (NumberFormatException e) {
091: fail(INTEGER);
092: return null;
093: }
094: }
095:
096: private Number parseFloat(String string) throws ParseException {
097: try {
098: return context.parseFloat(string);
099: } catch (NumberFormatException e) {
100: fail(FLOAT);
101: return null;
102: }
103: }
104:
105: /**
106: * throw exception
107: */
108: private void fail(String expected) throws ParseException {
109: String encountered = image == null ? symbol.toString() : "'"
110: + image + "'";
111: throw new ParseException(position, encountered, expected);
112: }
113:
114: /**
115: * throw exception
116: */
117: private void fail(Symbol expected) throws ParseException {
118: fail(expected.toString());
119: }
120:
121: /**
122: * get lookahead symbol.
123: */
124: private Symbol lookahead(int index) throws ScanException,
125: ParseException {
126: if (lookahead.isEmpty()) {
127: lookahead = new LinkedList<LookaheadToken>();
128: }
129: while (index >= lookahead.size()) {
130: lookahead.add(new LookaheadToken(scanner.next(), scanner
131: .getImage(), scanner.getPosition()));
132: }
133: return lookahead.get(index).symbol;
134: }
135:
136: /**
137: * consume current token (get next token)
138: */
139: private void consumeToken() throws ScanException, ParseException {
140: if (lookahead.isEmpty()) {
141: symbol = scanner.next();
142: image = scanner.getImage();
143: position = scanner.getPosition();
144: } else {
145: LookaheadToken token = lookahead.remove(0);
146: symbol = token.symbol;
147: image = token.image;
148: position = token.position;
149: }
150: }
151:
152: /**
153: * consume current token (get next token); throw exception if the current token doesn't
154: * match the expected symbol.
155: */
156: private void consumeToken(Symbol expected) throws ScanException,
157: ParseException {
158: if (symbol != expected) {
159: fail(expected);
160: }
161: consumeToken();
162: }
163:
164: /**
165: * tree := text? ((dynamic text?)+ | (deferred text?)+)?
166: */
167: public Tree tree() throws ScanException, ParseException {
168: consumeToken();
169: AstNode t = text();
170: if (symbol == EOF) {
171: if (t == null) {
172: t = new AstText("");
173: }
174: return new Tree(t, functions, identifiers, false);
175: }
176: AstEval e = eval();
177: if (symbol == EOF && t == null) {
178: return new Tree(e, functions, identifiers, e.isDeferred());
179: }
180: ArrayList<AstNode> list = new ArrayList<AstNode>();
181: if (t != null) {
182: list.add(t);
183: }
184: list.add(e);
185: t = text();
186: if (t != null) {
187: list.add(t);
188: }
189: while (symbol != EOF) {
190: if (e.isDeferred()) {
191: list.add(eval(true, true));
192: } else {
193: list.add(eval(true, false));
194: }
195: t = text();
196: if (t != null) {
197: list.add(t);
198: }
199: }
200: return new Tree(new AstComposite(list), functions, identifiers,
201: e.isDeferred());
202: }
203:
204: /**
205: * text := <TEXT>
206: */
207: private AstNode text() throws ScanException, ParseException {
208: AstNode v = null;
209: if (symbol == TEXT) {
210: v = new AstText(image);
211: consumeToken();
212: }
213: return v;
214: }
215:
216: /**
217: * eval := dynamic | deferred
218: */
219: private AstEval eval() throws ScanException, ParseException {
220: AstEval e = eval(false, false);
221: if (e == null) {
222: e = eval(false, true);
223: if (e == null) {
224: fail(START_EVAL_DEFERRED + "|" + START_EVAL_DYNAMIC);
225: }
226: }
227: return e;
228: }
229:
230: /**
231: * dynmamic := <START_EVAL_DYNAMIC> expr <END_EVAL>
232: * deferred := <START_EVAL_DEFERRED> expr <END_EVAL>
233: */
234: private AstEval eval(boolean required, boolean deferred)
235: throws ScanException, ParseException {
236: AstEval v = null;
237: Symbol start_eval = deferred ? START_EVAL_DEFERRED
238: : START_EVAL_DYNAMIC;
239: if (symbol == start_eval) {
240: consumeToken();
241: v = new AstEval(expr(true), deferred);
242: consumeToken(END_EVAL);
243: } else if (required) {
244: fail(start_eval);
245: }
246: return v;
247: }
248:
249: /**
250: * expr := or (<QUESTION> expr <COLON> expr)?
251: */
252: private AstNode expr(boolean required) throws ScanException,
253: ParseException {
254: AstNode v = or(required);
255: if (v == null) {
256: return null;
257: }
258: if (symbol == QUESTION) {
259: consumeToken();
260: AstNode a = expr(true);
261: consumeToken(COLON);
262: AstNode b = expr(true);
263: v = new AstChoice(v, a, b);
264: }
265: return v;
266: }
267:
268: /**
269: * or := and (<OR> and)*
270: */
271: private AstNode or(boolean required) throws ScanException,
272: ParseException {
273: AstNode v = and(required);
274: if (v == null) {
275: return null;
276: }
277: while (symbol == OR) {
278: consumeToken();
279: v = new AstBinary(v, and(true), AstBinary.OR);
280: }
281: return v;
282: }
283:
284: /**
285: * and := eq (<AND> eq)*
286: */
287: private AstNode and(boolean required) throws ScanException,
288: ParseException {
289: AstNode v = eq(required);
290: if (v == null) {
291: return null;
292: }
293: while (symbol == AND) {
294: consumeToken();
295: v = new AstBinary(v, eq(true), AstBinary.AND);
296: }
297: return v;
298: }
299:
300: /**
301: * eq := cmp (<EQ> cmp | <NE> cmp)*
302: */
303: private AstNode eq(boolean required) throws ScanException,
304: ParseException {
305: AstNode v = cmp(required);
306: if (v == null) {
307: return null;
308: }
309: while (true) {
310: switch (symbol) {
311: case EQ:
312: consumeToken();
313: v = new AstBinary(v, cmp(true), AstBinary.EQ);
314: break;
315: case NE:
316: consumeToken();
317: v = new AstBinary(v, cmp(true), AstBinary.NE);
318: break;
319: default:
320: return v;
321: }
322: }
323: }
324:
325: /**
326: * cmp := add (<LT> add | <LE> add | <GE> add | <GT> add)*
327: */
328: private AstNode cmp(boolean required) throws ScanException,
329: ParseException {
330: AstNode v = add(required);
331: if (v == null) {
332: return null;
333: }
334: while (true) {
335: switch (symbol) {
336: case LT:
337: consumeToken();
338: v = new AstBinary(v, add(true), AstBinary.LT);
339: break;
340: case LE:
341: consumeToken();
342: v = new AstBinary(v, add(true), AstBinary.LE);
343: break;
344: case GE:
345: consumeToken();
346: v = new AstBinary(v, add(true), AstBinary.GE);
347: break;
348: case GT:
349: consumeToken();
350: v = new AstBinary(v, add(true), AstBinary.GT);
351: break;
352: default:
353: return v;
354: }
355: }
356: }
357:
358: /**
359: * add := add (<PLUS> mul | <MINUS> mul)*
360: */
361: private AstNode add(boolean required) throws ScanException,
362: ParseException {
363: AstNode v = mul(required);
364: if (v == null) {
365: return null;
366: }
367: while (true) {
368: switch (symbol) {
369: case PLUS:
370: consumeToken();
371: v = new AstBinary(v, mul(true), AstBinary.ADD);
372: break;
373: case MINUS:
374: consumeToken();
375: v = new AstBinary(v, mul(true), AstBinary.SUB);
376: break;
377: default:
378: return v;
379: }
380: }
381: }
382:
383: /**
384: * mul := unary (<MUL> unary | <DIV> unary | <MOD> unary)*
385: */
386: private AstNode mul(boolean required) throws ScanException,
387: ParseException {
388: AstNode v = unary(required);
389: if (v == null) {
390: return null;
391: }
392: while (true) {
393: switch (symbol) {
394: case MUL:
395: consumeToken();
396: v = new AstBinary(v, unary(true), AstBinary.MUL);
397: break;
398: case DIV:
399: consumeToken();
400: v = new AstBinary(v, unary(true), AstBinary.DIV);
401: break;
402: case MOD:
403: consumeToken();
404: v = new AstBinary(v, unary(true), AstBinary.MOD);
405: break;
406: default:
407: return v;
408: }
409: }
410: }
411:
412: /**
413: * unary := <NOT> unary | <MINUS> unary | <EMPTY> unary | value
414: */
415: private AstNode unary(boolean required) throws ScanException,
416: ParseException {
417: AstNode v = null;
418: switch (symbol) {
419: case NOT:
420: consumeToken();
421: v = new AstUnary(unary(true), AstUnary.NOT);
422: break;
423: case MINUS:
424: consumeToken();
425: v = new AstUnary(unary(true), AstUnary.NEG);
426: break;
427: case EMPTY:
428: consumeToken();
429: v = new AstUnary(unary(true), AstUnary.EMPTY);
430: break;
431: default:
432: v = value();
433: }
434: if (v == null && required) {
435: fail(EXPR_FIRST);
436: }
437: return v;
438: }
439:
440: /**
441: * value := (nonliteral | literal) (<DOT> <IDENTIFIER> | <LBRACK> expr <RBRACK>)*
442: */
443: private AstNode value() throws ScanException, ParseException {
444: boolean lvalue = true;
445: AstNode v = nonliteral();
446: if (v == null) {
447: v = literal();
448: if (v == null) {
449: return null;
450: }
451: lvalue = false;
452: }
453: while (true) {
454: switch (symbol) {
455: case DOT:
456: consumeToken();
457: String name = image;
458: consumeToken(IDENTIFIER);
459: if (symbol == LPAREN
460: && context
461: .isEnabled(Builder.Feature.METHOD_INVOCATIONS)) {
462: consumeToken();
463: v = new AstMethod(v, name, list());
464: consumeToken(RPAREN);
465: } else {
466: v = new AstDot(v, name, lvalue);
467: }
468: break;
469: case LBRACK:
470: consumeToken();
471: AstNode property = expr(true);
472: boolean strict = !context
473: .isEnabled(Builder.Feature.NULL_PROPERTIES);
474: v = new AstBracket(v, property, lvalue, strict);
475: consumeToken(RBRACK);
476: break;
477: default:
478: return v;
479: }
480: }
481: }
482:
483: /**
484: * nonliteral := <IDENTIFIER> | function | <LPAREN> expr <RPAREN>
485: * function := (<IDENTIFIER> <COLON>)? <IDENTIFIER> <LPAREN> list? <RPAREN>
486: */
487: private AstNode nonliteral() throws ScanException, ParseException {
488: AstNode v = null;
489: switch (symbol) {
490: case IDENTIFIER:
491: String name = image;
492: consumeToken();
493: if (symbol == COLON && lookahead(0) == IDENTIFIER
494: && lookahead(1) == LPAREN) { // ns:f(...)
495: consumeToken();
496: name += ":" + image;
497: consumeToken();
498: }
499: if (symbol == LPAREN) { // function
500: consumeToken();
501: List<AstNode> args = list();
502: consumeToken(RPAREN);
503: if (functions.isEmpty()) {
504: functions = new ArrayList<FunctionNode>(4);
505: }
506: AstFunction function = new AstFunction(name, functions
507: .size(), args);
508: functions.add(function);
509: v = function;
510: } else { // identifier
511: if (identifiers.isEmpty()) {
512: identifiers = new ArrayList<IdentifierNode>(4);
513: }
514: AstIdentifier identifier = new AstIdentifier(name,
515: identifiers.size());
516: identifiers.add(identifier);
517: v = identifier;
518: }
519: break;
520: case LPAREN:
521: consumeToken();
522: v = expr(true);
523: consumeToken(RPAREN);
524: v = new AstNested(v);
525: break;
526: }
527: return v;
528: }
529:
530: /**
531: * list := expr (<COMMA> expr)*
532: */
533: private List<AstNode> list() throws ScanException, ParseException {
534: List<AstNode> l = null;
535: AstNode v = expr(false);
536: if (v != null) {
537: l = new ArrayList<AstNode>();
538: l.add(v);
539: while (symbol == COMMA) {
540: consumeToken();
541: l.add(expr(true));
542: }
543: }
544: return l;
545: }
546:
547: /**
548: * literal := <TRUE> | <FALSE> | <STRING> | <INTEGER> | <FLOAT> | <NULL>
549: */
550: private AstNode literal() throws ScanException, ParseException {
551: AstNode v = null;
552: switch (symbol) {
553: case TRUE:
554: v = new AstBoolean(true);
555: consumeToken();
556: break;
557: case FALSE:
558: v = new AstBoolean(false);
559: consumeToken();
560: break;
561: case STRING:
562: v = new AstString(image);
563: consumeToken();
564: break;
565: case INTEGER:
566: v = new AstNumber(parseInteger(image));
567: consumeToken();
568: break;
569: case FLOAT:
570: v = new AstNumber(parseFloat(image));
571: consumeToken();
572: break;
573: case NULL:
574: v = new AstNull();
575: consumeToken();
576: break;
577: }
578: return v;
579: }
580: }
|