Recent questions tagged parsing

1
A top down parser generates Left most derivation Right most derivation Left most derivation in reverse Right most derivation in reverse
2
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
3
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
4
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?
5
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).
6
Show that the following grammar $S\rightarrow Aa\mid bAc\mid dc\mid bda$ $A\rightarrow d$ is LALR(1) but not SLR(1).
7
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.
8
Repeat Exercise $4.7.1$ for each of the (augmented) grammars of Exercise $4.2.2(a)-(g)$.
9
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?
10
Show that the following grammar: $S\rightarrow SA\mid A$ $A\rightarrow a$ is SLR(1) but not LL(1).
11
Show that the following grammar: $S\rightarrow AaAb\mid BbBa$ $A\rightarrow \epsilon$ $A\rightarrow\epsilon$ is LL(1) but not SLR(1).
12
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.
13
Show the actions of your parsing table from Question $4.6.2$ on the input $aa \ast a+$.
1 vote
14
In operator precedence parsing we have the rule that production cannot have two adjacent non-terminals or an epsilon production, so this production, S--> ab is allowed but not S--> AB, A->a and B->b, though they are giving us the same output. Why so?
15
S → aSbS /bSaS / ϵ S → aABb A→ c/ ϵ B → d/ ϵ Which of the following is LL1. Explain in details.
16
why do first sets can have epsilon symbol but follow sets don’t? P.S: I’ve a silly doubt :P
17
Use the exhaustive search parsing method to parse the string $abbbbbb$ with the grammar with productions $S\rightarrow aAB,$ $A\rightarrow bBb,$ $B\rightarrow A|\lambda.$ In general, how many rounds will be needed to parse any string $w$ in this language?
18
Can lookahead symbol be epsilon in LR(1) parsing? and pls give the LR(1) diagram for the following grammar? A->AB | a B->*AC | Cb | ∈ C->+ABc | ∈
19
is it always true or not??? STATEMENT → in LR(0) Parsing i1 is a final state,there is a shift move. it always give S/R conflict. Explain with example.
20
Which one of the following kinds of derivation is used by LR parsers? Leftmost Leftmost in reverse Rightmost Rightmost in reverse
21
Consider the grammar given below: $S \rightarrow Aa$ $A \rightarrow BD$ $B \rightarrow b \mid \epsilon$ $D \rightarrow d \mid \epsilon$ Let $a,b,d$ and $\$ be indexed as follows:$\begin{array}{|l|l|l|l|} \hline a & b & d & \$ \\ \hline 3 & 2 & 1 & ... $)$ , then the answer should be $3210$)
22
Which of the following statements is FALSE? Any DCFL has an equivalent grammar that can be parsed by a SLR(1) parser with end string delimiter Languages of grammars parsed by LR(2) parsers is a strict super set of the languages of grammars parsed by LR(1) parsers Languages of ... of grammars parsed by LL(1) parsers There is no DCFL which is not having a grammar that can be parsed by a LR(1) parser
23
Which of the following statements regarding $LR(0)$ parser is FALSE? A $LR(0)$ configurating set cannot have multiple reduce items A $LR(0)$ configurating set cannot have both shift as well as reduce items If a reduce item is present in a $LR(0)$ configurating set it cannot have any other item A $LR(0)$ parser can parse any regular grammar
24
Which of the following sentences regarding Viable prefixes is/are CORRECT? Viable prefixes is the set of prefixes of right-sentential forms that can appear on the stack of a shift-reduce parser Viable prefixes is the set of prefixes of right-sentential forms that do not extend past the end of the ... prefixes can be recognized using a DFA Only (i) Only (ii) Only (i) and (ii) (i), (ii) and (iii)
25
Which of the following is TRUE regarding LL(0) grammar? We can have a LL(0) grammar for any regular language We can have a LL(0) grammar for a regular language only if it does not contain empty string We can have a LL(0) grammar for any regular language if and only if it has prefix property We can have a LL(0) grammar for only single string languages
26
Match the following: $\begin{array}{|cc|cc|} \hline (i) &LL(1)&(A)& \text{bottom-up} \\ \hline (ii)& \text{Recursive Descent}& (B) &\text{Predictive} \\ \hline (iii) &\text{Recursive Ascent}& (C)& \text{Top-down} \\ \hline (iv) &LR(1) &(D)& \text{Deterministic CFL} \\ \hline \end{array}$ i-b; ii-c; iii-a; iv-d i-d; ii-a; iii-c; iv-d i-c; ii-b; iii-d; iv-a i-a; ii-c; iii-b; iv-d
27
If we have more than 1 parse tree,but one is LMD and other is RMD , Is Grammar Ambiguous? There are no other parse tree other than these two.