Recent questions tagged parsing / GATE Overflow for GATE CSE

2 votes

2 answers

631

how to solve it??
Consider the following LL(1) grammar. E → TE′ E′ → + E|ε T → FT′ T′ → T|ε F → GF′ F′ → *F′|ε G → (E)|a|b|c Initially stack contains two symbols. Bottom of stack symbol is $ and top of stack (above $) symbol is E where E is start symbol of the grammar. The number of symbols on the stack after the sixth action taken by LL(1) parser to parse the input “ab*” are ______.

Consider the following LL(1) grammar.E → TE′E′ → + E|εT → FT′T′ → T|εF → GF′F′ → *F′|εG → (E)|a|b|cInitially stack contains two symbols. Bo...

Hira Thakur

4.2k views

Hira Thakur asked Nov 16, 2015

16 votes

2 answers

632

TIFR CSE 2012 | Part B | Question: 17
Which of the following correctly describes $\text{LR}(k)$ parsing? The input string is alternately scanned left to right and right to left with $k$ reversals. Input string is scanned once left to right with rightmost derivation and $k$ symbol ... string is scanned from left to right once with $k$ symbol to the right as look-ahead to give left-most derivation.

Which of the following correctly describes $\text{LR}(k)$ parsing?The input string is alternately scanned left to right and right to left with $k$ reversals.Input string ...

makhdoom ghaya

2.5k views

makhdoom ghaya asked Nov 2, 2015

19 votes

2 answers

633

TIFR CSE 2012 | Part B | Question: 8
Consider the parse tree Assume that $*$ has higher precedence than $+$, $-$ and operators associate right to left (i.e $(a + b + c= (a + (b + c)))$. Consider $2 + a - b$ $2 + a - b * a + b$ ... The parse tree corresponds to Expression (i) Expression (ii) Expression (iv) only Expression (ii), (iii), and (iv) Expression (iii) and (iv) only

Consider the parse treeAssume that $*$ has higher precedence than $+$, $-$ and operators associate right to left (i.e $(a + b + c= (a + (b + c)))$. Consider$2 + a - b$$2 ...

makhdoom ghaya

2.7k views

makhdoom ghaya asked Oct 31, 2015

4 votes

1 answer

634

Given a left recursive grammar. Whether LL(1) or not?
Do we directly say it is not LL(1) because it is left recursive or do we eliminate the left recursion, create the parsing table and then make a decision.

Do we directly say it is not LL(1) because it is left recursive or do we eliminate the left recursion, create the parsing table and then make a decision.

Akshay Jindal

3.6k views

Akshay Jindal asked Oct 19, 2015

3 votes

2 answers

635

Find out the number of rightmost derivations
Why only one derivation?? S-> E -> E+E -> E+a -> a+a S-> E+E -> E+a -> a+a Are these two derivations possible??

Why only one derivation?? S- E - E+E - E+a - a+a S- E+E - E+a - a+aAre these two derivations possible??

Sara

734 views

Sara asked Oct 18, 2015

8 votes

4 answers

636

ISRO2014-5
What is the number of steps required to derive the string $((()\; ())\; ())$ for the following grammar? $S \to SS$ $S \to (S)$ $S \to \varepsilon$ $10$ $12$ $15$ $16$

What is the number of steps required to derive the string $((()\; ())\; ())$ for the following grammar?$S \to SS$$S \to (S)$$S \to \varepsilon$ $10$ $12$ ...

ajit

9.3k views

ajit asked Sep 20, 2015

1 votes

2 answers

637

Which type of conflict is present ?
Hi , I am confused about this grammar . I can find there is one SR conflict , please clarify. S -> Aa | bAc | dc | bda A -> d Here , it is not LL1 as A -> bAc and S -> bda both need to placed in the same cell. Also , should I say that S -> Aa and A -> d are also SR conflicts as they both derive d ? And for that it is not LR(0) as well .

Hi , I am confused about this grammar .I can find there is one SR conflict , please clarify. S - Aa | bAc | dc | bdaA - d Here , it is not LL1 as A - bAc and S - bda both...

worst_engineer

1.9k views

worst_engineer asked Sep 11, 2015

2 votes

3 answers

638

SET OF VIABLE PREFIXES FOR A GIVEN SLR(1) GRAMMAR IS REGULAR LANGUAGE ?
SET OF VIABLE PREFIXES FOR A GIVEN SLR(1) GRAMMAR IS REGULAR LANGUAGE ?

SET OF VIABLE PREFIXES FOR A GIVEN SLR(1) GRAMMAR IS REGULAR LANGUAGE ?

Ankit Chourasiya

1.4k views

Ankit Chourasiya asked Sep 9, 2015

4 votes

3 answers

639

Viable Prefix

Suvam Chatterjee

2.7k views

Suvam Chatterjee asked Jul 18, 2015

2 votes

6 answers

640

Why is left recursion not a problem for bottom up parsers?
I know the parsing logic of bottom up parsers, that they start from the terminal and reduce it to the start symbol. But what really confuses me is the construction of LR(0)/LR(1) sets : Eg : S->Sa|a Then in LR(0) set : ... is in front of S , so shouldn't the S production be generated again and again and make it go to an inf. loop?

I know the parsing logic of bottom up parsers, that they start from the terminal and reduce it to the start symbol. But what really confuses me is the construction of LR(...

prasitamukherjee

10.5k views

prasitamukherjee asked Jul 16, 2015

0 votes

2 answers

641

Bottom up and top down parser's ?
q. 23 : can anyone explain why both statements are false? I thought option B is correct?

q. 23 : can anyone explain why both statements are false? I thought option B is correct?

prasitamukherjee

879 views

prasitamukherjee asked Jul 16, 2015

45 votes

5 answers

642

GATE CSE 2015 Set 3 | Question: 31
Consider the following grammar G $S \rightarrow F \mid H$ $F \rightarrow p \mid c$ $H \rightarrow d \mid c$ Where $S$, $F$, and $H$ are non-terminal symbols, $p, d$, and $c$ are terminal symbols. Which of the following statement(s) ... grammar G S2: LR(1) can parse all strings that are generated using grammar G Only S1 Only S2 Both S1 and S2 Neither S1 and S2

Consider the following grammar G$S \rightarrow F \mid H$$F \rightarrow p \mid c$$H \rightarrow d \mid c$ Where $S$, $F$, and $H$ are non-terminal symbols, $p, d$, and $c...

go_editor

15.2k views

go_editor asked Feb 15, 2015

29 votes

2 answers

643

GATE CSE 2015 Set 3 | Question: 16
Among simple LR (SLR), canonical LR, and look-ahead LR (LALR), which of the following pairs identify the method that is very easy to implement and the method that is the most powerful, in that order? SLR, LALR Canonical LR, LALR SLR, canonical LR LALR, canonical LR

Among simple LR (SLR), canonical LR, and look-ahead LR (LALR), which of the following pairs identify the method that is very easy to implement and the method that is the ...

go_editor

8.5k views

go_editor asked Feb 14, 2015

53 votes

2 answers

644

GATE CSE 2015 Set 1 | Question: 1‏3
Which one of the following is TRUE at any valid state in shift-reduce parsing? Viable prefixes appear only at the bottom of the stack and not inside Viable prefixes appear only at the top of the stack and not inside The stack contains only a set of viable prefixes The stack never contains viable prefixes

Which one of the following is TRUE at any valid state in shift-reduce parsing?Viable prefixes appear only at the bottom of the stack and not insideViable prefixes appear ...

makhdoom ghaya

19.1k views

makhdoom ghaya asked Feb 12, 2015

1 votes

2 answers

645

plz explain why b is correct?

neha pawar

491 views

neha pawar asked Dec 22, 2014

2 votes

1 answer

646

LR(K) grammer can be ambigious or not?

ansaritk

902 views

ansaritk asked Dec 17, 2014

37 votes

4 answers

647

GATE IT 2005 | Question: 83b
Consider the context-free grammar $E\rightarrow E+E$ $E\rightarrow (E *E)$ $E\rightarrow \text{id}$ where $E$ is the starting symbol, the set of terminals is $\{id, (,+,),*\}$, and the set of non-terminals is $\{E\}$. For the terminal string $id + id + id + id$, how many parse trees are possible? $5$ $4$ $3$ $2$

Consider the context-free grammar$E\rightarrow E+E$$E\rightarrow (E *E)$$E\rightarrow \text{id}$where $E$ is the starting symbol, the set of terminals is $\{id, (,+,),*\}...

Ishrat Jahan

6.9k views

Ishrat Jahan asked Nov 3, 2014

36 votes

2 answers

648

GATE IT 2005 | Question: 83a
Consider the context-free grammar $E \rightarrow E + E$ $E \rightarrow (E * E)$ $E \rightarrow id$ where $E$ is the starting symbol, the set of terminals is $\{id, (,+,),*\}$, and the set of nonterminals is $\{E\}$. Which of the following terminal strings has more than one parse tree ... $id + (id* (id * id))$ $(id* (id * id)) + id$ $((id * id + id) * id)$

Consider the context-free grammar$E \rightarrow E + E$$E \rightarrow (E * E)$$E \rightarrow id$where $E$ is the starting symbol, the set of terminals is $\{id, (,+,),*\...

Ishrat Jahan

6.5k views

Ishrat Jahan asked Nov 3, 2014

39 votes

1 answer

649

GATE IT 2008 | Question: 79
$A$ CFG $G$ is given with the following productions where $S$ is the start symbol, $A$ is a non-terminal and a and b are terminals. $S → aS \mid A$ $A → aAb \mid bAa \mid \epsilon$ For the string "$aabbaab$" how many steps are required to derive the string and how many parse trees are there? $6$ and $1$ $6$ and $2$ $7$ and $2$ $4$ and $2$

$A$ CFG $G$ is given with the following productions where $S$ is the start symbol, $A$ is a non-terminal and a and b are terminals.$S → aS \mid A$$A → aAb \mid bAa \m...

Ishrat Jahan

8.5k views

Ishrat Jahan asked Oct 29, 2014

39 votes

4 answers

650

GATE IT 2008 | Question: 78
A CFG $G$ is given with the following productions where $S$ is the start symbol, $A$ is a non-terminal and $a$ and $b$ are terminals. $S \to aS \mid A$ $A \to aAb \mid bAa \mid \epsilon$ Which of the following strings is generated by the grammar above? $aabbaba$ $aabaaba$ $abababb$ $aabbaab$

A CFG $G$ is given with the following productions where $S$ is the start symbol, $A$ is a non-terminal and $a$ and $b$ are terminals.$S \to aS \mid A$$A \to aAb \mid bAa ...

Ishrat Jahan

8.3k views

Ishrat Jahan asked Oct 29, 2014

6 votes

2 answers

651

GATE CSE 1995 | Question: 8
Construct the $\text{LL(1)}$ table for the following grammar. $Expr \rightarrow \_Expr$ $Expr \rightarrow (Expr)$ $Expr \rightarrow Var\; ExprTail$ $ExprTail \rightarrow \_Expr$ $Expr \rightarrow \lambda$ $Var \rightarrow Id\; VarTail$ $VarTail \rightarrow (Expr)$ $VarTail \rightarrow \lambda$ $Goal \rightarrow Expr$

Construct the $\text{LL(1)}$ table for the following grammar.$Expr \rightarrow \_Expr$$Expr \rightarrow (Expr)$$Expr \rightarrow Var\; ExprTail$$ExprTail \rightarrow \_Ex...

Kathleen

2.5k views

Kathleen asked Oct 8, 2014

7 votes

2 answers

652

GATE CSE 1993 | Question: 25
A simple Pascal like language has only three statements. assignment statement e.g. x:=expression loop construct e.g. for i:=expression to expression do statement sequencing e.g. begin statement ; ; statement end Write a context-free grammar (CFG) for statements in ... CFG. Show the parse tree for the following statements: for j:=2 to 10 do begin x:=expr1; y:=expr2; end

A simple Pascal like language has only three statements.assignment statement e.g. x:=expressionloop construct e.g. for i:=expression to expression do statementsequencing ...

Kathleen

1.5k views

Kathleen asked Sep 29, 2014

29 votes

3 answers

653

GATE CSE 2012 | Question: 52
For the grammar below, a partial $LL(1)$ parsing table is also presented along with the grammar. Entries that need to be filled are indicated as $E1, E2,$ and $E3$. $\varepsilon$ is the empty string, \$ indicates end of input, and, $ ... $ \text{FOLLOW}(A) = \{a, b\} $ $ \text{FOLLOW}(B) =\{a, b\} $

For the grammar below, a partial $LL(1)$ parsing table is also presented along with the grammar. Entries that need to be filled are indicated as $E1, E2,$ and $E3$. $\var...

gatecse

4.9k views

gatecse asked Sep 29, 2014

38 votes

4 answers

654

GATE CSE 2011 | Question: 27
Consider two binary operators $\text{ } \uparrow \text{'}$ and $\text{ } \downarrow \text{'}$ with the precedence of operator $\downarrow$ being lower than that of the operator $\uparrow$. Operator $\uparrow$ is right associative while operator ... Which one of the following represents the parse tree for expression $(7 \downarrow 3 \uparrow 4 \uparrow 3 \downarrow 2)$

Consider two binary operators $\text{‘} \uparrow \text{’}$ and $\text{‘} \downarrow \text{’}$ with the precedence of operator $\downarrow$ being lower than that ...

go_editor

7.2k views

go_editor asked Sep 29, 2014

26 votes

4 answers

655

GATE CSE 2006 | Question: 58
Consider the following grammar: $S\rightarrow FR$ $ R\rightarrow * S\mid \varepsilon $ $ F\rightarrow id $ In the predictive parser table $M$ of the grammar the entries $M[S,id]$ and $M[R,\$]$ respectively are $ \left \{ S\rightarrow FR \right \} $ and $ ... $ \left \{ F\rightarrow id \right \} $ and $ \left \{ R\rightarrow \varepsilon \right \} $

Consider the following grammar:$S\rightarrow FR$$ R\rightarrow * S\mid \varepsilon $$ F\rightarrow id $In the predictive parser table $M$ of the grammar the entries $M[S...

Rucha Shelke

8.2k views

Rucha Shelke asked Sep 26, 2014

44 votes

7 answers

656

GATE CSE 2014 Set 1 | Question: 34
A canonical set of items is given below $S \to L .> R $ $Q \to R.$ On input symbol $<$ the set has a shift-reduce conflict and a reduce-reduce conflict. a shift-reduce conflict but not a reduce-reduce conflict. a reduce-reduce conflict but not a shift-reduce conflict. neither a shift-reduce nor a reduce-reduce conflict.

A canonical set of items is given below$S \to L . R $$Q \to R.$On input symbol $<$ the set hasa shift-reduce conflict and a reduce-reduce conflict.a shift-reduce conflict...

go_editor

25.3k views

go_editor asked Sep 26, 2014

22 votes

2 answers

657

GATE CSE 1998 | Question: 22
An identifier in a programming language consists of up to six letters and digits of which the first character must be a letter. Derive a regular expression for the identifier. Build an $LL(1)$ parsing table for the language defined by the $LL(1)$ ... $X \rightarrow d \text{ semi } X \mid sY$ $Y \rightarrow \text{ semi } s Y \mid \epsilon$

An identifier in a programming language consists of up to six letters and digits of which the first character must be a letter. Derive a regular expression for the identi...

Kathleen

3.8k views

Kathleen asked Sep 26, 2014

46 votes

2 answers

658

GATE CSE 1998 | Question: 1.27
Type checking is normally done during lexical analysis syntax analysis syntax directed translation code optimization

Type checking is normally done duringlexical analysissyntax analysissyntax directed translationcode optimization

Kathleen

13.9k views

Kathleen asked Sep 25, 2014

24 votes

2 answers

659

GATE CSE 1998 | Question: 1.26
Which of the following statements is true? SLR parser is more powerful than LALR LALR parser is more powerful than Canonical LR parser Canonical LR parser is more powerful than LALR parser The parsers SLR, Canonical CR, and LALR have the same power

Which of the following statements is true?SLR parser is more powerful than LALRLALR parser is more powerful than Canonical LR parserCanonical LR parser is more powerful t...

Kathleen

12.8k views

Kathleen asked Sep 25, 2014

53 votes

4 answers

660

GATE CSE 2013 | Question: 40
Consider the following two sets of $\textsf{LR(1)}$ items of an $\textsf{LR(1)}$ grammar.$\begin{array}{l|l} X \rightarrow c.X, c∕d &X → c.X, \$\\ X \rightarrow .cX, c∕ d& X → .cX, \$\\ X \rightarrow .d, c∕ d & X → .d, \$ ... $\textsf{goto}$ on $c$ will lead to two different sets. $1$ only $2$ only $1$ and $4$ only $\text{1, 2, 3}$ and $4$

Consider the following two sets of $\textsf{LR(1)}$ items of an $\textsf{LR(1)}$ grammar.$$\begin{array}{l|l}X \rightarrow c.X, c∕d &X → c.X, \$\\X \rightarrow .cX, c...

Arjun

13.3k views

Arjun asked Sep 24, 2014

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true