The Relevance of Some Compiler Construction Techniques to the Description and Translation Of Languages

Steven I. LaszloCOLING 1967

TL;DR

This paper explores how techniques from compiler construction can be applied to the description and translation of programming languages, drawing parallels with linguistic theory. It argues that traditional methods like BNF are insufficient for handling complex issues like identifier identity and definition, proposing a transformational component alongside phrase-structure grammars to address these challenges.

What Problem Does This Paper Address?

Describing and translating programming languages presents significant challenges, particularly in accurately capturing the nuances of language structure and meaning. Traditional methods, such as Backus-Naur Form (BNF), while useful for defining syntax, struggle with crucial aspects like the "identity problem" (ensuring that multiple occurrences of an identifier refer to the same entity) and the "definition problem" (ensuring each identifier is defined before use). These issues are analogous to complexities found in natural language, where context and meaning are paramount. The paper aims to bridge this gap by demonstrating how compiler construction techniques, which inherently deal with these problems, can offer a more robust framework for language description and translation, aligning with linguistic theories of grammar and transformation.

Methods

The paper proposes a dual approach to language description, combining a phrase-structure component with a transformational component.

  • Phrase-Structure Component: This part of the grammar, inspired by BNF, handles the basic structure of the language, generating function definitions and program segments.
  • Transformational Component: This is the novel aspect. Transformations are introduced to address the identity and definition problems. The core idea is that when a function or identifier is defined, its form is generated. Then, "placeholders" are generated for instances of its use. Transformations are responsible for replacing these placeholders with the correct, definition-generated form. This mechanism is applied not only to functions but also to identifiers, subscript expressions, and other constructs.
  • T-rules: These are elementary transformations that can be combined to form more complex transformations, analogous to how simple operations build complex algorithms.

The paper uses the programming language P.O.L.2 as a case study, chosen for its existing adequate description and its inclusion of syntactically complex features.

Datasets

Not discussed in the paper. The paper uses examples from a hypothetical programming language (P.O.L.2) for illustration.

Key Insights and Ideas

  • Identity and Definition Problems: The paper highlights that traditional grammars like BNF fail to adequately handle the "identity problem" (tracking the same variable across its uses) and the "definition problem" (ensuring variables are defined before use). These are critical for accurate language processing.
  • Compiler Techniques as a Solution: The authors propose that compiler construction techniques, particularly those involving table-building and identity-testing, offer a practical solution to these problems.
  • Transformational Grammar Analogy: The paper draws a strong parallel between the proposed transformational component and Chomsky's transformational grammar for natural languages, suggesting a unified theoretical basis for describing both artificial and natural languages.
  • Functions and Operators as Unified Concepts: The paper posits that functions and operators are not fundamentally different but rather notational variants of the same underlying concept, which can be handled uniformly by the proposed framework.
  • Separation of Lexical Generation: The authors advocate for separating the rules that generate lexical items (words, symbols) from the phrase-structure rules, viewing lexical generation as a distinct "orthographic" class of rules.

Key Results

The paper doesn't present quantitative results in the form of performance metrics or accuracy scores. Instead, its key results are conceptual and methodological:

  • Demonstration of Inadequacy: The paper demonstrates the inadequacy of BNF and similar devices for handling identifier identity and definition problems through examples.
  • Proposed Framework: It proposes a framework combining phrase-structure and transformational components as a more adequate method for describing programming languages.
  • Illustrative Examples: The paper provides illustrative examples of how the proposed transformational rules can handle function definitions, identifier usage, and other complex language features.

Limitations and Future Work

  • Descriptive vs. Rigorous: The paper acknowledges that the presented transformations are in a descriptive rather than a rigorous form, stating that a rigorous statement of transformations as mappings of structural descriptions is available.
  • Simplification and Sophistication: The authors suggest that substantial simplification and sophistication can be achieved over the model presented.
  • Application to Formal Notation Systems: The paper indicates that the approach can be applied to other formal notation systems beyond programming languages.
  • Linguistic Standards: The effort is framed as conforming to a linguist's notion of "giving an account of the data," implying a higher standard than typically applied to programming language descriptions.

Summary updated

BibTeX
@inproceedings{laszlo1967relevance,
  author = {Steven I. Laszlo},
  title = {{The Relevance of Some Compiler Construction Techniques to the Description and Translation Of Languages}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1967},
}
Figure