States merging in LR parser

ABSTRACT

Here a scheme is presented, which reduces the size of an LR parser. It is accomplished by merging two states, which do not perform differently on the same input symbol or non-terminal. This state merging has following advantages:1. The reduction in number of states is greater than the reduction in an LALR parser.2. The power of parser is not reduced as it would be in an LALR parser.The above merging scheme has following disadvantages:1. Even erroneous inputs are accepted. However, it is stopped by changing the notion of acceptance.2. Errors are report late and in a misleading manner.3. Parsing takes more time because string matching is done during reduction.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Parsing

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Parsing

General Terms:
Algorithms, Design