Chapter 3 : Describing Syntax And Semantic

From Book : Concept Of Programming  Languages 
By : Robert W. Sebesta


REVIEW QUESTION :

16. In denotational semantics, what are the syntactic and semantic domains?
Answer :
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?
Answer :    
The state of a program for denotational semantics is the value of all its current variable.

18. Which semantics approach is most widely known?
Answer :  
The Denotational semantics is the most widely known semantics approach. 

Read More


19. What two things must be defined for each language entity in order to construct a denotational description of the language?
Answer :  
objects and functions

20. Which part of an inference rule is the antecedent? 
Answer : 
The antecedent is the top part of an inference rule.

PROBLEM SET :

16. Convert the BNF of Example 3.3 to EBNF.
Answer : 

<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

Answer : 

The BNF form is:

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

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

18.  What is a fully attributed parse tree?
Answer : 
A parse tree of an attribute grammar is the parse tree based on its underlying BNF
grammar, with a possibly empty set of attribute values attached to each node. If all the
attribute values in a parse tree have been computed, the tree is said to be fully attributed.

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.
Answer : 
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.

Answer :

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)