ON DETERMINISTIC MULTIPASS ANALYSIS

被引：9

作者：

CITRINI, C ^{[1
]}

CRESPIREGHIZZI, S ^{[1
]}

MANDRIOLI, D ^{[1
]}

机构：

[1] POLITECN MILAN,DIPARTIMENTO ELETTR,I-20133 MILAN,ITALY

来源：

SIAM JOURNAL ON COMPUTING | 1986年 / 15卷 / 03期

关键词：

COMPUTER OPERATING SYSTEMS - Program Compilers;

D O I：

10.1137/0215049

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Chains (or cascade composition) of push-down transducers are introduced as a model of multi-pass compilers, focusing on deterministic chains. Deterministic chains recognize in linear time a superset of contex-free deterministic languages. This family CH 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 CH is obviously linear, but not all linear-time parsable languages are in the CH. On the other hand it strictly includes the Boolean closure of deterministic languages. Finally, CH is not comparable with another classical Boolean algebra of formal languages, namely, real-time languages.

引用

页码：668 / 693

页数：26

共 20 条

[1] Aho A.V., 1972, THEORY PARSING TRANS, V1
[2] Aho A. V., 1973, THEORY PARSING TRANS, VII
[3] CITRINI C, 1983, 8313 POL MIL DEP EL
[4] ENGELFRIET J, 1982, MATH SYST THEORY, V15, P95
[5] Ginsburg S., 1968, Mathematical Systems Theory, V2, P159, DOI 10.1007/BF01692513
[6] GINSBURG S, 1966, INFORMATION CONTROL, V9, P602
[7] Ginsburg S, 1975, ALGEBRAIC AUTOMATA T
[8] Harrison M., 1978, INTRO FORMAL LANGUAG
[9] Hartmanis J., 1966, ALGEBRAIC STRUCTURE
[10] Hopcroft J.E., 1969, FORMAL LANGUAGES THE

← 1 2 →