Chapter 3

Review Questions

1. Define syntax and semantics!
Syntax is the form of its expressions, statements, and program units. Semantics is the meaning of those expressions, statements, and program units.

2.Who are language descriptions for ?

Potential users and Programming Language Implementors

3. Describe the operation of a general language generator.
A general language generator is a device that can be used to generate the sentences of the language. It generates unpredictable sentences which makes a generator seems to be a device of limited usefulness as language descriptor.


5. What is the difference between a sentence and a sentential form?
A sentence is a sentential form that has only terminal symbols. A sentence form is every string of symbols in the derivation.

7. What three extensions are common to most EBNFs ?
Three extensions are commonly included in the various versions of EBNF. The first extension denotes an optional part of an RHS, which is delimited by brackets. The second extension is the use of the brackets in an RHS to indicate that the enclosed part can be repeated indefinitely or left out altogether. And the third extension deals with multiple-choice options.

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 diference between a synthesized and an inherited atribute ?
The attributes are divided into two groups: synthesizedattributes and inherited attributes. 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 parent nodes.

12. What is the primary use of attribute grammar?

Attribute grammar is primary used to provide complete descriptions of the syntax and static semantics of programming languages.

22. Give an example of an ambiguous grammar.
<assign> -> <id> = <expr>

<id> -> A | B | C

<expr> -> <expr> + <expr>

| <expr> * <expr>

|  (  <expr>  )

| <id>

24. Give an unambiguous grammar for if-then-else.

<if_stmt> -> if <logic_expr> then <stmt>

if <logic_expr> then <stmt> else <stmt>

25. What is the problem with using a software pure interpreter for operational semantics?
The detailed characteristics of the particular computer would make actions difficult to understand. Such a semantic definition would be machine-dependent.

27. What is loop invariant? Explain with an example.
A loop invariant is a condition that is necessarily true immediately before and immediately after each iteration of a loop. Example:
int j = 9;
for(int i=0; i<10; i++)
j–;
In this example it is true (for every iteration) that i + j == 9. A weaker invariant that is also true is that
i >= 0 && i < 10 (because this is the termination condition) or that j <= 9 && j >= 0.

Problem Set

3. Rewrite the BNF of Example 3.4 to represent operator – and operator / instead of operator + and operator *.
<assign> → <id> = <expr>
<id> → A | B | C
<expr> → <expr> – <term>
| <term>
<term> → <term> / <factor>
| <factor>
<factor> → ( <expr> )
| <id>

4. Rewrite the BNF of Example 3.4 to add the ++ and — unary operators of Java.

<assign>

→ <id> = <expr>

<id>

→ A | B | C

<expr>

→ <expr> + <term> class  <Unary – condition- statement>

| (++/–) <term>

<term>

→ <factor> + <term>

| <factor>

<factor>

→ ( <expr> )

| (++/–) <id>

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>

11. Consider the following grammar:

<S> → <A> a <B> b

<A> → <A> b | b

<B> → a <B> | a

Which of the following sentences are in the language generated by this grammar?

a. bbaabb

b. bbaba

c. bbaaaabb

d. abaabb

a. bbaabb and c.bbaaaabb

15.   Convert the BNF of Example 3.1 to EBNF.

<program>  ->  begin <stmt_list> end

<stmt_list> -> <stmt>

| <stmt> ; <stmt_list>

<stmt> -> <var> = <expression>

<var> -> A | B | C

<expression> -> <var> {(+|-) <var>}

16. Convert the BNF of Example 3.3 to EBNF.

<assign> -> <id> = <expr>

<id> -> A | B | C

<expr> -> <expr> { ( + | * ) <expr> }

| ( <expr> )

| <id>

17. Convert the following EBNF to BNF:
S → A{bA}
A → a[b]A
S → A | A B
B → b A | b A B
A → a A | a b A

18. What is a fully attributed parse tree?

A fully attributed parse tree is a condition when all the attributed values in parse tree have been computed.

23. Compute the weakest precondition for each of the following assignment statements and postconditions:

a. a = 2 * (b – 1) – 1 (a > 0)

b. b = ( c + 10)  / 3 (b > 6)

c. a = a + 2 * b – 1 ( a > 1)

d. x = 2 * y + x – 1 (x > 11)

(a) ->   a = 2 * (b – 1) – 1 {a > 0}

2 * (b – 1) – 1 > 0

2 * b – 2 – 1 > 0

2 * b > 3

b > 3 / 2

(b) ->   b = (c + 10) / 3 {b > 6}

(c + 10) / 3 > 6

c + 10 > 18

c > 8

(c) ->   a = a + 2 * b – 1 {a > 1}

a + 2 * b – 1 > 1

2 * b > 2 – a

b > 1 – a / 2

(d) ->   x = 2 * y + x – 1 {x > 11}

2 * y + x – 1 > 11

2 * y + x > 12