Book contents
- Frontmatter
- Contents
- Preface
- Introduction
- I Basic Principles
- II Applications
- 5 Formal Terms, Pattern Matching, Unification
- 6 Balanced Trees
- 7 Graphs and Problem Solving
- 8 Syntactic Analysis
- 9 Geometry and Drawings
- 10 Exact Arithmetic
- III Implementation
- Quick Reference to the Syntax of Caml Light
- How to Get Caml, MLgraph, and the Examples
- References
- Index
- Index of Types and Functions
8 - Syntactic Analysis
Published online by Cambridge University Press: 05 June 2012
- Frontmatter
- Contents
- Preface
- Introduction
- I Basic Principles
- II Applications
- 5 Formal Terms, Pattern Matching, Unification
- 6 Balanced Trees
- 7 Graphs and Problem Solving
- 8 Syntactic Analysis
- 9 Geometry and Drawings
- 10 Exact Arithmetic
- III Implementation
- Quick Reference to the Syntax of Caml Light
- How to Get Caml, MLgraph, and the Examples
- References
- Index
- Index of Types and Functions
Summary
Most programs, especially those that expect a character string as input, begin by recognizing such strings in order to determine whether or not one happens to represent valid input. Next—in fact, at the same time—such a program transforms the string into internal data that is easier to handle. The preceding chapters assumed the existence of such features and functions. This chapter indicates how to program them.
A command to an operating system (such as Is on Unix, etc.) is a very simple example of a program that takes character strings as input and then decides to accept or reject them. A compiler is a more complicated program to take character strings as input; it accepts the concrete syntax of the program to compile. A compiler decides to accept or reject the program to compile; if it accepts, it transforms the program into more easily managed data, such as abstract syntax trees.
In each of these cases, we say that the command shell or the compiler accepts phrases belonging to a certain language; in the case of the command shell, we mean the options and arguments valid for a given command; for the compiler, the programming language to compile. In both cases, they reject any other phrases. In this chapter, we will call a language the set (possibly infinite) of acceptable character strings, and the chief problem that we take up is that of recognizing the phrases belonging to a given language.
- Type
- Chapter
- Information
- The Functional Approach to Programming , pp. 231 - 280Publisher: Cambridge University PressPrint publication year: 1998