The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register
|
I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged ullman
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
ullman
compiler-design
grammar
predictive-parser
descriptive
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
ullman
compiler-design
grammar
descriptive
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
ullman
compiler-design
context-free-grammars
descriptive
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
ullman
compiler-design
context-free-grammars
cyk
descriptive
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
ullman
compiler-design
cnf
grammar
descriptive
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
ullman
compiler-design
grammar
descriptive
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
ullman
compiler-design
grammar
descriptive
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
ullman
compiler-design
cnf
recursive-descent-parser
descriptive
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
ullman
compiler-design
grammar
first-follow
descriptive
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
ullman
compiler-design
grammar
first-follow
descriptive
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
ullman
compiler-design
predictive-parser
descriptive
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
ullman
compiler-design
grammar
left-recursion
descriptive
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
ullman
compiler-design
grammar
ambiguous
descriptive
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
ullman
compiler-design
regular-expressions
left-recursion
descriptive
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
ullman
compiler-design
regular-expressions
left-recursion
descriptive
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
ullman
compiler-design
grammar
descriptive
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
ullman
compiler-design
grammar
descriptive
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
ullman
compiler-design
grammar
descriptive
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
ullman
compiler-design
grammar
descriptive
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
ullman
compiler-design
descriptive
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
ullman
compiler-design
context-free-grammars
descriptive
+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
ullman
compiler-design
context-free-grammars
parse-tree
ambiguous
descriptive
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
ullman
compiler-design
context-free-grammars
parse-tree
ambiguous
descriptive
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
ullman
compiler-design
regular-expressions
descriptive
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
ullman
compiler-design
regular-expressions
descriptive
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
ullman
compiler-design
regular-expressions
descriptive
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
ullman
compiler-design
regular-expressions
descriptive
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
ullman
compiler-design
regular-expressions
descriptive
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
ullman
compiler-design
regular-expressions
descriptive
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
ullman
compiler-design
regular-expressions
descriptive
Page:
« prev
1
2
3
4
5
6
7
8
...
11
next »
Quick search syntax
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
ECIL Interview Experience
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
Follow @csegate
Recent questions tagged ullman
Recent Blog Comments
@Ayush Upadhyaya Thank you so much! ^_^
@JashanArora-No No. Don't directly say no.Think a...
@jeet-Yes, I am sorry for that.I saw ECIL Advt...
Congratulations man! A little question, please?...
Is IT eligible to apply in ECIL because they only...
50,645
questions
56,586
answers
195,787
comments
101,836
users