search
Log In

Recent questions tagged ullman

0 votes
0 answers
1
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
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
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
0 votes
0 answers
5
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
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
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
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
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
0 votes
0 answers
12
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
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
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
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
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
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
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
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
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
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
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
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
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
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
0 votes
0 answers
27
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
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
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
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
...