How do I tell, given a specific grammar, which is the upper bound for the number of states of a LR(0) or LR(1) automaton for its SLR parsing?

My guess is that generating the canonical item collection would provide the answer, but isn't it giving the exact number of states rather than an upper bound?

Plus, is there any heuristics or specific algorithm related to the grammar structure which can get to know the required bound? Possibly, one or more that can easily fit within undergraduate knowledge -- skimming through the Dragon Book didn't give me any useful insight (perhaps I'm not that good at searching).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.