--------------------------------------------------------------------------------------------------------------------------
6. Define a left-recursive grammar rule.
- A left-recursive grammar means that the parser can get into a loop in the parsing rules without making any progress consuming the input. A grammar is left-recursive if we can find some non-terminal A which will eventually derive a sentential form with itself as the left-symbol.
7. What three extensions are common to most EBNFs?
- Denotes an optional part of a RHS, which is delimited by brackets, the use of braces in an RHS to indicate that the enclosed part can be repeated indefinitely or left out altogether, deals with multiple choice options.
8. Distinguish between static and dynamic semantics.
- Static semantics is only indirectly related to the meaning of programs during execution. Dynamic semantics is not universally accepted in notation.
9.What purpose do predicates serve in an attribute grammar?
- The use of predicates functions is to state the static semantic rules of the language.
10. What is the difference between a synthesized and an inherited attribute?
- An inherited attribute proceeds in a top-down order, from roots to leaves. A synthesized attribute proceeds in a completely bottom-up order, from leaves to root.
---------------------------------------------------------------------------------------------------------------------------------
Problem Set :
---------------------------------------------------------------------------------------------------------------------------------
6. Using the grammar in Example 3.2, show a parse tree and a leftmost derivation for each of the following statements :
a. A = A * (B * ( C + A ) )
<assign> -> <id> = <expr>
<id> -> A | B | C
<expr> – > <id> + <expr>
| <id> * <expr>
| ( <expr> )
| <id>
b. B = C * (A + C * B )
<assign> -> <id> = <expr>
<id> -> A | B | C
<expr> – > <id> * <expr>
| <id> + <id> *<id>
| ( <expr> )
| <id>
c. A = A + (B * (C) )
<assign> -> <id> = <expr>
<id> -> A | B | C
<expr> – > <id> + <expr>
| <id> * <expr>
| ( <expr> )
| (<id>)
| <id>
7. Using the grammar in Example 3.4, show a parse tree and a leftmost derivation for each of the following statements:
a.) A = ( A + B ) * C
<assign> => <id> = <expr>
- A = <expr>
- A = <term>
- A = <factor> * <term>
- A = (<expr>) * <term>
- A = (<expr> + <term>) * <term>
- A = (<term> + <term>) * <term>
- A = (<factor> + <factor> ) * <term>
- A = (<id> + <term>) * <term>
- A = ( A + <term>) * <term>
- A = (A + <factor>) * <term>
- A = (A + <id>) * <term>
- A = (A + B) * <term>
- A = (A + B) * <factor>
- A = (A + B) * <id>
- A = (A + B) * C
b.)A = B + C + A
<assign> => <id>=<expr>
- A=<expr>
- A=<expr>+<term>
- A=<expr>+<term>+<term>
- A=<term>+<term>+<term>
- A=<factor>+<term>+<term>
- A=<id>+<term>+<term>
- A=A+<term>+<term>
- A=A+<factor>+<term>
- A=A+<id>+<term>
- A=A+C+<term>
- A=A+C+<factor>
- A=A+C+<id>
- A=A+C+A
c.) A = A * (B + C)
<assign> => <id>=<expr>
- A=<expr>
- A=<term>
- A=<term>*<factor>
- A=<factor>*<factor>
- A=<id>*<factor>
- A=A*<factor>
- A=A*(<expr>)
- A=A*(<expr>+<term>)
- A=A*(<term>+<term>)
- A=A*(<factor>+<term>)
- A=A*(<id>+<term>)
- A=A*(B+<term>)
- A=A*(B+<factor>)
- A=A*(B+<id>)
- A=A*(B+C)
d.) A = B * (C * (A + B))
<assign> => <id>=<expr>
- A=<term>
- A=<term>*<factor>
- A=<factor>*<factor>
- A=<id>*<factor>
- A=B*<factor>
- A=B*(<expr>)
- A=B*(<term>)
- A=B*(<term>*<factor>)
- A=B*(<factor>*<factor>)
- A=B*(<id>*<factor>)
- A=B*(C*<factor>)
- A=B*(C*(<expr>))
- A=B*(C*(<expr>+<term>))
- A=B*(C*(<term>+<term>))
- A=B*(C*(<factor>+<term>))
- A=B*(C*(<id>+<term>))
- A=B*(C*(A+<term>))
- A=B*(C*(A+<factor>))
- A=B*(C*(A+<id>))
- A=B*(C*(A+B))
8. Prove that the following grammar is ambiguous!
<S> -> <A>
<S> -> <A> * <A> | <id>
<id> -> x | y | z
It has two distinct parse tree. Unambiguous grammar don't have 2 distinct parse tree.
9. Modify the grammar of Example 3.4 to add a unary minus operator that has higher precedence than either + or *!
<assign> -> <id> = <expr>
<id> -> A | B | C
<expr> -> <expr> + <term>
| <term>
<term> -> <term> * <factor>
| <factor>
<factor> -> ( <expr> )
| +<id> | -<id>
10. Describe, in English, the language defined by the following grammar:
<S> → <A> <B> <C>
<A> → a <A> | a
<B> → b <B> | b
<C> → c <C> | c
No comments:
Post a Comment