An introduction to the notion of a grammar

Informally, a GRAMMAR describes the hierarchical structure of programming language constructs. For instance an if-then-else statement in C has the form

if (expression) statement else statement

Using the variable expr to denote an expression and the variable stmt to denote a statement, the above rule can be reformulated as follows in order to express that an if-then-else statement is a particular statement

stmt $\longmapsto$ if (expr) stmt else stmt

Such formulation will called a PRODUCTION.

Example 1   Another example is that of arithmetic expressions over arbitrary variables (i.e. expression involving variables, the four arithmetic operations and exponentiation) which can be defined by the following productions (or grammatical rules):

expr	$\longmapsto$	expr binop expr
expr	$\longmapsto$	(expr)
expr	$\longmapsto$	-expr
expr	$\longmapsto$	id
binop	$\longmapsto$	+
binop	$\longmapsto$	-
binop	$\longmapsto$	*
binop	$\longmapsto$	/
binop	$\longmapsto$	$\uparrow$

where id stands for any variable.

Remark 1   Let I be a finite set of identifiers and let us consider the alphabet

$$\Sigma \cup \uparrow$$ (1)

Let L be the language consisting of arithmetic expressions over $\Sigma$. We shall show that L cannot be recognized by FA.

First we observe that every word w = w₁ ^... w_$\ell$ of L is a well parenthesized expression that is

$$\forall \ell \mid_{{{(}}}^{{}} \geq \mid_{{{)}}}^{{}} \mid_{{{(}}}^{{}} \mid_{{{)}}}^{{}}$$ (2)

where | u$\mid_{{x}}^{{}}$ denotes the number of occurrences of the letter x in the word u. The proof is easy by induction.

Let us assume that L can be recognized by a DFA $\cal {A}$ = ($\Sigma$, S, s₀, F,$\delta$) with N states and initial state s₀. Let us consider an arithmetic expression a starting with N opening parentheses. There exists N states s₁, s₂,..., s_N such that for every i = 1 ^... N - 1 we have

$$\delta$$ (3)

There exists at least two values i₁ and i₂ of the index i in the range 0 ^... N such that s_i1 = s_i2. Hence by adding i₂ - i₁ opening parentheses in front of a we can build another word b recognized by L. However b is clearly not a well parenthesized expression and thus it is not an arithmetic expression.

Figure 1: Well parenthesized expressions cannot be recognized by FA.

Therefore the language of arithmetic expressions over $\Sigma$ cannot be recognized by FA.

It follows from Remark 1 that finite automata cannot recognize all languages that we may encounter when building a compiler. The notion of a grammar (to be introduced later) solves this difficulty.