6.1. Context-Free Grammars Part 1¶
6.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…endin 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.
