As we know, if we want to make a $LR(0)$ (say) parsing table for a context free grammar (CFG), we prepare the $LR(0)$ itemsets with $.$ (dot) in RHS of the CFG production.

With this $.$ we keep track of characters that compiler has seen yet, and continue to make states of these itemsets, which ultimately make a deterministic finite machine (DFA).

Formation of DFA is natural, as the compiler will visit the *finite* states *deterministically*.

My question is, **what does the regular language of this DFA signify?**


1 Answer 1


For grammar $$ S \rightarrow Sa | b $$ The following represents the $LR(0)$ itemset and its finite automata. (ignore the $ symbol) FA of LR0 Itemsets

If every state is final state of the above $FA$, it would recognise $\{\epsilon, b, S, Sa \}$ , hence this is set of all viable prefixes, which are defined as the prefixes of right sentential forms that can appear on the stack of a shift-reduce parser.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.