<p>I'd like to confirm whether a sketch of procedure over a DCFG (deterministic context-free grammar) can maintaining full functional equivalence over building a full states transition table and loop over it.</p>
<ol>
<li>Start with an empty stack.</li>
<li>Traverse the DCFG rules, look for the rule with longest matched sequence of tokens, by matching from right to left from the top of the stack.</li>
<li>If matched, join the tokens and reduce, then loop from step 2.</li>
<li>If no match, shift a token, then loop from step 2.</li>
</ol>
<p>While look for ways to detect errors that are akin to empty cells in table-driven LR parsers, I realized that this 4 steps would consume all inputs and only report error when it finds the stack cannot reduce to the start symbol, which has the desirable use-case of reporting syntax errors aggressively.</p>
<h2>post-posting update</h2>
<p>I realize I haven't torture-tested my idea with real-world grammars and source code fragments, so it may not be very robust.</p>

<parsing><context-free-grammar>
DCFG without using state table
CC BY-SA 4.0
2024-12-22T23:16:14.967Z
Not sure if this helps, but in case you're interested in a bottoms up, shift/reduce, table-free, infix expression parser, see: https://erikeidt.github.io/The-Double-E-Method.html .  This uses two stacks (operator & operand) and two simple states, which are each represented by their own separate code section rather than by tables and state variables.  This approach is industrial strength, accepting things it should and rejecting things it shouldn't.  Further discussion: https://www.reddit.com/r/ProgrammingLanguages/comments/16vqbey/alternatives_to_the_shunting_yard_algorithm_for/?rdt=50619
Erik Eidt
<p>The 4 rules can't work with the following grammar:</p>
<pre><code>Additive-Expression
: Multiplicative-Expression
| Additive-Expression (&quot;+&quot;|&quot;-&quot;) Multiplicative-Expression
;

Multiplicative-Expression
: Primary-Expression
| Multiplicative-Expression (&quot;*&quot;|&quot;/&quot;) Primary-Expression
;

Primary-Expression
: &lt;label&gt;
| &lt;literal&gt;
| &quot;(&quot; Additive-Expression &quot;)&quot;
;

%-&gt; Additive-Expression
</code></pre>
<p>Take the following example:</p>
<pre><code>1+2*3 []
+2*3  [1: literal]
+2*3  [1: primary-expr]
+2*3  [1: mul-expr]
+2*3  [1: add-expr]
2*3   [1+: &quot;+&quot;]
*3    [1+2: literal]
*3    [1+2: primary-expr]
*3    [1+2: mul-expr]  &lt;---------------Problem here.
3     [1+2*: &quot;*&quot;]
      [1+2*3: literal]
      [1+2*3: primary-expr]
      [1+&lt;mul-expr&gt;]
      [&lt;add-expr&gt;]
      [%start]
</code></pre>
<p>At the line marked &quot;Problem here&quot;, by the procedure sketched in the Q, the next step would not be the shift of the &quot;*&quot; operator, but rather, the reduction of &quot;1+2&quot; into <code>Additive-Expression</code>.</p>

CC BY-SA 4.0
2024-12-22T12:29:39.577Z
2024-12-22T12:29:39.577Z
DannyNiu
<p>The problems this will run into</p>
<ul>
<li><p>it will always reduce when both a shift and reduce are possible.  This will cause it to fail on any grammar that requires additional shifts before reducing things, like the simple one shown by @DannyNiu</p>
</li>
<li><p>it will have problems if there are any two rules with the same RHS (and different LHS), as it won't know which to reduce.</p>
</li>
</ul>
<p>Overall, this seems weaker than even LR(0) parsing.</p>

CC BY-SA 4.0
2024-12-24T00:48:01.343Z
2024-12-24T00:48:01.343Z
Chris Dodd
# DCFG without using state table
Posted by: username_0 on 2024-12-22
I'd like to confirm whether a sketch of procedure over a DCFG (deterministic context-free grammar) can maintaining full functional equivalence over building a full states transition table and loop over it.

1. Start with an empty stack.
2. Traverse the DCFG rules, look for the rule with longest matched sequence of tokens, by matching from right to left from the top of the stack.
3. If matched, join the tokens and reduce, then loop from step 2.
4. If no match, shift a token, then loop from step 2.

While look for ways to detect errors that are akin to empty cells in table-driven LR parsers, I realized that this 4 steps would consume all inputs and only report error when it finds the stack cannot reduce to the start symbol, which has the desirable use-case of reporting syntax errors aggressively.

## post-posting update

I realize I haven't torture-tested my idea with real-world grammars and source code fragments, so it may not be very robust.
**Tags:** parsing context-free-grammar
> **Comments:**
> **username_1**: Not sure if this helps, but in case you're interested in a bottoms up, shift/reduce, table-free, infix expression parser, see: https://erikeidt.github.io/The-Double-E-Method.html .  This uses two stacks (operator & operand) and two simple states, which are each represented by their own separate code section rather than by tables and state variables.  This approach is industrial strength, accepting things it should and rejecting things it shouldn't.  Further discussion: https://www.reddit.com/r/ProgrammingLanguages/comments/16vqbey/alternatives_to_the_shunting_yard_algorithm_for/?rdt=50619  
---
## 2 answers
### Answer by username_0 on 2024-12-22. Score: 2
The 4 rules can't work with the following grammar:
Additive-Expression
: Multiplicative-Expression
| Additive-Expression ("+"|"-") Multiplicative-Expression
;

Multiplicative-Expression
: Primary-Expression
| Multiplicative-Expression ("*"|"/") Primary-Expression
;

Primary-Expression
: 
| 
| "(" Additive-Expression ")"
;

%-> Additive-Expression

Take the following example:
1+2*3 []
+2*3  [1: literal]
+2*3  [1: primary-expr]
+2*3  [1: mul-expr]
+2*3  [1: add-expr]
2*3   [1+: "+"]
*3    [1+2: literal]
*3    [1+2: primary-expr]
*3    [1+2: mul-expr]  <---------------Problem here.
3     [1+2*: "*"]
      [1+2*3: literal]
      [1+2*3: primary-expr]
      [1+]
      []
      [%start]

At the line marked "Problem here", by the procedure sketched in the Q, the next step would not be the shift of the "*" operator, but rather, the reduction of "1+2" into Additive-Expression.
---
### Answer by username_2 on 2024-12-24. Score: 1
The problems this will run into

* it will always reduce when both a shift and reduce are possible. This will cause it to fail on any grammar that requires additional shifts before reducing things, like the simple one shown by @DannyNiu
* it will have problems if there are any two rules with the same RHS (and different LHS), as it won't know which to reduce.

Overall, this seems weaker than even LR(0) parsing.
---
