Syntax Programming

Stefan FeyockAAAI 1984

Abstract

Syntax Programming (SP) is a paradigm that treats language parsing as a general-purpose programming method. By establishing a formal parallel between context-free grammars (BNF) and logic programming (Horn clauses), SP leverages LR parser generators to build efficient, portable, and introspective expert systems. This paper explores the technical foundations of SP, its implementation via the MYSTRO system, and its application in real-world domains like NASA's optimizer expert systems.

Introduction

In the field of artificial intelligence, the representation of knowledge and the mechanism for reasoning are central concerns. Traditionally, expert systems have relied on specialized environments or logic programming languages like Prolog. While powerful, these approaches often face challenges regarding performance overhead and portability. This paper, originally presented at AAAI-84, introduces Syntax Programming (SP), a method that repurposes the mature technology of compiler construction—specifically LR parser generators—to create a new class of expert systems.

The Problem: Performance and Readability

During the early 1980s, building expert systems typically required specialized environments or logic programming (LP) languages. While LP was powerful, it often suffered from significant performance costs due to automatic backtracking. Furthermore, traditional "top-down" parsing techniques required developers to "mangle" their grammars (e.g., removing left recursion) to make them parsable. This transformation often rendered the rules unreadable to humans, which is a critical failure for expert systems that must explain their reasoning to users. SP seeks a middle ground: a framework as structured as logic programming but as efficient and readable as a standard compiler.

The Syntax Programming Paradigm

The core of SP is the use of bottom-up (LR/LALR) parser generators, exemplified by the MYSTRO system. The paradigm is built on several key technical innovations that bridge the gap between formal linguistics and expert system logic.

BNF as Logic

The most significant insight of SP is the grammar-logic duality. BNF productions are structurally almost identical to Horn clauses in logic programming. Consequently, a parser is, in effect, a logic engine. Just as a logic program searches for a proof, an SP program searches for a valid parse.

Technical Components

  • Pseudoterminals: Special symbols (e.g., <?ask,problem,is,gradient>) are introduced that the scanner treats as procedure calls. Instead of reading a static token from a file, the parser can query a user or database dynamically to determine if a "symbol" is present in the current environment.
  • Affix Grammars: To handle data flow, SP adopts Affix Grammars. This allows "arguments" or attributes to be passed up and down the parse tree, providing a disciplined way to propagate information similar to variable unification in Prolog.
  • Disambiguating Predicates: These act as metarules to resolve conflicts in the parser. When the parser encounters multiple possible rules, it evaluates a predicate to decide the correct path based on the current state.
The MYSTRO system architecture for generating parsers from grammars and skeletons.

System Architecture and Implementation

As illustrated in the system architecture above, the MYSTRO parser generator processes an input grammar and a parser skeleton to produce parse tables. These tables are then utilized by a parser engine to facilitate user interaction.

One of the most significant advantages of this table-driven approach is "introspection." Because the LR parser always knows its current state and the set of valid next inputs, implementing an "Explain" feature is trivial. The system can simply present the current parse tree or the expected next steps to the user, providing a transparent reasoning chain. Furthermore, the author argues that LR parsing is superior to LL (top-down) parsing for AI because it accepts a much wider, more "natural" range of grammars without requiring the obfuscating transformations that hinder human readability.

Key Results and Applications

The SP approach has demonstrated remarkable efficiency and portability. The core parser engine is extremely compact, requiring fewer than 800 lines of Pascal or 400 lines of LISP. Because the logic resides in the generated tables, systems can be ported across different programming languages without rewriting the underlying logic.

The paradigm has been validated through several implementations:

  • ADS-1 Optimizer Expert System: A consultation tool designed to help users navigate a large package of FORTRAN optimization programs, intended for distribution to NASA users.
  • Robot Controller: A system managing a robot arm through high-level commands like puton(object, support).
  • Tower of Hanoi: A classic algorithmic problem implemented via SP to demonstrate its general-purpose programming capabilities.
  • In-flight Pilot Aid: A NASA-funded project for diagnosing aircraft malfunctions in real-time.

Conclusion

Syntax Programming offers a robust alternative to traditional logic programming for expert system development. By leveraging the efficiency of LR parsing and the readability of BNF, SP provides a high-performance, portable, and transparent framework for complex decision-making tasks. While it lacks the automatic backtracking of Prolog, its deterministic nature and "introspection" capabilities make it a powerful tool for production-oriented AI applications. Future work aims to synthesize the strengths of SP with the automatic backtracking and unification features of logic programming.

Summary updated

BibTeX
@inproceedings{feyock1984syntax,
  author = {Stefan Feyock},
  title = {{Syntax Programming}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1984},
}
Figure