CSE461: Programming Languages ConceptsHomework 1: Solution
(5 points) We have the following grammar with the start symbol <e: <e - <d | <e * <e | <e / <e
<d - 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Show a leftmost derivation for the expression “2 * 3 * 6”. Show a rightmost derivation for the above expression. Show two different parse trees for the above expression. The grammar is ambiguous. Show a new grammar that removesthe ambiguity and makes “*” and “/” left-associative. Show the parse tree for “2 * 3 / 6” in your new grammar. Argue why this is the only parse tree in the new grammar. Show a new grammar that removes the ambiguity and makes “*”and “/” right-associative. Show the parse tree for “2 * 3 / 6” in the new grammar. (3 points) Consider the language consisting of strings that represent the list of numbers separated by commas. For instance, the string “10,7” and “1, 7, 5, 13” are in the language; also included in the language are lists of a single number (e.g., “12”). Write an unambiguous BNF grammar for the language. Briefly explain why your grammar is unambiguous. (3 points). The following grammar for arithmetic expressions allow addition, subtraction, as well as a unary operator “~” for negation; that is, “~8” is interpreted as number negative eight. 1
<e - <d | <e + <e | <e - <e | ~<e
<d - 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
The grammar is clearly ambiguous. Change the grammar so that “+” and “-” are left-associative and the precedence of “~” is higher than “+” and “-”.
(4 points) A simplified email address has (i) an account name starting with a letter and continuing with any number of letters or digits; (ii) an @ character; (iii) a host with two or more sequences of letters or digits separated by periods; the last sequence must be a toplevel domain— either ’edu’, ’org’, or ’com’. Define a context-free grammar to model this language. (4 points) The following grammar discussed in class is for constructing numbers: <n - <d | <n <d
<d - 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Numbers with leading zeros such as 007 belong to the above grammar. Change the grammar so that numbers with leading zeros cannot be derived from the new grammar; however, number 0 itself should still be allowed. As a sanity check, make sure numbers such as 70 and 107 belong to your grammar, while numbers such as 070 do not.
(3 points) The following E-BNF grammar is used to specify decimal numbers such as 7.9 and -10.78. Translate it into an equivalent BNF grammar. <expr - [-] <int [.<int]
