Assignment 3

Pada post kali ini, saya akan menjawab pertanyaan-pertanyaan Assignment #3 dari Chapter 3, dari buku "Concepts of Programming Languages" karya Robert W. Sebesta.

Review Questions

        1.  Define a left-recursive grammar rule.
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.

        2. What three extensions are common to most EBNFs ?
Denotes an optional part of a RHS, which is delimited by brackets, the use of braces in an RHS to indicate that the enclosed part can be repeated indefinitely or left out altogether, deals with multiple choice options.

        3. Distinguish between static and dynamic semantics.

Static semantics is only indirectly related to the meaning of programs during execution. Dynamic semantics is not universally accepted in notation.

        4. 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.

        5. What is the difference between a synthesized and an inherited attribute ?

An inherited attribute proceeds in a top-down order, from roots to leaves. A synthesized attribute proceeds in a completely bottom-up order, from leaves to root.

Problem Sets

        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 + (<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) )

        7. 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 ) )

        8. Prove that the following grammar is ambiguous !

<S> -> <A>

<S> -> <A> * <A> | <id>

<id> -> x | y | z

It is ambiguous because it has two distinct parse tree.

        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>

<term> -> <term> * <factor>

| <factor>

<factor> -> ( <expr> )

| +<id> | -<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

The LHS non-terminal S is defined as non-terminal A and non-terminal B and non-terminal C, where non-terminal A can be one or more a’s or one a, where non-terminal B can be one or more b’s or one b, and where non-terminal C can be one or more c’s or one c.