Grammar

To specify the syntax of a language, we define a grammar:

• an alphabet, $V=V_T\cup V_{NT}$ (terminals and non-terminals)
• rules
• initial symbol

Link to original

A context-free grammar (CFG) is a formal grammar whose rules can be applied to a non-terminal symbol regardless of context.

Example: a grammar for palindromes over the alphabet $\{a,b\}$

$$\begin{array}{rl}\text{S}& ::=a\cdot \text{S}\cdot a\\ \text{S}& ::=b\cdot \text{S}\cdot b\\ \text{S}& ::=a\\ \text{S}& ::=b\\ \text{S}& ::=ϵ\\ & \\ \text{alternative syntax:}& \\ \text{S}& ::=a\cdot \text{S}\cdot a|b\cdot \text{S}\cdot b|a|b|ϵ\end{array}$$

Example derivation: $\text{S}\to a\text{S}a\to ab\text{S}ba\to aba\text{S}aba\to abaaba$

Example: an (ambiguous) grammar for arithmetic expressions

$$\begin{array}{rl}\text{E}::& =0|1|2|\dots |9\\ & |\text{E}\cdot +\cdot \text{E}\\ & |\text{E}\cdot -\cdot \text{E}\\ & |\text{E}\cdot \ast \cdot \text{E}\\ & |(\cdot \text{E}\cdot )\end{array}$$

Example: another ambiguous grammar with a 'dangling' else

$$\begin{array}{rl}E& \to \text{if }E\text{ then }E\\ & |\text{if }E\text{ then }E\text{ else }E\\ & |\dots \end{array}$$

The compiler will get confused trying to parse if a then if x then y else c.

A CFG Derivation

1. Begin with a string containing only the start symbol $\text{S}$
2. Replace any non-terminal $X$ in the string by the right-hand side of some production $X::=\text{rhs}$
3. Repeat $2$ until there are no non-terminals left: $$\text{S}\to \dots \to \dots \to \dots \to \dots$$

A CFG is left-recursive if it has a non-terminal $E$ such that $E{\to }^{+}E\cdot \dots$

Parse Trees

For a given grammar:

We can actual create a tree which represents the parsing of, for example, $1+2\ast 3+4$:

graph TB;
	1[E]-->2[T];
	1-->3[+];
	1-->4[E];
	
	2-->5[F];
	5-->6[1];
	
	4-->7[T];
	4-->8[+];
	4-->9[E];
	
	7-->10[F];
	7-->11[*];
	7-->12[T];
	
	10-->13[2];
	12-->14[F];
	14-->15[3];
	
	9-->16[T];
	16-->17[F];
	17-->18[4];

CYK Parsing Algorithm

Example

We use this triangle and move upwards, merging items below and to the right.

It is the fastest possible algorithm for recognition problem, the runtime is $O(n^3)$. However, grammars must be transformed into CNF.

Chomsky Normal Form

In the Chomsky Normal Form, we:

• remove any $ϵ$

  $\{a,b\}$), $\text{S}::=a\cdot \text{S}\cdot a|b\cdot \text{S}\cdot b|a|b|ϵ$, we find: $\text{S}::=a\cdot \text{S}\cdot a|b\cdot \text{S}\cdot b|a\cdot a|b\cdot b|a|b$

  Given the grammar for palindromes (over

Context Sensitive Grammars

A context-sensitive grammar (CSG) is a formal grammar in which the left-hand and right-hand sides of rules may be surrounded by a context of terminal and non-terminal symbols.

It is much harder to find out whether a string is parsed by a CSG.

$$\begin{array}{rl}\text{S}& ::=b\text{SSA}|ϵ\\ \text{A}& ::=a\\ b\text{A}& ::=\text{A}b\\ & \\ \text{S}& \to \dots {\to }^{?}ababaa\end{array}$$