Consider the following grammar (G1) for simple assignment statements. (The symbols in double quotation marks are terminal symbols.)
assign → id “ = ” expr
id → “A” | “B” | “C”
expr → expr “ + ” expr
| expr “ ∗ ” expr
| “(” expr “)”
| id
a) Give a (leftmost) derivation for string A = B ∗ A + C.
b) Give the parse tree for string A = B ∗ A + C.
c) Is the grammar ambiguous or unambiguous? Explain your answer.
d) Consider the following grammar (G2).
assign → id “ = ” expr
id → “A” | “B” | “C”
expr → id “ + ” expr
| id “ ∗ ” expr
| “(” expr “)”
| id
What is the difference between G2 and G1? Explain your answer
c)
Ambiguous.
Grammar is ambiguous because we have more than one parse tree is there for one string.
d)
G1 is Ambiguous
G2 is unambigous
Since we have following in G2, we will substitute something to
expr only but not to id.
expr ? id “ + ” expr
| id “ * ” expr
| “(” expr “)”
| id
Where as in G1, we can substitute anything in any of the 2 expr's
we have
expr ? expr “ + ” expr
which lets it to have more than one derivation for one string
Consider the following grammar (G1) for simple assignment statements. (The symbols in double quotation marks are...
2. Consider the following grammar: <assign> à <id> = <expr> <id> à A | B | C <expr> à <id> + <expr> | <id> * <expr> | ( <expr> ) | <id> Show a parse tree and leftmost derivation for the following statements: (a) A = ( A + B ) * C (b) A = A * ( B + C ) 3. [10 Points] Show that the following grammar is...
3. Using the grammar below, show a parse tree and a leftmost derivation for the statement. A = ( A + (B)) * C assign <idxpr expr>? <expr> <term> term <term factor factor (<expr>) l <term I <factor l <id> 4. Prove that the following grammar is ambiguous (Give sentence that has two parse trees, and show the parse trees):
For the grammar <A> ::= <A><A> '+' | <A><A> '*' | 'a' and the string aa + a* Give the leftmost derivation Give the rightmost derivation Give a parse tree Is the grammar ambiguous or unambiguous? (Justify your answer) Describe the language generated by this grammar
- Using the grammar in Example 3.2, show a parse tree and a leftmost derivation for the following statement: B = C * (A * (B + C)). EXAMPLE 3.2 A Grammar for Simple Assignment Statements <assign> → <id> = <expr> <id> → A | B | C <expr> → <id> + <expr> | <id> * <expr> | ( <expr> ) | <id>
Given the following ambiguous context free grammar (3x20) 1. (a) Explain why the grammar is ambiguous (b) Find an equivalent unambiguous context-free grammar. (c) Give the unique leftmost derivation and derivation tree for the string s generated from the unambiguous grammar above. 2. Construct non-deterministic pushdown automata to accept the following language (20) 3. Convert the following CFG into an cquivalent CFG in Chomsky Normal Form (CNF) (20)-
6. (8 pts) Using grammar below show a Parse tree and leftmost derivation for a). A = A * (B+C) <assign> à<id> = <expr> <id> à A | B|C <expr>à <expr> + <term> | <term> <term> à <term> * <factor> |<factor> <factor> à ( <expr> ) |<id>
Question 3: Given the following grammar: assign → id := expr expr → expr + term \ term term -term *factor lfactor factor-(expr) id Using the above grammar, show a leftmost derivation (first five steps) for the following assignment statement: A ((A B)+ C) a. [3 marks] b. Using the above grammar, show a rightmost derivation (first five steps) for the following assignment statement: A:-A+B+C)+A [3 marks] Draw the abstract syntax tree for each of the above statements [4 marks]...
Consider the following grammar: (//some alternative rules are listed on separate lines without using symbol |): stmt −> assignment −> subr call assignment −> id := expr subr call −> id ( arg list ) expr −> primary expr tail expr tail −> op expr −> ε primary −> id −> subr call −> ( expr ) op −> + | - | * | / arg list −> expr args tail args tail −> , arg list −> ε...
1.a Consider the following Grammar, <assign> à <id> = <expr> <id> à A | B |C <expr> à < expr> + <expr> | <expr> * <expr> | ( <expr> ) | <id> Derive the following statement using leftmost derivation. A = A * (B*(C+ A)) b. 2 a}. Consider the following grammar that expresses parenthesized expressions of digits, including both addition and multiplication. <expr> := <expr> + <expr> | <expr> * <expr> | (expr>) | <digit> <digit> := 0 | 1 | 2 |...
1.) Consider the following grammar in which S, A, and B are nonterminal symbols and S is the start symbol. S → 1A | 0B A → A0 | 1B B → 10A| 1 Show that the grammar is ambiguous by showing two parse trees for the sentence 1110110 using leftmost derivation.