Assignment From Chapter 3 Programming Language Concepts R.Sebesta

Part: Review Question

16. In denotational semantics, what are the syntactic and semantic domains?

The mapping functions of a denotational semantics programming language specification, like all functions in math, have a domain and a range, the domain is called the syntactic domain, and the range is called the semantic domain.

17. What is stored in the state of a program for denotational semantics?

The state of a program for denotational semantics is the value of all its current variable.

18. Which semantics approach is most widely known?

The Denotational semantics is the most widely known semantics approach.

19. What two things must be defined for each language entity in order toconstruct a denotational description of the language?

objects and functions

20. Which part of an inference rule is the antecedent?

The antecedent is the top part of an inference rule.

Part: Problem Set

14. Draw parse trees for the sentences aabb and aaaabbbb, as derived from the grammar of Problem 13.

15. Convert the BNF of Example 3.1 to EBNF.

<program> → begin <stmt_list> end<stmt_list> → <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>}

| <id>

17. Convert the following EBNF to BNF:

S → A{bA}

A → a[b]A

The BNF form is:

<S> -> <S>b<A> | <A>

<A> -> a<A> | ab<A>

18. What is the difference between an intrinsic attribute and a nonintrinsic synthesized attribute?

1. An intrinsic attribute is an inherent characteristic of a terminal symbol in the grammar. So the value of the attribute is determined solely from the terminal symbol. A nonintrinsic synthesized attribute is an attribute of a non-terminal symbol in the grammar.

2. Intrinsic attributes are synthesized attributes of leaf nodes whose values are determined outside the parse tree. Nonintrinsic means the opposite, the values are not determined.

19. Write an attribute grammar whose BNF basis is that of Example 3.6 in Section 3.4.5 but whose language rules are as follows: Data types cannot be mixed in expressions, but assignment statements need not have the same types on both sides of the assignment operator.

1) Syntax rule: <assign> → <var> = <expr>

2) Syntax rule: <expr> → <var>[2] + <var>[3]

Predicate: <var>[2].actual_type == <var>[3].actual_type

3) Syntax rule: <expr> → <var>

4) Syntax rule: <var> → A | B | C

Semantic rule: <var>.actual_type ← lookup(<var>.string)

OR

Replace the second semantic rule with:
<var>[2].env ← <expr>.env
<var>[3].env ← <expr>.env
<expr>.actual_type ← <var>[2].actual_type
predicate: <var>[2].actual_type = <var>[3].actual_type

20. Write an attribute grammar whose base BNF is that of Example 3.2 and whose type rules are the same as for the assignment statement example of Section 3.4.5.

1) syntax rule: <assign> → <id> = <expr>

semantic rule: <expr>.expected_type ← <id>.actual_type

predicate: <expr>[1].actual_type == <expr>[1].expected_type

2) syntax rule: <expr>[1] → <id> + <expr>[2]

semantic rule: <expr>[1].actual_type ←

if (<id>.actual_type = int and <expr>[2].actual_type = int)

then int

else float

end if

3) syntax rule: <expr>[1] → <id> * <expr>[2]

semantic rule: <expr>[1].actual_type ←

if (<id>.actual_type = int and <expr>[2].actual_type = int)

then int

else float

end if

4) syntax rule: <expr>[1] → ( <expr>[2] )

semantic rule: <expr>[1].actual_type ← <expr>[2].actual_type

5) syntax rule: <expr> → <id>

semantic rule: <expr>.actual_type ← <id>.actual_type

6) syntax rule: <id> → A | B | C

semantic rule: <id>.actual_type ← lookup(<

id>.string)