Theory LR_Plain
theory LR_Plain
imports LR_Loop
begin
section ‹A plain action table›
text ‹The step on candidate tables (\<^const>‹kctl›) tries the shift and then
the reduce candidates of the lookahead, which takes a lookup in the shift
table, one in the table of candidates, and one in the table of productions
per candidate. Here one table gives per state and lookahead the actions to try: the
shift with its target if there is one (the step takes it before any
reduce), otherwise the reduces, each with its production and the number of
its left-hand side. A second table gives the reduces at the end of the
input, where there is no shift. This is the action table of Jourdan et al.
\<^cite>‹‹Sect.~2.4› in "jourdan2012-validating-lr1"›, and Knuth tabulates the same choice of
shift or reduce per state set \<^cite>‹‹Sect.~III, Table~I› in "knuth1965-lr-translation"›.
Here an entry is a list of actions rather than one, and the end of the input
has its own table, where Jourdan et al. assume an infinite input stream.
The step on these tables equals the step on
candidate tables on every stack, so the run is the same.›