I
Chapter 5
Context-Free
Languages
n the last chapter, we discovered that not all languages are regular. While
regular languages are effective in describing certain simple patterns, one
does not need to look very far for examples of nonregular languages. The
relevance of these limitations to programming languages becomes
evident if we reinterpret some of the examples. If in L = {a n b n : n ≥ 0}
we substitute a left parenthesis for a and a right parenthesis for b, then
parentheses strings such as (()) and ((())) are in L, but (() is not. The language
therefore describes a simple kind of nested structure found in programming
languages, indicating that some properties of programming languages require
something beyond regular languages. In order to cover this and other more
complicated features we must enlarge the family of languages. This leads us to
consider context-free languages and grammars.
We begin this chapter by defining context-free grammars and languages,
illustrating the definitions with some simple examples. Next, we consider the
important membership problem; in particular we ask how we can tell if a given
string is derivable from a given grammar. Explaining a sentence through its
grammatical derivation is familiar to most of us from a study of natural
languages and is called parsing. Parsing is a way of describing sentence
structure. It is important whenever we need to understand the meaning of a
sentence, as we do for instance in translating from one language to another. In
computer science, this is relevant in interpreters, compilers, and other translating
programs.
The topic of context-free languages is perhaps the most important aspect of
formal language theory as it applies to programming languages. Actual
programming languages have many features that can be described elegantly by
means of context-free languages. What formal language theory tells us about