Assignment 1 must be submitted electronically through Canvas. Acceptable file formats are Word, PDF, and RTF. You should clear with me in advance any other formats.
When you are ready to submit be sure to name your file using your netID so if your netID was broge2 then your file will be named broge2.doc, broge2.pdf, or broge2.rtf. Assignments which are not properly named will receive a penalty of 50%. Do not try to make your work fancy but do show all work. Focus is not on the form but on the content. “Typewriter graphics” are fine. Hand drawn diagrams or figures are fine if they can be read. Handwritten text is not allowed. You should transcribe your handwritten work to typed work. If I cannot read something, I will assume it is wrong.
1. (30 points) Using the following BNF grammar, show a parse tree and a leftmost derivation for the following sentence. Make sure you do not omit parentheses in your derivation and parse tree as they are terminal symbols. Your derivation must start with <assign>.
Grammar
<assign> 
<id> = <expr>
<id> A | B | C
<expr> <expr> + <term> | <term>
<term> <term> * <factor> | <factor>
<factor> (<expr>) | <id>
Derive
C = A + (A * B) + C
2. (20 Points) Consider the following grammars where S is the start symbol and a, b, and c are terminal symbols and X, Y, and Z are non-terminal symbols.
S aA | bB | cC
A aA | aB | a
B bB | bC | b
C cC | c
Explain in your own words what the grammar generates. Which of the following sentences are in the language generated by the grammar? Show derivations. If a sentence cannot be generated by the grammar, explain why
1) abcabcab
2) aaaaaabb
3) cccccaaaa
4) bbbbbbbc
5) aaaaaaccc
3. (30 Points) For the following grammar written in BNF and the right sentential form draw a parse tree and show all phrases, simple phrases, and the handle. E, T, and F are nonterminal symbols. E is the start symbol.
Grammar
E E + T | T
T T * F | F
F (E) | id
Sentential Form
E + T * (T * F + id * id)
4. (20 Points) Transform the following left recursive BNF grammar into an equivalent non-left recursive grammar. S and A are nonterminal symbols. S is the start symbol. a and b are terminal symbols.
Grammar
S aaA | aAb | abaaA
A abA | Abaa | Ab | Aa | baA
The post Assignment 1 must be submitted electronically through Canvas. Acceptable file formats are Word, PDF, and RTF. You should clear with me in advance any other formats. When you are ready to submit be sure to name your file using your netID so if your netID was broge2 then your file will be named broge2.doc, broge2.pdf, or broge2.rtf. Assignments which are not properly named will receive a penalty of 50%. Do not try to make your work fancy appeared first on My Academic Papers.
