Programming Languages and Systems (TOPLAS)


Search Issue
enter search term and/or author name


ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 28 Issue 4, July 2006

Right nulled GLR parsers
Elizabeth Scott, Adrian Johnstone
Pages: 577-618
DOI: 10.1145/1146809.1146810
The right nulled generalized LR parsing algorithm is a new generalization of LR parsing which provides an elegant correction to, and extension of, Tomita's GLR methods whereby we extend the notion of a reduction in a shift-reduce parser to...

A machine-checked model for a Java-like language, virtual machine, and compiler
Gerwin Klein, Tobias Nipkow
Pages: 619-695
DOI: 10.1145/1146809.1146811
We introduce Jinja, a Java-like programming language with a formal semantics designed to exhibit core features of the Java language architecture. Jinja is a compromise between the realism of the language and the tractability and clarity of its formal...

Fast partial evaluation of pattern matching in strings
Mads Sig Ager, Olivier Danvy, Henning Korsholm Rohde
Pages: 696-714
DOI: 10.1145/1146809.1146812
We show how to obtain all of Knuth, Morris, and Pratt's linear-time string matcher by specializing a quadratic-time string matcher with respect to a pattern string. Although it has been known for fifteen years how to obtain this linear matcher by...

Message analysis for concurrent programs using message passing
Richard Carlsson, Konstantinos Sagonas, Jesper Wilhelmsson
Pages: 715-746
DOI: 10.1145/1146809.1146813
We describe an analysis-driven storage allocation scheme for concurrent systems that use message passing with copying semantics. The basic principle is that in such a system, data which is not part of any message does not need to be allocated in a...

Calculational semantics: Deriving programming theories from equations by functional predicate calculus
Raymond T. Boute
Pages: 747-793
DOI: 10.1145/1146809.1146814
The objects of programming semantics, namely, programs and languages, are inherently formal, but the derivation of semantic theories is all too often informal, deprived of the benefits of formal calculation “guided by the shape of the...