1    // Copyright 2004 Adam Megacz, see the COPYING file for licensing [GPL]
2    package org.xwt.js;
3    
4    import org.xwt.util.*;
5    import java.io.*;
6    
7    /**
8     *  Parses a stream of lexed tokens into a tree of JSFunction's.
9     *
10    *  There are three kinds of things we parse: blocks, statements, and
11    *  expressions.
12    *
13    *  - Expressions are a special type of statement that evaluates to a
14    *    value (for example, "break" is not an expression, * but "3+2"
15    *    is).  Some tokens sequences start expressions (for * example,
16    *    literal numbers) and others continue an expression which * has
17    *    already been begun (for example, '+').  Finally, some *
18    *    expressions are valid targets for an assignment operation; after
19    *    * each of these expressions, continueExprAfterAssignable() is
20    *    called * to check for an assignment operation.
21    *
22    *  - A statement ends with a semicolon and does not return a value.
23    *
24    *  - A block is a single statement or a sequence of statements
25    *    surrounded by curly braces.
26    *
27    *  Each parsing method saves the parserLine before doing its actual
28    *  work and restores it afterwards.  This ensures that parsing a
29    *  subexpression does not modify the line number until a token
30    *  *after* the subexpression has been consumed by the parent
31    *  expression.
32    *
33    *  Technically it would be a better design for this class to build an
34    *  intermediate parse tree and use that to emit bytecode.  Here's the
35    *  tradeoff:
36    *
37    *  Advantages of building a parse tree:
38    *  - easier to apply optimizations
39    *  - would let us handle more sophisticated languages than JavaScript
40    *
41    *  Advantages of leaving out the parse tree
42    *  - faster compilation
43    *  - less load on the garbage collector
44    *  - much simpler code, easier to understand
45    *  - less error-prone
46    *
47    *  Fortunately JS is such a simple language that we can get away with
48    *  the half-assed approach and still produce a working, complete
49    *  compiler.
50    *
51    *  The bytecode language emitted doesn't really cause any appreciable
52    *  semantic loss, and is itself a parseable language very similar to
53    *  Forth or a postfix variant of LISP.  This means that the bytecode
54    *  can be transformed into a parse tree, which can be manipulated.
55    *  So if we ever want to add an optimizer, it could easily be done by
56    *  producing a parse tree from the bytecode, optimizing that tree,
57    *  and then re-emitting the bytecode.  The parse tree node class
58    *  would also be much simpler since the bytecode language has so few
59    *  operators.
60    *
61    *  Actually, the above paragraph is slightly inaccurate -- there are
62    *  places where we push a value and then perform an arbitrary number
63    *  of operations using it before popping it; this doesn't parse well.
64    *  But these cases are clearly marked and easy to change if we do
65    *  need to move to a parse tree format.
66    */
67   class Parser extends Lexer implements ByteCodes {
68   
69   
70       // Constructors //////////////////////////////////////////////////////
71   
72       public Parser(Reader r, String sourceName, int line) throws IOException { super(r, sourceName, line); }
73   
74       /** for debugging */
75       public static void main(String[] s) throws Exception {
76           JS block = JS.fromReader("stdin", 0, new InputStreamReader(System.in));
77           if (block == null) return;
78           System.out.println(block);
79       }
80   
81   
82       // Statics ////////////////////////////////////////////////////////////
83   
84       static byte[] precedence = new byte[MAX_TOKEN + 1];
85       static boolean[] isRightAssociative = new boolean[MAX_TOKEN + 1];
86       // Use this as the precedence when we want anything up to the comma
87       private final static int NO_COMMA = 2;
88       static {
89           isRightAssociative[ASSIGN] =
90               isRightAssociative[ASSIGN_BITOR] =
91               isRightAssociative[ASSIGN_BITXOR] =
92               isRightAssociative[ASSIGN_BITAND] =
93               isRightAssociative[ASSIGN_LSH] =
94               isRightAssociative[ASSIGN_RSH] =
95               isRightAssociative[ASSIGN_URSH] =
96               isRightAssociative[ASSIGN_ADD] =
97               isRightAssociative[ASSIGN_SUB] =
98               isRightAssociative[ASSIGN_MUL] =
99               isRightAssociative[ASSIGN_DIV] =
100              isRightAssociative[ASSIGN_MOD] = true;
101  
102          precedence[COMMA] = 1;
103          // 2 is intentionally left unassigned. we use minPrecedence==2 for comma separated lists
104          precedence[ASSIGN] =
105              precedence[ASSIGN_BITOR] =
106              precedence[ASSIGN_BITXOR] =
107              precedence[ASSIGN_BITAND] =
108              precedence[ASSIGN_LSH] =
109              precedence[ASSIGN_RSH] =
110              precedence[ASSIGN_URSH] =
111              precedence[ASSIGN_ADD] =
112              precedence[ASSIGN_SUB] =
113              precedence[ASSIGN_MUL] =
114              precedence[ASSIGN_DIV] =
115              precedence[ASSIGN_MOD] = 3;
116          precedence[HOOK] = 4;
117          precedence[OR] = 5;
118          precedence[AND] = 6;
119          precedence[BITOR] = 7;
120          precedence[BITXOR] = 8;
121          precedence[BITAND] = 9;
122          precedence[EQ] = precedence[NE] = precedence[SHEQ] = precedence[SHNE] = 10;
123          precedence[LT] = precedence[LE] = precedence[GT] = precedence[GE] = 11;
124          precedence[LSH] = precedence[RSH] = precedence[URSH] = 12;
125          precedence[ADD] = precedence[SUB] = 12;
126          precedence[MUL] = precedence[DIV] = precedence[MOD] = 13;
127          precedence[BITNOT] =  precedence[BANG] = precedence[TYPEOF] = 14;
128          precedence[DOT] = precedence[LB] = precedence[LP] =  precedence[INC] = precedence[DEC] = 15;
129      }
130  
131  
132      // Parsing Logic /////////////////////////////////////////////////////////
133  
134      /** gets a token and throws an exception if it is not <tt>code</tt> */
135      private void consume(int code) throws IOException {
136          if (getToken() != code) {
137              if(code == NAME) switch(op) {
138                  case RETURN: case TYPEOF: case BREAK: case CONTINUE: case TRY: case THROW:
139                  case ASSERT: case NULL: case TRUE: case FALSE: case IN: case IF: case ELSE:
140                  case SWITCH: case CASE: case DEFAULT: case WHILE: case VAR: case WITH:
141                  case CATCH: case FINALLY:
142                      throw pe("Bad variable name; '" + codeToString[op].toLowerCase() + "' is a javascript keyword");
143              }
144              throw pe("expected " + codeToString[code] + ", got " + (op == -1 ? "EOF" : codeToString[op]));
145          }
146      }
147  
148      /**
149       *  Parse the largest possible expression containing no operators
150       *  of precedence below <tt>minPrecedence</tt> and append the
151       *  bytecodes for that expression to <tt>appendTo</tt>; the
152       *  appended bytecodes MUST grow the stack by exactly one element.
153       */ 
154      private void startExpr(JSFunction appendTo, int minPrecedence) throws IOException {
155          int saveParserLine = parserLine;
156          _startExpr(appendTo, minPrecedence);
157          parserLine = saveParserLine;
158      }
159      private void _startExpr(JSFunction appendTo, int minPrecedence) throws IOException {
160          int tok = getToken();
161          JSFunction b = appendTo;
162  
163          switch (tok) {
164          case -1: throw pe("expected expression");
165  
166          // all of these simply push values onto the stack
167          case NUMBER: b.add(parserLine, LITERAL, number); break;
168          case STRING: b.add(parserLine, LITERAL, string); break;
169          case NULL: b.add(parserLine, LITERAL, null); break;
170          case TRUE: case FALSE: b.add(parserLine, LITERAL, JS.B(tok == TRUE)); break;
171  
172          // (.foo) syntax
173          case DOT: {
174              consume(NAME);
175              b.add(parserLine, TOPSCOPE);
176              b.add(parserLine, LITERAL, "");
177              b.add(parserLine, GET);
178              b.add(parserLine, LITERAL, string);
179              b.add(parserLine, GET);
180              continueExpr(b, minPrecedence);
181              break;
182          }
183  
184          case LB: {
185              b.add(parserLine, ARRAY, JS.ZERO);                       // push an array onto the stack
186              int size0 = b.size;
187              int i = 0;
188              if (peekToken() != RB)
189                  while(true) {                                               // iterate over the initialization values
190                      int size = b.size;
191                      b.add(parserLine, LITERAL, JS.N(i++));           // push the index in the array to place it into
192                      if (peekToken() == COMMA || peekToken() == RB)
193                          b.add(parserLine, LITERAL, null);                   // for stuff like [1,,2,]
194                      else
195                          startExpr(b, NO_COMMA);                             // push the value onto the stack
196                      b.add(parserLine, PUT);                                 // put it into the array
197                      b.add(parserLine, POP);                                 // discard the value remaining on the stack
198                      if (peekToken() == RB) break;
199                      consume(COMMA);
200                  }
201              b.set(size0 - 1, JS.N(i));                               // back at the ARRAY instruction, write the size of the array
202              consume(RB);
203              break;
204          }
205          case SUB: {  // negative literal (like "3 * -1")
206              consume(NUMBER);
207              b.add(parserLine, LITERAL, JS.N(number.doubleValue() * -1));
208              break;
209          }
210          case LP: {  // grouping (not calling)
211              startExpr(b, -1);
212              consume(RP);
213              break;
214          }
215          case INC: case DEC: {  // prefix (not postfix)
216              startExpr(b, precedence[tok]);
217              int prev = b.size - 1;
218              if (b.get(prev) == GET && b.getArg(prev) != null)
219                  b.set(prev, LITERAL, b.getArg(prev));
220              else if(b.get(prev) == GET)
221                  b.pop();
222              else
223                  throw pe("prefixed increment/decrement can only be performed on a valid assignment target");
224              b.add(parserLine, GET_PRESERVE, Boolean.TRUE);
225              b.add(parserLine, LITERAL, JS.N(1));
226              b.add(parserLine, tok == INC ? ADD : SUB, JS.N(2));
227              b.add(parserLine, PUT, null);
228              b.add(parserLine, SWAP, null);
229              b.add(parserLine, POP, null);
230              break;
231          }
232          case BANG: case BITNOT: case TYPEOF: {
233              startExpr(b, precedence[tok]);
234              b.add(parserLine, tok);
235              break;
236          }
237          case LC: { // object constructor
238              b.add(parserLine, OBJECT, null);                                     // put an object on the stack
239              if (peekToken() != RC)
240                  while(true) {
241                      if (peekToken() != NAME && peekToken() != STRING)
242                          throw pe("expected NAME or STRING");
243                      getToken();
244                      b.add(parserLine, LITERAL, string);                          // grab the key
245                      consume(COLON);
246                      startExpr(b, NO_COMMA);                                      // grab the value
247                      b.add(parserLine, PUT);                                      // put the value into the object
248                      b.add(parserLine, POP);                                      // discard the remaining value
249                      if (peekToken() == RC) break;
250                      consume(COMMA);
251                      if (peekToken() == RC) break;                                // we permit {,,} -- I'm not sure if ECMA does
252                  }
253              consume(RC);
254              break;
255          }
256          case NAME: {
257              b.add(parserLine, TOPSCOPE);
258              b.add(parserLine, LITERAL, string);
259              continueExprAfterAssignable(b,minPrecedence);
260              break;
261          }
262          case FUNCTION: {
263              consume(LP);
264              int numArgs = 0;
265              JSFunction b2 = new JSFunction(sourceName, parserLine, null);
266              b.add(parserLine, NEWFUNCTION, b2);
267  
268              // function prelude; arguments array is already on the stack
269              b2.add(parserLine, TOPSCOPE);
270              b2.add(parserLine, SWAP);
271              b2.add(parserLine, DECLARE, "arguments");                     // declare arguments (equivalent to 'var arguments;')
272              b2.add(parserLine, SWAP);                                     // set this.arguments and leave the value on the stack
273              b2.add(parserLine, PUT);
274  
275              while(peekToken() != RP) {                                    // run through the list of argument names
276                  numArgs++;
277                  if (peekToken() == NAME) {
278                      consume(NAME);                                        // a named argument
279                      String varName = string;
280                      
281                      b2.add(parserLine, DUP);                              // dup the args array 
282                      b2.add(parserLine, GET, JS.N(numArgs - 1));   // retrieve it from the arguments array
283                      b2.add(parserLine, TOPSCOPE);
284                      b2.add(parserLine, SWAP);
285                      b2.add(parserLine, DECLARE, varName);                  // declare the name
286                      b2.add(parserLine, SWAP);
287                      b2.add(parserLine, PUT); 
288                      b2.add(parserLine, POP);                               // pop the value
289                      b2.add(parserLine, POP);                               // pop the scope                  
290                  }
291                  if (peekToken() == RP) break;
292                  consume(COMMA);
293              }
294              consume(RP);
295  
296              b2.numFormalArgs = numArgs;
297              b2.add(parserLine, POP);                                      // pop off the arguments array
298              b2.add(parserLine, POP);                                      // pop off TOPSCOPE
299              
300             if(peekToken() != LC)
301                  throw pe("JSFunctions must have a block surrounded by curly brackets");
302                  
303              parseBlock(b2, null);                                   // the function body
304  
305              b2.add(parserLine, LITERAL, null);                        // in case we "fall out the bottom", return NULL
306              b2.add(parserLine, RETURN);
307  
308              break;
309          }
310          default: throw pe("expected expression, found " + codeToString[tok] + ", which cannot start an expression");
311          }
312  
313          // attempt to continue the expression
314          continueExpr(b, minPrecedence);
315      }
316  
317      private Grammar parseGrammar(Grammar g) throws IOException {
318          int tok = getToken();
319          if (g != null)
320              switch(tok) {
321                  case BITOR: return new Grammar.Alternative(g, parseGrammar(null));
322                  case ADD:   return parseGrammar(new Grammar.Repetition(g, 1, Integer.MAX_VALUE));
323                  case MUL:   return parseGrammar(new Grammar.Repetition(g, 0, Integer.MAX_VALUE));
324                  case HOOK:  return parseGrammar(new Grammar.Repetition(g, 0, 1));
325              }
326          Grammar g0 = null;
327          switch(tok) {
328              //case NUMBER: g0 = new Grammar.Literal(number); break;
329              case NAME: g0 = new Grammar.Reference(string); break;
330              case STRING:
331                  g0 = new Grammar.Literal(string);
332                  if (peekToken() == DOT) {
333                      String old = string;
334                      consume(DOT);
335                      consume(DOT);
336                      consume(STRING);
337                      if (old.length() != 1 || string.length() != 1) throw pe("literal ranges must be single-char strings");
338                      g0 = new Grammar.Range(old.charAt(0), string.charAt(0));
339                  }
340                  break;
341              case LP:     g0 = parseGrammar(null); consume(RP); break;
342              default:     pushBackToken(); return g;
343          }
344          if (g == null) return parseGrammar(g0);
345          return parseGrammar(new Grammar.Juxtaposition(g, g0));
346      }
347  
348      /**
349       *  Assuming that a complete assignable (lvalue) has just been
350       *  parsed and the object and key are on the stack,
351       *  <tt>continueExprAfterAssignable</tt> will attempt to parse an
352       *  expression that modifies the assignable.  This method always
353       *  decreases the stack depth by exactly one element.
354       */
355      private void continueExprAfterAssignable(JSFunction b,int minPrecedence) throws IOException {
356          int saveParserLine = parserLine;
357          _continueExprAfterAssignable(b,minPrecedence);
358          parserLine = saveParserLine;
359      }
360      private void _continueExprAfterAssignable(JSFunction b,int minPrecedence) throws IOException {
361          if (b == null) throw new Error("got null b; this should never happen");
362          int tok = getToken();
363          if (minPrecedence != -1 && (precedence[tok] < minPrecedence || (precedence[tok] == minPrecedence && !isRightAssociative[tok])))
364              // force the default case
365              tok = -1;
366          switch(tok) {
367  
368          case GRAMMAR: {
369              b.add(parserLine, GET_PRESERVE);
370              Grammar g = parseGrammar(null);
371              if (peekToken() == LC) {
372                  g.action = new JSFunction(sourceName, parserLine, null);
373                  parseBlock((JSFunction)g.action);
374                  ((JSFunction)g.action).add(parserLine, LITERAL, null);         // in case we "fall out the bottom", return NULL              
375                  ((JSFunction)g.action).add(parserLine, RETURN);
376              }
377              b.add(parserLine, MAKE_GRAMMAR, g);
378              b.add(parserLine, PUT);
379              break;
380          }
381  
382          case ASSIGN_BITOR: case ASSIGN_BITXOR: case ASSIGN_BITAND: case ASSIGN_LSH: case ASSIGN_RSH: case ASSIGN_URSH:
383          case ASSIGN_MUL: case ASSIGN_DIV: case ASSIGN_MOD: case ASSIGN_ADD: case ASSIGN_SUB: {
384              if (tok != ASSIGN_ADD && tok != ASSIGN_SUB) b.add(parserLine, GET_PRESERVE);
385              
386              startExpr(b,  precedence[tok]);
387              
388              int size = b.size;
389              if (tok == ASSIGN_ADD || tok == ASSIGN_SUB) {
390                  b.add(parserLine, tok);
391                  b.add(parserLine, GET);
392                  b.add(parserLine, SWAP);
393              }
394              
395              // tok-1 is always s/^ASSIGN_// (0 is BITOR, 1 is ASSIGN_BITOR, etc) 
396              b.add(parserLine, tok - 1, tok-1==ADD ? JS.N(2) : null);
397              b.add(parserLine, PUT);
398              b.add(parserLine, SWAP);
399              b.add(parserLine, POP);
400              
401              if (tok == ASSIGN_ADD || tok == ASSIGN_SUB) b.set(size, tok, JS.N(b.size - size));
402              break;
403          }
404          case INC: case DEC: { // postfix
405              b.add(parserLine, GET_PRESERVE, Boolean.TRUE);
406              b.add(parserLine, LITERAL, JS.N(1));
407              b.add(parserLine, tok == INC ? ADD : SUB, JS.N(2));
408              b.add(parserLine, PUT, null);
409              b.add(parserLine, SWAP, null);
410              b.add(parserLine, POP, null);
411              b.add(parserLine, LITERAL, JS.N(1));
412              b.add(parserLine, tok == INC ? SUB : ADD, null);   // undo what we just did, since this is postfix
413              break;
414          }
415          case ASSIGN: {
416              startExpr(b, precedence[tok]);
417              b.add(parserLine, PUT);
418              b.add(parserLine, SWAP);
419              b.add(parserLine, POP);
420              break;
421          }
422          case LP: {
423  
424              // Method calls are implemented by doing a GET_PRESERVE
425              // first.  If the object supports method calls, it will
426              // return JS.METHOD
427              int n = parseArgs(b, 2);
428              b.add(parserLine, GET_PRESERVE);
429              b.add(parserLine, CALLMETHOD, JS.N(n));
430              break;
431          }
432          default: {
433              pushBackToken();
434              if(b.get(b.size-1) == LITERAL && b.getArg(b.size-1) != null)
435                  b.set(b.size-1,GET,b.getArg(b.size-1));
436              else
437                  b.add(parserLine, GET);
438              return;
439          }
440          }
441      }
442  
443  
444      /**
445       *  Assuming that a complete expression has just been parsed,
446       *  <tt>continueExpr</tt> will attempt to extend this expression by
447       *  parsing additional tokens and appending additional bytecodes.
448       *
449       *  No operators with precedence less than <tt>minPrecedence</tt>
450       *  will be parsed.
451       *
452       *  If any bytecodes are appended, they will not alter the stack
453       *  depth.
454       */
455      private void continueExpr(JSFunction b, int minPrecedence) throws IOException {
456          int saveParserLine = parserLine;
457          _continueExpr(b, minPrecedence);
458          parserLine = saveParserLine;
459      }
460      private void _continueExpr(JSFunction b, int minPrecedence) throws IOException {
461          if (b == null) throw new Error("got null b; this should never happen");
462          int tok = getToken();
463          if (tok == -1) return;
464          if (minPrecedence != -1 && (precedence[tok] < minPrecedence || (precedence[tok] == minPrecedence && !isRightAssociative[tok]))) {
465              pushBackToken();
466              return;
467          }
468  
469          switch (tok) {
470          case LP: {  // invocation (not grouping)
471              int n = parseArgs(b, 1);
472              b.add(parserLine, CALL, JS.N(n));
473              break;
474          }
475          case BITOR: case BITXOR: case BITAND: case SHEQ: case SHNE: case LSH:
476          case RSH: case URSH: case MUL: case DIV: case MOD:
477          case GT: case GE: case EQ: case NE: case LT: case LE: case SUB: {
478              startExpr(b, precedence[tok]);
479              b.add(parserLine, tok);
480              break;
481          }
482          case ADD: {
483              int count=1;
484              int nextTok;
485              do {
486                  startExpr(b,precedence[tok]);
487                  count++;
488                  nextTok = getToken();
489              } while(nextTok == tok);
490              pushBackToken();
491              b.add(parserLine, tok, JS.N(count));
492              break;
493          }
494          case OR: case AND: {
495              b.add(parserLine, tok == AND ? b.JF : b.JT, JS.ZERO);       // test to see if we can short-circuit
496              int size = b.size;
497              startExpr(b, precedence[tok]);                                     // otherwise check the second value
498              b.add(parserLine, JMP, JS.N(2));                            // leave the second value on the stack and jump to the end
499              b.add(parserLine, LITERAL, tok == AND ?
500                    JS.B(false) : JS.B(true));                     // target of the short-circuit jump is here
501              b.set(size - 1, JS.N(b.size - size));                     // write the target of the short-circuit jump
502              break;
503          }
504          case DOT: {
505              // support foo..bar syntax for foo[""].bar
506              if (peekToken() == DOT) {
507                  string = "";
508              } else {
509                  consume(NAME);
510              }
511              b.add(parserLine, LITERAL, string);
512              continueExprAfterAssignable(b,minPrecedence);
513              break;
514          }
515          case LB: { // subscripting (not array constructor)
516              startExpr(b, -1);
517              consume(RB);
518              continueExprAfterAssignable(b,minPrecedence);
519              break;
520          }
521          case HOOK: {
522              b.add(parserLine, JF, JS.ZERO);                // jump to the if-false expression
523              int size = b.size;
524              startExpr(b, minPrecedence);                          // write the if-true expression
525              b.add(parserLine, JMP, JS.ZERO);               // if true, jump *over* the if-false expression     
526              b.set(size - 1, JS.N(b.size - size + 1));    // now we know where the target of the jump is
527              consume(COLON);
528              size = b.size;
529              startExpr(b, minPrecedence);                          // write the if-false expression
530              b.set(size - 1, JS.N(b.size - size + 1));    // this is the end; jump to here
531              break;
532          }
533          case COMMA: {
534              // pop the result of the previous expression, it is ignored
535              b.add(parserLine,POP);
536              startExpr(b,-1);
537              break;
538          }
539          default: {
540              pushBackToken();
541              return;
542          }
543          }
544  
545          continueExpr(b, minPrecedence);                           // try to continue the expression
546      }
547      
548      // parse a set of comma separated function arguments, assume LP has already been consumed
549      // if swap is true, (because the function is already on the stack) we will SWAP after each argument to keep it on top
550      private int parseArgs(JSFunction b, int pushdown) throws IOException {
551          int i = 0;
552          while(peekToken() != RP) {
553              i++;
554              if (peekToken() != COMMA) {
555                  startExpr(b, NO_COMMA);
556                  b.add(parserLine, SWAP, JS.N(pushdown));
557                  if (peekToken() == RP) break;
558              }
559              consume(COMMA);
560          }
561          consume(RP);
562          return i;
563      }
564      
565      /** Parse a block of statements which must be surrounded by LC..RC. */
566      void parseBlock(JSFunction b) throws IOException { parseBlock(b, null); }
567      void parseBlock(JSFunction b, String label) throws IOException {
568          int saveParserLine = parserLine;
569          _parseBlock(b, label);
570          parserLine = saveParserLine;
571      }
572      void _parseBlock(JSFunction b, String label) throws IOException {
573          if (peekToken() == -1) return;
574          else if (peekToken() != LC) parseStatement(b, null);
575          else {
576              consume(LC);
577              while(peekToken() != RC && peekToken() != -1) parseStatement(b, null);
578              consume(RC);
579          }
580      }
581  
582      /** Parse a single statement, consuming the RC or SEMI which terminates it. */
583      void parseStatement(JSFunction b, String label) throws IOException {
584          int saveParserLine = parserLine;
585          _parseStatement(b, label);
586          parserLine = saveParserLine;
587      }
588      void _parseStatement(JSFunction b, String label) throws IOException {
589          int tok = peekToken();
590          if (tok == -1) return;
591          switch(tok = getToken()) {
592              
593          case THROW: case ASSERT: case RETURN: {
594              if (tok == RETURN && peekToken() == SEMI)
595                  b.add(parserLine, LITERAL, null);
596              else
597                  startExpr(b, -1);
598              b.add(parserLine, tok);
599              consume(SEMI);
600              break;
601          }
602          case BREAK: case CONTINUE: {
603              if (peekToken() == NAME) consume(NAME);
604              b.add(parserLine, tok, string);
605              consume(SEMI);
606              break;
607          }
608          case VAR: {
609              b.add(parserLine, TOPSCOPE);                         // push the current scope
610              while(true) {
611                  consume(NAME);
612                  b.add(parserLine, DECLARE, string);               // declare it
613                  if (peekToken() == ASSIGN) {                     // if there is an '=' after the variable name
614                      consume(ASSIGN);
615                      startExpr(b, NO_COMMA);
616                      b.add(parserLine, PUT);                      // assign it
617                      b.add(parserLine, POP);                      // clean the stack
618                  } else {
619                      b.add(parserLine, POP);                      // pop the string pushed by declare
620                  }   
621                  if (peekToken() != COMMA) break;
622                  consume(COMMA);
623              }
624              b.add(parserLine, POP);                              // pop off the topscope
625              if ((mostRecentlyReadToken != RC || peekToken() == SEMI) && peekToken() != -1 && mostRecentlyReadToken != SEMI) consume(SEMI);
626              break;
627          }
628          case IF: {
629              consume(LP);
630              startExpr(b, -1);
631              consume(RP);
632              
633              b.add(parserLine, JF, JS.ZERO);                    // if false, jump to the else-block
634              int size = b.size;
635              parseStatement(b, null);
636              
637              if (peekToken() == ELSE) {
638                  consume(ELSE);
639                  b.add(parserLine, JMP, JS.ZERO);               // if we took the true-block, jump over the else-block
640                  b.set(size - 1, JS.N(b.size - size + 1));
641                  size = b.size;
642                  parseStatement(b, null);
643              }
644              b.set(size - 1, JS.N(b.size - size + 1));        // regardless of which branch we took, b[size] needs to point here
645              break;
646          }
647          case WHILE: {
648              consume(LP);
649              if (label != null) b.add(parserLine, LABEL, label);
650              b.add(parserLine, LOOP);
651              int size = b.size;
652              b.add(parserLine, POP);                                   // discard the first-iteration indicator
653              startExpr(b, -1);
654              b.add(parserLine, JT, JS.N(2));                    // if the while() clause is true, jump over the BREAK
655              b.add(parserLine, BREAK);
656              consume(RP);
657              parseStatement(b, null);
658              b.add(parserLine, CONTINUE);                              // if we fall out of the end, definately continue
659              b.set(size - 1, JS.N(b.size - size + 1));        // end of the loop
660              break;
661          }
662          case SWITCH: {
663              consume(LP);
664              if (label != null) b.add(parserLine, LABEL, label);
665              b.add(parserLine, LOOP);
666              int size0 = b.size;
667              startExpr(b, -1);
668              consume(RP);
669              consume(LC);
670              while(true)
671                  if (peekToken() == CASE) {                         // we compile CASE statements like a bunch of if..else's
672                      consume(CASE);
673                      b.add(parserLine, DUP);                        // duplicate the switch() value; we'll consume one copy
674                      startExpr(b, -1);
675                      consume(COLON);
676                      b.add(parserLine, EQ);                         // check if we should do this case-block
677                      b.add(parserLine, JF, JS.ZERO);         // if not, jump to the next one
678                      int size = b.size;
679                      while(peekToken() != CASE && peekToken() != DEFAULT && peekToken() != RC) parseStatement(b, null);
680                      b.set(size - 1, JS.N(1 + b.size - size));
681                  } else if (peekToken() == DEFAULT) {
682                      consume(DEFAULT);
683                      consume(COLON);
684                      while(peekToken() != CASE && peekToken() != DEFAULT && peekToken() != RC) parseStatement(b, null);
685                  } else if (peekToken() == RC) {
686                      consume(RC);
687                      b.add(parserLine, BREAK);                      // break out of the loop if we 'fall through'
688                      break;
689                  } else {
690                      throw pe("expected CASE, DEFAULT, or RC; got " + codeToString[peekToken()]);
691                  }
692              b.set(size0 - 1, JS.N(b.size - size0 + 1));      // end of the loop
693              break;
694          }
695              
696          case DO: {
697              if (label != null) b.add(parserLine, LABEL, label);
698              b.add(parserLine, LOOP);
699              int size = b.size;
700              parseStatement(b, null);
701              consume(WHILE);
702              consume(LP);
703              startExpr(b, -1);
704              b.add(parserLine, JT, JS.N(2));                  // check the while() clause; jump over the BREAK if true
705              b.add(parserLine, BREAK);
706              b.add(parserLine, CONTINUE);
707              consume(RP);
708              consume(SEMI);
709              b.set(size - 1, JS.N(b.size - size + 1));      // end of the loop; write this location to the LOOP instruction
710              break;
711          }
712              
713          case TRY: {
714              b.add(parserLine, TRY); // try bytecode causes a TryMarker to be pushed
715              int tryInsn = b.size - 1;
716              // parse the expression to be TRYed
717              parseStatement(b, null); 
718              // pop the try  marker. this is pushed when the TRY bytecode is executed                              
719              b.add(parserLine, POP);
720              // jump forward to the end of the catch block, start of the finally block                             
721              b.add(parserLine, JMP);                                  
722              int successJMPInsn = b.size - 1;
723              
724              if (peekToken() != CATCH && peekToken() != FINALLY)
725                  throw pe("try without catch or finally");
726              
727              int catchJMPDistance = -1;
728              if (peekToken() == CATCH) {
729                  Vec catchEnds = new Vec();
730                  boolean catchAll = false;
731                  
732                  catchJMPDistance = b.size - tryInsn;
733                  
734                  while(peekToken() == CATCH && !catchAll) {
735                      String exceptionVar;
736                      getToken();
737                      consume(LP);
738                      consume(NAME);
739                      exceptionVar = string;
740                      int[] writebacks = new int[] { -1, -1, -1 };
741                      if (peekToken() != RP) {
742                          // extended XWT catch block: catch(e faultCode "foo.bar.baz")
743                          consume(NAME);
744                          String propName = string;
745                          b.add(parserLine, DUP);
746                          b.add(parserLine, LITERAL, string);
747                          b.add(parserLine, GET);
748                          b.add(parserLine, DUP);
749                          b.add(parserLine, LITERAL, null);
750                          b.add(parserLine, EQ);
751                          b.add(parserLine, JT);
752                          writebacks[0] = b.size - 1;
753                          if (peekToken() == STRING) {
754                              consume(STRING);
755                              b.add(parserLine, DUP);
756                              b.add(parserLine, LITERAL, string);
757                              b.add(parserLine, LT);
758                              b.add(parserLine, JT);
759                              writebacks[1] = b.size - 1;
760                              b.add(parserLine, DUP);
761                              b.add(parserLine, LITERAL, string + "/");   // (slash is ASCII after dot)
762                              b.add(parserLine, GE);
763                              b.add(parserLine, JT);
764                              writebacks[2] = b.size - 1;
765                          } else {
766                              consume(NUMBER);
767                              b.add(parserLine, DUP);
768                              b.add(parserLine, LITERAL, number);
769                              b.add(parserLine, EQ);
770                              b.add(parserLine, JF);
771                              writebacks[1] = b.size - 1;
772                          }
773                          b.add(parserLine, POP);  // pop the element thats on the stack from the compare
774                      } else {
775                          catchAll = true;
776                      }
777                      consume(RP);
778                      // the exception is on top of the stack; put it to the chosen name
779                      b.add(parserLine, NEWSCOPE);
780                      b.add(parserLine, TOPSCOPE);
781                      b.add(parserLine, SWAP);
782                      b.add(parserLine, LITERAL,exceptionVar);
783                      b.add(parserLine, DECLARE);
784                      b.add(parserLine, SWAP);
785                      b.add(parserLine, PUT);
786                      b.add(parserLine, POP);
787                      b.add(parserLine, POP);
788                      parseBlock(b, null);
789                      b.add(parserLine, OLDSCOPE);
790                      
791                      b.add(parserLine, JMP);
792                      catchEnds.addElement(new Integer(b.size-1));
793                      
794                      for(int i=0; i<3; i++) if (writebacks[i] != -1) b.set(writebacks[i], JS.N(b.size-writebacks[i]));
795                      b.add(parserLine, POP); // pop the element thats on the stack from the compare
796                  }
797                  
798                  if(!catchAll)
799                      b.add(parserLine, THROW);
800                  
801                  for(int i=0;i<catchEnds.size();i++) {
802                      int n = ((Integer)catchEnds.elementAt(i)).intValue();
803                      b.set(n, JS.N(b.size-n));
804                  }
805                  
806                  // pop the try and catch markers
807                  b.add(parserLine,POP);
808                  b.add(parserLine,POP);
809              }
810                          
811              // jump here if no exception was thrown
812              b.set(successJMPInsn, JS.N(b.size - successJMPInsn)); 
813                          
814              int finallyJMPDistance = -1;
815              if (peekToken() == FINALLY) {
816                  b.add(parserLine, LITERAL, null); // null FinallyData
817                  finallyJMPDistance = b.size - tryInsn;
818                  consume(FINALLY);
819                  parseStatement(b, null);
820                  b.add(parserLine,FINALLY_DONE); 
821              }
822              
823              // setup the TRY arguments
824              b.set(tryInsn, new int[] { catchJMPDistance, finallyJMPDistance });
825              
826              break;
827          }
828              
829          case FOR: {
830              consume(LP);
831              
832              tok = getToken();
833              boolean hadVar = false;                                      // if it's a for..in, we ignore the VAR
834              if (tok == VAR) { hadVar = true; tok = getToken(); }
835              String varName = string;
836              boolean forIn = peekToken() == IN;                           // determine if this is a for..in loop or not
837              pushBackToken(tok, varName);
838              
839              if (forIn) {
840                  b.add(parserLine, NEWSCOPE);                             // for-loops always create new scopes
841                  b.add(parserLine, LITERAL, varName);                     // declare the new variable
842                  b.add(parserLine, DECLARE);
843                      
844                  b.add(parserLine, LOOP);                                 // we actually only add this to ensure that BREAK works
845                  b.add(parserLine, POP);                                  // discard the first-iteration indicator
846                  int size = b.size;
847                  consume(NAME);
848                  consume(IN);
849                  startExpr(b, -1);
850                  b.add(parserLine, PUSHKEYS);                             // push the keys as an array; check the length
851                  b.add(parserLine, LITERAL, "length");
852                  b.add(parserLine, GET);
853                  consume(RP);
854                      
855                  b.add(parserLine, LITERAL, JS.N(1));              // decrement the length
856                  b.add(parserLine, SUB);
857                  b.add(parserLine, DUP);
858                  b.add(parserLine, LITERAL, JS.ZERO);              // see if we've exhausted all the elements
859                  b.add(parserLine, LT);
860                  b.add(parserLine, JF, JS.N(2));
861                  b.add(parserLine, BREAK);                                // if we have, then BREAK
862                  b.add(parserLine, GET_PRESERVE);                         // get the key out of the keys array
863                  b.add(parserLine, LITERAL, varName);
864                  b.add(parserLine, PUT);                                  // write it to this[varName]                          
865                  parseStatement(b, null);                                 // do some stuff
866                  b.add(parserLine, CONTINUE);                             // continue if we fall out the bottom
867  
868                  b.set(size - 1, JS.N(b.size - size + 1));       // BREAK to here
869                  b.add(parserLine, OLDSCOPE);                             // restore the scope
870                      
871              } else {
872                  if (hadVar) pushBackToken(VAR, null);                    // yeah, this actually matters
873                  b.add(parserLine, NEWSCOPE);                             // grab a fresh scope
874                      
875                  parseStatement(b, null);                                 // initializer
876                  JSFunction e2 =                                    // we need to put the incrementor before the test
877                      new JSFunction(sourceName, parserLine, null);  // so we save the test here
878                  if (peekToken() != SEMI)
879                      startExpr(e2, -1);
880                  else
881                      e2.add(parserLine, b.LITERAL, Boolean.TRUE);         // handle the for(foo;;foo) case
882                  consume(SEMI);
883                  if (label != null) b.add(parserLine, LABEL, label);
884                  b.add(parserLine, LOOP);
885                  int size2 = b.size;
886                      
887                  b.add(parserLine, JT, JS.ZERO);                   // if we're on the first iteration, jump over the incrementor
888                  int size = b.size;
889                  if (peekToken() != RP) {                                 // do the increment thing
890                      startExpr(b, -1);
891                      b.add(parserLine, POP);
892                  }
893                  b.set(size - 1, JS.N(b.size - size + 1));
894                  consume(RP);
895                      
896                  b.paste(e2);                                             // ok, *now* test if we're done yet
897                  b.add(parserLine, JT, JS.N(2));                   // break out if we don't meet the test
898                  b.add(parserLine, BREAK);
899                  parseStatement(b, null);
900                  b.add(parserLine, CONTINUE);                             // if we fall out the bottom, CONTINUE
901                  b.set(size2 - 1, JS.N(b.size - size2 + 1));     // end of the loop
902                      
903                  b.add(parserLine, OLDSCOPE);                             // get our scope back
904              }
905              break;
906          }
907                  
908          case NAME: {  // either a label or an identifier; this is the one place we're not LL(1)
909              String possiblyTheLabel = string;
910              if (peekToken() == COLON) {      // label
911                  consume(COLON);
912                  parseStatement(b, possiblyTheLabel);
913                  break;
914              } else {                         // expression
915                  pushBackToken(NAME, possiblyTheLabel);  
916                  startExpr(b, -1);
917                  b.add(parserLine, POP);
918                  if ((mostRecentlyReadToken != RC || peekToken() == SEMI) && peekToken() != -1 && mostRecentlyReadToken != SEMI) consume(SEMI);
919                  break;
920              }
921          }
922  
923          case SEMI: return;                                               // yep, the null statement is valid
924  
925          case LC: {  // blocks are statements too
926              pushBackToken();
927              b.add(parserLine, NEWSCOPE);
928              parseBlock(b, label);
929              b.add(parserLine, OLDSCOPE);
930              break;
931          }
932  
933          default: {  // hope that it's an expression
934              pushBackToken();
935              startExpr(b, -1);
936              b.add(parserLine, POP);
937              if ((mostRecentlyReadToken != RC || peekToken() == SEMI) && peekToken() != -1 && mostRecentlyReadToken != SEMI) consume(SEMI);
938              break;
939          }
940          }
941      }
942  
943  
944      // ParserException //////////////////////////////////////////////////////////////////////
945      private IOException pe(String s) { return new IOException(sourceName + ":" + parserLine + " " + s); }
946      
947  }
948  
949