Databases
StackOverflow2013
Postsdbo
POLeft-factoring grammar of coffeescript expressions
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POLeft-factoring grammar of coffeescript expressions
    primarykey
    data
    text
    <p>I'm writing an <a href="https://bitbucket.org/adamschmideg/coffeescript-eclipse" rel="nofollow noreferrer">Antlr/Xtext parser for coffeescript grammar</a>. It's at the beginning yet, I just moved a subset of the <a href="http://jashkenas.github.com/coffee-script/documentation/docs/grammar.html" rel="nofollow noreferrer">original grammar</a>, and I am stuck with expressions. It's the dreaded "rule expression has non-LL(*) decision" error. I found some related questions here, <a href="https://stackoverflow.com/questions/6629397/help-with-left-factoring-a-grammar-to-remove-left-recursion">Help with left factoring a grammar to remove left recursion</a> and <a href="https://stackoverflow.com/questions/1452729/antlr-grammar-for-expressions">ANTLR Grammar for expressions</a>. I also tried <a href="http://www.antlr.org/wiki/display/ANTLR3/How+to+remove+global+backtracking+from+your+grammar" rel="nofollow noreferrer">How to remove global backtracking from your grammar</a>, but it just demonstrates a very simple case which I cannot use in real life. The post about <a href="http://eschew.wordpress.com/2010/08/01/antlr-grammar-tip-ll-and-left-factoring/" rel="nofollow noreferrer">ANTLR Grammar Tip: LL() and Left Factoring</a> gave me more insights, but I still can't get a handle.</p> <p>My question is how to fix the following grammar (sorry, I couldn't simplify it and still keep the error). I guess the trouble maker is the <code>term</code> rule, so I'd appreciate a local fix to it, rather than changing the whole thing (I'm trying to stay close to the rules of the original grammar). Pointers are also welcome to tips how to "debug" this kind of erroneous grammar in your head.</p> <pre><code>grammar CoffeeScript; options { output=AST; } tokens { AT_SIGIL; BOOL; BOUND_FUNC_ARROW; BY; CALL_END; CALL_START; CATCH; CLASS; COLON; COLON_SLASH; COMMA; COMPARE; COMPOUND_ASSIGN; DOT; DOT_DOT; DOUBLE_COLON; ELLIPSIS; ELSE; EQUAL; EXTENDS; FINALLY; FOR; FORIN; FOROF; FUNC_ARROW; FUNC_EXIST; HERECOMMENT; IDENTIFIER; IF; INDENT; INDEX_END; INDEX_PROTO; INDEX_SOAK; INDEX_START; JS; LBRACKET; LCURLY; LEADING_WHEN; LOGIC; LOOP; LPAREN; MATH; MINUS; MINUS; MINUS_MINUS; NEW; NUMBER; OUTDENT; OWN; PARAM_END; PARAM_START; PLUS; PLUS_PLUS; POST_IF; QUESTION; QUESTION_DOT; RBRACKET; RCURLY; REGEX; RELATION; RETURN; RPAREN; SHIFT; STATEMENT; STRING; SUPER; SWITCH; TERMINATOR; THEN; THIS; THROW; TRY; UNARY; UNTIL; WHEN; WHILE; } COMPARE : '&lt;' | '==' | '&gt;'; COMPOUND_ASSIGN : '+=' | '-='; EQUAL : '='; LOGIC : '&amp;&amp;' | '||'; LPAREN : '('; MATH : '*' | '/'; MINUS : '-'; MINUS_MINUS : '--'; NEW : 'new'; NUMBER : ('0'..'9')+; PLUS : '+'; PLUS_PLUS : '++'; QUESTION : '?'; RELATION : 'in' | 'of' | 'instanceof'; RPAREN : ')'; SHIFT : '&lt;&lt;' | '&gt;&gt;'; STRING : '"' (('a'..'z') | ' ')* '"'; TERMINATOR : '\n'; UNARY : '!' | '~' | NEW; // Put it at the end, so keywords will be matched earlier IDENTIFIER : ('a'..'z' | 'A'..'Z')+; WS : (' ')+ {skip();} ; root : body ; body : line ; line : expression ; assign : assignable EQUAL expression ; expression : value | assign | operation ; identifier : IDENTIFIER ; simpleAssignable : identifier ; assignable : simpleAssignable ; value : assignable | literal | parenthetical ; literal : alphaNumeric ; alphaNumeric : NUMBER | STRING; parenthetical : LPAREN body RPAREN ; // term should be the same as expression except operation to avoid left-recursion term : value | assign ; questionOp : term QUESTION? ; mathOp : questionOp (MATH questionOp)* ; additiveOp : mathOp ((PLUS | MINUS) mathOp)* ; shiftOp : additiveOp (SHIFT additiveOp)* ; relationOp : shiftOp (RELATION shiftOp)* ; compareOp : relationOp (COMPARE relationOp)* ; logicOp : compareOp (LOGIC compareOp)* ; operation : UNARY expression | MINUS expression | PLUS expression | MINUS_MINUS simpleAssignable | PLUS_PLUS simpleAssignable | simpleAssignable PLUS_PLUS | simpleAssignable MINUS_MINUS | simpleAssignable COMPOUND_ASSIGN expression | logicOp ; </code></pre> <p>UPDATE: The final solution will use Xtext with an external lexer to avoid to <a href="https://stackoverflow.com/questions/7167834/xtext-grammar-for-language-with-significant-semantic-whitespace">intricacies of handling significant whitespace</a>. Here is a snippet from my Xtext version:</p> <pre><code>CompareOp returns Operation: AdditiveOp ({CompareOp.left=current} operator=COMPARE right=AdditiveOp)*; </code></pre> <p>My strategy is to make a working Antlr parser first without a usable AST. (Well, it would deserve a separates question if this is a feasible approach.) So I don't care about tokens at the moment, they are included to make development easier.</p> <p>I am aware that the original grammar is LR. I don't know how close I can stay to it when transforming to LL. </p> <p>UPDATE2 and SOLUTION: I could simplify my problem with the insights gained from Bart's answer. Here is a working toy grammar to handle simple expressions with function calls to illustrate it. The comment before <code>expression</code> shows my insight.</p> <pre><code>grammar FunExp; ID: ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'0'..'9'|'_')*; NUMBER: '0'..'9'+; WS: (' ')+ {skip();}; root : expression ; // atom and functionCall would go here, // but they are reachable via operation -&gt; term // so they are omitted here expression : operation ; atom : NUMBER | ID ; functionCall : ID '(' expression (',' expression)* ')' ; operation : multiOp ; multiOp : additiveOp (('*' | '/') additiveOp)* ; additiveOp : term (('+' | '-') term)* ; term : atom | functionCall | '(' expression ')' ; </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USAdam Schmideg
    plurals
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    3. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POLeft-factoring grammar of coffeescript expressions
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POLeft-factoring grammar of coffeescript expressions
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POLeft-factoring grammar of coffeescript expressions
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload