Recent questions tagged grammar

3 votes

3 answers

31

ISRO2020-35
Given the grammar $s \rightarrow T ^{\ast} S\ \mid T$ $T \rightarrow U+T\ \mid U$ $U \rightarrow a \mid b$ Which of the following statements is wrong? Grammar is not ambiguous Priority of $+$ over $^{\ast}$ is ensured Right to left evaluation of $^{\ast}$ and $+$ happens None of these

Given the grammar$s \rightarrow T ^{\ast} S\ \mid T$$T \rightarrow U+T\ \mid U$$U \rightarrow a \mid b$Which of the following statements is wrong?Grammar is not ambiguou...

3.8k views

Satbir asked Jan 13, 2020

1 votes

3 answers

32

ISRO2020-75
A grammar is defined as $A \rightarrow BC$ $B \rightarrow x \mid Bx$ $C \rightarrow B \mid D$ $D \rightarrow y \mid Ey$ $E \rightarrow z$ The non terminal alphabet of the grammar is $\{A,B,C,D,E\}$ $\{B,C,D,E\}$ $\{A,B,C,D,E,x,y,z\}$ $\{x,y,z\}$

A grammar is defined as$A \rightarrow BC$$B \rightarrow x \mid Bx$$C \rightarrow B \mid D$$D \rightarrow y \mid Ey$$E \rightarrow z$The non terminal alphabet of the gram...

2.3k views

Satbir asked Jan 13, 2020

0 votes

0 answers

33

Ullman (Compiler Design) Edition 2 Exercise 5.4 Question 7 (Page No. 337)
Modify the SDD of Fig. $5.25$ to include superscripts denoted by operator sup between boxes. If box $B_{2}$ is a superscript of box $B_{1}$, then position the baseline of $B_{2}\:0.6$ times the point size of $B_{1}$ above the baseline of $B_{1}.\text{Add}$ the new production and rules to the SDT of Fig. $5.26$.

Modify the SDD of Fig. $5.25$ to include superscripts denoted by operator sup between boxes. If box $B_{2}$ is a superscript of box $B_{1}$, then position the baseline of...

605 views

admin asked Sep 6, 2019

0 votes

0 answers

34

Ullman (Compiler Design) Edition 2 Exercise 5.4 Question 6 (Page No. 337)
Modify the SDD of Fig. $5.25$ to include a synthesized attribute $B.le$, the length of a box. The length of the concatenation of two boxes is the sum of the lengths of each. Then add your new rules to the proper positions in the SDT of Fig. $5.26$.

Modify the SDD of Fig. $5.25$ to include a synthesized attribute $B.le$, the length of a box. The length of the concatenation of two boxes is the sum of the lengths of ea...

635 views

admin asked Sep 6, 2019

0 votes

0 answers

35

Ullman (Compiler Design) Edition 2 Exercise 5.4 Question 5 (Page No. 337)
Write L-attributed SDT's analogous to that of Example $5.19$ for the following productions, each of which represents a familiar flow-of-control construct, as in the programming language C. You may need to ... middle to the next statement, so it is not sufficient simply to generate code for each statement in order.

Write L-attributed SDT's analogous to that of Example $5.19$ for the following productions, each of which represents a familiar flow-of-control construct, as in the progr...

482 views

admin asked Sep 6, 2019

0 votes

0 answers

36

Ullman (Compiler Design) Edition 2 Exercise 5.4 Question 4 (Page No. 337)
Write L-attributed SDD's analogous to that of Example $5.19$ for the following productions, each of which represents a familiar flow-of-control construct, as in the programming language C. You may need to ... middle to the next statement, so it is not sufficient simply to generate code for each statement in order.

Write L-attributed SDD's analogous to that of Example $5.19$ for the following productions, each of which represents a familiar flow-of-control construct, as in the progr...

450 views

admin asked Sep 6, 2019

1 votes

1 answer

37

Ullman (Compiler Design) Edition 2 Exercise 5.4 Question 3 (Page No. 337)
The following SDT computes the value of a string of $0's$ and $1's$ ... so the underlying grammar is not left recursive, and yet the same value of $B.val$ is computed for the entire input string.

The following SDT computes the value of a string of $0's$ and $1's$ interpreted as a positive, binary integer.$B\rightarrow B_{1}0\:\{B.val=2\times B_{1}.val\}\mid B_{1}1...

2.1k views

admin asked Sep 6, 2019

1 votes

1 answer

38

Ullman (Compiler Design) Edition 2 Exercise 5.4 Question 2 (Page No. 336 - 337)
Rewrite the following SDT: $A\rightarrow A\{a\}B\mid AB\{b\}\mid 0$ $B\rightarrow B\{c\}A\mid BA\{d\}\mid 1$ so that the underlying grammar becomes non-left-recursive. Here, $a, b, c$, and $d$ are actions, and $0$ and $1$ are terminals.

Rewrite the following SDT:$A\rightarrow A\{a\}B\mid AB\{b\}\mid 0$$B\rightarrow B\{c\}A\mid BA\{d\}\mid 1$ so that the underlying grammar becomes non-left-recursive. Here...

789 views

admin asked Sep 6, 2019

0 votes

0 answers

39

Ullman (Compiler Design) Edition 2 Exercise 5.4 Question 1 (Page No. 336)
We mentioned in Section $5.4.2$ that it is possible to deduce, from the LR state on the parsing stack, what grammar symbol is represented by the state. How would we discover this information?

We mentioned in Section $5.4.2$ that it is possible to deduce, from the LR state on the parsing stack, what grammar symbol is represented by the state. How would we disco...

510 views

admin asked Sep 6, 2019

0 votes

0 answers

40

Ullman (Compiler Design) Edition 2 Exercise 5.3 Question 1 (Page No. 323)
Below is a grammar for expressions involving operator $+$ and integer or floating-point operands. Floating-point numbers are distinguished by having a decimal point. $E\rightarrow E+T\mid T$ ... translate expressions into postfix notation.Use the unary operator intToFloat to turn an integer into an equivalent float.

Below is a grammar for expressions involving operator $+$ and integer or floating-point operands. Floating-point numbers are distinguished by having a decimal point.$E\ri...

1.4k views

admin asked Sep 6, 2019

0 votes

1 answer

41

Ullman (Compiler Design) Edition 2 Exercise 5.2 Question 5 (Page No. 317)
This grammar generates binary numbers with a "decimal" point: $S\rightarrow L.L\mid L$ $L\rightarrow LB\mid B$ $B\rightarrow 0\mid 1$ Design an S-attributed SDD to compute $S.val$, the decimal-number value of an input string. For example, the translation of string $101.101$ should be the decimal number $5.625$.

This grammar generates binary numbers with a "decimal" point:$S\rightarrow L.L\mid L$$L\rightarrow LB\mid B$$B\rightarrow 0\mid 1$ Design an S-attributed SDD to compute $...

5.5k views

admin asked Sep 6, 2019

0 votes

0 answers

42

Ullman (Compiler Design) Edition 2 Exercise 5.2 Question 4 (Page No. 317)
This grammar generates binary numbers with a "decimal" point: $S\rightarrow L.L\mid L$ $L\rightarrow LB\mid B$ $B\rightarrow 0\mid 1$ Design an L-attributed SDD to compute $S.val$, the decimal-number value of ... $L.side$ that tells which side of the decimal point a bit is on.

This grammar generates binary numbers with a "decimal" point:$S\rightarrow L.L\mid L$$L\rightarrow LB\mid B$$B\rightarrow 0\mid 1$ Design an L-attributed SDD to compute $...

1.6k views

admin asked Sep 6, 2019

3 votes

0 answers

43

Ullman (Compiler Design) Edition 2 Exercise 4.9 Question 4 (Page No. 297)
Write a $Yacc$ program that takes regular expressions (as defined by the grammar of Question $4.2.2(d)$, but with any single character as an argument, not just a) and produces as output a transition table for a nondeterministic finite automaton recognizing the same language.

Write a $Yacc$ program that takes regular expressions (as defined by the grammar of Question $4.2.2(d)$, but with any single character as an argument, not just a) and p...

591 views

admin asked Aug 20, 2019

1 votes

0 answers

44

Ullman (Compiler Design) Edition 2 Exercise 4.9 Question 2 (Page No. 297)
Write a $Yacc$ program that takes lists (as defined by the grammar of Question $4.2.2(e)$, but with any single character as an element, not just $a$) and produces as output a linear representation of the same list; i.e., a single list of the elements, in the same order that they appear in the input.

Write a $Yacc$ program that takes lists (as defined by the grammar of Question $4.2.2(e)$, but with any single character as an element, not just $a$) and produces as outp...

489 views

admin asked Aug 20, 2019

0 votes

0 answers

45

Ullman (Compiler Design) Edition 2 Exercise 4.9 Question 3 (Page No. 297)
Write a $Yacc$ program that tells whether its input is a palindrome (sequence of characters that read the same forward and backward).

Write a $Yacc$ program that tells whether its input is a palindrome (sequence of characters that read the same forward and backward).

305 views

admin asked Aug 20, 2019

0 votes

0 answers

46

Ullman (Compiler Design) Edition 2 Exercise 4.9 Question 1 (Page No. 297)
Write a $Yacc$ program that takes boolean expressions as input [as given by the grammar of Question $4.2.2(g)$] and produces the truth value of the expressions.

Write a $Yacc$ program that takes boolean expressions as input [as given by the grammar of Question $4.2.2(g)$] and produces the truth value of the expressions.

438 views

admin asked Aug 20, 2019

2 votes

0 answers

47

Ullman (Compiler Design) Edition 2 Exercise 4.8 Question 2 (Page No. 286 - 287)
In Fig. $4.56$ is a grammar for certain statements, similar to that discussed in Question $4.4.12$. Again, $e$ and $s$ are terminals standing for conditional expressions and "other statements," respectively. Build an LR parsing ... inputs: if e then s ; if e then s end while e do begin s ; if e then s ; end

In Fig. $4.56$ is a grammar for certain statements, similar to that discussed in Question $4.4.12$. Again, $e$ and $s$ are terminals standing for conditional expressions ...

585 views

admin asked Aug 20, 2019

0 votes

0 answers

48

Ullman (Compiler Design) Edition 2 Exercise 4.8 Question 1 (Page No. 285 - 286)
The following is an ambiguous grammar for expressions with $n$ binary, infix operators, at $n$ ... ambiguous and unambiguous) grammars compare? What does that comparison tell you about the use of ambiguous expression grammars?

The following is an ambiguous grammar for expressions with $n$ binary, infix operators, at $n$ different levels of precedence: $E\rightarrow E\theta_{1}E\mid E\theta_{2}E...

704 views

admin asked Aug 20, 2019

0 votes

1 answer

49

Ullman (Compiler Design) Edition 2 Exercise 4.7 Question 5 (Page No. 278)
Show that the following grammar $S\rightarrow Aa\mid bAc\mid Bc\mid bBa$ $A\rightarrow d$ $B\rightarrow d$ is LR(1) but not LALR(1).

Show that the following grammar$S\rightarrow Aa\mid bAc\mid Bc\mid bBa$$A\rightarrow d$$B\rightarrow d$is LR(1) but not LALR(1).

762 views

admin asked Aug 20, 2019

0 votes

1 answer

50

Ullman (Compiler Design) Edition 2 Exercise 4.7 Question 4 (Page No. 278)
Show that the following grammar $S\rightarrow Aa\mid bAc\mid dc\mid bda$ $A\rightarrow d$ is LALR(1) but not SLR(1).

Show that the following grammar$S\rightarrow Aa\mid bAc\mid dc\mid bda$$A\rightarrow d$is LALR(1) but not SLR(1).

1.5k views

admin asked Aug 20, 2019

0 votes

0 answers

51

Ullman (Compiler Design) Edition 2 Exercise 4.7 Question 3 (Page No. 278)
For the grammar of Exercise $4.7.1$, use Algorithm $4.63$ to compute the collection of LALR sets of items from the kernels of the $LR(0)$ sets of items.

For the grammar of Exercise $4.7.1$, use Algorithm $4.63$ to compute the collection of LALR sets of items from the kernels of the $LR(0)$ sets of items.

283 views

admin asked Aug 20, 2019

0 votes

0 answers

52

Ullman (Compiler Design) Edition 2 Exercise 4.7 Question 2 (Page No. 278)
Repeat Exercise $4.7.1$ for each of the (augmented) grammars of Exercise $4.2.2(a)-(g)$.

Repeat Exercise $4.7.1$ for each of the (augmented) grammars of Exercise $4.2.2(a)-(g)$.

315 views

admin asked Aug 20, 2019

0 votes

0 answers

53

Ullman (Compiler Design) Edition 2 Exercise 4.7 Question 1 (Page No. 278)
Construct the canonical LR, and LALR sets of items for the grammar $S\rightarrow S S + \mid S S \ast \mid a$ of Question $4.2.1$.

Construct thecanonical LR, andLALR sets of items for the grammar $S\rightarrow S S + \mid S S \ast \mid a$ of Question $4.2.1$.

366 views

admin asked Aug 20, 2019

0 votes

0 answers

54

Ullman (Compiler Design) Edition 2 Exercise 4.6 Question 8 (Page No. 259)
We suggested that individual items could be regarded as states of a nondeterministic finite automaton, while sets of valid items are the states of a deterministic finite automaton (see the box on "Items as States of an NFA" ... the NFA that comes from the valid items for a grammar produces the $LR(0)$ sets of items.

We suggested that individual items could be regarded as states of a nondeterministic finite automaton, while sets of valid items are the states of a deterministic finite ...

275 views

admin asked Aug 20, 2019

0 votes

0 answers

55

Ullman (Compiler Design) Edition 2 Exercise 4.6 Question 7 (Page No. 258)
Consider the family of grammars $G_{n}$, defined by: $S\rightarrow A_{i}b_{i}$ for $1\leq i\leq n$ $A_{i} \rightarrow a_{j} A_{i}\mid a_{j}$ for $1\leq i,j\leq n$ and $i\neq j$ Show that: $G_{n}$ ... $LR(0)$ items. $G_{n}$ is $SLR(1)$. What does this analysis say about how large $LR$ parsers can get?

Consider the family of grammars $G_{n}$, defined by:$S\rightarrow A_{i}b_{i}$ for $1\leq i\leq n$$A_{i} \rightarrow a_{j} A_{i}\mid a_{j}$ for $1\leq i,j\leq n$ and $i\ne...

1.1k views

admin asked Aug 20, 2019

0 votes

0 answers

56

Ullman (Compiler Design) Edition 2 Exercise 4.6 Question 6 (Page No. 258)
Show that the following grammar: $S\rightarrow SA\mid A$ $A\rightarrow a$ is SLR(1) but not LL(1).

Show that the following grammar:$S\rightarrow SA\mid A$$A\rightarrow a$is SLR(1) but not LL(1).

467 views

admin asked Aug 20, 2019

2 votes

0 answers

57

Ullman (Compiler Design) Edition 2 Exercise 4.6 Question 5 (Page No. 258)
Show that the following grammar: $S\rightarrow AaAb\mid BbBa$ $A\rightarrow \epsilon$ $A\rightarrow\epsilon$ is LL(1) but not SLR(1).

Show that the following grammar:$S\rightarrow AaAb\mid BbBa$$A\rightarrow \epsilon$$A\rightarrow\epsilon$is LL(1) but not SLR(1).

370 views

admin asked Aug 20, 2019

5 votes

0 answers

58

Ullman (Compiler Design) Edition 2 Exercise 4.6 Question 1 (Page No. 257 - 258)
Describe all the viable prefixes for the following grammars: The grammar $S\rightarrow 0S1\mid 01$ of Question $4.2.2(a)$. The grammar $S\rightarrow SS+\mid SS\ast\mid a$ of Question $4.2.1$. The grammar $S\rightarrow S(S)\mid \epsilon$ of Question $4.2.2(c)$.

Describe all the viable prefixes for the following grammars:The grammar $S\rightarrow 0S1\mid 01$ of Question $4.2.2(a)$.The grammar $S\rightarrow SS+\mid SS\ast\mid a$ o...

814 views

admin asked Aug 20, 2019

0 votes

0 answers

59

Ullman (Compiler Design) Edition 2 Exercise 4.5 Question 3 (Page No. 241)
Give bottom-up parses for the following input strings and grammars: The input 000111 according to the grammar of $S\rightarrow 0\: S\: 1 \mid 0\: 1$. The input $aaa \ast a + + $according to the grammar of $S\rightarrow S S + \mid SS \ast \mid a$.

Give bottom-up parses for the following input strings and grammars: The input 000111 according to the grammar of $S\rightarrow 0\: S\: 1 \mid 0\: 1$.The input $aaa \ast a...

258 views

admin asked Aug 20, 2019

0 votes

0 answers

60

Ullman (Compiler Design) Edition 2 Exercise 4.5 Question 2 (Page No. 240 - 241)
Repeat Question $4.5.1$ for the grammar $S\rightarrow S\: S + \mid S\: S \ast \mid a$ of Exercise $4.2.1$ and the following right-sentential forms: $SSS+a\ast+.$ $SS+a\ast a+.$ $aaa\ast a++.$

Repeat Question $4.5.1$ for the grammar $S\rightarrow S\: S + \mid S\: S \ast \mid a$ of Exercise $4.2.1$ and the following right-sentential forms:$SSS+a\ast+.$$SS+a\ast ...

281 views

admin asked Aug 20, 2019

Page:

« prev
1
2
3
4
5
6
7
...
15
next »