# Recent questions tagged parsing

1
The most powerful parser is $\text{SLR}$ $\text{LALR}$ Canonical $\text{LR}$ Operator-precedence
2
$\text{YACC}$ builds up $\text{SLR}$ parsing table Canonical $\text{LR}$ parsing table $\text{LALR}$ parsing table None of these
3
Context-free grammar can be recognized by finite state automation $2$- way linear bounded automata push down automata both (B) and (C)
4
A top down parser generates Left most derivation Right most derivation Left most derivation in reverse Right most derivation in reverse
5
Implement Algorithm $3.23$, which converts a regular expression into a nondeterministic finite automaton, by an L-attributed SDD on a top-down parsable grammar. Assume that there is a token char representing any character, and that char.$lexval$ is the character it ... that is, a state never before returned by this function. Use any convenient notation to specify the transitions of the $NFA$.
1 vote
6
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 and "other statements," respectively. Build an LR parsing table for this grammar, resolving conflicts in the usual way ... your parser on the following inputs: if e then s ; if e then s end while e do begin s ; if e then s ; end
7
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\mid \cdot\cdot\cdot E\theta_{n}E\mid(E)\mid id$ ... of the tables for the two (ambiguous and unambiguous) grammars compare? What does that comparison tell you about the use of ambiguous expression grammars?
8
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).
9
Show that the following grammar $S\rightarrow Aa\mid bAc\mid dc\mid bda$ $A\rightarrow d$ is LALR(1) but not SLR(1).
10
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.
11
Repeat Exercise $4.7.1$ for each of the (augmented) grammars of Exercise $4.2.2(a)-(g)$.
12
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\neq j$ Show that: $G_{n}$, has $2n^{2}-n$ productions. $G_{n}$, has $2^{n} + n^{2} + n$ sets of $LR(0)$ items. $G_{n}$ is $SLR(1)$. What does this analysis say about how large $LR$ parsers can get?
Show that the following grammar: $S\rightarrow SA\mid A$ $A\rightarrow a$ is SLR(1) but not LL(1).
Show that the following grammar: $S\rightarrow AaAb\mid BbBa$ $A\rightarrow \epsilon$ $A\rightarrow\epsilon$ is LL(1) but not SLR(1).
For each of the (augmented) grammars of Question $4.2.2(a)-(g)$ : Construct the SLR sets of items and their GOTO function. Indicate any action conflicts in your sets of items. Construct the SLR-parsing table, if one exists.