Register

Recent questions tagged grammar

1 1 vote
1 1 answer
2.9k
2.9k views
Ullman (Compiler Design) Edition 2 Exercise 5.4 Question 3 (Page No. 337)
The following SDT computes the value of a string of $0's$ and $1's$ interpreted as a positive, binary integer.$B\rightarrow B_{1}0\:\{B.val=2\times B_{1}.val\}\mid B_{1}1...
User Avatar
1 1 vote
1 1 answer
1.3k
1.3k views
Ullman (Compiler Design) Edition 2 Exercise 5.4 Question 2 (Page No. 336 - 337)
Rewrite the following SDT:$A\rightarrow A\{a\}B\mid AB\{b\}\mid 0$$B\rightarrow B\{c\}A\mid BA\{d\}\mid 1$ so that the underlying grammar becomes non-left-recursive. Here...
User Avatar
0 0 votes
0 0 answers
723
723 views
Ullman (Compiler Design) Edition 2 Exercise 5.4 Question 1 (Page No. 336)
We mentioned in Section $5.4.2$ that it is possible to deduce, from the LR state on the parsing stack, what grammar symbol is represented by the state. How would we disco...
User Avatar
0 0 votes
0 0 answers
1.8k
1.8k views
Ullman (Compiler Design) Edition 2 Exercise 5.3 Question 1 (Page No. 323)
Below is a grammar for expressions involving operator $+$ and integer or floating-point operands. Floating-point numbers are distinguished by having a decimal point.$E\ri...
User Avatar
0 0 votes
1 1 answer
7.4k
7.4k views
Ullman (Compiler Design) Edition 2 Exercise 5.2 Question 5 (Page No. 317)
This grammar generates binary numbers with a "decimal" point:$S\rightarrow L.L\mid L$$L\rightarrow LB\mid B$$B\rightarrow 0\mid 1$ Design an S-attributed SDD to compute $...
User Avatar
0 0 votes
0 0 answers
2.1k
2.1k views
Ullman (Compiler Design) Edition 2 Exercise 5.2 Question 4 (Page No. 317)
This grammar generates binary numbers with a "decimal" point:$S\rightarrow L.L\mid L$$L\rightarrow LB\mid B$$B\rightarrow 0\mid 1$ Design an L-attributed SDD to compute $...
User Avatar
3 3 votes
0 0 answers
771
771 views
Ullman (Compiler Design) Edition 2 Exercise 4.9 Question 4 (Page No. 297)
Write a $Yacc$ program that takes regular expressions (as defined by the grammar of Question $4.2.2(d)$, but with any single character as an argument, not just a) and p...
User Avatar
1 1 vote
0 0 answers
672
672 views
Ullman (Compiler Design) Edition 2 Exercise 4.9 Question 2 (Page No. 297)
Write a $Yacc$ program that takes lists (as defined by the grammar of Question $4.2.2(e)$, but with any single character as an element, not just $a$) and produces as outp...
User Avatar
0 0 votes
0 0 answers
432
432 views
Ullman (Compiler Design) Edition 2 Exercise 4.9 Question 3 (Page No. 297)
Write a $Yacc$ program that tells whether its input is a palindrome (sequence of characters that read the same forward and backward).
User Avatar
0 0 votes
0 0 answers
620
620 views
Ullman (Compiler Design) Edition 2 Exercise 4.9 Question 1 (Page No. 297)
Write a $Yacc$ program that takes boolean expressions as input [as given by the grammar of Question $4.2.2(g)$] and produces the truth value of the expressions.
User Avatar
2 2 votes
0 0 answers
842
842 views
Ullman (Compiler Design) Edition 2 Exercise 4.8 Question 2 (Page No. 286 - 287)
In Fig. $4.56$ is a grammar for certain statements, similar to that discussed in Question $4.4.12$. Again, $e$ and $s$ are terminals standing for conditional expressions ...
User Avatar
0 0 votes
0 0 answers
1.1k
1.1k views
Ullman (Compiler Design) Edition 2 Exercise 4.8 Question 1 (Page No. 285 - 286)
The following is an ambiguous grammar for expressions with $n$ binary, infix operators, at $n$ different levels of precedence: $E\rightarrow E\theta_{1}E\mid E\theta_{2}E...
User Avatar
0 0 votes
1 1 answer
1.1k
1.1k views
Ullman (Compiler Design) Edition 2 Exercise 4.7 Question 5 (Page No. 278)
Show that the following grammar$S\rightarrow Aa\mid bAc\mid Bc\mid bBa$$A\rightarrow d$$B\rightarrow d$is LR(1) but not LALR(1).
User Avatar
0 0 votes
1 1 answer
2.0k
2.0k views
Ullman (Compiler Design) Edition 2 Exercise 4.7 Question 4 (Page No. 278)
Show that the following grammar$S\rightarrow Aa\mid bAc\mid dc\mid bda$$A\rightarrow d$is LALR(1) but not SLR(1).
User Avatar
0 0 votes
0 0 answers
463
463 views
Ullman (Compiler Design) Edition 2 Exercise 4.7 Question 3 (Page No. 278)
For the grammar of Exercise $4.7.1$, use Algorithm $4.63$ to compute the collection of LALR sets of items from the kernels of the $LR(0)$ sets of items.
User Avatar
0 0 votes
0 0 answers
480
480 views
Ullman (Compiler Design) Edition 2 Exercise 4.7 Question 2 (Page No. 278)
Repeat Exercise $4.7.1$ for each of the (augmented) grammars of Exercise $4.2.2(a)-(g)$.
User Avatar
0 0 votes
0 0 answers
592
592 views
Ullman (Compiler Design) Edition 2 Exercise 4.7 Question 1 (Page No. 278)
Construct thecanonical LR, andLALR sets of items for the grammar $S\rightarrow S S + \mid S S \ast \mid a$ of Question $4.2.1$.
User Avatar
0 0 votes
0 0 answers
470
470 views
Ullman (Compiler Design) Edition 2 Exercise 4.6 Question 8 (Page No. 259)
We suggested that individual items could be regarded as states of a nondeterministic finite automaton, while sets of valid items are the states of a deterministic finite ...
User Avatar
0 0 votes
0 0 answers
1.3k
1.3k views
Ullman (Compiler Design) Edition 2 Exercise 4.6 Question 7 (Page No. 258)
Consider the family of grammars $G_{n}$, defined by:$S\rightarrow A_{i}b_{i}$ for $1\leq i\leq n$$A_{i} \rightarrow a_{j} A_{i}\mid a_{j}$ for $1\leq i,j\leq n$ and $i\ne...
User Avatar
0 0 votes
0 0 answers
720
720 views
Ullman (Compiler Design) Edition 2 Exercise 4.6 Question 6 (Page No. 258)
Show that the following grammar:$S\rightarrow SA\mid A$$A\rightarrow a$is SLR(1) but not LL(1).
User Avatar
2 2 votes
0 0 answers
638
638 views
Ullman (Compiler Design) Edition 2 Exercise 4.6 Question 5 (Page No. 258)
Show that the following grammar:$S\rightarrow AaAb\mid BbBa$$A\rightarrow \epsilon$$A\rightarrow\epsilon$is LL(1) but not SLR(1).
User Avatar
5 5 votes
0 0 answers
1.2k
1.2k views
Ullman (Compiler Design) Edition 2 Exercise 4.6 Question 1 (Page No. 257 - 258)
Describe all the viable prefixes for the following grammars:The grammar $S\rightarrow 0S1\mid 01$ of Question $4.2.2(a)$.The grammar $S\rightarrow SS+\mid SS\ast\mid a$ o...
User Avatar
0 0 votes
0 0 answers
479
479 views
Ullman (Compiler Design) Edition 2 Exercise 4.5 Question 3 (Page No. 241)
Give bottom-up parses for the following input strings and grammars: The input 000111 according to the grammar of $S\rightarrow 0\: S\: 1 \mid 0\: 1$.The input $aaa \ast a...
User Avatar
0 0 votes
0 0 answers
421
421 views
Ullman (Compiler Design) Edition 2 Exercise 4.5 Question 2 (Page No. 240 - 241)
Repeat Question $4.5.1$ for the grammar $S\rightarrow S\: S + \mid S\: S \ast \mid a$ of Exercise $4.2.1$ and the following right-sentential forms:$SSS+a\ast+.$$SS+a\ast ...
User Avatar
0 0 votes
0 0 answers
372
372 views
Ullman (Compiler Design) Edition 2 Exercise 4.5 Question 1 (Page No. 240)
For the grammar $S \rightarrow 0\: S\: 1 \mid 0\: 1$ of Question $4.2.2(a)$,indicate the handle in each of the following right-sentential forms:$000111$$00S11$
User Avatar
1 1 vote
0 0 answers
669
669 views
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 w...
User Avatar
0 0 votes
0 0 answers
363
363 views
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) n...
User Avatar
0 0 votes
0 0 answers
498
498 views
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$ ar...
User Avatar
0 0 votes
0 0 answers
376
376 views
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 $...
User Avatar
2 2 votes
0 0 answers
393
393 views
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 gramma...
User Avatar
Page: