menu
search
Log In
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

Subjects

Recent questions tagged ullman

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

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
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" (nonterminal stmtTail) by preferring to consume an else from the input whenever ... $s$ ; if $e$ then $s$ end while $e$ do begin $s$ ; if $e$ then $s$ ; end
asked Aug 20, 2019 in Compiler Design Lakshman Patel RJIT 49 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.
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, 2019 in Compiler Design Lakshman Patel RJIT 17 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}$.
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, 2019 in Compiler Design Lakshman Patel RJIT 25 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?
Every language that has a context-free grammar can be recognized in at most $O(n^{3})$ time for strings of length $n$ ... n_{3})$ time. Having filled in the table, how do you determine whether $a_{l}a_{2}\cdot\cdot\cdot a_{n} is in the language?
asked Aug 20, 2019 in Compiler Design Lakshman Patel RJIT 16 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$).
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 terminal. Show how to convert any grammar into a CNF grammar for the same language (with the possible exception of the empty string - no CNF grammar can generate $\epsilon$).
asked Aug 20, 2019 in Compiler Design Lakshman Patel RJIT 25 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$).
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, that generates the same language (with the possible ... that has no cycles (derivations of one or more steps in which $A\overset{\ast}{\Rightarrow}A$ for some nonterminal $A$).
asked Aug 20, 2019 in Compiler Design Lakshman Patel RJIT 16 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.
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 (with the possible exception of the empty string - no ... $\epsilon$, perhaps by a long derivation.
asked Aug 20, 2019 in Compiler Design Lakshman Patel RJIT 14 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$.
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 production $S\rightarrow a \:a$ first, then we shall ... following exercises are useful steps in the construction of a "Chomsky Normal Form" grammar from arbitrary grammars, as defined in Question $4.4.8$.
asked Aug 20, 2019 in Compiler Design Lakshman Patel RJIT 48 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$
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$ $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, 2019 in Compiler Design Lakshman Patel RJIT 47 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)?
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, 2019 in Compiler Design Lakshman Patel RJIT 24 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$
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$ $S\rightarrow +SS\mid \ast SS\mid a$ $S\rightarrow S(S)S\mid \epsilon$ ... $bterm\:\rightarrow\:bterm\:and\:bfactor\mid bfactor$ $bfactor\:\rightarrow\:not\:bfactor\mid (bexpr)\mid true\mid false$
asked Aug 20, 2019 in Compiler Design Lakshman Patel RJIT 108 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.
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, 2019 in Compiler Design Lakshman Patel RJIT 98 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 $
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$ and $L\rightarrow L,S\mid S$ ... $bterm\rightarrow bterm\:and\:bfactor\mid bfactor$ $bfactor\rightarrow not\: bfactor\mid ( bexpr )\mid true \mid false $
asked Aug 20, 2019 in Compiler Design Lakshman Patel RJIT 68 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?
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 grammars: $rexpr\rightarrow rexpr+rterm\mid rterm$ ... -down parsing? In addition to left factoring, eliminate left recursion from the original grammar. Is the resulting grammar suitable for top-down parsing?
asked Aug 20, 2019 in Compiler Design Lakshman Patel RJIT 109 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?
The grammar in Fig. $4.7$ generates declarations for a single numerical identifier; these declarations involve four different, independent properties of numbers. Generalize the grammar of Fig. $4.7$ by allowing $n$ options $A_{i}$, for some ... say about the feasibility of enforcing nonredundancy and noncontradiction among options in declarations via the syntax of the programming language?
asked Aug 17, 2019 in Compiler Design Lakshman Patel RJIT 42 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$
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 derivation of any sentence. Give an algorithm ... all productions containing useless symbols. Apply your algorithm to the grammar: $S\rightarrow 0\mid A$ $A\rightarrow AB$ $B\rightarrow 1$
asked Aug 17, 2019 in Compiler Design Lakshman Patel RJIT 29 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.
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, 2019 in Compiler Design Lakshman Patel RJIT 12 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$
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, 2019 in Compiler Design Lakshman Patel RJIT 22 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.
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 around a grammar symbol or symbols denotes that these ... is, any language that can be generated by a grammar with these extensions can be generated by a grammar without the extensions.
asked Aug 17, 2019 in Compiler Design Lakshman Patel RJIT 29 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.
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 reads the same backward as forward. The set of all ... of all strings of $0's$ and $1's$ of the form $xy$, where $x\neq y$ and $x$ and $y$ are of the same length.
asked Aug 17, 2019 in Compiler Design Lakshman Patel RJIT 39 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$
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$. $S\rightarrow S(S)S\mid \epsilon$ with string $(()())$ ... $bterm\:\rightarrow\:bterm\:and\:bfactor\mid bfactor$ $bfactor\:\rightarrow\:not\:bfactor\mid (bexpr)\mid true\mid false$
asked Aug 17, 2019 in Compiler Design Lakshman Patel RJIT 68 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.
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. Give a parse tree for the string. Is the grammar ambiguous or unambiguous? Justify your answer. Describe the language generated by this grammar.
asked Aug 7, 2019 in Compiler Design Lakshman Patel RJIT 411 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.
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 addition, the programmer may define any character, say ... meaning. Show how to express any SQL pattern as a regular expression, given that we know which character is the escape character.
asked Aug 5, 2019 in Compiler Design Lakshman Patel RJIT 41 views
0 votes
0 answers
25
Ullman (Compiler Design) Edition 2 Exercise 3.3 Question 11 (Page No. 127 - 128)
The UNIX shell command sh uses the operators in Fig. $3.9$ in filename expressions to describe sets of file names. For example, the filename expression *.o matches all filenames ending in. o; sort 1. ? matches all filenames of the form ... character. Show how sh filename expressions can be replaced by equivalent regular expressions using only the basic union, concatenation, and closure operators.
asked Aug 5, 2019 in Compiler Design Lakshman Patel RJIT 50 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?
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, 2019 in Compiler Design Lakshman Patel RJIT 36 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.
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, 2019 in Compiler Design Lakshman Patel RJIT 30 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.
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 symbol (caret) is not itself part of the class being ... . Show that for every regular expression with complemented character classes, there is an equivalent regular expression without complemented character classes.
asked Aug 5, 2019 in Compiler Design Lakshman Patel RJIT 95 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 "\.
Note that these regular expressions give all of the following symbols (operator characters) a special meaning: \ " . ^ ... it by a backslash. Thus, the regular expression \*\* also matches the string **. Write a regular expression that matches the string "\.
asked Aug 5, 2019 in Compiler Design Lakshman Patel RJIT 28 views
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$.
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 upper or lower case for the "digits" above 9). The ... (the lexical-analyzer generator that we shall discuss extensively in Section $3.5)$. The extended notation is listed in Fig.$3.8$.
asked Aug 5, 2019 in Compiler Design Lakshman Patel RJIT 48 views
Page:
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...