Recent questions tagged ullman - GATE Overflow

0 votes

0 answers

1

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 Aug 20 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 6 views

0 votes

0 answers

2

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 Aug 20 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 4 views

0 votes

0 answers

3

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 Aug 20 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 2 views

0 votes

0 answers

4

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 Aug 20 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 3 views

0 votes

0 answers

5

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 Aug 20 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 2 views

0 votes

0 answers

6

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 Aug 20 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 2 views

0 votes

0 answers

7

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 Aug 20 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 4 views

0 votes

0 answers

8

Ullman (Compiler Design) Edition 2 Exercise 4.4 Question 5 (Page No. 231 - 232)
The grammar $S\rightarrow a\:S\:a \mid \:a\: a$ generates all even-length strings of $a's$. We can devise a recursive-descent parser with backtrack for this grammar. If we choose to expand by ... the construction of a "Chomsky Normal Form" grammar from arbitrary grammars, as defined in Question $4.4.8$.

asked Aug 20 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 7 views

0 votes

0 answers

9

Ullman (Compiler Design) Edition 2 Exercise 4.4 Question 4 (Page No. 231)
Compute FIRST and FOLLOW for each of the grammars of $S\rightarrow 0S1\mid 01$ $S\rightarrow +SS\mid \ast SS\mid a$ $S\rightarrow S(S)S\mid \epsilon$ $S\rightarrow S+S\mid SS\mid (S)\mid S\ast\mid a$ ... $bterm\:\rightarrow\:bterm\:and\:bfactor\mid bfactor$ $bfactor\:\rightarrow\:not\:bfactor\mid (bexpr)\mid true\mid false$

asked Aug 20 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 8 views

0 votes

1 answer

10

Ullman (Compiler Design) Edition 2 Exercise 4.4 Question 3 (Page No. 231)
Compute FIRST and FOLLOW for the grammar of $S\rightarrow SS + \mid SS {\ast} \mid a$

asked Aug 20 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 11 views

0 votes

0 answers

11

Ullman (Compiler Design) Edition 2 Exercise 4.4 Question 2 (Page No. 231)
Is it possible, by modifying the grammar in any way, to construct a predictive parser for the language of $S\rightarrow SS + \mid SS {\ast} \mid a$ (postfix expressions with operand a)?

asked Aug 20 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 7 views

0 votes

0 answers

12

Ullman (Compiler Design) Edition 2 Exercise 4.4 Question 1 (Page No. 231)
For each of the following grammars, devise predictive parsers and show the parsing tables. You may left-factor and/or eliminate left-recursion from your grammars first. $S\rightarrow 0S1\mid 01$ ... $bfactor\:\rightarrow\:not\:bfactor\mid (bexpr)\mid true\mid false$

asked Aug 20 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 5 views

0 votes

0 answers

13

Ullman (Compiler Design) Edition 2 Exercise 4.3 Question 3 (Page No. 217)
The following grammar is proposed to remove the "danglingelse ambiguity" discussed in Section $4.3.2$: $stmt\rightarrow if\: expr\: then\: stmt\mid matchedstmt$ $matchedstmt \rightarrow if \:expr \:then \:matchedstmt\: else\: stmt\mid other$ Show that this grammar is still ambiguous.

asked Aug 20 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 8 views

0 votes

0 answers

14

Ullman (Compiler Design) Edition 2 Exercise 4.3 Question 2 (Page No. 216 - 217)
Repeat Exercise 4.3.1 on the following grammars: $S\rightarrow SS+\mid SS\: \ast\mid a$ $S\rightarrow 0S1\mid 01$ $S\rightarrow S ( S ) S\mid \epsilon$ $S\rightarrow (L)\mid a$ ... $bterm\rightarrow bterm\:and\:bfactor\mid bfactor$ $bfactor\rightarrow not\: bfactor\mid ( bexpr )\mid true \mid false $

asked Aug 20 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 22 views

0 votes

0 answers

15

Ullman (Compiler Design) Edition 2 Exercise 4.3 Question 1 (Page No. 216)
The following is a grammar for regular expressions over symbols $a$ and $b$ only, using $+$ in place of $\mid$ for union, to avoid conflict with the use of vertical bar as a metasymbol in ... to left factoring, eliminate left recursion from the original grammar. Is the resulting grammar suitable for top-down parsing?

asked Aug 20 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 28 views

0 votes

0 answers

16

Ullman (Compiler Design) Edition 2 Exercise 4.2 Question 8 (Page No. 208 - 209)
The grammar in Fig. $4.7$ ... of enforcing nonredundancy and noncontradiction among options in declarations via the syntax of the programming language?

asked Aug 17 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 21 views

0 votes

0 answers

17

Ullman (Compiler Design) Edition 2 Exercise 4.2 Question 7 (Page No. 208)
A grammar symbol $X$ (terminal or nonterminal) is useless if there is no derivation of the form $S \overset{\ast}{\Rightarrow} wXy\overset{\ast}{\Rightarrow} wxy$. That is, $X$ can never appear in the ... useless symbols. Apply your algorithm to the grammar: $S\rightarrow 0\mid A$ $A\rightarrow AB$ $B\rightarrow 1$

asked Aug 17 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 8 views

0 votes

0 answers

18

Ullman (Compiler Design) Edition 2 Exercise 4.2 Question 6 (Page No. 208)
Extend the idea of Question $4.2.4$ to allow any regular expression of grammar symbols in the body of a production. Show that this extension does not allow grammars to define any new languages.

asked Aug 17 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 3 views

0 votes

0 answers

19

Ullman (Compiler Design) Edition 2 Exercise 4.2 Question 5 (Page No. 208)
Use the braces described in Question $4.2.4$ to simplify the following grammar for statement blocks and conditional statements: $stmt\rightarrow if\: expr\:then\:stmt\:else\:stmt$ $\mid if \: stmt \: then \: stmt$ $\mid begin\: stmtList\: end$ $stmtList\rightarrow stmt;stmtList\mid stmt$

asked Aug 17 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 4 views

0 votes

0 answers

20

Ullman (Compiler Design) Edition 2 Exercise 4.2 Question 4 (Page No. 207 - 208)
There is an extended grammar notation in common use. In this notation, square and curly braces in production bodies are metasymbols (like $\rightarrow$ or $\mid$) with the following meanings: Square braces ... can be generated by a grammar with these extensions can be generated by a grammar without the extensions.

asked Aug 17 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 2 views

0 votes

0 answers

21

Ullman (Compiler Design) Edition 2 Exercise 4.2 Question 3 (Page No. 207)
Design grammars for the following languages: The set of all strings of $0's$ and $1's$ such that every $0$ is immediately followed by at least one $1$. The set of all strings of $0's$ and $1's$ that are palindromes; that is, the string ... $1's$ of the form $xy$, where $x\neq y$ and $x$ and $y$ are of the same length.

asked Aug 17 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 4 views

+1 vote

0 answers

22

Ullman (Compiler Design) Edition 2 Exercise 4.2 Question 2 (Page No. 206 - 207)
Repeat Question $4.2.1$ for each of the following grammars and strings: $S\rightarrow 0S1\mid 01$ with string $000111$. $S\rightarrow +SS\mid \ast SS\mid a$ with string $+\ast aaa$ ... $bfactor\:\rightarrow\:not\:bfactor\mid (bexpr)\mid true\mid false$

asked Aug 17 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 11 views

0 votes

1 answer

23

Ullman (Compiler Design) Edition 2 Exercise 4.2 Question 1 (Page No. 206)
Consider the context-free grammar:$S\rightarrow SS + \mid SS {\ast} \mid a$and the string $aa + a{\ast}$. Give a leftmost derivation for the string. Give a rightmost derivation for the string. ... for the string. Is the grammar ambiguous or unambiguous? Justify your answer. Describe the language generated by this grammar.

asked Aug 7 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 42 views

0 votes

0 answers

24

Ullman (Compiler Design) Edition 2 Exercise 3.3 Question 12 (Page No. 128)
SQL allows a rudimentary form of patterns in which two characters have special meaning: underscore (_) stands for any one character and percent-sign (%) stands for any string of $0$ or more characters. In ... to express any SQL pattern as a regular expression, given that we know which character is the escape character.

asked Aug 5 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 19 views

0 votes

0 answers

25

Ullman (Compiler Design) Edition 2 Exercise 3.3 Question 11 (Page No. 127 - 128)

asked Aug 5 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 17 views

0 votes

0 answers

26

Ullman (Compiler Design) Edition 2 Exercise 3.3 Question 10 (Page No. 127)
The operator ^ matches the left end of a line, and \ ... operators by an equivalent expression that does not use either of these operators?

asked Aug 5 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 13 views

0 votes

0 answers

27

Ullman (Compiler Design) Edition 2 Exercise 3.3 Question 9 (Page No. 127)
The regular expression $r\{m, n\}$ matches from $m$ to $n$ occurrences of the pattern $r$. For example, $a [1, 5]$ matches a string of one to five a's. Show that for every regular expression containing repetition operators of this form, there is an equivalent regular expression without repetition operators.

asked Aug 5 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 8 views

0 votes

0 answers

28

Ullman (Compiler Design) Edition 2 Exercise 3.3 Question 8 (Page No. 126 - 127)
In Lex, a complemented character class represents any character except the ones listed in the character class. We denote a complemented class by using ^ as the first character; this ... expression with complemented character classes, there is an equivalent regular expression without complemented character classes.

asked Aug 5 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 4 views

0 votes

0 answers

29

Ullman (Compiler Design) Edition 2 Exercise 3.3 Question 7 (Page No. 126)
Note that these regular expressions give all of the following symbols (operator characters) a special meaning: \ " . ^ ... the regular expression \*\* also matches the string **. Write a regular expression that matches the string "\.

asked Aug 5 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 1 view

0 votes

0 answers

30

Ullman (Compiler Design) Edition 2 Exercise 3.3 Question 6 (Page No. 126)
Write character classes for the following sets of characters: The first ten letters (up to "j" ) in either upper or lower case. The lowercase consonants. The "digits" in a hexadecimal number (choose either ... we shall discuss extensively in Section $3.5)$. The extended notation is listed in Fig.$3.8$.

asked Aug 5 in Compiler Design by Lakshman Patel RJIT Veteran (55k points) | 3 views

Page:

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

Recent questions tagged ullman

50,645 questions

56,586 answers

195,787 comments

101,836 users