search
Log In
1 vote
166 views
$L=\{x^n:n \in N\} \cup\{x^ny^n|n \in N\}$

This language does not have LL(k) parser while being deterministic context free.Why?
in Compiler Design 166 views
0
is this DCFL ?
0
yes. If we assume end delimiter is there. i.e., all strings end with a delimiter like '$'.
0

If we assume end delimiter is there

then it is DCFL, in that case it should have LL(k) for some k

right sir ?

then there is no meaning in this question !

2
No. DCFL is guaranteed to have only LR(1) not necessarily LL(k)
0

if it is LL(k) for some k, then it is LR(m) for some m. but converse not true !

Forgot that basic point, thanks sir !!

1

@Arjun sir and  @Shaik Masthan-I am trying to build a proof  point out if anywhere I go wrong.

The grammar can be

$S->A|B\\A->xA|x\\B->xBy|xy$

For string let's say $w_1=x^3$ we need to use production $S->A$ and for string $w_2=x^3y^3$ we need to use the production $S->B$

So here we are in a dilemma which one to use.

Similarly, for a given string of length say $n$, we are not sure how much of lookahead we need for each string so that production to be used at each step can be uniquely determined.

So, the given language does not have an LL(K) parser for any fixed k.

Am I going in the correct direction?

0
yes, intuitively that is correct 👍 Similar to why LR(k) is more powerful than LL(k).
0
sir, can you show in formal way, why it doesn't have any LL(k) parser?
1

1 Answer

0 votes

Till DCFL there exist a LR(K) parser.

Related questions

0 votes
0 answers
1
86 views
Say I have a grammar, S→ AB A→ a B→ b This grammar is not operator grammar as 2 non terminals are lying side by side, but can be converted to an operator grammar. S→ ab , A→ a , B→ b here i have a doubt, operator grammar as the name suggests should have a ... right? how can we operate even two terminal symbols when placed side by side? Isn't it same as placing 2 non-terminal symbol side by side?
asked Jun 6, 2019 in Compiler Design Hirak 86 views
1 vote
4 answers
2
0 votes
1 answer
3
141 views
S → aSbS /bSaS / ϵ S → aABb A→ c/ ϵ B → d/ ϵ Which of the following is LL1. Explain in details.
asked Jun 1, 2019 in Compiler Design Hirak 141 views
0 votes
1 answer
4
72 views
Can we comment/compare the number of GOTO moves in LALR and CLR CLR and SLR?
asked Oct 21, 2018 in Compiler Design manisha11 72 views
...