Parsing as abstract interpretation of grammar semantics. (English) Zbl 1019.68048
Summary: Earley’s parsing algorithm is shown to be an abstract interpretation of a refinement of the derivation semantics of context-free grammars.
References:
| [1] | Aczel, P., An introduction to inductive definitions, (Barwise, J., Studies in Logic and the Foundations of Mathematics. Studies in Logic and the Foundations of Mathematics, Handbook of Mathematical Logic, Vol. 90 (1977), Elsevier: Elsevier Amsterdam), 739-782 |
| [2] | P. Cousot, Types as abstract interpretations, invited paper, in: Conference Record of the 24th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, ACM Press, New York, 1997, pp. 316-331.; P. Cousot, Types as abstract interpretations, invited paper, in: Conference Record of the 24th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, ACM Press, New York, 1997, pp. 316-331. |
| [3] | Cousot, P.; Cousot, R., Abstract interpretation of algebraic polynomial systems, (Johnson, M., Proc. 6th Internat. Conf. on Algebraic Methodology and Software Technology, AMAST ’97, Sydney, Australia. Proc. 6th Internat. Conf. on Algebraic Methodology and Software Technology, AMAST ’97, Sydney, Australia, Lecture Notes in Computer Science, Vol. 1349 (1997), Springer: Springer Berlin), 138-154 · Zbl 0788.68094 |
| [4] | P. Cousot, R. Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, in: Conference Record of the Fourth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, ACM Press, New York, 1977, pp. 238-252.; P. Cousot, R. Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, in: Conference Record of the Fourth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, ACM Press, New York, 1977, pp. 238-252. |
| [5] | Cousot, P.; Cousot, R., Constructive versions of Tarski’s fixed point theorems, Pacific J. Math., 82, 1, 43-57 (1979) · Zbl 0413.06004 |
| [6] | P. Cousot, R. Cousot, Systematic design of program analysis frameworks, in: Conf. Record of the Sixth Annual ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, ACM Press, New York, 1979, pp. 269-282.; P. Cousot, R. Cousot, Systematic design of program analysis frameworks, in: Conf. Record of the Sixth Annual ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, ACM Press, New York, 1979, pp. 269-282. · Zbl 1323.68356 |
| [7] | Cousot, P.; Cousot, R., Compositional and inductive semantic definitions in fixpoint, equational, constraint, closure-condition, rule-based and game-theoretic form, invited paper, (Wolper, P., Proc. 7th Internat. Conf. on Computer Aided Verification, CAV ’95, Liège, Belgium. Proc. 7th Internat. Conf. on Computer Aided Verification, CAV ’95, Liège, Belgium, Lecture Notes in Computer Science, Vol. 939 (1995), Springer: Springer Berlin), 293-308 |
| [8] | P. Cousot, R. Cousot, Temporal abstract interpretation, in: Conference Record of the 27th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, ACM Press, New York, 2000, pp. 12-25.; P. Cousot, R. Cousot, Temporal abstract interpretation, in: Conference Record of the 27th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, ACM Press, New York, 2000, pp. 12-25. · Zbl 1323.68367 |
| [9] | Earley, J., An efficient context-free parsing algorithm, Communications of the Association for Computing Machinary, 13, 2, 94-102 (1970) · Zbl 0185.43401 |
| [10] | Knuth, D. E., On the translation of languages from left to right, Information and Control, 8, 607-639 (1965) · Zbl 0231.68027 |
| [11] | K. Sikkel, A. Nijholt, Parsing of context-free languages, in: G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, Vol. 2, Linear Modeling: Background and Application, Springer, Berlin, 1997, pp. 61-100.; K. Sikkel, A. Nijholt, Parsing of context-free languages, in: G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, Vol. 2, Linear Modeling: Background and Application, Springer, Berlin, 1997, pp. 61-100. |
| [12] | Sudkamp, T. A., Languages and Machines: An Introduction to the Theory of Computer Science (November 1996), Addison-Wesley Pub. Co.: Addison-Wesley Pub. Co. Reading, MA |
| [13] | Tarski, A., A lattice theoretical fixpoint theorem and its applications, Pacific J. Math., 5, 285-310 (1955) · Zbl 0064.26004 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
