A grammar is said to be a (uniquely invertible) operator-precedence grammar if it is an operator grammar with no two righ[ sides that have the same pattern of terminals. and the method of Exercise 4.26 yields at most one precedence relation between any pair of terminals. Which of the grammars of Exercise 4.27 are operator-precedence grammars?
Exercise 4.27 Generate operator-precedence relations for the following grammars.
a) The grammar of Exercise 4.2.
b) The grammar of Exercise 4.3.
c} The expression grammar (4. 10).
Exercise 4.2. Consider the grammar
a) Show that this grammar is ambiguous by constructing two different leftmost derivations for the sentence abab.
b) Construct the corresponding rightmost derivations for abab.
c) Construct the corresponding parse trees for obob.
*d) What ,language does this grammar generate'!
Exercise 4.3 Consider the grammar
a) Construct a parse tree for the sentence not (true or false).
b) Show that this grammar generates all boolean expressions.
*c) Is this grammar ambiguous? Why?
Exercise 4.26 There is a mechanical way to produce operator-precedence relations from an operator grammar. including those with many different nonterminals. Define leading (A) for nonterminal A to be the set of terminals a such that a is the leftmost terminal in some string derived from A. and define trailing (A) to be the set of terminals that can be the rightmost in a string derived from A. Tben for terminals a and b. we say a .,; b if there is a right side of the form au(3.b")'. where (3. is either empty or a single nonterminal, and a and 'Yare arbitrary. We say a b if there is a right side of the form «Abf3.. and lJ is in trailing (A ). •n both cases. a and 13 are arbitrary slrings, Also. $