Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
E -> E * B .
E -> E + B .
E -> B .
B -> 0 .
B -> 1 .
I am confused because Wikipedia cites this grammar as an example of an LR(0) grammar and constructs an LR(0) parsing table for this grammar, while Grammophone reports shift-reduce conflicts and marks some cells in the grammar's LR(0) parsing table red. (The dots are not terminals; rather, they denote end of production; Grammophone requires this.)
What's going on here?
Before applying the LR algorithm to a grammar, the grammar must be "augmented" by adding the rule
$S' \to S \$$
where $S$ is the original start symbol and $S'$ and $\$$ are symbols not in the grammar. $S'$ becomes the start symbol for the augmented grammar, and the string to be parsed is augmented by appending a $\$$ at the end. A reduce action for this newly added rule is written as "accept", which has the side effect of terminating the parse.
The table shown in the Wikipedia article is for the augmented grammar, as you can see from its parsing table, which includes "accept" actions and the $\$$ end marker symbol.
For whatever reason, Grammophone does not augment grammars before applying the LR(0) algorithm. The grammar is augmented for the other algorithms. (I would call this a bug, but it could argued that it is an idiosyncratic interpretation of the algorithm.) If you give it an augmented grammar, then you get roughly the same LR(0) table as is found in Wikipedia (although an extra state is produced prior to the accept action.)
Grammophone has other issues. I don't recommend relying on it for grammar analysis.
