retagged by
10,267 views
18 votes
18 votes

​​​Consider the following grammar (that admits a series of declarations, followed by expressions) and the associated syntax directed translation $\text{(SDT)}$ actions, given as pseudo-code

$\begin{array}{lll} P & \rightarrow & D^* E^* \\ D & \rightarrow & \textsf{int ID} \{ \text{record that } \textsf{ID.} \text{lexeme is of type} \textsf{ int\}} \\  D & \rightarrow & \textsf{bool ID} \{ \text{record that } \textsf{ID.} \text{lexeme is of type} \textsf{ bool\}}  \\ E& \rightarrow & E_1 +E_2 \{ \text{check that } E_1. \text{type}=E_2. \text{type} = \textsf{int}; \text{set }  E.\text{type }:= \textsf{int} \} \\ E & \rightarrow & !E_1 \{ \text{check that } E_1. \text{type} = \textsf{bool}; \text{ set } E.\text{type} := \textsf{bool} \} \\ E & \rightarrow & \textsf{ID} \{ \text{set } E. \text{type } := \textsf{int} \} \end{array}$

With respect to the above grammar, which one of the following choices is correct?

  1. The actions can be used to correctly type-check any syntactically correct program
  2. The actions can be used to type-check syntactically correct integer variable declarations and integer expressions
  3. The actions can be used to type-check syntactically correct boolean variable declarations and boolean expressions.
  4. The actions will lead to an infinite loop
retagged by

3 Answers

11 votes
11 votes

Answer (A) The actions can be used to correctly type-check any syntactically correct program

 

SHORT ANSWER:

A grammar is given with the SDT actions on it.

Now, the option A:

“ The actions can be used to correctly type-check any syntactically correct program “

  • syntactically correct program: so we have to do SDT TYPE-CHECKING on any SYNTACTICALLY CORRECT PROGRAM

                     this means the PROGRAM (string) is legally generated by the grammar                             

(so syntactically correct programs ensured)

  • now correctly type-check: the SDT defined can  ONLY TELL what the CORRECT SYNTAX is!

        Thus, the SDT that defines the semantics of the declarations and expressions IS USED TO type-check the declaration and expressions of integer and boolean type

this will ensure that correct type-checking of any syntactically correct program is happening!

 


 


Long Answer:

 

OFFICIAL KEY says option (B) The actions can be used to type-check syntactically correct integer variable declarations and integer expressions

So, as said above, we have already a SYNTACTICALLY CORRECT program (string generated by the grammar)

The KEY thing for me while answering this question would always be to see

  • GRAMMAR   : syntactically correct programs
  • SDT             : type-checking

both separately.

First Grammar will generate SYNTACTICALLY correct programs (as always if grammar is used to generate the strings, THOSE STRINGS WILL BELONG to the grammar and thus THOSE PROGRAMS WOULD BE SYNTACTICALLY CORRECT)

Second step, the program is passed to the SDT and it type-checks it for both

  • declarations
  • expressions

Now, the program generated by grammar  be like:

ID

 

So, after generating the string (program) :    ID

we perform SEMANTIC ACTIONS.

So, our example: string: ID

Now the program is having integer expressions or boolean expression can NOT BE DETERMINED IN syntax analyzer phase, and ONLY THE SDT ACTIONS will determine the nature of expression (integer or boolean)

Thus, never this SDT could fail to correctly type-check  boolean variable expressions: as there be none.

All the expressions are of INTEGER VARIABLE only.

And integer variables too are being correctly type-checked as per the specified SDT rules, as the actions seem to correctly propagate and check type-meaning of the variables.

 


 

4 votes
4 votes

The Correct answer is B

As the given grammar does type checking and also it syntactically checks integer expressions.

0 votes
0 votes

The answer should be option “B” as its checking if the string produced will  be of int type only and not BOOLEAN. Hence option “B” is correct.

Answer:

Related questions

13 votes
13 votes
2 answers
1
Arjun asked Feb 18, 2021
6,273 views
Consider the following context-free grammar where the set of terminals is $\{a,b,c,d,f\}$. $$\begin{array}{lll} \text{S} & \rightarrow & d \: a \: \text{T} \mid \text{R} ...
12 votes
12 votes
4 answers
2