Assignment 3
Review Questions
6. Define a left-recursive grammar rule
A left-recursive grammar rule means that when a grammar rule has its left-hand side also appearing at the beginning of its right hand side so therefore the rule is said to be left-recursive.
7. What three extensions are common to most EBNF’s?
The first one is denotes an optional part of an RHS, which is delimited by brackets. The second extension is the use of braces in an RHS to indicate that the enclosed part can be repeated indefinitely or left out altogether. And lastly the third common extension deals with multiple-choice options.
8. Distinguish between static and dynamic semantics
The static semantics of a language is only indirectly related with to the meaning of program execution. While dynamic semantics is not universally accepted in notation.
9. What purpose do predicates serve in an attribute grammar?
Predicates function state the static semantic rules of the language, that are associated with grammar rules. A false value in predicates indicates that there is an invalid syntax or static semantics and determines whether an action is allowed or not.
10. What is the difference between a synthesized and an inherited attribute?
A synthesized attribute associated with the nonterminals <var> and <expr>. It is used to store the actual type, int or real, of a variable or expression. In the case of a variable, the actual type is intrinsic. In the case of an expression, it is determined from the actual types of the child node or children nodes of the <expr> nonterminal. While an inherited attribute associated with the nonterminal <expr>. It is used to store the type, either int or real, that is expected for the expression, as determined by the type of the variable on the left side of the assignment statement.
Problem sets
1. Using the grammar in Example 3.2, show a parse tree for each of the following statements :
a) A = A * ( B + ( C * A ) )
<assign>=> <id> = <expr>
=> A = <expr>
=> A = <id> * <expr>
=> A = A * <expr>
=> A = A * (<expr>)
=> A = A * (<id> + <expr>)
=> A = A * (B + <expr>)
=> A = A * (B + (<expr>))
=> A = A * (B + (<id> * <expr>))
=> A = A * (B + (<id> * <id>))
=> A = A * (B + (C * <id>))
=> A = A * (B + (C * A))
b) B = C * (A * C + B)
<assign>=> <id> = <expr>
=> B = <expr>
=> B = <id>* <expr>
=> B = <id>* (<expr>)
=> B = C * (<expr>)
=> B = C * (<id> * <expr>)
=> B = C * (A * <expr>)
=> B = C * (A * <id> + <expr>)
=> B = C * (A * <id> + <id>)
=> B = C * (A * C + <id>)
=> B = C * (A * C + B)
c) A = A * (B + (C) )
<assign>=> <id>= <expr>
=> A = <expr>
=> A = <id> * <expr>
=> A = A * <expr>
=> A = A * (<expr> )
=> A = A * (<id>+ <expr> )
=> A = A * (B + <expr> )
=> A = A * (B + (<expr>) )
=> A = A * (B + (<id>) )
=> A = A * (B + (C) )
2. Using the grammar in Example 3.4, show a parse tree for each of the following statements :
a) A = ( A + B ) * C
<assign> => <id> = <expr>
=> A = <expr>
=> A = <term>
=> A = <factor> * <factor>
=> A = <factor> * <id>
=> A = ( <expr> ) * <id>
=> A = ( <term> + <term> ) * <id>
=> A = ( <id> + <term> ) * <id>
=> A = ( <id> + <id> ) * <id>
=> A = ( A + <id> ) * <id>
=> A = ( A + B ) * <id>
=> A = ( A + B ) * C
b) A = B + C + A
<assign> => <id> = <expr>
=> A = <expr>
=> A = <term> + <expr>
=> A = <id> + <expr>
=> A = <id> + <term> + <term>
=> A = <id> + <id> + <term>
=> A = <id> + <id> + <id>
=> A = B + <id> + <id>
=> A = B + C + <id>
=> A = B + C + A
c) A = A * ( B + C )
<assign> => <id> = <expr>
=> A = <expr>
=> A = <term>
=> A = <term> * <factor>
=> A = <id> * <factor>
=> A = A * <factor>
=> A = A * ( <expr> )
=> A = A * ( <term> + <term> )
=> A = A * ( <id> + <term> )
=> A = A * ( <id> + <id> )
=> A = A * ( B + <id> )
=> A = A * ( B + C )
d) A = B * ( C * ( A + B ) )
<assign> => <id> = <expr>
=> A = <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 * ( <id> + <term> ) )
=> A = B * ( C * ( <id> + <id> ) )
=> A = B * ( C * ( A + <id> ) )
=> A = B * ( C * ( A + B ) )
3. Prove that the following grammar is ambiguous:
<S> => <A>
<A> => <A> + <A> | <id>
<id> => a | b | c
A grammar that generates a sentential form for which there are two or more distinct parse trees is said to be ambiguous. Because of the statement A = A + B + C the statement has 2 distinct parse tree. The grammar specifies slightly less syntactic structure.
4. 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> – <expr>
<expr> => <expr> + <expr>
| <term>
<term> => <term> * <factor>
| <factor>
<factor> => ( <expr> )
| <id>
5. 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
The <S> statement is equivalent to <A> statement, <B> statement, and <C> statement. Where as <A> statement is equivalent to character a and <A> statement or only character a. <B> statement is equivalent to character b and <B> statement or only character b. <C> statement is equivalent to character c and <C> statement or only character c.
