Nama: Stefanus Eduard Adrian
NIM: 1801382963
Kali ini saya akan menjawab Assignment #3 dari Chapter 3 programming Language Concepts R Sebesta
Review
Questions
*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. Also, this left recursion specifies left associativity.
7. What three extensions are common to most EBNFs?
*Three extensions that are common to most EBNFs:
a. The first extension denotes an optional part of a RHS, which is delimited by brackets.
b. 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.
c. The third extension deals with multiple choice options.
8. Distinguish between static and dynamic semantics.
* Static semantis are represented declaratively. It is represented in passive data that is descriptive and can be retrieved, e.g. a Web page on a Web server. It also changes relatively slowly. The Web publishing events happen rarely relative to actions such as browsing a page or clicking a link.
The dynamic semantis are represented procedurally. It can be computed by programs running on the client or server side, based on immediate interactive user input. This computation can depend on the immediate context - including time, personal information about the user, user-initiated actions, etc. It also changes relatively rapidly. A single user click can cause the semantics to be generated or to change, or it can be changed by the actions of programs continuously in real-time.
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?
*A synthesized attribute proceeds in a bottom-up order, from leaves to roots. While an inherited attribute proceeds in a top-down order, from roots to leaves.
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>
= > 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 ) )
b. B = C * (A * C + B)
< 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)
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>
<A> →
<A> + <A> | <id>
<id>
→ a | b | c
*A grammar
is ambiguous if there are two different trees for derivation of same
expression.
The
following string is a sentence for this grammar and it has two
different
left-most derivations:
a + b + c
Left-most
derivation 1:
Rule Used
1
<S> => <A> 1
2 => <A> + <A> 2
3
=> id + <A>
3
4
=> a + <A>
4
5
=> a + <A> + <A>
2
6
=> a + id + <A> 3
7
=> a + b + <A> 5
8
=> a + b + id 3
9
=> a + b + c 6
Left-most
derivation 2:
Rule Used
1
<S> => <A>
1
2
=> <A> + <A>
2
3
=> <A> + <A> + <A> 2
4
=> id + <A> + <A>
3
5
=> a + <A> + <A>
4
6
=> a + id + <A>
3
7
=> a + b + <A>
5
8
=> a + b + id 3
9
=> a + b + c 6
9. Modify
the grammar of Example 3.4 to add a unary minus operator that has higher
precedence than either + or *.
*We can assume that the operators can precede any operand then<factor> → <id>
with
<factor> → + <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