1 |
|
2 |
|
3 |
|
4 |
|
5 | var typal = require('./util/typal').typal;
|
6 | var Set = require('./util/set').Set;
|
7 |
|
8 | var Jison = exports.Jison = exports;
|
9 |
|
10 |
|
11 | if (typeof console !== 'undefined' && console.log) {
|
12 | Jison.print = console.log;
|
13 | } else if (typeof puts !== 'undefined') {
|
14 | Jison.print = function print () { puts([].join.call(arguments, ' ')); };
|
15 | } else if (typeof print !== 'undefined') {
|
16 | Jison.print = print;
|
17 | } else {
|
18 | Jison.print = function print () {};
|
19 | }
|
20 |
|
21 | Jison.Parser = (function () {
|
22 |
|
23 |
|
24 | function each (obj, func) {
|
25 | if (obj.forEach) {
|
26 | obj.forEach(func);
|
27 | } else {
|
28 | var p;
|
29 | for (p in obj) {
|
30 | if (obj.hasOwnProperty(p)) {
|
31 | func.call(obj, obj[p], p, obj);
|
32 | }
|
33 | }
|
34 | }
|
35 | }
|
36 |
|
37 | var Nonterminal = typal.construct({
|
38 | constructor: function Nonterminal (symbol) {
|
39 | this.symbol = symbol;
|
40 | this.productions = new Set();
|
41 | this.first = [];
|
42 | this.follows = [];
|
43 | this.nullable = false;
|
44 | },
|
45 | toString: function Nonterminal_toString () {
|
46 | var str = this.symbol+"\n";
|
47 | str += (this.nullable ? 'nullable' : 'not nullable');
|
48 | str += "\nFirsts: "+this.first.join(', ');
|
49 | str += "\nFollows: "+this.first.join(', ');
|
50 | str += "\nProductions:\n "+this.productions.join('\n ');
|
51 |
|
52 | return str;
|
53 | }
|
54 | });
|
55 |
|
56 | var Production = typal.construct({
|
57 | constructor: function Production (symbol, handle, id) {
|
58 | this.symbol = symbol;
|
59 | this.handle = handle;
|
60 | this.nullable = false;
|
61 | this.id = id;
|
62 | this.first = [];
|
63 | this.precedence = 0;
|
64 | },
|
65 | toString: function Production_toString () {
|
66 | return this.symbol+" -> "+this.handle.join(' ');
|
67 | }
|
68 | });
|
69 |
|
70 | var generator = typal.beget();
|
71 |
|
72 | generator.constructor = function Jison_Generator (grammar, opt) {
|
73 | var options = typal.mix.call({}, grammar.options, opt);
|
74 | this.terms = {};
|
75 | this.operators = {};
|
76 | this.productions = [];
|
77 | this.conflicts = 0;
|
78 | this.resolutions = [];
|
79 | this.options = options;
|
80 | this.parseParams = grammar.parseParams;
|
81 | this.yy = {};
|
82 |
|
83 |
|
84 | if (grammar.actionInclude) {
|
85 | if (typeof grammar.actionInclude === 'function') {
|
86 | grammar.actionInclude = String(grammar.actionInclude).replace(/^\s*function \(\) \{/, '').replace(/\}\s*$/, '');
|
87 | }
|
88 | this.actionInclude = grammar.actionInclude;
|
89 | }
|
90 | this.moduleInclude = grammar.moduleInclude || '';
|
91 |
|
92 | this.DEBUG = options.debug || false;
|
93 | if (this.DEBUG) this.mix(generatorDebug);
|
94 |
|
95 | this.processGrammar(grammar);
|
96 |
|
97 | };
|
98 |
|
99 | generator.processGrammar = function processGrammarDef (grammar) {
|
100 | var bnf = grammar.bnf,
|
101 | tokens = grammar.tokens,
|
102 | nonterminals = this.nonterminals = {},
|
103 | productions = this.productions,
|
104 | self = this;
|
105 |
|
106 | if (tokens) {
|
107 | if (typeof tokens === 'string') {
|
108 | tokens = tokens.trim().split(' ');
|
109 | } else {
|
110 | tokens = tokens.slice(0);
|
111 | }
|
112 | }
|
113 |
|
114 | var symbols = this.symbols = [];
|
115 |
|
116 |
|
117 | var operators = this.operators = processOperators(grammar.operators);
|
118 |
|
119 |
|
120 | this.buildProductions(bnf, productions, nonterminals, symbols, operators);
|
121 |
|
122 | if (tokens && this.terminals.length !== tokens.length) {
|
123 | self.trace("Warning: declared tokens differ from tokens found in rules.");
|
124 | self.trace(this.terminals);
|
125 | self.trace(tokens);
|
126 | }
|
127 |
|
128 |
|
129 | this.augmentGrammar(grammar);
|
130 | };
|
131 |
|
132 | generator.augmentGrammar = function augmentGrammar (grammar) {
|
133 | if (this.productions.length === 0) {
|
134 | throw new Error("Grammar error: must have at least one rule.");
|
135 | }
|
136 |
|
137 | this.startSymbol = grammar.start || grammar.startSymbol || this.productions[0].symbol;
|
138 | if (!this.nonterminals[this.startSymbol]) {
|
139 | throw new Error("Grammar error: startSymbol must be a non-terminal found in your grammar.");
|
140 | }
|
141 | this.EOF = "$end";
|
142 |
|
143 |
|
144 | var acceptProduction = new Production('$accept', [this.startSymbol, '$end'], 0);
|
145 | this.productions.unshift(acceptProduction);
|
146 |
|
147 |
|
148 | this.symbols.unshift("$accept",this.EOF);
|
149 | this.symbols_.$accept = 0;
|
150 | this.symbols_[this.EOF] = 1;
|
151 | this.terminals.unshift(this.EOF);
|
152 |
|
153 | this.nonterminals.$accept = new Nonterminal("$accept");
|
154 | this.nonterminals.$accept.productions.push(acceptProduction);
|
155 |
|
156 |
|
157 | this.nonterminals[this.startSymbol].follows.push(this.EOF);
|
158 | };
|
159 |
|
160 |
|
161 | function processOperators (ops) {
|
162 | if (!ops) return {};
|
163 | var operators = {};
|
164 | for (var i=0,k,prec;prec=ops[i]; i++) {
|
165 | for (k=1;k < prec.length;k++) {
|
166 | operators[prec[k]] = {precedence: i+1, assoc: prec[0]};
|
167 | }
|
168 | }
|
169 | return operators;
|
170 | }
|
171 |
|
172 |
|
173 | generator.buildProductions = function buildProductions(bnf, productions, nonterminals, symbols, operators) {
|
174 |
|
175 |
|
176 | var actions = [
|
177 | '/* self == yyval */',
|
178 | this.actionInclude || '',
|
179 | 'var $0 = $$.length - 1;',
|
180 | 'switch (yystate) {'
|
181 | ];
|
182 |
|
183 | var actionGroups = {};
|
184 | var prods, symbol;
|
185 | var productions_ = [0];
|
186 | var symbolId = 1;
|
187 | var symbols_ = {};
|
188 |
|
189 | var her = false;
|
190 |
|
191 | function addSymbol (s) {
|
192 | if (s && !symbols_[s]) {
|
193 | symbols_[s] = ++symbolId;
|
194 | symbols.push(s);
|
195 | }
|
196 | }
|
197 |
|
198 |
|
199 | addSymbol("error");
|
200 |
|
201 | for (symbol in bnf) {
|
202 | if (!bnf.hasOwnProperty(symbol)) continue;
|
203 |
|
204 | addSymbol(symbol);
|
205 | nonterminals[symbol] = new Nonterminal(symbol);
|
206 |
|
207 | if (typeof bnf[symbol] === 'string') {
|
208 | prods = bnf[symbol].split(/\s*\|\s*/g);
|
209 | } else {
|
210 | prods = bnf[symbol].slice(0);
|
211 | }
|
212 |
|
213 | prods.forEach(buildProduction);
|
214 | }
|
215 | for (var action in actionGroups)
|
216 | actions.push(actionGroups[action].join(' '), action, 'break;');
|
217 |
|
218 | var sym, terms = [], terms_ = {};
|
219 | each(symbols_, function (id, sym) {
|
220 | if (!nonterminals[sym]) {
|
221 | terms.push(sym);
|
222 | terms_[id] = sym;
|
223 | }
|
224 | });
|
225 |
|
226 | this.hasErrorRecovery = her;
|
227 |
|
228 | this.terminals = terms;
|
229 | this.terminals_ = terms_;
|
230 | this.symbols_ = symbols_;
|
231 |
|
232 | this.productions_ = productions_;
|
233 | actions.push('}');
|
234 |
|
235 | actions = actions.join("\n")
|
236 | .replace(/YYABORT/g, 'return false')
|
237 | .replace(/YYACCEPT/g, 'return true');
|
238 |
|
239 |
|
240 | var yyvalParam = "this";
|
241 | var parameters = "self, yytext, yy, yystate /* action[1] */, $$ /* vstack */";
|
242 | if (this.parseParams) parameters += ', ' + this.parseParams.join(', ');
|
243 |
|
244 | this.performAction = "function performAction(" + parameters + ") {\n" + actions + "\n}";
|
245 |
|
246 | function buildProduction (handle) {
|
247 | var r, rhs, i;
|
248 | if (handle.constructor === Array) {
|
249 | rhs = (typeof handle[0] === 'string') ?
|
250 | handle[0].trim().split(' ') :
|
251 | handle[0].slice(0);
|
252 |
|
253 | for (i=0; i<rhs.length; i++) {
|
254 | if (rhs[i] === 'error') her = true;
|
255 | if (!symbols_[rhs[i]]) {
|
256 | addSymbol(rhs[i]);
|
257 | }
|
258 | }
|
259 |
|
260 | if (typeof handle[1] === 'string' || handle.length == 3) {
|
261 |
|
262 | var label = 'case ' + (productions.length+1) + ':', action = handle[1];
|
263 |
|
264 |
|
265 | if (action.match(/[$@][a-zA-Z][a-zA-Z0-9_]*/)) {
|
266 | var count = {},
|
267 | names = {};
|
268 | for (i=0;i<rhs.length;i++) {
|
269 |
|
270 | var rhs_i = rhs[i].match(/\[[a-zA-Z][a-zA-Z0-9_-]*\]/);
|
271 | if (rhs_i) {
|
272 | rhs_i = rhs_i[0].substr(1, rhs_i[0].length-2);
|
273 | rhs[i] = rhs[i].substr(0, rhs[i].indexOf('['));
|
274 | } else {
|
275 | rhs_i = rhs[i];
|
276 | }
|
277 |
|
278 | if (names[rhs_i]) {
|
279 | names[rhs_i + (++count[rhs_i])] = i+1;
|
280 | } else {
|
281 | names[rhs_i] = i+1;
|
282 | names[rhs_i + "1"] = i+1;
|
283 | count[rhs_i] = 1;
|
284 | }
|
285 | }
|
286 | action = action.replace(/\$([a-zA-Z][a-zA-Z0-9_]*)/g, function (str, pl) {
|
287 | return names[pl] ? '$'+names[pl] : str;
|
288 | }).replace(/@([a-zA-Z][a-zA-Z0-9_]*)/g, function (str, pl) {
|
289 | return names[pl] ? '@'+names[pl] : str;
|
290 | });
|
291 | }
|
292 | action = action
|
293 |
|
294 | .replace(/([^'"])\$\$|^\$\$/g, '$1self.$').replace(/@[0$]/g, "self._$")
|
295 |
|
296 |
|
297 | .replace(/\$(-?\d+)/g, function (_, n) {
|
298 | return "$$[$0" + (parseInt(n, 10) - rhs.length || '') + "]";
|
299 | })
|
300 |
|
301 | .replace(/@(-?\d+)/g, function (_, n) {
|
302 | return "_$[$0" + (n - rhs.length || '') + "]";
|
303 | });
|
304 |
|
305 | if (action in actionGroups) actionGroups[action].push(label);
|
306 | else actionGroups[action] = [label];
|
307 |
|
308 |
|
309 | rhs = rhs.map(function(e,i) { return e.replace(/\[[a-zA-Z_][a-zA-Z0-9_-]*\]/g, '') });
|
310 | r = new Production(symbol, rhs, productions.length+1);
|
311 |
|
312 | if (handle[2] && operators[handle[2].prec]) {
|
313 | r.precedence = operators[handle[2].prec].precedence;
|
314 | }
|
315 | } else {
|
316 |
|
317 | rhs = rhs.map(function(e,i) { return e.replace(/\[[a-zA-Z_][a-zA-Z0-9_-]*\]/g, '') });
|
318 |
|
319 | r = new Production(symbol, rhs, productions.length+1);
|
320 | if (operators[handle[1].prec]) {
|
321 | r.precedence = operators[handle[1].prec].precedence;
|
322 | }
|
323 | }
|
324 | } else {
|
325 |
|
326 | handle = handle.replace(/\[[a-zA-Z_][a-zA-Z0-9_-]*\]/g, '');
|
327 | rhs = handle.trim().split(' ');
|
328 | for (i=0; i<rhs.length; i++) {
|
329 | if (rhs[i] === 'error') her = true;
|
330 | if (!symbols_[rhs[i]]) {
|
331 | addSymbol(rhs[i]);
|
332 | }
|
333 | }
|
334 | r = new Production(symbol, rhs, productions.length+1);
|
335 | }
|
336 | if (r.precedence === 0) {
|
337 |
|
338 | for (i=r.handle.length-1; i>=0; i--) {
|
339 | if (!(r.handle[i] in nonterminals) && r.handle[i] in operators) {
|
340 | r.precedence = operators[r.handle[i]].precedence;
|
341 | }
|
342 | }
|
343 | }
|
344 |
|
345 | productions.push(r);
|
346 | productions_.push([symbols_[r.symbol], r.handle[0] === '' ? 0 : r.handle.length]);
|
347 | nonterminals[symbol].productions.push(r);
|
348 | }
|
349 | };
|
350 |
|
351 |
|
352 |
|
353 | generator.createParser = function createParser () {
|
354 | throw new Error('Calling abstract method.');
|
355 | };
|
356 |
|
357 |
|
358 | generator.trace = function trace () { };
|
359 |
|
360 | generator.warn = function warn () {
|
361 | var args = Array.prototype.slice.call(arguments,0);
|
362 | Jison.print.call(null,args.join(""));
|
363 | };
|
364 |
|
365 | generator.error = function error (msg) {
|
366 | throw new Error(msg);
|
367 | };
|
368 |
|
369 |
|
370 |
|
371 | var generatorDebug = {
|
372 | trace: function trace () {
|
373 | Jison.print.apply(null, arguments);
|
374 | },
|
375 | beforeprocessGrammar: function () {
|
376 | this.trace("Processing grammar.");
|
377 | },
|
378 | afteraugmentGrammar: function () {
|
379 | var trace = this.trace;
|
380 | each(this.symbols, function (sym, i) {
|
381 | trace(sym+"("+i+")");
|
382 | });
|
383 | }
|
384 | };
|
385 |
|
386 |
|
387 |
|
388 |
|
389 |
|
390 |
|
391 | var lookaheadMixin = {};
|
392 |
|
393 | lookaheadMixin.computeLookaheads = function computeLookaheads () {
|
394 | if (this.DEBUG) this.mix(lookaheadDebug);
|
395 |
|
396 | this.computeLookaheads = function () {};
|
397 | this.nullableSets();
|
398 | this.firstSets();
|
399 | this.followSets();
|
400 | };
|
401 |
|
402 |
|
403 | lookaheadMixin.followSets = function followSets () {
|
404 | var productions = this.productions,
|
405 | nonterminals = this.nonterminals,
|
406 | self = this,
|
407 | cont = true;
|
408 |
|
409 |
|
410 | while(cont) {
|
411 | cont = false;
|
412 |
|
413 | productions.forEach(function Follow_prod_forEach (production, k) {
|
414 |
|
415 |
|
416 | var q;
|
417 | var ctx = !!self.go_;
|
418 |
|
419 | var set = [],oldcount;
|
420 | for (var i=0,t;t=production.handle[i];++i) {
|
421 | if (!nonterminals[t]) continue;
|
422 |
|
423 |
|
424 | if (ctx)
|
425 | q = self.go_(production.symbol, production.handle.slice(0, i));
|
426 | var bool = !ctx || q === parseInt(self.nterms_[t], 10);
|
427 |
|
428 | if (i === production.handle.length+1 && bool) {
|
429 | set = nonterminals[production.symbol].follows;
|
430 | } else {
|
431 | var part = production.handle.slice(i+1);
|
432 |
|
433 | set = self.first(part);
|
434 | if (self.nullable(part) && bool) {
|
435 | set.push.apply(set, nonterminals[production.symbol].follows);
|
436 | }
|
437 | }
|
438 | oldcount = nonterminals[t].follows.length;
|
439 | Set.union(nonterminals[t].follows, set);
|
440 | if (oldcount !== nonterminals[t].follows.length) {
|
441 | cont = true;
|
442 | }
|
443 | }
|
444 | });
|
445 | }
|
446 | };
|
447 |
|
448 |
|
449 | lookaheadMixin.first = function first (symbol) {
|
450 |
|
451 | if (symbol === '') {
|
452 | return [];
|
453 |
|
454 | } else if (symbol instanceof Array) {
|
455 | var firsts = [];
|
456 | for (var i=0,t;t=symbol[i];++i) {
|
457 | if (!this.nonterminals[t]) {
|
458 | if (firsts.indexOf(t) === -1)
|
459 | firsts.push(t);
|
460 | } else {
|
461 | Set.union(firsts, this.nonterminals[t].first);
|
462 | }
|
463 | if (!this.nullable(t))
|
464 | break;
|
465 | }
|
466 | return firsts;
|
467 |
|
468 | } else if (!this.nonterminals[symbol]) {
|
469 | return [symbol];
|
470 |
|
471 | } else {
|
472 | return this.nonterminals[symbol].first;
|
473 | }
|
474 | };
|
475 |
|
476 |
|
477 | lookaheadMixin.firstSets = function firstSets () {
|
478 | var productions = this.productions,
|
479 | nonterminals = this.nonterminals,
|
480 | self = this,
|
481 | cont = true,
|
482 | symbol,firsts;
|
483 |
|
484 |
|
485 | while(cont) {
|
486 | cont = false;
|
487 |
|
488 | productions.forEach(function FirstSets_forEach (production, k) {
|
489 | var firsts = self.first(production.handle);
|
490 | if (firsts.length !== production.first.length) {
|
491 | production.first = firsts;
|
492 | cont=true;
|
493 | }
|
494 | });
|
495 |
|
496 | for (symbol in nonterminals) {
|
497 | firsts = [];
|
498 | nonterminals[symbol].productions.forEach(function (production) {
|
499 | Set.union(firsts, production.first);
|
500 | });
|
501 | if (firsts.length !== nonterminals[symbol].first.length) {
|
502 | nonterminals[symbol].first = firsts;
|
503 | cont=true;
|
504 | }
|
505 | }
|
506 | }
|
507 | };
|
508 |
|
509 |
|
510 | lookaheadMixin.nullableSets = function nullableSets () {
|
511 | var firsts = this.firsts = {},
|
512 | nonterminals = this.nonterminals,
|
513 | self = this,
|
514 | cont = true;
|
515 |
|
516 |
|
517 | while(cont) {
|
518 | cont = false;
|
519 |
|
520 |
|
521 | this.productions.forEach(function (production, k) {
|
522 | if (!production.nullable) {
|
523 | for (var i=0,n=0,t;t=production.handle[i];++i) {
|
524 | if (self.nullable(t)) n++;
|
525 | }
|
526 | if (n===i) {
|
527 | production.nullable = cont = true;
|
528 | }
|
529 | }
|
530 | });
|
531 |
|
532 |
|
533 | for (var symbol in nonterminals) {
|
534 | if (!this.nullable(symbol)) {
|
535 | for (var i=0,production;production=nonterminals[symbol].productions.item(i);i++) {
|
536 | if (production.nullable)
|
537 | nonterminals[symbol].nullable = cont = true;
|
538 | }
|
539 | }
|
540 | }
|
541 | }
|
542 | };
|
543 |
|
544 |
|
545 | lookaheadMixin.nullable = function nullable (symbol) {
|
546 |
|
547 | if (symbol === '') {
|
548 | return true;
|
549 |
|
550 | } else if (symbol instanceof Array) {
|
551 | for (var i=0,t;t=symbol[i];++i) {
|
552 | if (!this.nullable(t))
|
553 | return false;
|
554 | }
|
555 | return true;
|
556 |
|
557 | } else if (!this.nonterminals[symbol]) {
|
558 | return false;
|
559 |
|
560 | } else {
|
561 | return this.nonterminals[symbol].nullable;
|
562 | }
|
563 | };
|
564 |
|
565 |
|
566 |
|
567 | var lookaheadDebug = {
|
568 | beforenullableSets: function () {
|
569 | this.trace("Computing Nullable sets.");
|
570 | },
|
571 | beforefirstSets: function () {
|
572 | this.trace("Computing First sets.");
|
573 | },
|
574 | beforefollowSets: function () {
|
575 | this.trace("Computing Follow sets.");
|
576 | },
|
577 | afterfollowSets: function () {
|
578 | var trace = this.trace;
|
579 | each(this.nonterminals, function (nt, t) {
|
580 | trace(nt, '\n');
|
581 | });
|
582 | }
|
583 | };
|
584 |
|
585 |
|
586 |
|
587 |
|
588 | var lrGeneratorMixin = {};
|
589 |
|
590 | lrGeneratorMixin.buildTable = function buildTable () {
|
591 | if (this.DEBUG) this.mix(lrGeneratorDebug);
|
592 |
|
593 | this.states = this.canonicalCollection();
|
594 | this.table = this.parseTable(this.states);
|
595 | this.defaultActions = findDefaults(this.table);
|
596 | };
|
597 |
|
598 | lrGeneratorMixin.Item = typal.construct({
|
599 | constructor: function Item(production, dot, f, predecessor) {
|
600 | this.production = production;
|
601 | this.dotPosition = dot || 0;
|
602 | this.follows = f || [];
|
603 | this.predecessor = predecessor;
|
604 | this.id = parseInt(production.id+'a'+this.dotPosition, 36);
|
605 | this.markedSymbol = this.production.handle[this.dotPosition];
|
606 | },
|
607 | remainingHandle: function () {
|
608 | return this.production.handle.slice(this.dotPosition+1);
|
609 | },
|
610 | eq: function (e) {
|
611 | return e.id === this.id;
|
612 | },
|
613 | handleToString: function () {
|
614 | var handle = this.production.handle.slice(0);
|
615 | handle[this.dotPosition] = '.'+(handle[this.dotPosition]||'');
|
616 | return handle.join(' ');
|
617 | },
|
618 | toString: function () {
|
619 | var temp = this.production.handle.slice(0);
|
620 | temp[this.dotPosition] = '.'+(temp[this.dotPosition]||'');
|
621 | return this.production.symbol+" -> "+temp.join(' ') +
|
622 | (this.follows.length === 0 ? "" : " #lookaheads= "+this.follows.join(' '));
|
623 | }
|
624 | });
|
625 |
|
626 | lrGeneratorMixin.ItemSet = Set.prototype.construct({
|
627 | afterconstructor: function () {
|
628 | this.reductions = [];
|
629 | this.goes = {};
|
630 | this.edges = {};
|
631 | this.shifts = false;
|
632 | this.inadequate = false;
|
633 | this.hash_ = {};
|
634 | for (var i=this._items.length-1;i >=0;i--) {
|
635 | this.hash_[this._items[i].id] = true;
|
636 | }
|
637 | },
|
638 | concat: function concat (set) {
|
639 | var a = set._items || set;
|
640 | for (var i=a.length-1;i >=0;i--) {
|
641 | this.hash_[a[i].id] = true;
|
642 | }
|
643 | this._items.push.apply(this._items, a);
|
644 | return this;
|
645 | },
|
646 | push: function (item) {
|
647 | this.hash_[item.id] = true;
|
648 | return this._items.push(item);
|
649 | },
|
650 | contains: function (item) {
|
651 | return this.hash_[item.id];
|
652 | },
|
653 | valueOf: function toValue () {
|
654 | var v = this._items.map(function (a) {return a.id;}).sort().join('|');
|
655 | this.valueOf = function toValue_inner() {return v;};
|
656 | return v;
|
657 | }
|
658 | });
|
659 |
|
660 | lrGeneratorMixin.closureOperation = function closureOperation (itemSet /*, closureSet*/) {
|
661 | var closureSet = new this.ItemSet();
|
662 | var self = this;
|
663 |
|
664 | var set = itemSet,
|
665 | itemQueue, syms = {};
|
666 |
|
667 | do {
|
668 | itemQueue = new Set();
|
669 | closureSet.concat(set);
|
670 | set.forEach(function CO_set_forEach (item) {
|
671 | var symbol = item.markedSymbol;
|
672 |
|
673 |
|
674 | if (symbol && self.nonterminals[symbol]) {
|
675 | if(!syms[symbol]) {
|
676 | self.nonterminals[symbol].productions.forEach(function CO_nt_forEach (production) {
|
677 | var newItem = new self.Item(production, 0);
|
678 | if(!closureSet.contains(newItem))
|
679 | itemQueue.push(newItem);
|
680 | });
|
681 | syms[symbol] = true;
|
682 | }
|
683 | } else if (!symbol) {
|
684 |
|
685 | closureSet.reductions.push(item);
|
686 | closureSet.inadequate = closureSet.reductions.length > 1 || closureSet.shifts;
|
687 | } else {
|
688 |
|
689 | closureSet.shifts = true;
|
690 | closureSet.inadequate = closureSet.reductions.length > 0;
|
691 | }
|
692 | });
|
693 |
|
694 | set = itemQueue;
|
695 |
|
696 | } while (!itemQueue.isEmpty());
|
697 |
|
698 | return closureSet;
|
699 | };
|
700 |
|
701 | lrGeneratorMixin.gotoOperation = function gotoOperation (itemSet, symbol) {
|
702 | var gotoSet = new this.ItemSet(),
|
703 | self = this;
|
704 |
|
705 | itemSet.forEach(function goto_forEach(item, n) {
|
706 | if (item.markedSymbol === symbol) {
|
707 | gotoSet.push(new self.Item(item.production, item.dotPosition+1, item.follows, n));
|
708 | }
|
709 | });
|
710 |
|
711 | return gotoSet.isEmpty() ? gotoSet : this.closureOperation(gotoSet);
|
712 | };
|
713 |
|
714 |
|
715 |
|
716 | lrGeneratorMixin.canonicalCollection = function canonicalCollection () {
|
717 | var item1 = new this.Item(this.productions[0], 0, [this.EOF]);
|
718 | var firstState = this.closureOperation(new this.ItemSet(item1)),
|
719 | states = new Set(firstState),
|
720 | marked = 0,
|
721 | self = this,
|
722 | itemSet;
|
723 |
|
724 | states.has = {};
|
725 | states.has[firstState] = 0;
|
726 |
|
727 | while (marked !== states.size()) {
|
728 | itemSet = states.item(marked); marked++;
|
729 | itemSet.forEach(function CC_itemSet_forEach (item) {
|
730 | if (item.markedSymbol && item.markedSymbol !== self.EOF)
|
731 | self.canonicalCollectionInsert(item.markedSymbol, itemSet, states, marked-1);
|
732 | });
|
733 | }
|
734 |
|
735 | return states;
|
736 | };
|
737 |
|
738 |
|
739 | lrGeneratorMixin.canonicalCollectionInsert = function canonicalCollectionInsert (symbol, itemSet, states, stateNum) {
|
740 | var g = this.gotoOperation(itemSet, symbol);
|
741 | if (!g.predecessors)
|
742 | g.predecessors = {};
|
743 |
|
744 | if (!g.isEmpty()) {
|
745 | var gv = g.valueOf(),
|
746 | i = states.has[gv];
|
747 | if (i === -1 || typeof i === 'undefined') {
|
748 | states.has[gv] = states.size();
|
749 | itemSet.edges[symbol] = states.size();
|
750 | states.push(g);
|
751 | g.predecessors[symbol] = [stateNum];
|
752 | } else {
|
753 | itemSet.edges[symbol] = i;
|
754 | states.item(i).predecessors[symbol].push(stateNum);
|
755 | }
|
756 | }
|
757 | };
|
758 |
|
759 | var NONASSOC = 0;
|
760 | lrGeneratorMixin.parseTable = function parseTable (itemSets) {
|
761 | var states = [],
|
762 | nonterminals = this.nonterminals,
|
763 | operators = this.operators,
|
764 | conflictedStates = {},
|
765 | self = this,
|
766 | s = 1,
|
767 | r = 2,
|
768 | a = 3;
|
769 |
|
770 |
|
771 | itemSets.forEach(function (itemSet, k) {
|
772 | var state = states[k] = {};
|
773 | var action, stackSymbol;
|
774 |
|
775 |
|
776 | for (stackSymbol in itemSet.edges) {
|
777 | itemSet.forEach(function (item, j) {
|
778 |
|
779 | if (item.markedSymbol == stackSymbol) {
|
780 | var gotoState = itemSet.edges[stackSymbol];
|
781 | if (nonterminals[stackSymbol]) {
|
782 |
|
783 |
|
784 | state[self.symbols_[stackSymbol]] = gotoState;
|
785 | } else {
|
786 |
|
787 | state[self.symbols_[stackSymbol]] = [s,gotoState];
|
788 | }
|
789 | }
|
790 | });
|
791 | }
|
792 |
|
793 |
|
794 | itemSet.forEach(function (item, j) {
|
795 | if (item.markedSymbol == self.EOF) {
|
796 |
|
797 | state[self.symbols_[self.EOF]] = [a];
|
798 |
|
799 | }
|
800 | });
|
801 |
|
802 | var allterms = self.lookAheads ? false : self.terminals;
|
803 |
|
804 |
|
805 | itemSet.reductions.forEach(function (item, j) {
|
806 |
|
807 | var terminals = allterms || self.lookAheads(itemSet, item);
|
808 |
|
809 | terminals.forEach(function (stackSymbol) {
|
810 | action = state[self.symbols_[stackSymbol]];
|
811 | var op = operators[stackSymbol];
|
812 |
|
813 |
|
814 | if (action || action && action.length) {
|
815 | var sol = resolveConflict(item.production, op, [r,item.production.id], action[0] instanceof Array ? action[0] : action);
|
816 | self.resolutions.push([k,stackSymbol,sol]);
|
817 | if (sol.bydefault) {
|
818 | self.conflicts++;
|
819 | if (!self.DEBUG) {
|
820 | self.warn('Conflict in grammar: multiple actions possible when lookahead token is ',stackSymbol,' in state ',k, "\n- ", printAction(sol.r, self), "\n- ", printAction(sol.s, self));
|
821 | conflictedStates[k] = true;
|
822 | }
|
823 | if (self.options.noDefaultResolve) {
|
824 | if (!(action[0] instanceof Array))
|
825 | action = [action];
|
826 | action.push(sol.r);
|
827 | }
|
828 | } else {
|
829 | action = sol.action;
|
830 | }
|
831 | } else {
|
832 | action = [r,item.production.id];
|
833 | }
|
834 | if (action && action.length) {
|
835 | state[self.symbols_[stackSymbol]] = action;
|
836 | } else if (action === NONASSOC) {
|
837 | state[self.symbols_[stackSymbol]] = undefined;
|
838 | }
|
839 | });
|
840 | });
|
841 |
|
842 | });
|
843 |
|
844 | if (!self.DEBUG && self.conflicts > 0) {
|
845 | self.warn("\nStates with conflicts:");
|
846 | each(conflictedStates, function (val, state) {
|
847 | self.warn('State '+state);
|
848 | self.warn(' ',itemSets.item(state).join("\n "));
|
849 | });
|
850 | }
|
851 |
|
852 | return states;
|
853 | };
|
854 |
|
855 |
|
856 | function findDefaults (states) {
|
857 | var defaults = {};
|
858 | states.forEach(function (state, k) {
|
859 | var i = 0;
|
860 | for (var act in state) {
|
861 | if ({}.hasOwnProperty.call(state, act)) i++;
|
862 | }
|
863 |
|
864 | if (i === 1 && state[act][0] === 2) {
|
865 |
|
866 | defaults[k] = state[act];
|
867 | }
|
868 | });
|
869 |
|
870 | return defaults;
|
871 | }
|
872 |
|
873 |
|
874 | function resolveConflict (production, op, reduce, shift) {
|
875 | var sln = {production: production, operator: op, r: reduce, s: shift},
|
876 | s = 1,
|
877 | r = 2,
|
878 | a = 3;
|
879 |
|
880 | if (shift[0] === r) {
|
881 | sln.msg = "Resolve R/R conflict (use first production declared in grammar.)";
|
882 | sln.action = shift[1] < reduce[1] ? shift : reduce;
|
883 | if (shift[1] !== reduce[1]) sln.bydefault = true;
|
884 | return sln;
|
885 | }
|
886 |
|
887 | if (production.precedence === 0 || !op) {
|
888 | sln.msg = "Resolve S/R conflict (shift by default.)";
|
889 | sln.bydefault = true;
|
890 | sln.action = shift;
|
891 | } else if (production.precedence < op.precedence ) {
|
892 | sln.msg = "Resolve S/R conflict (shift for higher precedent operator.)";
|
893 | sln.action = shift;
|
894 | } else if (production.precedence === op.precedence) {
|
895 | if (op.assoc === "right" ) {
|
896 | sln.msg = "Resolve S/R conflict (shift for right associative operator.)";
|
897 | sln.action = shift;
|
898 | } else if (op.assoc === "left" ) {
|
899 | sln.msg = "Resolve S/R conflict (reduce for left associative operator.)";
|
900 | sln.action = reduce;
|
901 | } else if (op.assoc === "nonassoc" ) {
|
902 | sln.msg = "Resolve S/R conflict (no action for non-associative operator.)";
|
903 | sln.action = NONASSOC;
|
904 | }
|
905 | } else {
|
906 | sln.msg = "Resolve conflict (reduce for higher precedent production.)";
|
907 | sln.action = reduce;
|
908 | }
|
909 |
|
910 | return sln;
|
911 | }
|
912 |
|
913 | lrGeneratorMixin.generate = function parser_generate (opt) {
|
914 | opt = typal.mix.call({}, this.options, opt);
|
915 | var code = "";
|
916 |
|
917 |
|
918 | if (!opt.moduleName || !opt.moduleName.match(/^[A-Za-z_$][A-Za-z0-9_$]*$/)) {
|
919 | opt.moduleName = "parser";
|
920 | }
|
921 | switch (opt.moduleType) {
|
922 | case "js":
|
923 | code = this.generateModule(opt);
|
924 | break;
|
925 | case "amd":
|
926 | code = this.generateAMDModule(opt);
|
927 | break;
|
928 | default:
|
929 | code = this.generateCommonJSModule(opt);
|
930 | break;
|
931 | }
|
932 |
|
933 | return code;
|
934 | };
|
935 |
|
936 | lrGeneratorMixin.generateAMDModule = function generateAMDModule(opt){
|
937 | opt = typal.mix.call({}, this.options, opt);
|
938 | var module = this.generateModule_();
|
939 | var out = '\n\ndefine(function(require){\n'
|
940 | + module.commonCode
|
941 | + '\nvar parser = '+ module.moduleCode
|
942 | + "\n"+this.moduleInclude
|
943 | + (this.lexer && this.lexer.generateModule ?
|
944 | '\n' + this.lexer.generateModule() +
|
945 | '\nparser.lexer = lexer;' : '')
|
946 | + '\nreturn parser;'
|
947 | + '\n});'
|
948 | return out;
|
949 | };
|
950 |
|
951 | lrGeneratorMixin.generateCommonJSModule = function generateCommonJSModule (opt) {
|
952 | opt = typal.mix.call({}, this.options, opt);
|
953 | var moduleName = opt.moduleName || "parser";
|
954 | var out = this.generateModule(opt)
|
955 | + "\n\n\nif (typeof require !== 'undefined' && typeof exports !== 'undefined') {"
|
956 | + "\nexports.parser = "+moduleName+";"
|
957 | + "\nexports.Parser = "+moduleName+".Parser;"
|
958 | + "\nexports.parse = function () { return "+moduleName+".parse.apply("+moduleName+", arguments); };"
|
959 | + "\n}";
|
960 |
|
961 | return out;
|
962 | };
|
963 |
|
964 | lrGeneratorMixin.generateModule = function generateModule (opt) {
|
965 | opt = typal.mix.call({}, this.options, opt);
|
966 | var moduleName = opt.moduleName || "parser";
|
967 | var out = "/* parser generated by jison-fork */\n";
|
968 |
|
969 | out += (moduleName.match(/\./) ? moduleName : "var "+moduleName) +
|
970 | " = " + this.generateModuleExpr();
|
971 |
|
972 | return out;
|
973 | };
|
974 |
|
975 |
|
976 | lrGeneratorMixin.generateModuleExpr = function generateModuleExpr () {
|
977 | var out = '';
|
978 | var module = this.generateModule_();
|
979 |
|
980 | out += "(function(){\n";
|
981 | out += module.commonCode;
|
982 | out += "\nvar parser = "+module.moduleCode;
|
983 | out += "\n"+this.moduleInclude;
|
984 | if (this.lexer && this.lexer.generateModule) {
|
985 | out += this.lexer.generateModule();
|
986 | out += "\nparser.lexer = lexer;";
|
987 | }
|
988 | out += "\nfunction Parser () {\n this.yy = {};\n}\n"
|
989 | + "Parser.prototype = parser;"
|
990 | + "parser.Parser = Parser;"
|
991 | + "\nreturn new Parser;\n})();";
|
992 |
|
993 | return out;
|
994 | };
|
995 |
|
996 | function addTokenStack (fn) {
|
997 | var parseFn = fn;
|
998 | return fn;
|
999 | }
|
1000 |
|
1001 |
|
1002 | function tokenStackLex() {
|
1003 | var token;
|
1004 | token = tstack.pop() || lexer.lex() || EOF;
|
1005 |
|
1006 | if (typeof token !== 'number') {
|
1007 | if (token instanceof Array) {
|
1008 | tstack = token;
|
1009 | token = tstack.pop();
|
1010 | }
|
1011 | token = self.symbols_[token] || token;
|
1012 | }
|
1013 | return token;
|
1014 | }
|
1015 |
|
1016 |
|
1017 |
|
1018 |
|
1019 | lrGeneratorMixin.generateModule_ = function generateModule_ () {
|
1020 | var parseFn = String(parser.parse);
|
1021 |
|
1022 |
|
1023 |
|
1024 |
|
1025 |
|
1026 | nextVariableId = 0;
|
1027 | var tableCode = this.generateTableCode(this.table);
|
1028 |
|
1029 |
|
1030 | var commonCode = tableCode.commonCode;
|
1031 |
|
1032 |
|
1033 | var moduleCode = "{";
|
1034 | moduleCode += [
|
1035 | "trace: " + String(this.trace || parser.trace),
|
1036 | "yy: {}",
|
1037 | "symbols_: " + JSON.stringify(this.symbols_),
|
1038 | "terminals_: " + JSON.stringify(this.terminals_).replace(/"([0-9]+)":/g,"$1:"),
|
1039 | "productions_: " + JSON.stringify(this.productions_),
|
1040 | "performAction: " + String(this.performAction),
|
1041 | "table: " + tableCode.moduleCode,
|
1042 | "defaultActions: " + JSON.stringify(this.defaultActions).replace(/"([0-9]+)":/g,"$1:"),
|
1043 | "parseError: " + String(this.parseError || (this.hasErrorRecovery ? traceParseError : parser.parseError)),
|
1044 | "parse: " + parseFn
|
1045 | ].join(",\n");
|
1046 | moduleCode += "};";
|
1047 |
|
1048 | return { commonCode: commonCode, moduleCode: moduleCode }
|
1049 | };
|
1050 |
|
1051 |
|
1052 | lrGeneratorMixin.generateTableCode = function (table) {
|
1053 | var moduleCode = JSON.stringify(table);
|
1054 | var variables = [createObjectCode];
|
1055 |
|
1056 |
|
1057 | moduleCode = moduleCode.replace(/"([0-9]+)"(?=:)/g, "$1");
|
1058 |
|
1059 |
|
1060 |
|
1061 | moduleCode = moduleCode.replace(/\{\d+:[^\}]+,\d+:[^\}]+\}/g, function (object) {
|
1062 |
|
1063 | var value, frequentValue, key, keys = {}, keyCount, maxKeyCount = 0,
|
1064 | keyValue, keyValues = [], keyValueMatcher = /(\d+):([^:]+)(?=,\d+:|\})/g;
|
1065 |
|
1066 | while ((keyValue = keyValueMatcher.exec(object))) {
|
1067 |
|
1068 | key = keyValue[1];
|
1069 | value = keyValue[2];
|
1070 | keyCount = 1;
|
1071 |
|
1072 | if (!(value in keys)) {
|
1073 | keys[value] = [key];
|
1074 | } else {
|
1075 | keyCount = keys[value].push(key);
|
1076 | }
|
1077 |
|
1078 | if (keyCount > maxKeyCount) {
|
1079 | maxKeyCount = keyCount;
|
1080 | frequentValue = value;
|
1081 | }
|
1082 | }
|
1083 |
|
1084 | if (maxKeyCount > 1) {
|
1085 |
|
1086 | for (value in keys) {
|
1087 | if (value !== frequentValue) {
|
1088 | for (var k = keys[value], i = 0, l = k.length; i < l; i++) {
|
1089 | keyValues.push(k[i] + ':' + value);
|
1090 | }
|
1091 | }
|
1092 | }
|
1093 | keyValues = keyValues.length ? ',{' + keyValues.join(',') + '}' : '';
|
1094 |
|
1095 | object = 'o([' + keys[frequentValue].join(',') + '],' + frequentValue + keyValues + ')';
|
1096 | }
|
1097 | return object;
|
1098 | });
|
1099 |
|
1100 |
|
1101 | var list;
|
1102 | var lists = {};
|
1103 | var listMatcher = /\[[0-9,]+\]/g;
|
1104 |
|
1105 | while (list = listMatcher.exec(moduleCode)) {
|
1106 | lists[list] = (lists[list] || 0) + 1;
|
1107 | }
|
1108 |
|
1109 |
|
1110 | moduleCode = moduleCode.replace(listMatcher, function (list) {
|
1111 | var listId = lists[list];
|
1112 |
|
1113 | if (typeof listId === 'number') {
|
1114 |
|
1115 | if (listId === 1) {
|
1116 | lists[list] = listId = list;
|
1117 |
|
1118 | } else {
|
1119 | lists[list] = listId = createVariable();
|
1120 | variables.push(listId + '=' + list);
|
1121 | }
|
1122 | }
|
1123 | return listId;
|
1124 | });
|
1125 |
|
1126 |
|
1127 | return {
|
1128 | commonCode: 'var ' + variables.join(',') + ';',
|
1129 | moduleCode: moduleCode
|
1130 | };
|
1131 | };
|
1132 |
|
1133 |
|
1134 | var createObjectCode = 'o=function(k,v,o,l){' +
|
1135 | 'for(o=o||{},l=k.length;l--;o[k[l]]=v);' +
|
1136 | 'return o}';
|
1137 |
|
1138 |
|
1139 | function createVariable() {
|
1140 | var id = nextVariableId++;
|
1141 | var name = '$V';
|
1142 |
|
1143 | do {
|
1144 | name += variableTokens[id % variableTokensLength];
|
1145 | id = ~~(id / variableTokensLength);
|
1146 | } while (id !== 0);
|
1147 |
|
1148 | return name;
|
1149 | }
|
1150 |
|
1151 | var nextVariableId = 0;
|
1152 | var variableTokens = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_$';
|
1153 | var variableTokensLength = variableTokens.length;
|
1154 |
|
1155 |
|
1156 |
|
1157 | function printAction (a, gen) {
|
1158 | var s = a[0] == 1 ? 'shift token (then go to state '+a[1]+')' :
|
1159 | a[0] == 2 ? 'reduce by rule: '+gen.productions[a[1]] :
|
1160 | 'accept' ;
|
1161 |
|
1162 | return s;
|
1163 | }
|
1164 |
|
1165 | var lrGeneratorDebug = {
|
1166 | beforeparseTable: function () {
|
1167 | this.trace("Building parse table.");
|
1168 | },
|
1169 | afterparseTable: function () {
|
1170 | var self = this;
|
1171 | if (this.conflicts > 0) {
|
1172 | this.resolutions.forEach(function (r, i) {
|
1173 | if (r[2].bydefault) {
|
1174 | self.warn('Conflict at state: ',r[0], ', token: ',r[1], "\n ", printAction(r[2].r, self), "\n ", printAction(r[2].s, self));
|
1175 | }
|
1176 | });
|
1177 | this.trace("\n"+this.conflicts+" Conflict(s) found in grammar.");
|
1178 | }
|
1179 | this.trace("Done.");
|
1180 | },
|
1181 | aftercanonicalCollection: function (states) {
|
1182 | var trace = this.trace;
|
1183 | trace("\nItem sets\n------");
|
1184 |
|
1185 | states.forEach(function (state, i) {
|
1186 | trace("\nitem set",i,"\n"+state.join("\n"), '\ntransitions -> ', JSON.stringify(state.edges));
|
1187 | });
|
1188 | }
|
1189 | };
|
1190 |
|
1191 | var parser = typal.beget();
|
1192 |
|
1193 | lrGeneratorMixin.createParser = function createParser () {
|
1194 |
|
1195 | var p = eval(this.generateModuleExpr());
|
1196 |
|
1197 |
|
1198 | p.productions = this.productions;
|
1199 |
|
1200 | var self = this;
|
1201 | function bind(method) {
|
1202 | return function() {
|
1203 | self.lexer = p.lexer;
|
1204 | return self[method].apply(self, arguments);
|
1205 | };
|
1206 | }
|
1207 |
|
1208 |
|
1209 | p.generate = bind('generate');
|
1210 | p.generateAMDModule = bind('generateAMDModule');
|
1211 | p.generateModule = bind('generateModule');
|
1212 | p.generateCommonJSModule = bind('generateCommonJSModule');
|
1213 |
|
1214 | return p;
|
1215 | };
|
1216 |
|
1217 | parser.trace = generator.trace;
|
1218 | parser.warn = generator.warn;
|
1219 | parser.error = generator.error;
|
1220 |
|
1221 | function traceParseError (err, hash) {
|
1222 | this.trace(err);
|
1223 | }
|
1224 |
|
1225 | function parseError (str, hash) {
|
1226 | if (hash.recoverable) {
|
1227 | this.trace(str);
|
1228 | } else {
|
1229 | throw new Error(str);
|
1230 | }
|
1231 | }
|
1232 |
|
1233 | parser.parseError = lrGeneratorMixin.parseError = parseError;
|
1234 |
|
1235 | parser.parse = function parse (input, script = null) {
|
1236 |
|
1237 |
|
1238 |
|
1239 |
|
1240 |
|
1241 | var self = this,
|
1242 | stack = [0],
|
1243 | tstack = [],
|
1244 | vstack = [null],
|
1245 | table = this.table,
|
1246 | yytext = '',
|
1247 | yylineno = 0,
|
1248 | yyleng = 0,
|
1249 | recovering = 0,
|
1250 | TERROR = 2,
|
1251 | EOF = 1;
|
1252 |
|
1253 |
|
1254 |
|
1255 |
|
1256 | var lexer = Object.create(this.lexer);
|
1257 | var yy = this.yy;
|
1258 |
|
1259 | lexer.setInput(input,yy);
|
1260 |
|
1261 | if (typeof yy.parseError === 'function') {
|
1262 | this.parseError = yy.parseError;
|
1263 | } else {
|
1264 | this.parseError = Object.getPrototypeOf(this).parseError;
|
1265 | }
|
1266 |
|
1267 | function popStack (n) {
|
1268 | stack.length = stack.length - 2 * n;
|
1269 | vstack.length = vstack.length - n;
|
1270 | }
|
1271 |
|
1272 | var symbol, preErrorSymbol, state, action, a, r, yyval = {}, p, len, newState, expected;
|
1273 |
|
1274 | function handleError(){
|
1275 | var error_rule_depth;
|
1276 | var errStr = '';
|
1277 |
|
1278 |
|
1279 |
|
1280 |
|
1281 | function locateNearestErrorRecoveryRule(state) {
|
1282 | var stack_probe = stack.length - 1;
|
1283 | var depth = 0;
|
1284 |
|
1285 |
|
1286 | for(;;) {
|
1287 |
|
1288 | if ((TERROR.toString()) in table[state]) {
|
1289 | return depth;
|
1290 | }
|
1291 | if (state === 0 || stack_probe < 2) {
|
1292 | return false;
|
1293 | }
|
1294 | stack_probe -= 2;
|
1295 | state = stack[stack_probe];
|
1296 | ++depth;
|
1297 | }
|
1298 | }
|
1299 |
|
1300 | if (!recovering) {
|
1301 |
|
1302 | error_rule_depth = locateNearestErrorRecoveryRule(state);
|
1303 |
|
1304 |
|
1305 | expected = [];
|
1306 |
|
1307 | var tsym = lexer.yytext;
|
1308 | var lastToken = tsym;
|
1309 | var tok = self.terminals_[symbol] || symbol;
|
1310 |
|
1311 |
|
1312 | let tidx = lexer.tokens.indexOf(tsym);
|
1313 | let ttok = tsym;
|
1314 | while(ttok && ttok._loc == -1){
|
1315 | ttok = lexer.tokens[--tidx];
|
1316 | }
|
1317 |
|
1318 | var tloc = ttok ? ttok._loc : -1;
|
1319 | var tend = tloc > -1 ? (tloc + (ttok._len || 0)) : -1;
|
1320 | var tpos = tloc != -1 ? "[" + ttok._loc + ":" + ttok._len + "]" : '[0:0]';
|
1321 |
|
1322 |
|
1323 |
|
1324 | if (lexer.showPosition) {
|
1325 | errStr = 'Parse error at '+(tpos)+":\n"+lexer.showPosition()+"\nExpecting "+expected.join(', ') + ", got '" + (tok)+ "'";
|
1326 | } else {
|
1327 |
|
1328 | errStr = "Unexpected " + (symbol == EOF ? "end of input" : ("'"+(tok)+"'"));
|
1329 | }
|
1330 |
|
1331 | if(script){
|
1332 |
|
1333 | let err = script.addDiagnostic('error',{
|
1334 | message: errStr,
|
1335 | source: 'imba-parser',
|
1336 | range: script.rangeAt(tloc,tend)
|
1337 | })
|
1338 |
|
1339 | err.raise();
|
1340 | }
|
1341 |
|
1342 | self.parseError(errStr, {
|
1343 | lexer: lexer,
|
1344 | text: lexer.match,
|
1345 | token: tok,
|
1346 | offset: tloc,
|
1347 | length: (tend - tloc),
|
1348 | start: {offset: tloc},
|
1349 | end: {offset: tend},
|
1350 | line: lexer.yylineno,
|
1351 | expected: expected,
|
1352 | recoverable: (error_rule_depth !== false)
|
1353 | });
|
1354 |
|
1355 | } else if (preErrorSymbol !== EOF) {
|
1356 | error_rule_depth = locateNearestErrorRecoveryRule(state);
|
1357 | }
|
1358 |
|
1359 |
|
1360 | if (recovering == 3) {
|
1361 | if (symbol === EOF || preErrorSymbol === EOF) {
|
1362 | throw new Error(errStr || 'Parsing halted while starting to recover from another error.');
|
1363 | }
|
1364 |
|
1365 |
|
1366 | yytext = lexer.yytext;
|
1367 | }
|
1368 |
|
1369 |
|
1370 | if (error_rule_depth === false) {
|
1371 | throw new Error(errStr || 'Parsing halted. No suitable error recovery rule available.');
|
1372 | }
|
1373 | popStack(error_rule_depth);
|
1374 | preErrorSymbol = (symbol == TERROR ? null : symbol);
|
1375 | symbol = TERROR;
|
1376 | state = stack[stack.length-1];
|
1377 | action = table[state] && table[state][TERROR];
|
1378 | recovering = 3;
|
1379 | }
|
1380 |
|
1381 |
|
1382 | var __sym = this.symbols_;
|
1383 | var __prod = this.productions_;
|
1384 |
|
1385 | while (true) {
|
1386 |
|
1387 | state = stack[stack.length - 1];
|
1388 |
|
1389 | if (symbol === null || typeof symbol == 'undefined') {
|
1390 | symbol = __sym[lexer.lex()] || EOF;
|
1391 | }
|
1392 | action = table[state] && table[state][symbol];
|
1393 |
|
1394 | _handle_error:
|
1395 | if (typeof action === 'undefined' || !action.length || !action[0]) {
|
1396 | handleError();
|
1397 | }
|
1398 |
|
1399 | switch (action[0]) {
|
1400 | case 1:
|
1401 | stack.push(symbol);
|
1402 | stack.push(action[1]);
|
1403 | vstack.push(lexer.yytext);
|
1404 |
|
1405 | symbol = null;
|
1406 | if (!preErrorSymbol) {
|
1407 | yytext = lexer.yytext;
|
1408 | if (recovering > 0) {
|
1409 | recovering--;
|
1410 | }
|
1411 | } else {
|
1412 |
|
1413 | symbol = preErrorSymbol;
|
1414 | preErrorSymbol = null;
|
1415 | }
|
1416 | break;
|
1417 |
|
1418 | case 2:
|
1419 | len = __prod[action[1]][1];
|
1420 |
|
1421 | yyval.$ = vstack[vstack.length-len];
|
1422 | r = this.performAction(yyval, yytext, yy, action[1], vstack);
|
1423 | if (typeof r !== 'undefined') {
|
1424 | return r;
|
1425 | }
|
1426 |
|
1427 | while(len > 0) {
|
1428 | stack.pop();
|
1429 | stack.pop();
|
1430 | vstack.pop();
|
1431 | len--;
|
1432 | }
|
1433 |
|
1434 | stack.push(__prod[action[1]][0]);
|
1435 | newState = table[stack[stack.length-2]][stack[stack.length-1]];
|
1436 | stack.push(newState);
|
1437 | vstack.push(yyval.$);
|
1438 | break;
|
1439 |
|
1440 | case 3:
|
1441 | return true;
|
1442 | }
|
1443 | }
|
1444 |
|
1445 | return true;
|
1446 | };
|
1447 |
|
1448 | parser.init = function parser_init (dict) {
|
1449 | this.table = dict.table;
|
1450 | this.defaultActions = dict.defaultActions;
|
1451 | this.performAction = dict.performAction;
|
1452 | this.productions_ = dict.productions_;
|
1453 | this.symbols_ = dict.symbols_;
|
1454 | this.terminals_ = dict.terminals_;
|
1455 | };
|
1456 |
|
1457 |
|
1458 |
|
1459 |
|
1460 |
|
1461 | var lr0 = generator.beget(lookaheadMixin, lrGeneratorMixin, {
|
1462 | type: "LR(0)",
|
1463 | afterconstructor: function lr0_afterconstructor () {
|
1464 | this.buildTable();
|
1465 | }
|
1466 | });
|
1467 |
|
1468 | var LR0Generator = exports.LR0Generator = lr0.construct();
|
1469 |
|
1470 |
|
1471 |
|
1472 |
|
1473 |
|
1474 | var lalr = generator.beget(lookaheadMixin, lrGeneratorMixin, {
|
1475 | type: "LALR(1)",
|
1476 |
|
1477 | afterconstructor: function (grammar, options) {
|
1478 | if (this.DEBUG) this.mix(lrGeneratorDebug, lalrGeneratorDebug);
|
1479 |
|
1480 | options = options || {};
|
1481 | this.states = this.canonicalCollection();
|
1482 | this.terms_ = {};
|
1483 |
|
1484 | var newg = this.newg = typal.beget(lookaheadMixin,{
|
1485 | oldg: this,
|
1486 | trace: this.trace,
|
1487 | nterms_: {},
|
1488 | DEBUG: false,
|
1489 | go_: function (r, B) {
|
1490 | r = r.split(":")[0];
|
1491 | B = B.map(function (b) { return b.slice(b.indexOf(":")+1); });
|
1492 | return this.oldg.go(r, B);
|
1493 | }
|
1494 | });
|
1495 | newg.nonterminals = {};
|
1496 | newg.productions = [];
|
1497 |
|
1498 | this.inadequateStates = [];
|
1499 |
|
1500 |
|
1501 |
|
1502 | this.onDemandLookahead = options.onDemandLookahead || false;
|
1503 |
|
1504 | this.buildNewGrammar();
|
1505 | newg.computeLookaheads();
|
1506 | this.unionLookaheads();
|
1507 |
|
1508 | this.table = this.parseTable(this.states);
|
1509 | this.defaultActions = findDefaults(this.table);
|
1510 | },
|
1511 |
|
1512 | lookAheads: function LALR_lookaheads (state, item) {
|
1513 | return (!!this.onDemandLookahead && !state.inadequate) ? this.terminals : item.follows;
|
1514 | },
|
1515 | go: function LALR_go (p, w) {
|
1516 | var q = parseInt(p, 10);
|
1517 | for (var i=0;i<w.length;i++) {
|
1518 | q = this.states.item(q).edges[w[i]] || q;
|
1519 | }
|
1520 | return q;
|
1521 | },
|
1522 | goPath: function LALR_goPath (p, w) {
|
1523 | var q = parseInt(p, 10),t,
|
1524 | path = [];
|
1525 | for (var i=0;i<w.length;i++) {
|
1526 | t = w[i] ? q+":"+w[i] : '';
|
1527 | if (t) this.newg.nterms_[t] = q;
|
1528 | path.push(t);
|
1529 | q = this.states.item(q).edges[w[i]] || q;
|
1530 | this.terms_[t] = w[i];
|
1531 | }
|
1532 | return {path: path, endState: q};
|
1533 | },
|
1534 |
|
1535 | buildNewGrammar: function LALR_buildNewGrammar () {
|
1536 | var self = this,
|
1537 | newg = this.newg;
|
1538 |
|
1539 | this.states.forEach(function (state, i) {
|
1540 | state.forEach(function (item) {
|
1541 | if (item.dotPosition === 0) {
|
1542 |
|
1543 | var symbol = i+":"+item.production.symbol;
|
1544 | self.terms_[symbol] = item.production.symbol;
|
1545 | newg.nterms_[symbol] = i;
|
1546 | if (!newg.nonterminals[symbol])
|
1547 | newg.nonterminals[symbol] = new Nonterminal(symbol);
|
1548 | var pathInfo = self.goPath(i, item.production.handle);
|
1549 | var p = new Production(symbol, pathInfo.path, newg.productions.length);
|
1550 | newg.productions.push(p);
|
1551 | newg.nonterminals[symbol].productions.push(p);
|
1552 |
|
1553 |
|
1554 | var handle = item.production.handle.join(' ');
|
1555 | var goes = self.states.item(pathInfo.endState).goes;
|
1556 | if (!goes[handle])
|
1557 | goes[handle] = [];
|
1558 | goes[handle].push(symbol);
|
1559 |
|
1560 |
|
1561 | }
|
1562 | });
|
1563 | if (state.inadequate)
|
1564 | self.inadequateStates.push(i);
|
1565 | });
|
1566 | },
|
1567 | unionLookaheads: function LALR_unionLookaheads () {
|
1568 | var self = this,
|
1569 | newg = this.newg,
|
1570 | states = !!this.onDemandLookahead ? this.inadequateStates : this.states;
|
1571 |
|
1572 | states.forEach(function union_states_forEach (i) {
|
1573 | var state = typeof i === 'number' ? self.states.item(i) : i,
|
1574 | follows = [];
|
1575 | if (state.reductions.length)
|
1576 | state.reductions.forEach(function union_reduction_forEach (item) {
|
1577 | var follows = {};
|
1578 | for (var k=0;k<item.follows.length;k++) {
|
1579 | follows[item.follows[k]] = true;
|
1580 | }
|
1581 | state.goes[item.production.handle.join(' ')].forEach(function reduction_goes_forEach (symbol) {
|
1582 | newg.nonterminals[symbol].follows.forEach(function goes_follows_forEach (symbol) {
|
1583 | var terminal = self.terms_[symbol];
|
1584 | if (!follows[terminal]) {
|
1585 | follows[terminal]=true;
|
1586 | item.follows.push(terminal);
|
1587 | }
|
1588 | });
|
1589 | });
|
1590 |
|
1591 | });
|
1592 | });
|
1593 | }
|
1594 | });
|
1595 |
|
1596 | var LALRGenerator = exports.LALRGenerator = lalr.construct();
|
1597 |
|
1598 |
|
1599 |
|
1600 | var lalrGeneratorDebug = {
|
1601 | trace: function trace () {
|
1602 | Jison.print.apply(null, arguments);
|
1603 | },
|
1604 | beforebuildNewGrammar: function () {
|
1605 | this.trace(this.states.size()+" states.");
|
1606 | this.trace("Building lookahead grammar.");
|
1607 | },
|
1608 | beforeunionLookaheads: function () {
|
1609 | this.trace("Computing lookaheads.");
|
1610 | }
|
1611 | };
|
1612 |
|
1613 |
|
1614 |
|
1615 |
|
1616 |
|
1617 |
|
1618 | var lrLookaheadGenerator = generator.beget(lookaheadMixin, lrGeneratorMixin, {
|
1619 | afterconstructor: function lr_aftercontructor () {
|
1620 | this.computeLookaheads();
|
1621 | this.buildTable();
|
1622 | }
|
1623 | });
|
1624 |
|
1625 |
|
1626 |
|
1627 |
|
1628 | var SLRGenerator = exports.SLRGenerator = lrLookaheadGenerator.construct({
|
1629 | type: "SLR(1)",
|
1630 |
|
1631 | lookAheads: function SLR_lookAhead (state, item) {
|
1632 | return this.nonterminals[item.production.symbol].follows;
|
1633 | }
|
1634 | });
|
1635 |
|
1636 |
|
1637 |
|
1638 |
|
1639 |
|
1640 | var lr1 = lrLookaheadGenerator.beget({
|
1641 | type: "Canonical LR(1)",
|
1642 |
|
1643 | lookAheads: function LR_lookAheads (state, item) {
|
1644 | return item.follows;
|
1645 | },
|
1646 | Item: lrGeneratorMixin.Item.prototype.construct({
|
1647 | afterconstructor: function () {
|
1648 | this.id = this.production.id+'a'+this.dotPosition+'a'+this.follows.sort().join(',');
|
1649 | },
|
1650 | eq: function (e) {
|
1651 | return e.id === this.id;
|
1652 | }
|
1653 | }),
|
1654 |
|
1655 | closureOperation: function LR_ClosureOperation (itemSet /*, closureSet*/) {
|
1656 | var closureSet = new this.ItemSet();
|
1657 | var self = this;
|
1658 |
|
1659 | var set = itemSet,
|
1660 | itemQueue, syms = {};
|
1661 |
|
1662 | do {
|
1663 | itemQueue = new Set();
|
1664 | closureSet.concat(set);
|
1665 | set.forEach(function (item) {
|
1666 | var symbol = item.markedSymbol;
|
1667 | var b, r;
|
1668 |
|
1669 |
|
1670 | if (symbol && self.nonterminals[symbol]) {
|
1671 | r = item.remainingHandle();
|
1672 | b = self.first(item.remainingHandle());
|
1673 | if (b.length === 0 || item.production.nullable || self.nullable(r)) {
|
1674 | b = b.concat(item.follows);
|
1675 | }
|
1676 | self.nonterminals[symbol].productions.forEach(function (production) {
|
1677 | var newItem = new self.Item(production, 0, b);
|
1678 | if(!closureSet.contains(newItem) && !itemQueue.contains(newItem)) {
|
1679 | itemQueue.push(newItem);
|
1680 | }
|
1681 | });
|
1682 | } else if (!symbol) {
|
1683 |
|
1684 | closureSet.reductions.push(item);
|
1685 | }
|
1686 | });
|
1687 |
|
1688 | set = itemQueue;
|
1689 | } while (!itemQueue.isEmpty());
|
1690 |
|
1691 | return closureSet;
|
1692 | }
|
1693 | });
|
1694 |
|
1695 | var LR1Generator = exports.LR1Generator = lr1.construct();
|
1696 |
|
1697 | /*
|
1698 | * LL Parser
|
1699 | * */
|
1700 | var ll = generator.beget(lookaheadMixin, {
|
1701 | type: "LL(1)",
|
1702 |
|
1703 | afterconstructor: function ll_aftercontructor () {
|
1704 | this.computeLookaheads();
|
1705 | this.table = this.parseTable(this.productions);
|
1706 | },
|
1707 | parseTable: function llParseTable (productions) {
|
1708 | var table = {},
|
1709 | self = this;
|
1710 | productions.forEach(function (production, i) {
|
1711 | var row = table[production.symbol] || {};
|
1712 | var tokens = production.first;
|
1713 | if (self.nullable(production.handle)) {
|
1714 | Set.union(tokens, self.nonterminals[production.symbol].follows);
|
1715 | }
|
1716 | tokens.forEach(function (token) {
|
1717 | if (row[token]) {
|
1718 | row[token].push(i);
|
1719 | self.conflicts++;
|
1720 | } else {
|
1721 | row[token] = [i];
|
1722 | }
|
1723 | });
|
1724 | table[production.symbol] = row;
|
1725 | });
|
1726 |
|
1727 | return table;
|
1728 | }
|
1729 | });
|
1730 |
|
1731 | var LLGenerator = exports.LLGenerator = ll.construct();
|
1732 |
|
1733 | Jison.Generator = function Jison_Generator (g, options) {
|
1734 | var opt = typal.mix.call({}, g.options, options);
|
1735 | switch (opt.type) {
|
1736 | case 'lr0':
|
1737 | return new LR0Generator(g, opt);
|
1738 | case 'slr':
|
1739 | return new SLRGenerator(g, opt);
|
1740 | case 'lr':
|
1741 | return new LR1Generator(g, opt);
|
1742 | case 'll':
|
1743 | return new LLGenerator(g, opt);
|
1744 | default:
|
1745 | return new LALRGenerator(g, opt);
|
1746 | }
|
1747 | };
|
1748 |
|
1749 | return function Parser (g, options) {
|
1750 | var gen = Jison.Generator(g, options);
|
1751 | return gen.createParser();
|
1752 | };
|
1753 |
|
1754 | })();
|