ITEC 380 2009spring ibarland

home—info—lectures—exams—hws—archive

hw05
grammar

1. (7pts) Programming Exercise 15.8 (subst-in-tree), in Scheme. Include sufficient test cases.
   Note that this function takes in any list-of-S-expression, (here¹ is the data def'n for SExpr in lecture. It's easy if you follow the recipe: have one function for each of the data types, and whenever you have a datum of the appropriate type, call a function to handle that type.) This is (slightly) easier than the file/folder example covered from lecture.
2. (3pts) 3.6c Show a parse tree.
3. (3pts) 3.7d Show a parse tree.
4. (4pts) 3.4 (add Java's ++ and -- to the AExpr def'n)
   You may want to work some of the other problems and come back to this one. (But on the hw you turn in, please include this before the following solutions, thanks.)
5. (4pts) 3.8 (prove grammar ambiguous)
6. (2pts) 3.10 (English description of a grammar)
7. (3pts) 3.11 (which strings derivable?)
   1. baab
   2. bbbab
   3. bbaaaaa
   4. bbaab
8. (3pts) 3.12 (which strings derivable?)
   1. abcd
   2. acccbd
   3. acccbcc
   4. acd
   5. accc
9. (4pts) 3.16 (convert BNF to EBNF)

SExpr ::= Atom | List-of-SExpr
Atom ::= symbol | boolean | number | char | string | image | struct
List-of-SExpr ::= empty | (cons SExpr List-of-SExpr)

home—info—lectures—exams—hws—archive

©2009, Ian Barland, Radford University Last modified 2009.Apr.20 (Mon)

Please mail any suggestions (incl. typos, broken links) to iba�rlandrad�ford.edu