Name : Vina Melinda
NIM : 1801380106
NIM : 1801380106
Untuk kali ini saya akan menjawab Assignment #5 Problem Set dan Review Questions dari Chapter 3 dari Sebesta.
Review Questions:
6. Q: Define a left-recursive grammar rule.
A: 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. Q: What three extensions are common to most EBNFs?
A: Three extensions are common to most EBNFs:
a. The first extension denotes an optional part of a RHS, which is delimited by brackets. For example: <if_stmt> -> if ( <expr> ) stmt [ else <stmt> ]
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. For example: <ident_list> -> ident {, <ident> }
c. The third extension deals with multiple choice options. For example: <term> -> <term> ( *|/|% ) <factor>
8. Q: Distinguish between static and dynamic semantics.
9. Q: What purpose do predicates serve in an attribute grammar?
A: Static semantics is more on the legal forms of programs (syntax rather semantics) and is only indirectly related to the meaning of the programs during execution. Static semantics is so named because the analysis required to check these specifications can be done at compile time. In many cases, the semantic rules of language state its type constraints.
Dynamic semantics is describing the meaning of the programs. Programmers need to know precisely what statements of a language do. Compile writers determine the semantics of a language for which they are writing compilers from English descriptions
10. Q: What is the difference between a synthesized and an inherited attribute?
a. A = A * (B + (C * A))
Leftmost Derivation:
<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)
7. Q: 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
b. A = B + C + A
c. A = A * (B + C)
d. A = B * (C * (A + B))
A: Grammar in Example 3.4:
<assign> → <id> = <expr>
<id> → A | B | C
<expr> → <expr> + <term>
| <term>
<term> → <term> * <factor>
| <factor>
<factor> → ( <expr> )
| <id>
a. A = ( A + B ) * C
Leftmost Derivation
<assign> -> <id> = <expr>
b. A = B + C + A
Leftmost Derivation
<assign> -> <id> = <expr>
c. A = A * (B + C)
Leftmost Derivation
<assign> -> <id> = <expr>
d. A = B * (C * (A + B))
Leftmost Derivation
<assign> -> <id> = <expr>
8. Q: Prove that the following grammar is ambiguous:
<S> → <A>
<A> → <A> + <A> | <id>
<id> → a | b | c
A: The grammar is ambiguous because there's to different parse tree can be made from grammar above
9. Q: Modify the grammar of Example 3.4 to add a unary minus operator that
has higher precedence than either + or *.
A: <assign> → <id> = <expr>
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
A: It means all sentences consisting of one or more A’s followed by one or more B’s and then also followed by one or more C’s.
6. Q: Define a left-recursive grammar rule.
A: 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. Q: What three extensions are common to most EBNFs?
A: Three extensions are common to most EBNFs:
a. The first extension denotes an optional part of a RHS, which is delimited by brackets. For example: <if_stmt> -> if ( <expr> ) stmt [ else <stmt> ]
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. For example: <ident_list> -> ident {, <ident> }
c. The third extension deals with multiple choice options. For example: <term> -> <term> ( *|/|% ) <factor>
8. Q: Distinguish between static and dynamic semantics.
A: Static semantics is more on the legal forms of programs (syntax rather semantics) and is only indirectly related to the meaning of the programs during execution. Static semantics is so named because the analysis required checking these specifications can be done at compile time. Dynamic semantics is describing the meaning of the programs. Programmers need to know precisely what statements of a language do. Compile writers determine the semantics of a language for which they are writing compilers from English descriptions.
9. Q: What purpose do predicates serve in an attribute grammar?
A: Static semantics is more on the legal forms of programs (syntax rather semantics) and is only indirectly related to the meaning of the programs during execution. Static semantics is so named because the analysis required to check these specifications can be done at compile time. In many cases, the semantic rules of language state its type constraints.
Dynamic semantics is describing the meaning of the programs. Programmers need to know precisely what statements of a language do. Compile writers determine the semantics of a language for which they are writing compilers from English descriptions
10. Q: What is the difference between a synthesized and an inherited attribute?
A: The synthesized attributes are the result of the attribute evaluation rules, and may also use the values of the inherited attributes. The inherited attributes are passed down from parentnodes.In some approaches, synthesized attributes are used to pass semantic information up the parse tree, while inherited attributes help pass semantic information down it.
Problem Set:
6. Q: 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))
b. B = C * (A * C + B)
c. A = A * (B + (C))
Problem Set:
6. Q: 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))
b. B = C * (A * C + B)
c. A = A * (B + (C))
A: Grammar in Example 3.2:
<assign> -> <id> = <expr>
<id> -> A | B | C
<expr> -> <id> + <expr>
| <id> * <expr>
| ( <expr>)
| ( <expr>)
Leftmost Derivation:
<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))
Parse Tree
b. B = C * (A * C + B)
Leftmost Derivation
<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)
<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)
Parse Tree
c. A = A * (B + (C))
Leftmost Derivation
<assign> -> <id> = <expr>
-> A
= <expr>
-> A
= <id> * <expr>
-> A
= A * (expr>)
-> A
= A * (<id> + (<expr>))
-> A
= A * (B + <expr>)
-> A
= A * (B + (<expr>))
-> A
= A * (B + (<id>))
-> A
= A * (B + (C))
Parse Tree
derivation for each of the following statements:
a. A = ( A + B ) * C
b. A = B + C + A
c. A = A * (B + C)
d. A = B * (C * (A + B))
A: Grammar in Example 3.4:
<assign> → <id> = <expr>
<id> → A | B | C
<expr> → <expr> + <term>
| <term>
<term> → <term> * <factor>
| <factor>
<factor> → ( <expr> )
| <id>
a. A = ( A + B ) * C
Leftmost Derivation
<assign> -> <id> = <expr>
-> A
= <expr>
-> A = <term>
-> A = <term> * <factor>
-> A = <factor> * <factor>
-> A = <expr> * <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 ) * <factor>
-> A = ( A
+ B ) * <id>
-> A = ( A + B ) *
C
Parse Tree
b. A = B + C + A
Leftmost Derivation
<assign> -> <id> = <expr>
-> A = <expr>
-> A = <expr> + <term>
-> A = <term> + <term>
-> A = <factor> + <term>
-> A = <id> + <term>
-> A = B + <term>
-> A = B + <factor>
-> A = B + <expr>
-> A = B + <expr> + <term>
-> A = B + <term> + <term>
-> A = B + <factor> + <term>
-> A = B + <id> + <term>
-> A = B + C + <term>
-> A = B + C + <factor>
-> A = B + C + <id>
-> A = B + C + A
Parse Tree
Leftmost Derivation
<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>)
-> 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)
Parse Tree
Leftmost Derivation
<assign> -> <id> = <expr>
-> A = <expr>
-> A = <term>
-> A = <term> * <factor>
-> A = <factor> * <factor>
-> A = <id> * <factor>
-> A = B * <factor>
-> A = B * (<term>)
-> 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))
Parse Tree
8. Q: Prove that the following grammar is ambiguous:
<A> → <A> + <A> | <id>
<id> → a | b | c
A: The grammar is ambiguous because there's to different parse tree can be made from grammar above
Ambiguous Parse Tree
has higher precedence than either + or *.
A: <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
A: It means all sentences consisting of one or more A’s followed by one or more B’s and then also followed by one or more C’s.
No comments:
Post a Comment