1. Describe in English the language defined by the following grammar:

->

-> a | a

-> b | b

-> c | c

2. Consider the following grammar:

-> a c | | b

-> c | c

-> d |

Which of the following sentences are in the language defined by the grammar? Justify your answer by showing derivations or parse trees.

(a) abcd

(b) acccbd

(c) acd

(d) accc

3. Either prove or disprove the ambiguity of the following grammar.

->

-> * |

-> X | Y | Z

4. Rewrite the following grammar to give + precedence over * and force + to be right associative:

-> =

-> A | B | C

-> + |

-> * |

-> () |

5. Using the your rewritten grammar of Problem 4 above, show a parse tree and a leftmost derivation of the following statement:

A = B * (C * (A + B))

6. Convert the following EBNF to BNF:

-> { [ _ | $ ] }

-> |

-> |

-> A | B | C | D | E | F | G

-> a | b | c | d | e | f | g

-> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

7. You are to define the syntax of BNF itself.

(a) Write a BNF grammar describing the syntax of BNF; i.e., define the syntax of BNF itself using BNF. Use a pair of single quotes to use meta symbols like | and -> as terminal symbols, e.g., '|' and '->'. You may assume that non-terminals such as and are already defined.

(b) Is the following a sentence of the language you defined in (a) above? Justify your answer by stating the reason.

-> + |

-> 5

(c) Based on your answer to (a) above, draw a parse tree of the following sentence.

->

-> + | -

8. Define the syntax of the Connect Four Web service APIs and their JSON outputs. The Web service provides three APIs: info, new, and play. For each service API, define the syntax of:

- calling it, i.e., URL including its query string, e.g., http://www.cs.utep.edu/cheon/cs3360/project/c4/info

- JSON outputs (normal and error/exceptional responses), e.g., {"width":7,"height":6,"strategies":["Smart","Random"]}

Use the Java client (c4-web.jar) available from the course website and/or your favorite Web browser to learn about the APIs of the Web service and their sample outputs.

Refer to the JSON website (www.json.org) for the BNF syntax of JSON.

9. Consider the following BNF grammar that describes some of the "technical elective" courses allowed by the CS degree plan.

->

-> |

-> CS4390 | CS4371 | CS4373 | CS4330 | CS4317 | CS4339 | CS4342

You need to take at least five technical elective courses. However, no more than two courses of CS4390 (Special Topics), CS4371 (Independent Studies) and CS4373 (Internship) in any combination can count for technical electives.

CS4390 CS4330 CS4317 CS4339 CS4342 -- ok: one special course

CS4390 CS4390 CS4317 CS4339 CS4342 -- ok: two

CS4390 CS4371 CS4317 CS4339 CS4342 -- ok: two

CS4390 CS4390 CS4390 CS4330 CS4317 CS4339 -- ok: why?

CS4390 CS4330 CS4317 -- not okay: < five

CS4390 CS4390 CS4373 CS4330 CS4342 -- not okay: three

Extend the given BNF grammar to an attribute grammar to specify the above rules.