Concrete Abstractions: Chapter 10

Exercise 10.2: Even when a category is directly testable by Scheme, using EBNF to express it at a more primitive level can help you appreciate the expressive power of EBNF. In this exercise you will use EBNF to describe certain kinds of numbers—a small subset of those allowed by Scheme.
a. Write a production for <unsigned-integer>. You can use the productions for <digit> given above.
b. Next write productions for <integer>; an <integer> may start with a – sign, a + sign, or neither.
c. Finally, write productions for <real-number>, which are (possibly) signed numbers that may have a decimal point. Note that if the real number has a decimal point, there must be at least one digit to the left or to the right (or both) of the decimal point. Thus, -43., .43, 43, 43.21, and 43.0 are all valid real numbers.

Solution: a. <unsigned integer> -> <digit>+
b. <integer> -> -<unsigned integer> | +<unsigned integer> | <unsigned integer>
c. <real-number> -> <integer>. | <integer>.<unsigned integer>* | .<unsigned integer>+ | <integer>

Exercise 10.3: In Section 8.3 we considered expression trees for simple arithmetic expressions. All such expressions are either numbers or lists having an operator (one of +, -, *, or /) and two operands. Actually, there are three important variants, depending on where the operator occurs: in the first position (prefix or Scheme notation), the second position (infix or standard notation), or the third position (postfix, also known as Reverse Polish notation, or RPN). Let’s consider how such expressions can be specified using EBNF.
a. Write productions for <arithmetic-prefix-expression>.

b. Write productions for <arithmetic-infix-expression>.

c. Write productions for <arithmetic-postfix-expression>.

d. As noted in Section 8.3, a postorder traversal of an expression tree re-
sults in a list of the nodes that is identical to the language specified by <arithmetic-postfix-expression>, except that subexpressions are not parenthesized. Revise the productions for <arithmetic-postfix-expression> so that subexpressions are not parenthesized. (The overall top-level expression needn’t be parenthesized either.)

Solution:  <arithmetic-expression> -> + | – | * | /
a. <arithmetic-prefix-expression> -> (<arithmetic-expression> <real-number> <real-number>)
b. <aritmethic-infix-expression> -> (<real-number> <arithmetic-expression> <real-number>)
c. <arithmetic-postfix-expression> -> (<real-number> <real-number> <arithmetic-expression>)

Exercise 10.4: Let’s consider two possible additions to our Micro-Scheme grammar involving regular Scheme expressions.
a. Write a production for let expressions. Remember that let expressions allow zero or more bindings (i.e., parenthesized name/expression pairs), and the body of the let contains one or more expressions. You should define a separate syntactic category for <binding>.
b. Write productions for cond expressions. Remember that cond expressions allow one or more branches, the last of which may be an else, and each branch has one or more expressions following the test condition.

Solution: a. <binding> –> (let ((<name> <expression>)) <expression>+>
b.
<condition> –> (cond ((<expression>+ <expression>))+ (else <expression>+ )
)

Exercise 10.6:

Solution: a. (if 3 1 5) is a <conditional>. Let’s check if 3, 1, and 5 are <expression>s. 3, 1 and 5  are <number>s which are <literal>s which are <constant>s which are <expression>s. So that’s valid.
b. (lambda x (+ x 2)) that isn’t valid because a <abstraction> needs parenthisis after lambda.
c. (((a ((b))) c)) that looks like an <application> let’s check if ((a ((b))) c) is an <expression>. Because an <application> is an <expression> we have to check if <em>(a ((b)))</em> and <em>c</em> is an <expression>. c is an <name> and therefore an <expression>. <em>(a ((b)))</em> is an <application> which have to consists of one or more expressions. So there’s <em>a ((b))</em> left to check. a is an <expression>. ((b)) is an <application> of an <application> of a <name> which is an <expression>. So that’s valid.
d. (lambda (lambda) 3). We have to check if lambda ist a <name> which is false. Not valid.
e. (lambda () lambda). We have to check if lambda is an <expression> which it isn’t.
f. (lambda (x) (if (> x 0) x (- x) 0)). Let’s check if <em>if</em> is an <conditional>. It isn’t because it has more than three <expression>s in its body.
g. (lambda () x). This is valid if x is an <expression>. A <name> is an <expression>, so this is valid.
h. (lambda () ). Not valid, because there’s no <expression> in the body.
i. (/). Not valid, because it needs at least two <arithmetic-expression>s in the body.
j. (#t #f). This is an <application> of two expressions. Are #f and #t <expression>s?  They aren’t definied, so this is not valid.

Exercise 10.31: Use EBNF to write a grammar for the language of all strings of one or more digits that simultaneously meet both of the following requirements:
a. The digits alternate between even and odd, starting with either.

b. The string of digits is the same backward as forward (i.e., is palindromic).

Solution:

<even> -> 0 | 2 | 4 | 6 | 8
<odd>  -> 1 | 3 | 5 | 7 | 9
<palindrome-even> -> 0<palindrome-odd>0 | 2<palindrome-odd>2 | 4<palindrome-odd>4 | 6<palindrome-odd>6 |
                     8<palindrome-odd>8 | <even>
<palindrome-odd> ->  1<palindrome-even>1 | 3<palindrome-even>3 | 5<palindrome-even>5 | 7<palindrome-even>7 | 
                     9<palindrome-even>9 | <odd>
<legal> -> <palindrome-even> | <palindrome-odd>