Using the following grammar, show a parse tree and a leftmost derivation for the following sentence (make sure you do not omit parentheses in your derivation. Parentheses, because they are terminal symbols, should have edges in your parse tree as well.) Grammar → = → A | B | C → + | → * | → () | Derive: B = A + (B * A + C)
Using the following grammar, show a parse tree and a leftmost derivation for the following sentence (make sure you do not omit parentheses in your derivation. Parentheses, because they are terminal symbols, should have edges in your parse tree as well.)
Grammar
<assign> → <id> = <expr>
<id> → A | B | C
<expr> → <expr> + <term> | <term>
<term> → <term> * <factor> | <factor>
<factor> → (<expr>) | <id>
Derive:
B = A + (B * A + C)
Grammar
Rule 1: <assign> → <id> = <expr>
Rule 2: <id> → A
Rule 3: <id> → B
Rule 4: <id> → C
Rule 5: <expr> → <expr> + <term>
Rule 6: <expr> → <term>
Rule 7: <term> → <term> * <factor>
Rule 8: <term> → <factor>
Rule 9: <factor> → (<expr>)
Rule 10: <factor> → <id>
LeftMost Derivation
<assign> → <id> = <expr> [Rule 1]
→ B = <expr> [Rule 3]
→ B = <expr> + <term> [Rule 5]
→ B = <term> + <term> [Rule 6]
→ B = <factor> + <term> [Rule 8]
→ B = <id> + <term> [Rule 10]
→ B = A + <term> [Rule 2]
→ B = A + <factor> [Rule 8]
→ B = A + (<expr>) [Rule 9]
→ B = A + (<expr> + <term>) [Rule 5]
→ B = A + (<term> + <term>) [Rule 6]
→ B = A + (<term> * <factor> + <term>) [Rule 7]
→ B = A + (<factor> * <factor> + <term>) [Rule 8]
→ B = A + (<id> * <factor> + <term>) [Rule 10]
→ B = A + (B * <factor> + <term>) [Rule 3]
→ B = A + (B * <id> + <term>) [Rule 10]
→ B = A + (B * A + <term>) [Rule 2]
→ B = A + (B * A + <factor>) [Rule 8]
→ B = A + (B * A + <id>) [Rule 10]
→ B = A + (B * A + C) [Rule 4]
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 1 images
