On deterministic multi-pass analysis. (English) Zbl 0611.68051
Chains (or cascade composition) of push-down transducers are introduced as a model of multi-pass compilers. We focus on deterministic chains, since nondeterministic transducer chains of length two define the recursively enumerable sets. Deterministic chains recognize in linear time a superset of context-free deterministic languages. This family \({\mathcal C}{\mathcal H}\) is closed under Boolean operations, disjoint shuffle, and reverse deterministic pushdown translation, but not under homomorphism. Equivalent definitions of the family in terms of composition of syntax-directed translation schemes and control languages are considered. The family is a strict hierarchy ordered by the length of the chain. The complexity of \({\mathcal C}{\mathcal H}\) is obviously linear, but not all linear-time parsable languages are in \({\mathcal C}{\mathcal H}\). On the other hand it strictly includes the Boolean closure of deterministic languages. Finally \({\mathcal C}{\mathcal H}\) is not comparable with another classical Boolean algebra of formal languages, namely real-time languages.
MSC:
68Q45 | Formal languages and automata |
68N20 | Theory of compilers and interpreters |
68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |