The week's pick
Reseach Article
State Merging in LR Parser under Count based Reduction
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 100 - Number 17 |
| Year of Publication: 2014 |
| Authors: R. D. Solomon Raju, Pawan Kumar |
10.5120/17616-8235
|
R. D. Solomon Raju, Pawan Kumar . State Merging in LR Parser under Count based Reduction. International Journal of Computer Applications. 100, 17 ( August 2014), 19-31. DOI=10.5120/17616-8235
Abstract
An LR parser shows error only during scanning input symbol. Error is never shown during the reduction of a handle (substring of stack) into nonterminal. It is because a symbol is put into the stack only when it is guaranteed to be the correct one. If the method of reduction of a handle is known then errors can also be shown during reduction. Hence a wrong symbol can be shifted on the stack and error can be detected during reduce operation. It may permit the merging of few states. The simplest type of reduction scheme is to remove few symbols (the number of symbols equal to the length of the handle) from the top of the stack and push the corresponding nonterminal on the stack. In this paper, a state merging scheme is proposed under this method of reduction.
References
- Alfred V, Aho, Ravi Sethi, and Jeffery D. Ullaman, Compiler: Principles, Techniques and Tools, 1986, Addison-Wesley
- Dillip Kumar and Pawan Kumar, State Merging in LR parser, ACM SIGPLAN notices, Vol 41(4), pp 24-29, 2006
- Anderson T, Syntactic Analysis of LR (k) languages. PhD Thesis, University Newcastle-upon- Tyne, Northumberland, England, 1972
- Anderson T, Eve J, and Horning, J J, "Efficient LR(1) parsers. " Acla Informatics 2 , pp 12-39, 1973
- Deremer F. L, "Simple LR(k) grammars " Comm. ACM 14,Vol 7, pp 453-460, 1971
- Floyd R. W, "Syntactic analysis and operator precedence " J. ACM 10,Vol 3, pp 316-333, 1963
- Lalonde W R, Lee E S, and Homing J. J, "An LALR (k) parser generator. " Proc. IFIP Congress 71 TA-3, North-Holland Publishing Co. , Amsterdam, the Netherlands, pp 153-157, 1971
- Pager D, "On the incremental approach to left- to-right parsing " Technical Report PE 238, Information Sciences Program, Univ. Hawaii, Honolulu, Hawan, 1972a
- Pager D, "A fast left-to-right parser for context-free grammars. " Technical Report PE 240, Information Sciences Program, Univ. Hawaii, Honolulu, Hawaii, 1972b
Index Terms
Keywords