NIM : 1801384174
Kali ini saya akan menjawab assigntment #3 dari chapter 3 Programming Language Concepts R Sebesta E-book :
Review Questions #6-10 :
6. Define a left-recursive grammar rule.
When a grammar rule has its LHS also appearing at the beginning of its RHS, the rule is said to be left recursive. This left recursion specifies left associativity.
7. What three extensions are common to most EBNFs?
Three extensions are commonly included in the various versions of EBNF.
The first of these 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. This extension allows lists to be built with a single rule, instead of using recursion and two rules.
The third common extension deals with multiple-choice options. When a single element must be chosen from a group, the options are placed in parentheses and separated by the OR operator, |.
8. Distinguish between static and dynamic semantics.
The static semantics of a language is only indirectly
related to the meaning of programs during execution; rather, it has to do
with the legal forms of programs (syntax rather than semantics).
Dynamic semantics is a perspective on natural language semantics that emphasises the growth of information in time. It is an approach to meaning representation where pieces of text or discourse are viewed as instructions to update an existing context with new information, with an updated context as result.
9. What purpose do predicates serve in an attribute grammar?
Predicates in attribute grammar states the static semantic rules a language needs to follow. 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?
actual_type—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.
expected_type—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 Set#6-10 :
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>
= > 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 + (C * <expr> ))
= > A = A * ( B + ( C * <id> ) )
= > A = A * ( B + ( C * A ) )
< assign > = > <id> = <expr>
= > B = <expr>
= > B = <id> + <expr>
= > B = C + <expr>
= > B = C + ( <expr> )
= > B = C + ( <id> + <expr> )
= > B = C + ( A * <expr> )
= > B = C + ( A * <id> + <expr> )
= > B = C + ( A * C + <expr> )
= > 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 ) )
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=<term>*<factor>
=> A=<factor>*<factor>
=> A=(<expr>)*<factor>
=> A=(<expr>+<term>)*<factor>
=> A=(<term>+<term>)*<factor>
=> A=(<factor>+<term>)*<factor>
=> A=(<id>+<term>)*<factor>
=> A=(A+<term>)*<factor>
=> A=(A+<factor>)*<factor>
=> A=(A+<id>)*<factor>
=> 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)
<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))
<S> → <A>
<A> → <A> + <A> | <id>
<id> → a | b | c
A grammar is ambiguous if there
are two different trees for derivation of same expression. Expressed in more
formal way, a grammar is ambiguous if fr(T)=fr(T’) implies T <> T’. fr(T)
means a frontier of a tree, which specifies the leaves of a tree. Therefore, if
two trees have same frontiers and the grammar is ambiguous, the trees will be
structurally different.
Moreover, two trees for a
derivation of an expression are structurally different if the grammar allows both
left and right growing of the tree.
For the grammar of this problem
and the expression a=a+b+c there are two different leftmost derivations:
<S>-><A>
-> <A>+<A>
-> <A>+<A>+<A>
-> <id>+<A>+<A>
-> a+<A>+<A>
-> a+<id>+<A>
-> a+b+<A>
-> a+b+<id>
-> a+b+c
<S>-><A>
-><A>+<A>
-><id>+<A>
->a+<A>
->a+<A>+<A>
->a+<id>+<A>
->a+b+<A>
->a+b+<id>
->a+b+c
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> | - <factor>
<term> =>
<term>*<factor> | <factor>
<factor> =>
(<expr>) | <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
All sentences consisting of one or more a’s followed by one or more b’s followed by one or more c’s
No comments:
Post a Comment