Recent questions

0 votes

0 answers

1

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.

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 16 views

0 votes

0 answers

2

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.

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 5 views

0 votes

0 answers

3

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).

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 2 views

0 votes

0 answers

4

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.

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 4 views

+1 vote

0 answers

5

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

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 2 views

0 votes

0 answers

6

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?

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 1 view

0 votes

1 answer

7

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).

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 4 views

0 votes

1 answer

8

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).

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 10 views

0 votes

0 answers

9

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.

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 1 view

0 votes

0 answers

10

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)$.

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 1 view

0 votes

0 answers

11

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$.

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 2 views

0 votes

0 answers

12

Ullman (Compiler Design) Edition 2 Exercise 4.6 Question 9 (Page No. 259)
The following is an ambiguous grammar: $S\rightarrow AS\mid b$ $A\rightarrow SA\mid a$ Construct for this grammar its collection of sets of $LR(0)$ items. If we try to build an LR-parsing table for ... choosing a possible action whenever there is a conflict. Show all the possible sequences of actions on input $abab$.

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 1 view

0 votes

0 answers

13

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.

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 1 view

0 votes

0 answers

14

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?

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 2 views

0 votes

0 answers

15

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).

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 4 views

0 votes

0 answers

16

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).

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 2 views

0 votes

0 answers

17

Ullman (Compiler Design) Edition 2 Exercise 4.6 Question 4 (Page No. 258)
For each of the (augmented) grammars of Question $4.2.2(a)-(g)$ : Construct the SLR sets of items and their GOTO function. Indicate any action conflicts in your sets of items. Construct the SLR-parsing table, if one exists.

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 1 view

0 votes

0 answers

18

Ullman (Compiler Design) Edition 2 Exercise 4.6 Question 3 (Page No. 258)
Show the actions of your parsing table from Question $4.6.2$ on the input $aa \ast a+$.

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 1 view

0 votes

0 answers

19

Ullman (Compiler Design) Edition 2 Exercise 4.6 Question 2 (Page No. 258)
Construct the SLR sets of items for the (augmented) grammar of Question $4.2.1$. Compute the GOTO function for these sets of items. Show the parsing table for this grammar. Is the grammar SLR?

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 1 view

0 votes

0 answers

20

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)$.

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 1 view

0 votes

0 answers

21

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$.

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 1 view

0 votes

0 answers

22

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++.$

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 1 view

0 votes

0 answers

23

Ullman (Compiler Design) Edition 2 Exercise 4.5 Question 1 (Page No. 240)
For the grammar $S \rightarrow 0\: S\: 1 \mid 0\: 1$ of Question $4.2.2(a)$,indicate the handle in each of the following right-sentential forms: $000111$ $00S11$

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 1 view

0 votes

0 answers

24

Ullman (Compiler Design) Edition 2 Exercise 4.4 Question 12 (Page No. 233)
In Fig. 4.24 is a grammar for certain statements. You may take $e$ and $s$ to be terminals standing for conditional expressions and "other statements," respectively. If we resolve the conflict regarding expansion of the optional "else" ... if $e$ then $s$ end while $e$ do begin $s$ ; if $e$ then $s$ ; end

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 2 views

0 votes

0 answers

25

Ullman (Compiler Design) Edition 2 Exercise 4.4 Question 11 (Page No. 233)
Modify your algorithm of Question $4.4.9$ so that it will find, for any string, the smallest number of insert, delete, and mutate errors (each error a single character) needed to turn the string into a string in the language of the underlying grammar.

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 3 views

0 votes

0 answers

26

Ullman (Compiler Design) Edition 2 Exercise 4.4 Question 10 (Page No. 233)
Show how, having filled in the table as in Question $4.4.9$, we can in $O(n)$ time recover a parse tree for $a_{1}a_{2}\cdot\cdot\cdot a_{n}$. Hint: modify the table so it records, for each nonterminal $A$ in each table entry $T_{ij}$, some pair of nonterminals in other table entries that justified putting $A$ in $T_{ij}$.

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 2 views

0 votes

0 answers

27

Ullman (Compiler Design) Edition 2 Exercise 4.4 Question 9 (Page No. 232)
Every language that has a context-free grammar can be recognized in at most $O(n^{3})$ time for strings of length $n$. A simple way to do so,called the Cocke- Younger-Kasami (or CYK) algorithm is based on dynamic programming. ... a_{l}a_{2}\cdot\cdot\cdot a_{n} is in the language?

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 2 views

0 votes

0 answers

28

Ullman (Compiler Design) Edition 2 Exercise 4.4 Question 8 (Page No. 232)
A grammar is said to be in Chomsky Normal Form (CNF) if every production is either of the form $A\rightarrow BC$ or of the form $A\rightarrow a$, where $A, B$, and $C$ are nonterminals, and a is a ... CNF grammar for the same language (with the possible exception of the empty string - no CNF grammar can generate $\epsilon$).

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 1 view

0 votes

0 answers

29

Ullman (Compiler Design) Edition 2 Exercise 4.4 Question 7 (Page No. 232)
A single production is a production whose body is a single nonterminal, i.e., a production of the form $A\rightarrow A$. Give an algorithm to convert any grammar into an $\epsilon$-free grammar, with no single productions ... (derivations of one or more steps in which $A\overset{\ast}{\Rightarrow}A$ for some nonterminal $A$).

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 2 views

0 votes

0 answers

30

Ullman (Compiler Design) Edition 2 Exercise 4.4 Question 6 (Page No. 232)
A grammar is $\epsilon$-free if no production body is $\epsilon$ (called an $\epsilon$-production). Give an algorithm to convert any grammar into an $\epsilon$-free grammar that generates the same language ( ... find all the nonterminals that are nullable, meaning that they generate $\epsilon$, perhaps by a long derivation.

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 2 views

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true

Recent Posts

Recent Blog Comments