Upper bounds on the size of LR(k) parsers |
| |
| Authors: | Esko Ukkonen |
| |
| Affiliation: | Department of Computer Science, University of Helsinki, Tukholmankatu 2, SF-00250 Helsinki 25, Finland |
| |
| Abstract: | It is shown that in many cases the trivial upper bound 2|G|k + 1 on the number of states of an LR(k) parser for a grammar G is too conservative. In particular, if G is not right-recursive, the canonical LR(k) parser for G has at most |Gk|G|·2|G| states. Examples of grammars with large LR(k) parsers are given. |
| |
| Keywords: | LR(k) parser right recursion size bound |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
