We recall the notion of regular closure of classes of languages. We present two important results. The first result is that all languages which are in the regular closure of the class of deterministic (context-free) languages can be recognized in linear time. This is a nontrivial result, since this closure contains many inherently ambiguous languages. The second result is that the class of deterministic languages is contained in the closure of the class of deterministic languages with the prefix property or, stated in an equivalent way, all LR(k) languages are in the regular closure of the class of LR(0) languages.

A previous article presented a technique to compute the least-cost error repair by incrementally generating configurations that result from inserting and deleting tokens a syntactically incorrect input. An additional mechanism to improve the run-time efficiency of this algorithm by pruning some of the configurations was discussed as well. In this communication we show that the pruning mechanism may lead to suboptimal repairs or may block all repairs. Certain grammatical errors in a common construct of the Java programming language also lead to the above kind of failure.

We present a linear-time algorithm to decide for any fixed deterministic context-free language L and input string w whether w is a suffix of some string in L . In contrast to a previously published technique, the decision procedure may be extended to produce syntactic structures (parses) without an increase in time complexity. We also show how this algorithm may be applied to pocess incorrect input in linear time.

In the full paper in the companion volume, we introduce a new subclass of the context free languages, the meta-deterministic languages, which includes the deterministic languages, but also the languages that result if deterministic languages are combined via regular expressions.

Abstract Several alternative ways of defining the syntax of expressions in Pascal are compared. Based on experimental observations, measures of syntactic efficiency are calculated for each variant of the syntax. An optimal variant is determined for each such measure.

The relative parsing time of grammars belonging to a common family is investigated