Grammar-based analysis of string expressions

ABSTRACT

We specify a polymorphic type system for an applied lambda calculus that refines the string type with a subtype hierarchy derived from language containment. It enables us to find a language for each string-type expression such that the value of the expression is a member of that language. Type inference for this system infers language inclusion constraints that can be viewed as a context-free grammar with a nonterminal for each string-valued expression.Then we present two algorithms that solve language inclusion constraints with respect to a fixed context-free reference grammar. The solutions are sound but incomplete because the general problem of context-free language inclusion is undecidable. Both algorithms are derived from Earley's parsing algorithm for context-free languages.Taking the two parts together enables us to answer questions like: Is the value of a string-type expression derivable from a given nonterminal in the reference grammar?

REFERENCES

• 1: Aske Simon Christensen, Anders Møller, and Michael I. Schwartzbach. Precise analysis of string expressions. In Radhia Cousot, editor, Proc. International Static Analysis Symposium, SAS'03, number 2694 in Lecture Notes in Computer Science, pages 1--18, San Diego, CA, USA, June 2003. Springer-Verlag.
• 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: Thom W. Frühwirth, Constraint Handling Rules, Selected Papers from Constraint Programming: Basics and Trends, p.90-107, May 16-20, 1994
• 4: John E. Hopcroft. On the equivalence and containment problems for context-free languages. Math. Systems Theory, 3(2):119--124, 1969.
• 5: Haruo Hosoya , Benjamin Pierce, Regular expression pattern matching for XML, Proceedings of the 28th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.67-80, January 2001, London, United Kingdom
• 6: Haruo Hosoya , Jérôme Vouillon , Benjamin C. Pierce, Regular expression types for XML, Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, p.11-22, September 2000
• 7: Mehryar Mohri and Mark-Jan Nederhof. Regular approximation of context-free grammars through transformation. In Jean-Claude Junqua and Gertjan van Noord, editors, Robustness in Language and Speech Technology, pages 153--163. Kluwer Academic Publishers, Dordrecht, 2001.
• 8: Martin Odersky , Martin Sulzmann , Martin Wehr, Type inference with constrained types, Theory and Practice of Object Systems, v.5 n.1, p.35-55, Jan. 1999 [doi>10.1002/(SICI)1096-9942(199901/03)5:1<35::AID-TAPO4>3.0.CO;2-4]
• 9: Naoshi Tabuchi, Eijiro Sumii, and Akinori Yonezawa. Regular expression types for strings in a text processing language. In Gilles Barthe and Peter Thiemann, editors, Proceedings of Workshop on Types in Programming (TIP02), volume~75 of ENTCS, pages 1--19, 2003.
• 10: Eelco Visser. Scannerless generalized-LR parsing. Technical Report P9707, Programming Research Group, University of Amsterdam, 1997.
• 11: Seth White , Cattell , Fisher , Hamilton, JDBC API Tutorial and Reference, Second Edition: Universal Data Access for the Java 2 Platform, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 12: Andrew K. Wright , Matthias Felleisen, A syntactic approach to type soundness, Information and Computation, v.115 n.1, p.38-94, Nov. 15, 1994 [doi>10.1006/inco.1994.1093]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Type structure

General Terms:
Algorithms, Languages, Theory

Keywords:
constraints, string expression analysis, type inference