Chapter 11

Identify the tokens in each of the following statements. (You do not need to classify them; just identify them.) a. if \((a==b 1) a=x+y ;\) b. delta \(=\) epsilon \(+1.23-\) sqrt( zz); c. \(\operatorname{print}(\mathrm{Q})\);

Assume that we are working in a programming language that allows underscores \(U\) in variable names. When a scanner sees a character string such as \(A B_{-} C D\), is it more likely to classify this string as the single five-character token AB_CD or as three separate tokens: \(A B, \ldots\), CD? Explain your answer.

In some programming languages, a comment can be enclosed either in braces \\{\\} or in the symbols \((* *)\). How do you think a scanner would group the four symbols \(\\{,\\},\left(^{*}, *^{*}\right\), for purposes of classification? That is, would each symbol be given its own classification number or would some share classifications?

a. Write a BNF grammar that describes the structure of a nonterminal called \(\langle\) number \(\rangle\). Assume that contains an optional + sign followed by exactly two decimal digits, the first of which cannot be a 0 . Thus \(23,+91\), and \(+40\) are legal, but \(9,+01\), and 123 are not. b. Using your grammar from Exercise \(5 a\), show a parse tree for the value \(+90\).

a. Write a BNF grammar that describes the structure of U.S. telephone numbers, which can be either \((x x x) x x x-x x x x\) or \(x x x-x x x x\), where \(x\) can be any digit from 0 to 9 . b. Modify your grammar from Exercise 6a so that (1) the middle digit of an area code must be either a 0 or a \(1,(2)\) the first digit of an area code cannot be a 0 or a 1 , and (3) the first digit of the seven-digit phone number cannot be a 0 or a 1 . c. Using your grammar from either Exercise \(6 a\) or \(6 b\), show a parse tree for the phone number (612)555-1212.

a. Write a BNF grammar for identifiers that consist of an arbitrarily long string of letters and digits, the first one of which must be a letter. b. Using your grammar from Exercise 7a, show a parse tree for the identifier \(A B 5 C 8 .\)

Assume that we represent dollar amounts in the following way: \(\$$ number.numberCR The dollar sign and the dollar value must be present. The cents part (including both the decimal point and the number) and the CR (which stands for CRedit and is how businesspeople represent negative numbers) are both optional, and number is a variablelength sequence of one or more decimal digits. Examples of legal dollar amounts include \)\$ 995\(, \)\$ 99 \mathrm{CR}, \$ 199.95\(, and \)\$ 500.000 \mathrm{CR}\(. a. Write a BNF grammar for the dollar amount just described. b. Modify your grammar so that the cents part is no longer an arbitrarily long sequence of digits but is exactly two digits, no more and no less. c. Using your grammar from either Exercise \)8 \mathrm{a}\( or \)8 \mathrm{~b}\(, show a parse tree for \)\$ 19.95 \mathrm{CR}$.

Describe the language defined by the following grammar: \(\langle\) goal \(\rangle::=\langle\) letter \(\rangle \mid\langle\) letter \(\rangle\langle\) next \(\rangle\) \(\langle\) next \(\rangle::=,<\) letter \(>\) ::= A

a. Create a BNF grammar that describes simple Boolean expressions of the form var AND var var OR var where var is one of the symbols \(w, x, y\), and \(z\). b. Modify your grammar from Exercise 11 a so that the Boolean expressions can be of the form expr AND expr expr OR expr where expr is either a simple variable \((w, x, y,\), or z) or an expression of the form (var = var) (var < var) (var > var) c. Modify your grammar one more time to allow a Boolean expression to have an arbitrary number of terms connected by either AND or OR. That is, your expressions can be of the form expr AND expr OR expr OR expr AND expr....

Write a BNF grammar that describes an arbitrarily long string of the characters \(a, b\), and \(c\). The string can contain any number of occurrences of these three letters (including none) in any order. The strings "empty", \(a\), accaa, abcabccba, and bbbbb are all valid members of this language.