Databases
StackOverflow2013
Postsdbo
POHelp with left factoring a grammar to remove left recursion
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHelp with left factoring a grammar to remove left recursion
    primarykey
    data
    text
    <p>I have a small custom scripting language, and I am trying to update it to allow boolean expressions such as <code>a &gt; 2</code> and <code>a &gt; 2 and (b &lt; 3 or c &gt; 5)</code>. It's the parenthetical expressions that I am having trouble with here.</p> <p>Here is a (edited since the original post based on the answer from @Bart Kiers) full grammar that exhibits the problem. This is a pared-down version of my actual grammar, but the problem occurs here too.</p> <pre><code>grammar test; options { language = 'JavaScript'; output = AST; } statement : value_assignment_statement EOF ; value_assignment_statement : IDENT '=' expression ; value_expression : value_list_expression | IDENT ; value_list_expression : value_enumerated_list ; value_enumerated_list : '{' unary+ '}' ; term : LPAREN expression RPAREN | INTEGER | value_expression ; unary : ( '+' | '-' )* term ; mult : unary ( ('*' | '/') unary)* ; expression : mult ( ('+' | '-') mult )* ; boolean : boolean_expression EOF ; boolean_expression : boolean_or_expression ; boolean_or_expression : boolean_and_expression (OR boolean_and_expression)* ; boolean_and_expression : boolean_rel_expression (AND boolean_rel_expression)* ; boolean_rel_expression : boolean_neg_expression relational_operator boolean_neg_expression ; boolean_neg_expression : (NOT)? atom ; atom : LPAREN boolean_expression RPAREN //| expression ; relational_operator : '=' | '&gt;' | '&lt;'; LPAREN : '('; RPAREN : ')'; AND : 'and'; OR : 'or'; NOT : 'not'; IDENT : LETTER LETTER+; INTEGER : DIGIT+; WS : (' ' | '\n' | '\r' | '\t')+ { $channel = HIDDEN; }; fragment DIGIT : '0'..'9'; fragment LETTER : ('a'..'z' | 'A'..'Z'); </code></pre> <p>My attempt to accommodate parenthetical boolean expressions such as <code>a &gt; 2 or (b &lt; 3)</code> is in the commented-out line in the <code>atom</code> rule. When I uncomment this line and include it in the grammar, ANTLR gives me this error:</p> <blockquote> <p>[fatal] rule atom has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2. Resolve by left-factoring or using syntactic predicates or using backtrack=true option.</p> </blockquote> <p>I would like to address this by removing the recursion, but I can't seem to make the transition from the <a href="http://en.wikipedia.org/wiki/Left_recursion" rel="noreferrer">Wikipedia description on how to remove left recursion</a> to my own stuff. </p> <p>In using this grammar, I want sometimes to use <code>statement</code> as a root with input such as <code>abc = 2 + 3</code>, which assigns a value to a variable named abc. Other times I want to use the grammar to evaluate an expression with <code>boolean</code> as the root with input such as <code>abc &gt; 3 and (xyz &lt; 5 or xyz &gt; 10)</code>. When I tried to use @Bart's answer as a model, it worked fine until I tried to merge the parts of the grammar used by <code>statement</code> with the parts used by <code>boolean</code>. They should both be able to use an <code>expression</code>, but that's where I'm stuck with this left recursion error.</p> <p>So, how can I both handle parentheses and avoid the left recursion problem?</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USChris Farmer
    1. USChris Farmer
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHelp with left factoring a grammar to remove left recursion
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POHelp with left factoring a grammar to remove left recursion
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POHelp with left factoring a grammar to remove left recursion
      1. USA.H.
      1. VTFavorite
    1. CODoes your `expression` symbol have a rule for parenthesized expressions?
      singulars
      1. POHelp with left factoring a grammar to remove left recursion
      1. USFred Foo
    2. CO@larsmans: It can represent parenthetical expressions that evaluate to a number, such as `(3 + x) * 2` but doesn't accommodate the boolean evaluations I am doing now.
      singulars
      1. POHelp with left factoring a grammar to remove left recursion
      1. USChris Farmer
 

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