This assignment is due on March 24th.

Actually, the grammar in question 1 is not an accurate excerpt of the Scheme report as it diverts in an important point. However, the grammar of the question remains unchanged.

Question 1

Following production rules, specified in BNF, are an slightly but still significantly changed excerpt of the Scheme Report that specifies the syntax of identifiers:

<identifier> ---> <initial> <subsequent identifier>
<initial> ---> <letter> | <special initial>
<letter> ---> a | b | c | ... | z
<special initial> ---> ! | $ | % | & | * | / | : | < | =
   | > | ? | ^ | _ | ~
<subsequent identifier> ---> <subsequent>
   | <subsequent> <subsequent identifier>
<subsequent> ---> <initial> | <digit> | <special subsequent>
<digit> ---> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<special subsequent> ---> + | - | . | @

Please tell for each of the following terminal sequences whether they can be derived from <identifier> and, if your response is yes, how:

1. a
2. a2
3. 2a
4. ?a?
5. @a@

Question 2

Define a context-free grammar for list expressions in BNF (not EBNF) which should follow following rules:

• A list expression begins with ( and ends with ), including a possibly empty sequence of list elements.
• List elements are separated by commas.
• List elements are either non-empty sequences of digits (0 - 9) or list expressions.

Examples:

• ()
• (1,21,3)
• (())
• ((00))
• ((1234567890))
• ((12,21,(34,4),()),(5131,612),71)

Please write a text file with your answers for each of the both questions and attach them to an email that is sent to your individual submission address. The text files must be plain ASCII. Anything else (HTML, Microsoft Word, RTF, PostScript, PDF) will not be accepted.