On the covering of parsable grammars

摘要

The notion of a parsable grammar is introduced. A definition of cover is provided which is a generalization of a well-known definition of cover. With this new definition of cover we prove that every parsable grammar is covered by an LR(1) grammar or, if the language is prefix-free, by a strict deterministic grammar. A consequence of this result is that every LR(k) grammar is covered by an LR(1) or a strict deterministic grammar.