Accession Number : AD0733459

Title :   Syntactic Analysis and Translation of Programming Languages.

Descriptive Note : Technical rept.,

Corporate Author : UNIVERSITY OF SOUTHERN CALIFORNIA LOS ANGELES DEPT OF ELECTRICAL ENGINEERING

Personal Author(s) : Gilbert,Philip

Report Date : 29 NOV 1971

Pagination or Media Count : 38

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)

Descriptors :   (*PROGRAMMING LANGUAGES, *SYNTAX), CONTEXT SENSITIVE GRAMMARS, COMPILERS, SET THEORY, MAPPING(TRANSFORMATIONS), PHRASE STRUCTURE GRAMMARS, THEOREMS

Subject Categories : Linguistics
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE