Accession Number : AD0699501

Title :   PRACTICAL TRANSLATORS FOR LR(k) LANGUAGES.

Descriptive Note : Doctoral thesis,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE PROJECT MAC

Personal Author(s) : DeRemer,Franklin Lewis

Report Date : 24 OCT 1969

Pagination or Media Count : 219

Abstract : A context-free syntactical translator (CFST) is a machine which defines a translation from one context-free language to another. A transduction grammar is a formal system based on a context-free grammar and it specifies a context-free syntactical translation. A simple suffix transduction grammar based on a context-free grammar which is LR(k) specifies a translation which can be defined by a deterministic push-down automation (DPDA). A method is presented for automatically constructing CFSTs (DPDAs) from those simple suffix transduction grammars which are based on the LR(k) grammars. The method is developed by first considering grammatical analysis from the string-manipulation viewpoint, then converting the resulting string-manipulation algorithms to DPDAs, and finally considering translation from the automata-theoretic viewpoint. The results are relevant to the automatic construction of compilers from formal specifications of programming languages. If the specifications are, at least in part, based on LR(k) grammars, then corresponding compilers can be constructed which are, in part, based on CFSTs. (Author)

Descriptors :   (*PROGRAMMING LANGUAGES, COMPILERS), (*CONTEXT FREE GRAMMARS, *COMPUTATIONAL LINGUISTICS), SYNTAX, MACHINE TRANSLATION, ALGORITHMS, AUTOMATA, THESES

Subject Categories : Linguistics
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE