- Using the following context-sensitive grammar: (20%)
<sentence> ::= abc | a<thing>bc
<thing>b ::= b<thing>
<thing>c ::= <other>bcc
a<other> ::= aa | aa<thing>
b<other> ::= <other>b
derive the <sentence> aaabbbccc and construct a derivation tree for it.
- Describe the language over the terminal set {
a, b} defined by the following grammar: (20%)
<string> ::= a <B> | b <A>
<A> ::= a | a <string> | b <A> <A>
<B> ::= b | b <string> | b <B> <B>
- Show the following grammar is ambiguous: (30%)
<stmt> ::= if <expr> then <stmt> | <matchedStmt>
<matchedStmt> ::= if <expr> then <matchedStmt> else <stmt> | other
<expr> ::= 0 | 1
- Write a BNF specification of the syntax of the Roman numerals less than 100. (30%)