Context-Free Grammars and Parsing

Subjects: Compilers
Links: Strings and Grammars

Def: Let $G=(V_N,V_T,S,\mathrm{\Phi })$ be a grammar, and let $\sigma ={\varphi }_1\beta {\varphi }_2$ be a sentential form. Then $\beta$ is called a phrase of the sentential form $\sigma$ for some nonterminal $A$ if $$S\stackrel{*}{\Rightarrow} \phi_1 A \phi_2 \qquad \text{and}\qquad A \stackrel{+}{\Rightarrow}\beta.$$Furthermore, $\beta$ is called a simple phrase if $S\stackrel{\ast }{\Rightarrow }{\varphi }_{1}A{\varphi }_2$ and $A\Rightarrow \beta$.

Def: The handle of the sentential form is the leftmost simple phrase.

Def: A sentence generated by a grammar is ambiguous if there exisrt more than one syntax tree for it. A grammar is ambiguous if it generates at least one ambiguous sentence; otherwise it is unambiguous. There are certain languages, however, for which no ambiguous grammars can be found. Such languages are said to be inherentle ambiguous.

In addition to the relation $\Rightarrow$, which was defined in the connection with a grammar, we can also define the following leftmost canonical direct derivation: $$\phi_1 A \phi_2 \underset{L}{\Rightarrow} \phi_1 \beta \phi_2$$if $A\to \beta$ is a rule of the grammar and ${\varphi }_1\in V_T^{\ast }$