title: Parser/Grammar: 2x parenthesis in nested rules
body: <p>Despite my limited knowledge about compiling/parsing I dared to build a small recursive-descent parser for OData $filter expressions. The parser only needs to check the expression for correctness and output a corresponding condition in SQL. As input and output have almost the same tokens and structure, this was fairly straightforward, and my implementation does 90% of what I want.</p>
  <p>But now I got stuck with parentheses, which appear in separate rules for logical and arithmetic expressions. The full OData grammar in ABNF is <a href="http://docs.oasis-open.org/odata/odata/v4.0/errata02/os/complete/abnf/odata-abnf-construction-rules.txt" rel="nofollow noreferrer">here</a>, a condensed version of the rules involved is this:</p>
  <pre><code>boolCommonExpr = ( boolMethodCallExpr 
                   / notExpr  
                   / commonExpr [ eqExpr / neExpr / ltExpr / ... ]
                   / boolParenExpr
                   ) [ andExpr / orExpr ] 
  commonExpr = ( primitiveLiteral
               / firstMemberExpr  ; = identifier
               / methodCallExpr 
               / parenExpr 
               ) [ addExpr / subExpr / mulExpr / divExpr / modExpr ]  
  boolParenExpr = &quot;(&quot; boolCommonExpr &quot;)&quot;
  parenExpr     = &quot;(&quot; commonExpr &quot;)&quot;
  </code></pre>
  <p>How does this grammar match a simple expression like <code>(1 eq 2)</code>? From what I can see all <code>(</code> are consumed by the rule <code>parenExpr</code> inside <code>commonExpr</code>, i.e. they must also close after <code>commonExpr</code> to not cause an error and <code>boolParenExpr</code> never gets hit. I suppose my experience / intuition on reading such a grammar is just insufficient to get it. A comment in the ABNF says: &quot;Note that boolCommonExpr is also a commonExpr&quot;. Maybe that's part of the mystery?</p>
  <p>Obviously an opening <code>(</code> alone won't tell me where it's going to close: After the current <code>commonExpr</code> expression or further away after <code>boolCommonExpr</code>. My lexer has a list of <strong>all</strong> tokens ahead (URL is very short input). I was thinking to use that to find out what type of <code>(</code> I have. Good idea?</p>
  <p>I'd rather have restrictions in input or a little hack than switching to a generally more powerful parser model. For a simple expression translation like this I also want to avoid compiler tools.</p>
  <hr />
  <p><strong>Edit 1: Extension after answer by rici - Is grammar rewrite correct?</strong></p>
  <p>Actually I started out with the <a href="https://en.wikipedia.org/wiki/Recursive_descent_parser" rel="nofollow noreferrer">example for recursive-descent parsers given on Wikipedia</a>. Then I though to better adapt to the official grammar given by the OData standard to be more &quot;conformant&quot;. But with the advice from rici (and the comment from &quot;Internal Server Error&quot;) to rewrite the grammar I would tend to go back to the more comprehensible structure provided on Wikipedia.</p>
  <p>Adapted to the boolean expression for the OData $filter this could maybe look like this:</p>
  <pre><code>boolSequence= boolExpr {(&quot;and&quot;|&quot;or&quot;) boolExpr} .
  boolExpr    = [&quot;not&quot;] expression (&quot;eq&quot;|&quot;ne&quot;|&quot;lt&quot;|&quot;gt&quot;|&quot;lt&quot;|&quot;le&quot;) expression .
  expression  = term {(&quot;add&quot;|&quot;sum&quot;) term} .
  term        = factor {(&quot;mul&quot;|&quot;div&quot;|&quot;mod&quot;) factor} .
  factor      = IDENT | methodCall | LITERAL | &quot;(&quot; boolSequence&quot;)&quot; .
  methodCall  = METHODNAME &quot;(&quot; [ expression {&quot;,&quot; expression} ] &quot;)&quot; .
  </code></pre>
  <p>Does the above make sense in general for boolean expressions, is it mostly equivalent to the original structure above and digestible for a recursive descent parser?</p>
  <p>@rici: Thanks for your detailed remarks on type checking. The new grammar should resolve your concerns about precedence in arithmetic expressions.</p>
  <p>For all three terminals (UPPERCASE in the grammar above) my lexer supplies a type (string, number, datetime or boolean). Non-terminals return the type they produce. With this I managed quite nicely do type checking on the fly in my current implementation, including decent error messages. Hopefully this will also work for the new grammar.</p>
  <hr />
  <p><strong>Edit 2: Return to original OData grammar</strong></p>
  <p>The differentiation between a &quot;logical&quot; and &quot;arithmetic&quot; <code>(</code> is not a trivial one. To solve the problem even N.Wirth uses a dodgy workaround to keep the grammar of Pascal simple. As a consequence, in Pascal an extra pair of <code>()</code> is <em>mandatory</em> around <code>and</code> and <code>or</code> expressions. Neither intuitive nor OData conformant :-(. The best read about the &quot;() difficulty&quot; I found is in <a href="https://compilers.iecc.com/crenshaw/tutor6.txt" rel="nofollow noreferrer">Let's Build a Compiler (Part VI)</a>. Other languages seem to go to great length in the grammar to solve the problem. As I don't have experience with grammar construction I stopped doing my own.</p>
  <p>I ended up implementing the original OData grammar. Before I run the parser I go over all tokens backwards to figure out which <code>(</code> belong to a logical/arithmetic expression. Not a problem for the potential length of a URL.</p>