PRACTICAL TRANSLATORS FOR LR(k) LANGUAGES.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 24, 1969
- Accession Number
- AD0699501
Entities
People
- Franklin Lewis Deremer
Organizations
- Massachusetts Institute of Technology