2.13 Chapter Summary

This chapter addresses constructs (e.g., regular expressions, grammars, automata) for defining (i.e., denoting, generating, and recognizing, respectively) languages and the capabilities (or limitations) of those constructs in relation to programming languages (Table 2.12). A regular expression denotes a set of strings—that is, the sentences of the language that the regular expression denotes. Regular expressions and regular grammars can capture the rules for a valid identifier in a programming language. More generally, regular expressions can model the lexics (i.e., lexical structure) of a programming language. Context-free grammars can capture the concept of balanced entities nested arbitrarily deep (e.g., parentheses, brackets, curly braces) whose use is pervasive in the syntactic structures (e.g., mathematical expression, if–else blocks) of programming languages. More generally, context-free grammars can model the syntax (i.e., syntactic structure) of a programming language. (Formally, context-free grammars are expressive enough to define formal languages that require an unbounded amount of memory used in a restricted way [i.e., LIFO] to recognize sentences in those languages.) If a sentence from a language has more than one parse tree, then the grammar for the language is ambiguous. Neither regular grammars nor context-free grammars can capture the rule that a variable must be declared before it is used. However, we can model some semantic properties, including operator precedence and associativity, with a context-free grammar. Thus, not all formal grammars have the same expressive power; likewise, not all automata have the same power to decide if a string is a sentence in a language. (The corollary is that there are limits to computation.) While most programming languages are context-sensitive (because variables often must be declared before they are used), context-free grammars are the theoretical basis for the syntax of programming languages (in both language definition and implementation, as we see in Chapters 3 and 4).

Table 2.12 Formal Grammar Capabilities Vis-à-Vis Programming Language Constructs (Key: PL = programming language.)

Table 2.13 summarizes each of the progressive four types of formal grammars in the Chomsky Hierarchy; the class of formal language each grammar generates; the type of automaton that recognizes each member of each class of those formal languages; and the constraints on the production rules of the grammars. Regular and context-free grammars are fundamental topics in the study of the formal languages. In our course of study, they are useful for both describing the syntax of and parsing programming languages. In particular, regular and context-free grammars are essential ingredients in scanners and parsers, respectively, which are discussed in Chapter 3.

Table 2.13 Summary of Formal Languages and Grammars, and Models of Computation