Enforcing Order of Operations¶
1. Evaluation of Expressions¶
In this section, we will learn about:
Operator precedence
Operator associativity
EBNF extensions and their advantages
In the previous section, we saw that ambiguous grammars are to be avoided because the parse trees they allow lead to confusion when we attach semantics (i.e., meaning) to the structure of the parse tree. The tree cannot be relied upon to specify the order of operations.
Although First Sample Grammar does not suffer from ambiguity, it has another problem. In particular, if you return to the parse tree slide show that accompanied First Sample Grammar, you will note that in parsing \(A+B*C\), the \(+\) operation was at a deeper level in the tree than \(*\), thereby indicating that \(A+B\) would be evaluated first and then multiplied by \(C\). However, this order of operations does not coincide with the operator precedence rules in almost every programming language. So First Sample Grammar, although unambiguous, is not the algebraic expression grammar that we need. Instead consider the following grammar.
1.1. Third Sample Grammar¶
Note how the parse tree in the slide show below, produced using Third Sample Grammar, is different from the one produced by First Sample Grammar.
In particular, with Third Sample Grammar, the sub-tree corresponding to the multiplication operator appears at a deeper level in the parse tree than the sub-tree for addition, thereby corresponding to normal operator precedence in programming languages.
The slide show below is a “producer” for Third Sample Gramar that you can control by entering the expression for which you want a parse tree produced. You should experiment with producing a variety of slide shows until you feel confident that you could manually construct the parse tree corresponding to any possible expression.
Once you feel confident working with parse trees, here are two questions to consider before you start on the review problems for this section.
Question 1: If you are designing a grammar corresponding to expressions, what is the strategy you would employ for introducing a different level of operator precedence, one that is either higher or lower than that of other operators? How would this strategy play out with respect to Third Sample Grammar if you wanted to add an operator corresponding to exponentiation?
Question 2: In Third Sample Grammar, operators at the same level of precedence associate in left-to-right order, that is, \(A+B-C\) evaluates as the parenthesized expression \(((A+B)-C)\). What about the grammar dictates this left-to-right associativity? How would you change the productions to achieve right-to-left associativity, that is, \((A+(B-C))\)?
The problem set for this section contains five review problems, the first four of which concern themselves with how a grammar dictates operator precedence and associativity. Do not start these problems until you have thought through answers to the two questions posed above.
2. Expression Evaluation¶
This first problem illustrates how grammatical structure influences the evaluation of arithmetic expressions, and thus the semantics of programs. Note that, to get credit for the first problem, you must solve it correctly three times in a row because the question is randomized. After you get the question right one time, the Check Answer button will then allow you to proceed to the next instance of the question.
3. Associativity¶
This problem demonstrates how grammatical structure impacts the associativity property of arithmetic operators.
4. Precedence and Associativity¶
This problem illustrates how grammatical structure impacts the associativity property and order of precedence of arithmetic operators.
5. Characterizing a Language Given a BNF Grammar¶
This problem asks you to provide a characterization in English of the language generated by a BNF grammar. After you finish it, there is one more problem about Extended Backus-Naur Form, which is described before the problem.
6. Extended BNF¶
Recall that the symbols we have used in our representation of grammars collectively comprise what is known as Backus-Naur Form (BNF). In Extended Backus-Naur Form (EBNF) we add five meta-symbols to those already used in BNF notation:
Kleene closure operator \(*\), which means “zero or more”. Hence if \(<fn\_name>\) were a non-terminal representing a valid function name and \(<argument>\) were a non-terminal representing a valid argument, then the EBNF notation for function calls with zero or more arguments (with no commas between them) would be
\[<fn\_name>\ "("\ <argument>*\ ")"\]Positive closure operator \(+\). The EBNF notation for function calls that must have at least one argument would be
\[<fn\_name>\ "("\ <argument>+\ ")"\]The two paired parenthesis symbols \(( \; )\), which are used for grouping. For example, if \(<positive\_number>\) were the non-terminal denoting a valid positive number, then the following EBNF would dictate that we must have a plus or minus sign preceding a number
\[(+ | -) <positive\_number>\]
The “optional operator” \(?\), which specifies that you can have zero or one of whatever grammatical structure precedes the operator. For example, if our language allowed an optional plus or minus sign in front of a number, we would use the EBNF
\[(+ | -)? <positive\_number>\]
EBNF is used to reduce the number of productions a grammar needs to specify a language. However, it does not increase the expressive power of grammars, that is, any grammatical structure that can be expressed in EBNF can also be expressed in BNF if one is willing to use more productions.
This last problem is about the equivalence between a given BNF grammar (the same one as in the previous problem) and a smaller EBNF grammar.
