search

mdaines / grammophone

A tool for analyzing and transforming context-free grammars.
https://mdaines.github.io/grammophone
MIT License
206 stars 24 forks source link

Is the approach to propagating the EOF lookahead that Grammophone takes a nonstandard extension? #51

Closed modulovalue closed 3 weeks ago

modulovalue commented 6 months ago

Hello @mdaines,

Consider the following fragment of an LALR(1) automaton as produced by Grammophone:

Screenshot 2024-04-27 at 12 01 30

I was wondering, do you know if this approach to introducing the EOF $ lookahead/follow symbol is the standard approach for doing that, or is this an extension that Grammophone decided to introduce?

What I'm doing in my implementation is to simply give the starting production with the dot on the rightmost side (e.g. S -> A B C •) a $ starting lookahead which should then be propagated to wherever it is expected. One benefit of this approach is that there's no special casing needed for the constituents of a DFA node, that is, all constituents are a real production with a dot. In your case, the constituents of a DFA node can be a production with a dot, or a synthetic production with a dot (e.g. Start •, • Start).

Just wanted to hear your thoughts on that. Do you know which approach is more common?

modulovalue commented 3 weeks ago

So, I’m pretty sure now that this is an extension that is not common outside of grammophone. Items are defined as a production with a dot where a production is defined as a nonterminal symbol and a finite word consisting of terminal and nonterminal symbols. The extension highlighted here introduces a new type of item. I’m going to close this issue as I see it as resolved now.