Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

A major research goal for compilers and environments is the automatic derivation of tools from formal specifications. However, the formal model of the language is often inadequate; in particular, LR(k) grammars are unable to describe the natural syntax of many languages, such as C⁺⁺ and Fortran, which are inherently non-deterministic. Designers of batch compilers work around such limitations by combining generated components with ad hoc techniques (for instance, performing partial type and scope analysis in tandem with parsing). Unfortunately, the complexity of incremental systems precludes the use of batch solutions. The inability to generate incremental tools for important languages inhibits the widespread use of language-rich interactive environments.We address this problem by extending the language model itself, introducing a program representation based on parse dags that is suitable for both batch and incremental analysis. Ambiguities unresolved by one stage are retained in this representation until further stages can complete the analysis, even if the reaolution depends on further actions by the user. Representing ambiguity explicitly increases the number and variety of languages that can be analyzed incrementally using existing methods.To create this representation, we have developed an efficient incremental parser for general context-free grammars. Our algorithm combines Tomita's generalized LR parser with reuse of entire subtrees via state-matching. Disambiguation can occur statically, during or after parsing, or during semantic analysis (using existing incremental techniques); program errors that preclude disambiguation retsin multiple interpretations indefinitely. Our representation and analyses gain efficiency by exploiting the local nature of ambiguities: for the SPEC95 C programs, the explicit representation of ambiguity requires only 0.5% additional space and less than 1% additional time during reconstruction.

REFERENCES

• 1: A. V. Aho , S. C. Johnson , J. D. Ullman, Deterministic parsing of ambiguous grammars, Communications of the ACM, v.18 n.8, p.441-452, Aug. 1975 [doi>10.1145/360933.360969]
• 2: Jay Earley, An efficient context-free parsing algorithm, Communications of the ACM, v.13 n.2, p.94-102, Feb 1970 [doi>10.1145/362007.362035]
• 3: Margaret A. Ellis , Bjarne Stroustrup, The annotated C++ reference manual, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 4: M. V. Ferro and B. A. Dion. Efficient incremental parsing for context-free languages. In Proc. 1994 IEEE Intl. Conf. Comp. Lang., pages 241-252. IEEE Computer Society Press, May 1994.
• 5: Robert Giegerich. Considerate code selection. In Robert Giegerich and Susan L. Graham, editors, Code Generation --Concepts, Tools, Techniques., Workshops in Computing, pages 51-65, Berlin, May 1991. Springer-Verlag.
• 6: J. Heering, P. R. H. Hendriks, P. Klint, and J. Rekers. The syntax definition formalism SDF ~ Reference Manual, Dec. 1992.
• 7: Paul Hudak , Joseph H. Fasel, A gentle introduction to Haskell, ACM SIGPLAN Notices, v.27 n.5, p.1-52, May 1992 [doi>10.1145/130697.130698]
• 8: Fahimeh Jalili , Jean H. Gallier, Building friendly parsers, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.196-206, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582175]
• 9: Mark Johnson. The computational complexity of GLR parsing. In Masaru Tomita, editor, Generalized LR Parsing, pages 35-42. Kluwer Academic Publishers, 1991.
• 10: Neil D. Jones , C. Michael Madsen, Attribute-influenced LR parsing, Semantics-Directed Compiler Generation, Proceedings of a Workshop, p.393-407, January 14-18, 1980
• 11: Paul Klint and Eelco Visser Using filters for the disambiguation of context-free grammars. In Proc. ASMICS Workshop on Parsing Theory, Milan, Italy, 1994.
• 12: Wilf R. LaLonde, Regular right part grammars and their parsers, Communications of the ACM, v.20 n.10, p.731-741, Oct. 1977 [doi>10.1145/359842.359853]
• 13: Marc Lankhorst. An empirical comparison of generalized LR tables. In R. Heemels. A. Nijholt, and K. Sikkel, editors, Tomita's Algorithm: Extensions and Applications (TWLT1), number 91-68 of Memoranda Informatica in Twente Workshops on Language Technology, pages 87-93. Universeit Twente, 1991.
• 14: J.-M. Larchevêque, Optimal incremental parsing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.1, p.1-15, Jan. 1995 [doi>10.1145/200994.200996]
• 15: Maryellen C. MacDonald, Marcel Adam Just, and Patricia A. Carpenter. Working memory constraints on the processing of syntactic ambiguity. Cog. Psych., 24(1):56-98, 1992.
• 16: William Harry Maddox, Incremental static semantic analysis, University of California at Berkeley, Berkeley, CA, 1998
• 17: Akira Miyake, Marcel Adam Just, and Patricia A. Carpenter. Working memory constraints on the resolution of lexical ambiguity: Maintaining multiple interpretations in neutral contexts. J. Memory and Lang., 33(2):175-202, Apr. 1994.
• 18: R. Nozohoor-Farshi. GLR parsing for ~-grammars. In Masaru Tomita, editor, Generalized LR Parsing, pages 61- 75. K}uwer Academic Publishers, 1991.
• 19: Luigi Petrone, Reusing Batch Parsers as Incremental Parsers, Proceedings of the 15th Conference on Foundations of Software Technology and Theoretical Computer Science, p.111-123, December 18-20, 1995
• 20: Jan Rekers. Parser Generation for Interactive Environments. Ph.D. dissertation, University of Amsterdam, 1992.
• 21: Masataka Sassa , Harushi Ishizuka , Ikuo Nakata, Rie, a compiler generator based on a one-pass-type attribute grammar, Software—Practice & Experience, v.25 n.3, p.229-250, March 1995 [doi>10.1002/spe.4380250302]
• 22: Masaru Tomita, Efficient Parsing for Natural Language: A Fast Algorithm for Practical Systems, Kluwer Academic Publishers, Norwell, MA, 1985
• 23: Eelco Visser. A case study in optimizing parsing schemata by disambiguation filters. Technical Report P9507, Programming Research Group, University of Amsterdam, Jul. 1995.
• 24: Eelco Visser. Scannerless generalized-LR parsing, 1997. In preparation.
• 25: Tim A. Wagner , Susan L. Graham, Efficient and flexible incremental parsing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.5, p.980-1013, Sept. 1998 [doi>10.1145/293677.293678]
• 26: T. A. Wagner , S. L. Graham, Efficient self-versioning documents, Proceedings of the 42nd IEEE International Computer Conference, p.62, February 23-26, 1997
• 27: Tim A~ Wagner and Susan L. Graham. Isolating errors--a history-based approach, 1997. In preparation.
• 28: David A. Watt, Rule splitting and attribute-directed parsing, Semantics-Directed Compiler Generation, Proceedings of a Workshop, p.363-392, January 14-18, 1980

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Parsing

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Grammar types (e.g., context-free, context-sensitive)

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Design, Languages, Performance, Reliability, Theory