StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The reduce-reduce conflict in your grammar comes from the context:</p> <pre><code>... = ... x , </code></pre> <p>At this point, the parser has to decide whether <code>x</code> is an <code>fe</code> or an <code>fp</code>, and it cannot know with one symbol lookahead. Indeed, it cannot know with any finite lookahead, you could have any number of repetitions of <code>x ,</code> following that point without encountering a <code>=</code>, <code>;</code> or the end of the input, any of which would reveal the answer.</p> <p>This is not quite the same as the C issue, which can be resolved with single symbol lookahead. However, the C example is a classic illustration of why SLR(1) grammars are less powerful than LALR(1) grammars -- it's used for that purpose in the dragon book -- and a similarly problematic grammar is an example of the difference between LALR(1) and LR(1); it can be found in the bison manual (<a href="http://www.gnu.org/software/bison/manual/html_node/Mysterious-Conflicts.html" rel="nofollow">here</a>):</p> <pre><code> def: param_spec return_spec ','; param_spec: type | name_list ':' type; return_spec: type | name ':' type; type: "id"; name: "id"; name_list: name | name ',' name_list; </code></pre> <p>(The bison manual explains how to resolve this issue for LALR(1) grammars, although using a GLR grammar is always a possibility.)</p> <p>The key to resolving such conflicts without using a GLR grammar is to avoid forcing the parser to make premature decisions.</p> <p>For example, it is traditional to distinguish syntactically between lvalues and rvalues, and some languages continue to do so. C and C++ do not, however; and this turns out to be an extremely powerful feature in C++ because it allows the definition of functions which can act as lvalues.</p> <p>In C, I think it's just to simplify the grammar a bit: the C grammar allows the result of any unary operator to appear on the left hand side of an assignment operator, but unary operators are actually a mix of lvalues (<code>*v</code>, <code>v[expr]</code>) and rvalues (<code>sizeof v</code>, <code>f(expr)</code>). The grammar <em>could</em> have distinguished between the two kinds of unary operators, but it could not resolve the actual restriction, which is that only <em>modifiable</em> lvalues may appears on the left side of an assignment operator.</p> <p>C++ allows an arbitrary expression to appear on the left-hand side of an assignment operator (although some need to be parenthesized); consequently, the following is totally legal:</p> <pre><code>(predicate(x) ? *some_pointer : some_variable) = 42; </code></pre> <p>In your case, you could resolve the conflict syntactically by replacing <code>te</code> with <code>p</code>, since both non-terminals produce the same set of derivations. That's probably not the general solution, unless it is really the case in your full grammar that left-side expressions are a strict subset of right-side expressions. In a full grammar, you might end up with three types of expression (left-only, right-only, common), which could considerably complicated the grammar, and leaving the resolution for semantic analysis might prove to be easier (and even, as in the case of C++, surprisingly useful).</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

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