6.2.1. Ambiguity¶

Settings

Saving...
Server Error
Resubmit

6.2.2. Precedence Practice¶

6.2.3. Unambiguous grammar parse tree Example¶

Settings

Saving...
Server Error
Resubmit

6.2.4. Why Context Free?¶

We have been throwing around the term “context free” to describe certain languages and their associated grammars. We have a definitions: A context-free language is one with a context-free grammar, and a context-free grammar is any grammar whose production rules all have a single variable on the left-hand side. Finally, we know that the class of context free languages is a superset of the class of regular languages.

But why the name “context free”? This comes from the idea that, in a sentential form for a partial derivation for a string, we are free to replace any variable with one of its production rule right-hand sides, without concern for what else appears in that sentential form. For example, consider a grammar that has these rules:

S \(\rightarrow\) ABC \(|\) GBH

B \(\rightarrow\) E \(+\) E

The point is that regardless of which production rule we use on S to start, we are then free to expand B in the next step, regardless of whether it is surrounded by variables A and C, or by variables G and H.

In contrast, there are also context-sensitive grammars. These are grammars that can have multiple variables on the left hand side of a production. For example, consider this partial grammar:

S \(\rightarrow\) ABC \(|\) GBH

AB \(\rightarrow\) AE \(+\) E

GB \(\rightarrow\) AE \(-\) E

In this case, we have to see A and B appear together in the sentential form in order to fire the production rule that yields E \(+\) E, or G and B appear together to fire the production rule that yields E \(-\) E.

We will see later that context-sensitive grammars are more powerful than CFGs. Which of course means that there are languages that are not context free, but which are context sensitive.