# Recent questions tagged ullman 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
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.
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}$.
4
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?
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$).
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$).
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.
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$.
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$
10
Compute FIRST and FOLLOW for the grammar of $S\rightarrow SS + \mid SS {\ast} \mid a$
11
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)?
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$
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.
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$
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?
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?
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$
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.
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$
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.
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.
1 vote
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$
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.
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.
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.
26
The operator ^ matches the left end of a line, and \ ... operators by an equivalent expression that does not use either of these operators?
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.
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$.