Chapter 3

Posted by : Unknown Minggu, 19 Oktober 2014

Name : Romy Hermawan

NIM : 1801378902

Class : LD001

Lecturer: Ir. Tri Djoko Wahjono,M.Sc

6. Define a left-recursive grammar rule
Answer:

A left-recursive grammar rule means that when a grammar rule has its left-hand side(LHS) also appearing at the beginning of its right hand side(RHS) so therefore the rule is said to be left-recursive.

7. What three extensions are common to most EBNF’s?

Answer:

-The first one is 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.
-The third common extension deals with multiple-choice options.

8. Distinguish between static and dynamic semantics

Answer:

The static semantics defines restrictions on the structure of valid texts that are hard or impossible to express in standard syntactic formalism.And The dynamic semantics (also known as execution semantics) of a language defines how and when the various constructs of a language should produce a program behavior.

9. What purpose do predicates serve in an attribute grammar?

Answer:

Predicate functions, which state the static semantic rules of the language, are associated with grammar rules. A false predicate function value indicates a violation of the syntax or static semantics rules of the language.

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

Answer:

-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. In the case of a variable, the actual type is intrinsic.

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

Answer:

a. A = A * (B + C * A))

→ A = <expr>

→ A = <expr> * <expr>

→ A = <id> * <expr>

→ A = A * <expr>

→ A = A * ( <expr> )

→ A = A * ( <expr> + <expr>)

→ A = A * ( <id> + <expr>)

→ A = A * ( B + (<expr>)

→ A = A * ( B + (<expr> * <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)

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

→ 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

b. A = B + C + A

c. A = A * (B + C)

d. A = B * (C * (A + B))

Answer:

a. A = ( A + B ) * C

→ 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 = 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

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

3. Prove that the following grammar is ambiguous:
<S> => <A>
<A> => <A> + <A> | <id>
<id> => a | b | c
Answer:
There are several other characteristics of a grammar that are sometimes useful in determining whether a grammar is ambiguous.1 They include the following: (1) if the grammar generates a sentence with more than one leftmost derivation and (2) if the grammar generates a sentence with more than one rightmost derivation.

The grammar above is ambiguous because the sentence

A = B + C + A

has two distinct parse trees.The grammar specifies slightly less syntactic structure.

9. Modify the grammar of Example 3.4 to add a unary minus operator that

has higher precedence than either + or *.

Answer:

<id> → A | B | C

| <term>

| <factor>

<factor> → ( <expr> )

| <id>

5. Describe, in English, the language defined by the following grammar:

<A> => a <A> | a

<B> => b <B> | b

<C> => c <C> | c

Answer:

<S> is the start symbol ,in the start symbol exist 2 string of <X> and <Y>..The string <X> can be replaced with x<X> or with x.The same can be done with string <Y>.