Formal Grammar

When defining a formal grammar, we fix ourselves to a collection of symbols. These symbols are divided into two disjoint groups: the terminal symbols and the non-terminal symbols. We will always notate a non-terminal symbol by something of the form <non-term> (where we replace non-term with something more descriptive) and terminal symbols by sequence of (typically) alphanumeric symbols.

Remark. We almost never state outright what the underlying symbols of a grammar are. It should always be possible to determine what terminal and non-terminal symbols we are considering by looking at the BNF specification itself.

In the proof that the cow jumped over the moon was grammatical, we built a sequence of not-quite sentences, until the very last one which was an actual sentences. We call these not-quite sentences sentential forms.

Definition. A sentential form is a sequence of symbols (terminal or non-terminal). A sentence is a sequence of terminal symbols.

Remark. We notate a sequences of symbols by white space separation. For example,

the dog jumped

is a sentence and

the <noun> jumped

is a sentential form. But it is important to note that this is just notation. If it helps, it may be useful to imagine a list

[the; <noun>; jumped]

when thinking about what a sentential form is.

In the process of building sentential forms, we replaced non-terminal symbols with sentential forms, e.g., we replaced <noun phrase> with <article> <noun>. A grammar is determined by what replacements we are allowed to do.

Definition. A production rule is an equation of the form

<non-term> ::= SENTENTIAL-FORM

where the left-hand side of the ::= is a non-terminal symbol, and the right-hand side is a sentential form.

We read a production rule as: "the non-terminal symbol on the left-hand side can be replaced with the sentential form on the right hand side." In a sense, production rules define the non-terminal symbols, e.g., a sentence is a noun phrase followed by a verb phrase.

Definition. A Backus-Naur Form (BNF) specification is a collection of production rules, together with a designated the starting symbol.

We will always take the start symbol will be designated as the left-hand side of the first rule appearing in a specification.

Example. The following is an example of a grammar which recognizes the sentence above.

<sentence>    ::= <noun-phrase> <verb-phrase>
<verb-phrase> ::= <verb> <prep-phrase>
<verb-phrase> ::= <verb>
<prep-phrase> ::= <prep> <noun-phrase>
<noun-phrase> ::= <article> <noun>
<article>     ::= the
<noun>        ::= cow
<noun>        ::= moon
<verb>        ::= jumped
<prep>        ::= over

The nonterminal symbol <sentence> is our starting symbol because it appears as the left-hand side of the first rule.

Note that a non-terminal symbol can have multiple associated production rules. This is common enough that we have special syntax for this.

Notation. We write

<non-term> ::= SENT-FORM-1 | SENT-FORM-2 | ... | SENT-FORM-n

as shorthand for

<non-term> ::= SENT-FORM-1
<non-term> ::= SENT-FORM-2
...
<non-term> ::= SENT-FORM-n

With this shorthand, we can write the above grammar as:

<sentence>    ::= <noun-phrase> <verb-phrase>
<verb-phrase> ::= <verb> | <verb> <prep-phrase>
<prep-phrase> ::= <prep> <noun-phrase>
<noun-phrase> ::= <article> <noun>
<article>     ::= the
<noun>        ::= cow | moon
<verb>        ::= jumped
<prep>        ::= over

The last piece of the thought experiment above that we need to formalize is the proof that the given sentence was grammatical. We formalize this in the notion of a derivation.

Definition. A derivation of a sentence S in a BNF grammar is a sequence of sentential forms with the following properties:

• it beginning with the designated start symbol;
• it ends in the sentence S;
• each sentential form is a the result of replacing one of the non-terminal symbols in the preceding sentence with a sentential form according to a production rule of the grammar.

We say that a grammar recognizes a sentence S if there is a derivation of S in the grammar.

This definition restates the process from the thought experiment mathematically. That said, it deviates in one way which makes the definition easier to state: in the thought experiment, we allowed ourselves to replace multiple non-terminal symbols simultaneously. This is not allowed in the above notion of a derivation. A correct derivation would look like:

<sentence>
<noun-phrase>    <verb-phrase>
<noun-phrase>    <verb> <prep-phrase>
<noun-phrase>    <verb> <prep> <noun-phrase>
<article> <noun> <verb> <prep> <noun-phrase>
<article> <noun> <verb> <prep> <article> <noun>
the       <noun> <verb> <prep> <article> <noun>
the       cow    <verb> <prep> <article> <noun>
the       cow    jumped <prep> <article> <noun>
the       cow    jumped over   <article> <noun>
the       cow    jumped over   the       <noun>
the       cow    jumped over   the       moon

Exercise. In the above derivation, mark the nonterminal in each sentential form which was replaced in the following line.

A sentence is not guaranteed to have a unique derivation. There are two forms of derivations that will be of particular importance for us.

Definition. A leftmost derivation of a sentence is one in which the leftmost nonterminal symbol is expanded in each step. A rightmost derivation is one in which the rightmost nonterminal symbol is expanded in each step.

Note that the above derivation is neither the leftmost derivation or the rightmost derivation.

Exercise. Write leftmost and rightmost derivations for the sentence

the cow jumped over the moon

in the above grammar.

The following is a BNF specification for a fragment of a simple imperative programming language.

<program> ::= <stmts>
<stmts>   ::= <stmt> | <stmt> ; <stmts>
<stmt>    ::= <var> = <expr>
<var>     ::= a | b | c | d
<expr>    ::= <term> | <term> + <term> | <term> - <term>
<term>    ::= <var> | const

In English, we would read this specification as:

• a PROGRAM is a SEQUENCE OF STATEMENTS;
• a SEQUENCE OF STATEMENTS is either a single STATEMENT, or a single STATEMENT followed a semicolon, followed by a SEQUENCE OF STATEMENTS;
• a STATEMENT is a VARIABLE followed by an equals sign, followed by an EXPRESSION.

and so on.

This second rule highlights something interesting which we can do in BNF specifications: rules are allowed to be recursive. The production rule for <stmts> allows us to replace it with a sentential form which contains the non-terminal symbol <stmts>. This is quite powerful, particularly because it means it is possible to derive an infinite number of sentences in a given grammar.

Exercise. Determine the number of sentences that can be derived in the grammar from the previous section (i.e., the number of sentences which can be derived from the starting symbol <sentence>).

Consider the following program.

a = const ;
a = a + const ;
b = a

We can verify that this program is recognized by the above grammar by finding a (leftmost) derivation.

<program>
<stmts>
<stmt> ; <stmts>
<var> = <expr> ; <stmts>
a = <expr> ; <stmts>
a = <term> ; <stmts>
a = const ; <stmts>
a = const ; <stmt> ; <stmts>
a = const ; <var> = <expr> ; <stmts>
a = const ; a = <expr> ; <stmts>
a = const ; a = <term> + <term> ; <stmts>
a = const ; a = <var> + <term> ; <stmts>
a = const ; a = a + <term> ; <stmts>
a = const ; a = a + const ; <stmts>
a = const ; a = a + const ; <var> = <expr>
a = const ; a = a + const ; b = <expr>
a = const ; a = a + const ; b = <term>
a = const ; a = a + const ; b = <var>
a = const ; a = a + const ; b = a

Remark. As a reminder, we're not interested in white space when we consider whether or not a sentence is recognized by a grammar. The choice to present the sentences in three lines was for readability, and the choice to present it in a single line in the derivation was for convenience.

One notable feature of the last four lines of the above derivation: even if a nonterminal symbol is replaced by a single nonterminal symbol in succession, we have to include each step. We're only allowed to apply one production rule at a time, e.g., we cannot immedatiely replace <expr> with <var> because that is not one of our production rules.

Exercise. Write a rightmost derivation for the above program.

Exercise. Verify that

a = a + a ; b = b

is recognized by the above grammar.

Grammars imbue sentences with hierarchical structure. This structure is represented graphically as a parse tree. We've seen a couple examples of English grammar parse trees so far, but we can also build parse trees for sentences recognized by any grammar with a BNF specification.

Definition. A parse tree for a sentence S in a grammar is a tree T with the following properties:

• every leaf of T has a terminal symbol;
• every non-leaf node n has a nonterminal symbol (we write val(n) for the value at n);

• if a node n with has children [t1, t2, ..., tk] then

  val(n) ::= root(t1) root(t2) ... root(tk)
  

  is a production rule in the grammar (where root(t) denotes the value at the root of the tree t);

• the leaves (in order) (i.e., the frontier of T) form the sentence S.

The details of the above definition are not so important, as long as you have the right picture in your head. For example, the sentence a = b + const has the following derivation.

<program>
<stmts>
<stmt>
<var> = <expr>
a = <expr>
a = <term> + <term>
a = <var> + <term>
a = b + <term>
a = b + const

And has the following parse tree.

<program>
│
<stmts>
│
<stmt>
├─────┬───┐
<var> │   <expr>
│     │   ├──────┬─┐
│     │   <term> │ <term>
│     │   │      │ │
│     │   <var>  │ │
│     │   │      │ │
a     =   b      + const

Remark. You don't have to draw your trees in this rectilinear styling. If you're drawing one on paper, I'd recommend drawing it like any other tree you've drawn for another computer science course. I just have a predilection for ASCII art…

Exercise. Given the ADT

type 'a tree
   = Leaf of 'a
   | Node of 'a * 'a tree list

write the OCaml function frontier which, given

• t of type 'a tree

returns the list of leaves of t in order from left to right.

Every derivation can be converted into a parse tree, and vice versa, but multiple derivations may correspond to the same parse tree. This will be important when we cover ambiguity in the next section.

Exercise. Write a derivation corresponding to the above parse tree when is neither leftmost nor rightmost.

Our next task it to determine how to avoid this ambiguity, but first, why should we care? Natural language is ambiguous and we get along perfectly fine. Why should we go through this trouble to make sure grammars we design are unambiguous?

It's a fair question; the way I see it, it's something of a promise that we make to the user of a programming language that we never make unspoken assumptions about what a user meant when we read one of their programs. To be fair, we try to do this with natural language too, but in communication, if a statement is ambiguous, we can usually just ask our interlocutor what they meant. We can't do this for a program, so instead we make it impossible for a sentence to have multiple meanings.

Aside. We see a similar phenomena in legal language, which tends to be grammatically sterile, and usually no fun to read.

Associativity refers to how arguments are grouped when we are given a sequence of applications of an infix operator in the absence of parentheses, e.g.,

x + x + x + x

may be understood as any one of the following (among others):

(((x + x) + x) + x)
(x + (x + (x + x)))
((x + x) + (x + x))
(x + ((x + x) + x))

Exercise. Determine the number of ways the expression

x + x + x + x

can be parenthesized.

In the case of addition this point is somewhat moot. The order in which we group arguments does not affect the value of a sequence of additions. That is, addition is associative.

Definition. An operator \(\circ: X \to X \to X\) is associative if

\begin{align*} (a \circ b) \circ c = a \circ (b \circ c) \end{align*}

for any \(a\), \(b\), and \(c\) in \(X\).

Not all operators are associative. Take division for example. We need to decide how to implicitly parenthesize an expression like

Again, we could try to bar the ability to write an expression like this, but we might rather avoid using parentheses if possible.

Exercise. How does OCaml evaluate the expression 100 / 5 / 4? How are arguments grouped?

For binary operators, we typically choose one of the first two choices in the list of parenthesizations above.

Definition. A operation \(\circ : X \to X \to X\) is said to be left-associative if sequences of applications of the operator are understood as grouping arguments from the left, i.e.,

\begin{align*} a \circ b \circ c \circ d = (((a \circ b) \circ c) \circ d) \end{align*}

for any \(a\), \(b\), \(c\), and \(d\), in \(X\). It's said to be right-associative if arguments are grouped from the right, i.e.,

\begin{align*} a \circ b \circ c \circ d = (a \circ (b \circ (c \circ d))) \end{align*}

Remark. Another option is that a binary operator can have no associativity. It does not, for instance, make sense to apply a sequence of (=) operators in OCaml.

Bringing this back to grammatical ambiguity, giving a parenthesization of a sequence of operators means specifying a "shape" for the corresponding parse tree. For example, taking addition to be left-associative, i.e., taking x + x + x to mean ((x + x) + x), implies that, of the two parse trees for this sentence in the above image, the one on the right should be the "correct" one, not the one on the left.

Example. Another common ambiguous grammar in programming languages is the one for function types.

<fun-type> ::= <int-type> | <fun-type> -> <fun-type>
<int-type> ::= int

Exercise. Give two leftmost derivations of int -> int -> int in the above grammar.

Aside. Looking ahead a bit, we will end up building parsers using a parser generator. In this setting, specifying the associativity of an operator will be simple: there will be a command for doing so, a line we'll add to the code. But we can also deal with associativity in the grammar itself.

Function types are right associative, so we understand

int -> int -> int

to be parenthesized implicitly as

int -> (int -> int)

The problem, as it stands, is that because of the production rule

<fun-type> ::= <fun-type> -> <fun-type>

the argument type can an arbitrary complex function type. But we might recognize that, no matter how deep the nesting, the argument types have the special property in the case we assume right associativity: they're always just int. Therefore, we might consider the following updated grammar.

<fun-type> ::= <int-type> | <int-type> -> <fun-type>
<int-type> ::= int

In this grammar, no matter how many times you apply the second alternative of the first production rule, the argument type is always just the int type. So we were, in fact, able to restrict the shape of the parse tree for sentences, by breaking the symmetry the production rule. (This, of course, is more complicated once we start considering higher-order functions).

Exercise. Write the leftmost derivation of

int -> int -> int

in the above grammar, along with its parse tree.

In the examples from the previous section, there was only one operator. In the presence of multiple operators we have new issues to deal with. How should something like \(x * y + z\) be implicitly parenthesized?

This is an issue of precedence or order of operations something probably already somewhat familiar to you.

If you went through the American public school system then you probably learned the abbreviation PEMDAS ((P)arentheses, (E)xponentiation, (M)ultiplication, (D)ivision, (A)ddition, (S)ubtraction, along with an accompanying mnemonic, something like "please excuse my dear aunt sally"). Focusing on just the last four letters, this rule tells us that we should group multiplications and divisions first, and then group additions and subtractions. That is to say, multiplication and division have greater precedence than addition and subtraction.

Definition. The precedence of an operator, relative to another operator, determines which operator binds more tightly, in the presents of ambiguity.

Example. The expression \(2 * 3 + 4 * 5\) should be implicitly parenthesized as \((2 * 3) + (4 * 5)\) because multiplication binds tighter, it is considered first.

The relative precedence of a collection of operators determines the "shape" of the parse tree we get when we generate the sentence with a grammar. To say that multiplication has higher precedence is to say that when we build the parse tree for x * x + x, we want + to be the top-level operation, at the root of the tree.

Remark. One thing that was probably glossed over if/when you learned PEMDAS: what do you do with something like \(1 + 1 - 1 + 1\)? Do you group additions and then subtractions? Or vice versa? The issue here is that addition and subtraction have the same precedence. In this case, we will use the associativity of the operators to determine how to parenthesize: given a sequences of operators of the same precedence, we use their associativity to group them.

Since addition and subtraction are both left-associative, this would be parenthesized as \(((1 + 1) - 1) + 1\). Things can get truly ugly if you have two operators with the same precedence, but different associativity. We will ignore this possibility in this course, but this really matters in languages like Haskell, in which users can define their own operators, with specified precedence and associativity.

All of this is to say: in order to define an unambiguous grammar without parentheses, we need to know three things of each operator appearing in the grammar: fixity, associativity, and precedence. Fixity is determined directly by the production rules, but we will have to specify associativity and precedence explicitly.

We can, for example, present the four basic arithmetic operators along with this information. The operators are presented in order of decreasing precedence.³

In fact, just like the grammar for the OCaml is given in the OCaml Manual, so is the associativity and precedence of all its operators.

Aside. As with associativity, we will be able to specify precedence the parser generator we use. And, as with associativity, we can also deal with precedence in the grammar itself.

In the case of arithmetic expressions, we use similar observations:

• because of associativity, the right argument of multiplication or division must be a variable x;
• because of precedence, the left argument of multiplication or division must contain only multiplications and divisions;
• because of associativity, the right argument of addition or subtraction must be an expression with only multiplications and divisions.

These observations yields the following grammar. I've tried to use suggestive names to indicate how the three points above manifest.

<expr>         ::= <only-mul-div> | <expr> <add-sub> <only-mul-div>
<only-mul-div> ::= <var> | <only-mul-div> <mul-div> <var>
<add-sub>      ::= + | -
<mul-div>      ::= * | /
<var>          ::= x

Exercise. Give the leftmost derivation of

x * x + x * x

in the above grammar. Also draw its parse tree.

Proving that this grammar is unambiguous is a bit tricky (we won't do this). It suffices to say that, given we know how to parenthesize such expressions, and this grammar captures the rules we use, it would seem to be ambiguous.

We're not quite done. Without parentheses, we can't derive all expressions we might want to write down. This is important: parentheses in a programming language aren't just "there" implicitly. We have to explicitly include them in our grammar.

Given the rules we've described above, we cannot write an expression (without parentheses) which is equivalent to

(x + x) + x

To give a complete specification of the arithmetic expressions we know and love, we have to add back parentheses (this is the "P" part of PEMDAS).

But where should we put parentheses into the grammar? As we saw above, if we put them everywhere, we get unnecessarily verbose sentences. Rather, it should be the case that: it should be possible put any expression as an argument to operator if it's wrapped in parentheses. For this we will replace <var> with something can also be any expression wrapped in parentheses.

<expr>          ::= <only-mul-div> | <expr> <add-sub> <only-mul-div>
<only-mul-div>  ::= <var-or-parens> | <only-mul-div> <mul-div> <var-or-parens>
<add-sub>       ::= + | -
<mul-div>       ::= * | /
<var-or-parens> ::= x | ( <expr> )

We might worry that now, it is again possible to have an arbitrary expression as an argument to an operator, but the point is that, if we do this, it must be wrapped in parentheses, which ensures unambiguity.

> Exercise. Give a leftmost derivation of

( x + x ) * x

in the above grammar. Draw its parse tree.

Exercise. (Challenge) According to PEMDAS, we also need to handle exponentiation. Give a grammar for arithmetic expressions including parentheses and exponentiation, using the following operator information.

Operator	Fixity	Associativity
^	infix	right
*, /	infix	left
+, -	infix	left

Exercise. (Challenge) Write a grammar for Boolean expressions in Python. You can check what sorts of expressions are allowed by using the Python interpreter.

We use [ SENT-FORM ] to notate part of a production rule which is optional. We may, for instance, want to write a language which has both if-then and if-then-else expressions. Rather than using the BNF production rules

<if-expr> ::= if <expr> then <expr> | if <expr> then <expr> else <expr>

we can use the EBNF production rule

<if-expr> ::= if <expr> then <expr> [ else <expr> ]

These two rules express the same thing. In fact, all BNF production rules are also EBNF production rules, and all EBNF production rules can be rewritten as a collection of BNF production rules.

Exercise. Rewrite the following EBNF production rule as a collection of BNF production rules.

<a> ::= a [ <b> ] [ a ]

Remark. One issue with extending BNF is now we've made it harder to express grammars which include the symbols used for the EBNF extensions (e.g., [ and ]). In practice this is not a problem, we will try to be very explicit if something like [ appears as part of a symbol of the grammar, and not a part of the specification of the grammar.

We use ( SENT-FORM₁ | SENT-FORM₂ | ... | SENT-FORMₖ ) to notate the choice of multiple sentential forms as part of a production rule. In the previous section we defined a grammar for arithmetic expressions with multiple rules for the choice of operation.

<expr>          ::= <only-mul-div> | <expr> <add-sub> <only-mul-div>
<only-mul-div>  ::= <var-or-parens> | <only-mul-div> <mul-div> <var-or-parens>
<add-sub>       ::= + | -
<mul-div>       ::= * | /
<var-or-parens> ::= x | ( <expr> )

We can simplify this in EBNF by removing the production rules for operators.

<expr>          ::= <only-mul-div> | <expr> (+ | -)  <only-mul-div>
<only-mul-div>  ::= <var-or-parens> | <only-mul-div> (* | /) <var-or-parens>
<var-or-parens> ::= x | ( <expr> )

We use { SENT-FORM } to notate a part of a production rule which can be repeated as many times as we want. We can also combine this with the alternative notation to as

{ SENT-FORM₁ | SENT-FORM₂ | ... | SENT-FORMₖ }

to represent a collection of choices we may repeat as many times as we want.

In the same grammar as above, we can rewrite the recursive production rules in terms of repetition.

<expr>          ::= <only-mul-div> { (+ | -) <only-mul-div> }
<only-mul-div>  ::= <var-or-parens> { (* | /) <var-or-parens> }
<var-or-parens> ::= x | ( <expr> )

Exercise. (Challenge) Write an EBNF specification for Boolean expressions in Python.