Syntex Directed Translation MCQ - 1


20 Questions MCQ Test RRB JE for Computer Science Engineering | Syntex Directed Translation MCQ - 1


Description
This mock test of Syntex Directed Translation MCQ - 1 for Computer Science Engineering (CSE) helps you for every Computer Science Engineering (CSE) entrance exam. This contains 20 Multiple Choice Questions for Computer Science Engineering (CSE) Syntex Directed Translation MCQ - 1 (mcq) to study with solutions a complete question bank. The solved questions answers in this Syntex Directed Translation MCQ - 1 quiz give you a good mix of easy questions and tough questions. Computer Science Engineering (CSE) students definitely take this Syntex Directed Translation MCQ - 1 exercise for a better result in the exam. You can find other Syntex Directed Translation MCQ - 1 extra questions, long questions & short questions for Computer Science Engineering (CSE) on EduRev as well by searching above.
QUESTION: 1

To evaluate an expression without any embedded function calls

Solution:

Expression without any calls in it ⇒ 1+2*3-4

Expression with embedded calls ⇒ 1 + fun1(a,b,c) *fun2(3.4,58) - fun3(x,yz);

First we can convert Infix to Postfix using single stack (Using it as operator stack)

Then we can evaluate that expression using Single stack.

*Answer can only contain numeric values
QUESTION: 2

Consider the expression tree shown. Each leaf represents a numerical value, which can either be 0 or 1. Over all possible choices of the values at the leaves, the maximum possible value of the expression represented by the tree is ___. 


Solution:

at left  leafs
+   -----> (1,1)=2         intermediate + ------->  2-(-1)=3    -  -------->(0,1)=-1
at right leafs
-  minus ------->(1,0)=1       intermediate   +    ------> 1+2=3 +     ------------->(1,1)=2
at root   + -------> 3+3=6

QUESTION: 3

Which one of the following grammars is free from left recursion?

Solution:


Option (b) is free from left recursion. No direct left recursion. No indirect left recursion.

QUESTION: 4

The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is _______.

Solution:
QUESTION: 5

Which of the following features cannot be captured by context-free grammars?

Solution:

Since CFG's are used to show syntactic rules while designing compiler, and syntactic rules don't check for meaningful things such as if a variable has been declared before its use or not. Such things are meant to be handled by Semantic Analysis phase (requires power of a context sensitive grammar).
For D, a regular expression does not restrict the string length. Languages have restriction for variable name length for storing purpose like in symbol table.
For A, if then else is inherently ambiguous. But CFG can represent inherently ambiguous languages just that there are more than one parse trees possible for some strings.

QUESTION: 6

Consider a grammar with the following productions

The above grammar is:

Solution:

S∝ ->

This violates the conditions of context-free and hence the grammar becomes context-sensitive.

QUESTION: 7

The grammar whose productions are

-> if id then <stmt>

-> if id then <stmt> else <stmt>

-> id := id

is ambiguous because

Solution:

 if a then if b then c: = d else c:= f  has two parse trees as follows:

1. if a then (if b then c:= d) else c:= f 2. and if a then (if b then c:=d else c:= f)

QUESTION: 8

In the following grammar

Which of the following is true?

Solution:

It will be A. For multiple ' ', the derivation is possible only via ' ' which is on left side of ' ' in the production. Hence it is left associative. 

For multiple '* ', the derivation is possible only via '* ' which is on the right side of ' ' in the production. Hence it is right associative. 

If both left and right derivations were possible, the grammar would have been ambiguous and we couldn't have given associativity.

QUESTION: 9

A grammar that is both left and right recursive for a non-terminal, is

Solution:

Let grammar is like this :


This grammar is left as well as right recursive but still unambiguous.. A is useless production but still part of grammar..
A grammar having both left as well as right recursion may or may not be ambiguous ..

Let's take a grammar say 

Now, according to the link https://en.wikipedia.org/wiki/Formal_grammar

For a grammar G, if we have L(G) then all the strings/sentences in this language can be produced after some finite number of steps .

But, for the grammar

Can we produce any string after a finite number of steps ? NO, and hence language of this grammar is empty set {} .

Hence, If a grammar is having both left and right recursion, then grammar may or may not be ambiguous .

QUESTION: 10

Given the following expression grammar:

Which of the following is true?

Solution:

Operator which is at lower level in the grammar is termed to have higher precedence.

QUESTION: 11

Which of the following statements is false?

Solution:

(A) We can not have different Left Most Derivation and Right Most Derivation parse trees BUT we can certainly have different LMD and RMD for a given string.(LMD and RMD here refers to the order of various productions used for derivation which could be different.)

(D) is wrong w.r.t. question because IT IS TRUE that any LR(k) IS NEVER AMBIGUOUS and so an ambiguous can never be an LR(K) for any k, no matter how large k becomes.

(B) and (C) can not be the answer because LL(1) is TOP-DOWN parser and LALR is powerful than SLR. So both are TRUE.

QUESTION: 12

Consider the grammar shown below

S → i E t S S’ | a
S’ → e S | ε
E → b

In the predictive parse table, M, of this grammar, the entries M[S’ , e] and M[S’ , $] respectively are

Solution:

QUESTION: 13

Consider the translation scheme shown below.

Here num is a token that represents an integer and num.val represents the corresponding integer value. For an input string ‘9 + 5 + 2’, this translation scheme will print

Solution:
QUESTION: 14

Consider the grammar with the following translation rules and E as the start symbol

                           

                           

Compute E.value for the root of the parse tree for the expression:2 # 3 & 5 # 6 & 4

Solution:

we can do in simple manner ...

here # is multiplication and & is addition by semantics rules given in the question ...

and by observation of productions ..

1. here &(+) is higher precedence than #(*). bcoz & is far from starting symbol ...

2. and both &,# are left associative so we can solve the express in this way ...

((2*(3+5))*(6+4)) =160 so ans should be (C).

QUESTION: 15

Which of the following grammar rules violate the requirements of an operator grammar? P, Q, R are nonterminals, and r, s, t are terminals.

Solution:

because operator grammer  does not contain  1)  nullable variable  2) 2 adjacent non-terminal on rhs of production

QUESTION: 16

Consider the following grammar G:

Let Na(ω) and Nb(ω)  denote the number of a’s and b’s in a string ω respectively.

Solution:

above CFG generate string b, aaa.. b will eliminate options A and D aaa eliminate options B.
C is answer i.e. number of a = 3k, k =0,1,2....

QUESTION: 17

Consider the grammar:

For a sentence , the handles in the right-sentential form of the reduction are:

Solution:

n+n*n

E+n*n

E*n

E

string in red indicates handle here

QUESTION: 18

Consider the following statements about the context free grammar

I. G is ambiguous
II. G produces all strings with equal number of a's and b's
III. G can be accepted by a deterministic PDA

Which combination below expresses all the true statements about ?

Solution:

1.G is ambiguous. E.g. the string  has multiple derivation trees like

II. False.  does not produce all strings with equal no. of `s and `s. ( cannot be generated).

III. True. The given grammar G generates the language , which is Regular and therefore also DCFL. So, a DPDA can be designed for G .

QUESTION: 19

Which one of the following grammars generates the language 

Solution:

as A will generate a or aa or aaa... i,e a+ ,  so S→ AC will generate a+anbn , i.e aibj i>j

QUESTION: 20

Consider the grammar with non-terminals N= {S,C,S1} terminals T = {a,b,i,t,e} with S as the start symbol, and the following set of rules:

The grammar is NOT LL(1) because:

Solution:

here, we can expand any one of S1  to ∈  and other to , but which one will it be need not matter, coz in the end we will still get the same string.

this means that the Grammar is Ambiguous. LL(1) cannot be ambiguous. Here's a Proof for that.