Source:
Concepts of Programming Languages, Robert W. Sebesta.
Chapter 3: Describing Syntax and Semantics, page 162-164
By:
Name : Helena Natanael
NIM : 1801380333
Review Question:
6. Define a left-recursive grammar rule.
When a grammar rule has its left hand side (LHS) also appearing at the beginning of its right hand side (RHS), the rule is said to be left recursive. This left recursion specifies left associativity.
7. What three extensions are common to most EBNFs?
Extended Backus-Naur Forms has three common extensions:
1. The first extension denotes an optional part of an right hand side (RHS), which is delimited by brackets. 2. 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.
3. 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?
An attribute grammar consists of a grammar, a set of attributes, a set of attribute computation functions, and a set of predicates, which together describe static semantics rules. So predicates is a part of attribute grammar which is without the predicates, there would be no attribute grammar.
10. What is the difference between a synthesized and an inherited attribute
The difference between Synthesized and Inherited attribute is :
Synthesized attributes are used to pass semantic information up a parse tree, in the other hand inherited attributes pass semantic information down and across a tree.
Problem Set:
6. Using the grammar in Example 3.2, show a parse tree and a leftmost derivation for each of the following statements:
Grammar in Example 3.2:
<assign> → <id> = <expr>
<id> → A | B | C
<expr> → <id> + <expr>
| <id> * <expr>
| ( <expr>
a. A = A * (B + (C * A))
Parse Tree:
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)
Parse Tree:
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 )
c. A = A * (B + (C))
Parse Tree:
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>) )
→ 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:
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
Parse Tree:
Leftmost Derivation:
<assign> → <id> = <expr>
→ A = <expr>
→ A = <term>
→ A = <term> * <term>
→ A = <factor> * <term>
→ 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 + B ) * <term>
→ A = ( A + B ) * <factor>
→ A = ( A + B ) * <id>
→ A = ( A + B ) * C
b. A = B + C + A
Parse Tree:
Leftmost Derivation:
<assign> → <id> = <expr>
→ A = <expr>
→ A = <expr> + <term>
→ A = <term> + <term>
→ A = <factor> + <term>
→ A = <id> + <term>
→ A = B + <term>
→ A = B + <term> + <factor>
→ A = B + <factor> + <factor>
→ A = B + <id> + <factor>
→ A = B + C + <factor>
→ A = B + C + <id>
→ A = B + C + A
c. A = A * (B + C)
Parse Tree:
Leftmost Derivation:
<assign> → <id> = <expr>
→ A = <expr>
→ A = <term>
→ A = <factor> * <term>
→ 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))
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 * ( <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
The grammar is ambiguous because there's 2 different parse trees can be made from grammar above.
9. Modify the grammar of Example 3.4 to add a unary minus operator that
has higher precedence than either + or *.
By:
Name : Helena Natanael
NIM : 1801380333
Review Question:
6. Define a left-recursive grammar rule.
When a grammar rule has its left hand side (LHS) also appearing at the beginning of its right hand side (RHS), the rule is said to be left recursive. This left recursion specifies left associativity.
7. What three extensions are common to most EBNFs?
Extended Backus-Naur Forms has three common extensions:
1. The first extension denotes an optional part of an right hand side (RHS), which is delimited by brackets. 2. 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.
3. 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?
An attribute grammar consists of a grammar, a set of attributes, a set of attribute computation functions, and a set of predicates, which together describe static semantics rules. So predicates is a part of attribute grammar which is without the predicates, there would be no attribute grammar.
10. What is the difference between a synthesized and an inherited attribute
The difference between Synthesized and Inherited attribute is :
Synthesized attributes are used to pass semantic information up a parse tree, in the other hand inherited attributes pass semantic information down and across a tree.
Problem Set:
6. Using the grammar in Example 3.2, show a parse tree and a leftmost derivation for each of the following statements:
Grammar in Example 3.2:
<assign> → <id> = <expr>
<id> → A | B | C
<expr> → <id> + <expr>
| <id> * <expr>
| ( <expr>
a. A = A * (B + (C * A))
Parse Tree:
<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)
Parse Tree:
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 )
c. A = A * (B + (C))
Parse Tree:
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>) )
→ 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:
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
Parse Tree:
Leftmost Derivation:
<assign> → <id> = <expr>
→ A = <expr>
→ A = <term>
→ A = <term> * <term>
→ A = <factor> * <term>
→ A = (<expr>) * <term>
→ A = (<expr> + <term>) * <term>
→ A = (<term>
→ A = (<factor> + <term>) * <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
Parse Tree:
Leftmost Derivation:
<assign> → <id> = <expr>
→ A = <expr>
→ A = <expr> + <term>
→ A = <term> + <term>
→ A = <factor> + <term>
→ A = <id> + <term>
→ A = B + <term>
→ A = B + <term> + <factor>
→ A = B + <factor> + <factor>
→ A = B + <id> + <factor>
→ A = B + C + <factor>
→ A = B + C + <id>
→ A = B + C + A
c. A = A * (B + C)
Parse Tree:
Leftmost Derivation:
<assign> → <id> = <expr>
→ A = <expr>
→ A = <term>
→ A = <factor> * <term>
→ 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))
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 * ( <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
The grammar is ambiguous because there's 2 different parse trees can be made from grammar above.
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
It means all sentences consisting of one or more a, then a is followed by one or more b and then also followed by one or more c.
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
It means all sentences consisting of one or more a, then a is followed by one or more b and then also followed by one or more c.
No comments:
Post a Comment