Syntactic Analysis and Translation of Programming Languages.
Abstract
An analytic grammar is a reductive grammar which incorporates an explicit constraint rule (i.e. parsing scheme) which constrains the rewritings of strings. Each constraint rule defines a language class. It is shown that every constraint rule satisfying certain simple conditions yields precisely the class of deterministic context-sensitive languages. This class includes all known programming languages. A partitioned analytic grammar parses strings as do programs in the Production Language of Floyd. The analytic transducer performs syntax-directed translation. Any unique and linear-bounded mapping may be performed by an analytic transducer (Theorem 8). All known translations of actual programming languages are linear-bounded mappings. The compilation mapping associated with a mapping M and set of strings A, yields for each source string sigma over the vocabulary of A, a target string which is M(sigma) if sigma is in A, and otherwise is an error indication. For every linear-bounded mapping of every deterministic context-sensitive source language, there is a transducer which performs the associated compilation mapping (Theorem 9). (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 29, 1971
- Accession Number
- AD0733459
Entities
People
- Philip Gilbert
Organizations
- University of Southern California