Parsing Theory

In this chapter we shall review the mathematical and computer science background on which the presentation in this book is based. We shall discuss the elements of discrete mathematics and formal language theory, emphasizing those issues that are of importance from the point of view of context-free parsing. We shall devote a considerable part of this chapter to matters such as random access machines and computational complexity. These will be relevant later when we derive efficient algorithms for parsing theoretic problems or prove lower bounds for the complexity of these problems. In this chapter we shall also discuss a general class of formal language descriptors called “rewriting systems” or “semi-Thue systems”. Later in the book we shall consider various language descriptors and language recognizers as special cases of a general rewriting system. As this approach is somewhat unconventional, we advise even the experienced reader to go through the definitions given in this chapter if he or she wishes to appreciate fully the presentation in this book.

In this chapter we shall develop some basic algorithms for directed graphs and relations which will be of use in later chapters, where the efficient construction of parsers is considered. The constructions needed can be expressed as the computing of certain “relational expressions”. These are expressions whose operands are relations and whose operators are chosen from among multiplication, closure, union and inverse. For this purpose we need to develop an algorithm for computing the closure of a relation. In view of the nature of our applications, the most appropriate way to do this is by a depth-first traversal of the graph that corresponds to the given relation. Other ways of computing the closure of a relation are considered in the exercises.

In this chapter we shall consider a subfamily of the family of context-free languages known as the regular languages. The family of regular languages over an alphabet V is the smallest family of languages over V that contains all finite languages over V and is closed under the operations closure, concatenation and finite union. We shall consider three equivalent ways of describing regular languages, namely regular expressions, finite automata and regular grammars. These are “equivalent” in the sense that each defines precisely the same family of regular languages. Moreover, there exist algorithms for transforming any regular expression, finite automaton or regular grammar into an equivalent language description belonging to either of the other two classes.

In this chapter we shall define a class of rewriting systems called context-free grammars. The left-hand side of a rule in a context-free grammar consists of a single symbol, so that symbols are rewritten “context-freely”. Context-free grammars are of central importance to us because they define the class of context-free languages, the parsing of which is the subject of this book. In this chapter we shall consider some structural properties of context-free grammars which are of importance in parsing. Also, a basic method for recognizing context-free languages will be given.

In this chapter we shall introduce the central concept of this monograph, namely the parsing of context-free languages. The theory of parsing plays an important role in the design of compilers for programming languages. Every compiler includes a module called the parser, which has a twofold task in the compilation process. First, the parser checks that the program text to be compiled is syntactically correct, i.e., derivable by the context-free grammar of the programming language. In doing this the parser acts as a language recognizer. Secondly, if the program text proves to be syntactically correct, the parser goes on to produce some intermediate representation of the text for use as input to the module responsible for object code generation. In doing this the parser acts as a text transformer.