37.1. Context-Free Grammars Part 1¶

37.1.1. Context-Free Languages¶

In previous chapters, we saw that some languages are regular languages, which means that we can define a DFA, NFA that recognizes that language, or we can represent it with a regular expression or regular grammar. Here are a few examples of regular languages:

keywords in a programming language
names of identifiers
integers
a finite list of miscillaneous symbols such as \(=\).

We also know that some languages are non-regular, and we learned how to use tools like the Pumping Lemma to prove a given language is non-regular. Examples of non-regular languages include:

\(\{a^ncb^n\ |\ n > 0\}\)
mathematical expressions like \(((a + b) - c)\)
block structures for programming languages (\(\{\}\) in Java/C++ and begin … end in Pascal)
Balanced parentheses

Now we will look at a class of languages that is larger than the class of regular languages, called context-free languages or CFG. Perhaps not surprisingly, a CFL is any language that can be represented by a context-free grammar or CFG.

Settings