96c211843a3980dbaa4da3a0d4c324960c279322
[WebKit-https.git] / PerformanceTests / RexBench / Basic / parser.js
1 /*
2  * Copyright (C) 2016-2017 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25 "use strict";
26
27 function parse(tokenizer)
28 {
29     let program;
30     
31     let pushBackBuffer = [];
32     
33     function nextToken()
34     {
35         if (pushBackBuffer.length)
36             return pushBackBuffer.pop();
37         let result = tokenizer.next();
38         if (result.done)
39             return {kind: "endOfFile", string: "<end of file>"};
40         return result.value;
41     }
42     
43     function pushToken(token)
44     {
45         pushBackBuffer.push(token);
46     }
47     
48     function peekToken()
49     {
50         let result = nextToken();
51         pushToken(result);
52         return result;
53     }
54     
55     function consumeKind(kind)
56     {
57         let token = nextToken();
58         if (token.kind != kind) {
59             throw new Error("At " + token.sourceLineNumber + ": expected " + kind + " but got: " + token.string);
60         }
61         return token;
62     }
63     
64     function consumeToken(string)
65     {
66         let token = nextToken();
67         if (token.string.toLowerCase() != string.toLowerCase())
68             throw new Error("At " + token.sourceLineNumber + ": expected " + string + " but got: " + token.string);
69         return token;
70     }
71     
72     function parseVariable()
73     {
74         let name = consumeKind("identifier").string;
75         let result = {evaluate: Basic.Variable, name, parameters: []};
76         if (peekToken().string == "(") {
77             do {
78                 nextToken();
79                 result.parameters.push(parseNumericExpression());
80             } while (peekToken().string == ",");
81             consumeToken(")");
82         }
83         return result;
84     }
85     
86     function parseNumericExpression()
87     {
88         function parsePrimary()
89         {
90             let token = nextToken();
91             switch (token.kind) {
92             case "identifier": {
93                 let result = {evaluate: Basic.NumberApply, name: token.string, parameters: []};
94                 if (peekToken().string == "(") {
95                     do {
96                         nextToken();
97                         result.parameters.push(parseNumericExpression());
98                     } while (peekToken().string == ",");
99                     consumeToken(")");
100                 }
101                 return result;
102             }
103                 
104             case "number":
105                 return {evaluate: Basic.Const, value: token.value};
106                 
107             case "operator":
108                 switch (token.string) {
109                 case "(": {
110                     let result = parseNumericExpression();
111                     consumeToken(")");
112                     return result;
113                 } }
114                 break;
115             }
116             throw new Error("At " + token.sourceLineNumber + ": expected identifier, number, or (, but got: " + token.string);
117         }
118         
119         function parseFactor()
120         {
121             let primary = parsePrimary();
122             
123             let ok = true;
124             while (ok) {
125                 switch (peekToken().string) {
126                 case "^":
127                     nextToken();
128                     primary = {evaluate: Basic.NumberPow, left: primary, right: parsePrimary()};
129                     break;
130                 default:
131                     ok = false;
132                     break;
133                 }
134             }
135             
136             return primary;
137         }
138         
139         function parseTerm()
140         {
141             let factor = parseFactor();
142             
143             let ok = true;
144             while (ok) {
145                 switch (peekToken().string) {
146                 case "*":
147                     nextToken();
148                     factor = {evaluate: Basic.NumberMul, left: factor, right: parseFactor()};
149                     break;
150                 case "/":
151                     nextToken();
152                     factor = {evaluate: Basic.NumberDiv, left: factor, right: parseFactor()};
153                     break;
154                 default:
155                     ok = false;
156                     break;
157                 }
158             }
159             
160             return factor;
161         }
162         
163         // Only the leading term in Basic can have a sign.
164         let negate = false;
165         switch (peekToken().string) {
166         case "+":
167             nextToken();
168             break;
169         case "-":
170             negate = true;
171             nextToken()
172             break;
173         }
174         
175         let term = parseTerm();
176         if (negate)
177             term = {evaluate: Basic.NumberNeg, term: term};
178         
179         let ok = true;
180         while (ok) {
181             switch (peekToken().string) {
182             case "+":
183                 nextToken();
184                 term = {evaluate: Basic.NumberAdd, left: term, right: parseTerm()};
185                 break;
186             case "-":
187                 nextToken();
188                 term = {evaluate: Basic.NumberSub, left: term, right: parseTerm()};
189                 break;
190             default:
191                 ok = false;
192                 break;
193             }
194         }
195         
196         return term;
197     }
198     
199     function parseConstant()
200     {
201         switch (peekToken().string) {
202         case "+":
203             nextToken();
204             return consumeKind("number").value;
205         case "-":
206             nextToken();
207             return -consumeKind("number").value;
208         default:
209             if (isStringExpression())
210                 return consumeKind("string").value;
211             return consumeKind("number").value;
212         }
213     }
214     
215     function parseStringExpression()
216     {
217         let token = nextToken();
218         switch (token.kind) {
219         case "string":
220             return {evaluate: Basic.Const, value: token.value};
221         case "identifier":
222             consumeToken("$");
223             return {evaluate: Basic.StringVar, name: token.string};
224         default:
225             throw new Error("At " + token.sourceLineNumber + ": expected string expression but got " + token.string);
226         }
227     }
228     
229     function isStringExpression()
230     {
231         // A string expression must start with a string variable or a string constant.
232         let token = nextToken();
233         if (token.kind == "string") {
234             pushToken(token);
235             return true;
236         }
237         if (token.kind == "identifier") {
238             let result = peekToken().string == "$";
239             pushToken(token);
240             return result;
241         }
242         pushToken(token);
243         return false;
244     }
245     
246     function parseRelationalExpression()
247     {
248         if (isStringExpression()) {
249             let left = parseStringExpression();
250             let operator = nextToken();
251             let evaluate;
252             switch (operator.string) {
253             case "=":
254                 evaluate = Basic.Equals;
255                 break;
256             case "<>":
257                 evaluate = Basic.NotEquals;
258                 break;
259             default:
260                 throw new Error("At " + operator.sourceLineNumber + ": expected a string comparison operator but got: " + operator.string);
261             }
262             return {evaluate, left, right: parseStringExpression()};
263         }
264         
265         let left = parseNumericExpression();
266         let operator = nextToken();
267         let evaluate;
268         switch (operator.string) {
269         case "=":
270             evaluate = Basic.Equals;
271             break;
272         case "<>":
273             evaluate = Basic.NotEquals;
274             break;
275         case "<":
276             evaluate = Basic.LessThan;
277             break;
278         case ">":
279             evaluate = Basic.GreaterThan;
280             break;
281         case "<=":
282             evaluate = Basic.LessEqual;
283             break;
284         case ">=":
285             evaluate = Basic.GreaterEqual;
286             break;
287         default:
288             throw new Error("At " + operator.sourceLineNumber + ": expected a numeric comparison operator but got: " + operator.string);
289         }
290         return {evaluate, left, right: parseNumericExpression()};
291     }
292     
293     function parseNonNegativeInteger()
294     {
295         let token = nextToken();
296         if (!/^[0-9]+$/.test(token.string))
297             throw new Error("At ", token.sourceLineNumber + ": expected a line number but got: " + token.string);
298         return token.value;
299     }
300     
301     function parseGoToStatement()
302     {
303         statement.kind = Basic.GoTo;
304         statement.target = parseNonNegativeInteger();
305     }
306     
307     function parseGoSubStatement()
308     {
309         statement.kind = Basic.GoSub;
310         statement.target = parseNonNegativeInteger();
311     }
312     
313     function parseStatement()
314     {
315         let statement = {};
316         statement.lineNumber = consumeKind("userLineNumber").userLineNumber;
317         program.statements.set(statement.lineNumber, statement);
318         
319         let command = nextToken();
320         statement.sourceLineNumber = command.sourceLineNumber;
321         switch (command.kind) {
322         case "keyword":
323             switch (command.string.toLowerCase()) {
324             case "def":
325                 statement.process = Basic.Def;
326                 statement.name = consumeKind("identifier");
327                 statement.parameters = [];
328                 if (peekToken().string == "(") {
329                     do {
330                         nextToken();
331                         statement.parameters.push(consumeKind("identifier"));
332                     } while (peekToken().string == ",");
333                 }
334                 statement.expression = parseNumericExpression();
335                 break;
336             case "let":
337                 statement.process = Basic.Let;
338                 statement.variable = parseVariable();
339                 consumeToken("=");
340                 if (statement.process == Basic.Let)
341                     statement.expression = parseNumericExpression();
342                 else
343                     statement.expression = parseStringExpression();
344                 break;
345             case "go": {
346                 let next = nextToken();
347                 if (next.string == "to")
348                     parseGoToStatement();
349                 else if (next.string == "sub")
350                     parseGoSubStatement();
351                 else
352                     throw new Error("At " + next.sourceLineNumber + ": expected to or sub but got: " + next.string);
353                 break;
354             }
355             case "goto":
356                 parseGoToStatement();
357                 break;
358             case "gosub":
359                 parseGoSubStatement();
360                 break;
361             case "if":
362                 statement.process = Basic.If;
363                 statement.condition = parseRelationalExpression();
364                 consumeToken("then");
365                 statement.target = parseNonNegativeInteger();
366                 break;
367             case "return":
368                 statement.process = Basic.Return;
369                 break;
370             case "stop":
371                 statement.process = Basic.Stop;
372                 break;
373             case "on":
374                 statement.process = Basic.On;
375                 statement.expression = parseNumericExpression();
376                 if (peekToken().string == "go") {
377                     consumeToken("go");
378                     consumeToken("to");
379                 } else
380                     consumeToken("goto");
381                 statement.targets = [];
382                 for (;;) {
383                     statement.targets.push(parseNonNegativeInteger());
384                     if (peekToken().string != ",")
385                         break;
386                     nextToken();
387                 }
388                 break;
389             case "for":
390                 statement.process = Basic.For;
391                 statement.variable = consumeKind("identifier").string;
392                 consumeToken("=");
393                 statement.initial = parseNumericExpression();
394                 consumeToken("to");
395                 statement.limit = parseNumericExpression();
396                 if (peekToken().string == "step") {
397                     nextToken();
398                     statement.step = parseNumericExpression();
399                 } else
400                     statement.step = {evaluate: Basic.Const, value: 1};
401                 consumeKind("newLine");
402                 let lastStatement = parseStatements();
403                 if (lastStatement.process != Basic.Next)
404                     throw new Error("At " + lastStatement.sourceLineNumber + ": expected next statement");
405                 if (lastStatement.variable != statement.variable)
406                     throw new Error("At " + lastStatement.sourceLineNumber + ": expected next for " + statement.variable + " but got " + lastStatement.variable);
407                 lastStatement.target = statement;
408                 statement.target = lastStatement;
409                 return statement;
410             case "next":
411                 statement.process = Basic.Next;
412                 statement.variable = consumeKind("identifier").string;
413                 break;
414             case "print": {
415                 statement.process = Basic.Print;
416                 statement.items = [];
417                 let ok = true;
418                 while (ok) {
419                     switch (peekToken().string) {
420                     case ",":
421                         nextToken();
422                         statement.items.push({kind: "comma"});
423                         break;
424                     case ";":
425                         nextToken();
426                         break;
427                     case "tab":
428                         nextToken();
429                         consumeToken("(");
430                         statement.items.push({kind: "tab", value: parseNumericExpression()});
431                         break;
432                     case "\n":
433                         ok = false;
434                         break;
435                     default:
436                         if (isStringExpression()) {
437                             statement.items.push({kind: "string", value: parseStringExpression()});
438                             break;
439                         }
440                         statement.items.push({kind: "number", value: parseNumericExpression()});
441                         break;
442                     }
443                 }
444                 break;
445             }
446             case "input":
447                 statement.process = Basic.Input;
448                 statement.items = [];
449                 for (;;) {
450                     statement.items.push(parseVariable());
451                     if (peekToken().string != ",")
452                         break;
453                     nextToken();
454                 }
455                 break;
456             case "read":
457                 statement.process = Basic.Read;
458                 statement.items = [];
459                 for (;;) {
460                     stament.items.push(parseVariable());
461                     if (peekToken().string != ",")
462                         break;
463                     nextToken();
464                 }
465                 break;
466             case "restore":
467                 statement.process = Basic.Restore;
468                 break;
469             case "data":
470                 for (;;) {
471                     program.data.push(parseConstant());
472                     if (peekToken().string != ",")
473                         break;
474                     nextToken();
475                 }
476                 break;
477             case "dim":
478                 statement.process = Basic.Dim;
479                 statement.items = [];
480                 for (;;) {
481                     let name = consumeKind("identifier").string;
482                     consumeToken("(");
483                     let bounds = [];
484                     bounds.push(parseNonNegativeInteger());
485                     if (peekToken().string == ",") {
486                         nextToken();
487                         bounds.push(parseNonNegativeInteger());
488                     }
489                     consumeToken(")");
490                     statement.items.push({name, bounds});
491                     
492                     if (peekToken().string != ",")
493                         break;
494                     consumeToken(",");
495                 }
496                 break;
497             case "option": {
498                 consumeToken("base");
499                 let base = parseNonNegativeInteger();
500                 if (base != 0 && base != 1)
501                     throw new Error("At " + command.sourceLineNumber + ": unexpected base: " + base);
502                 program.base = base;
503                 break;
504             }
505             case "randomize":
506                 statement.process = Basic.Randomize;
507                 break;
508             case "end":
509                 statement.process = Basic.End;
510                 break;
511             default:
512                 throw new Error("At " + command.sourceLineNumber + ": unexpected command but got: " + command.string);
513             }
514             break;
515         case "remark":
516             // Just ignore it.
517             break;
518         default:
519             throw new Error("At " + command.sourceLineNumber + ": expected command but got: " + command.string + " (of kind " + command.kind + ")");
520         }
521         
522         consumeKind("newLine");
523         return statement;
524     }
525     
526     function parseStatements()
527     {
528         let statement;
529         do {
530             statement = parseStatement();
531         } while (!statement.process || !statement.process.isBlockEnd);
532         return statement;
533     }
534     
535     return {
536         program()
537         {
538             program = {
539                 process: Basic.Program,
540                 statements: new Map(),
541                 data: [],
542                 base: 0
543             };
544             let lastStatement = parseStatements(program.statements);
545             if (lastStatement.process != Basic.End)
546                 throw new Error("At " + lastStatement.sourceLineNumber + ": expected end");
547             
548             return program;
549         },
550         
551         statement(program_)
552         {
553             program = program_;
554             return parseStatement();
555         }
556     };
557 }
558