a result on the relationship between simple precedence languages and reducing transition languages
Two of the more recently published systems for the efficient parsing of subclasses of deterministic, context-free languages are the backwards-deterministic , (or unambiguous , as they were originally called) simple precedence languages due to Wirth and Weber, and the reducing transition languages due to Eickel, Paul, Bauer, and Samelson. The main result demonstrated in this paper is that the backwards-deterministic, simple precedence languages are a proper subclass of the reducing transition languages. The reducing transition languages are certainly a subclass of the deterministic, context-free (LR(1)) languages but it is not known if this inclusion is proper. The major complaint against the reducing transition languages is the large amount of memory required when this technique is utilized with large grammars, such as the ALGOL 60 grammar. With memory costs and physical memory sizes decreasing at a rapid rate, it is very possible that this disadvantage will not exist in the not-too-distant future. When this becomes true, the advantage of reducing transition languages, i.e., the relatively small amount of time required for their parsing, may result in their significance being substantially increased. Thus it is of some import that we study their relationship to other languages. The main result is based on two theorems: (1) if G is a backwards-deterministic simple precedence grammar, then G is a reducing transition grammar; and (2) the language L 1 &equil; {a0 n 1 n 2 m m,n ? 1} &ugr; {b0 n 1 m 2 n m,n ? 1} is a reducing transition language but is not a backwards-deterministic simple precedence language.
relationships language transit systems efficiency parsing paper inclusion memorialized grammar physical future timing context