Linked Questions

0 votes
0 answers
74 views

Does $LL(K)$ grammar has one to one correspondence with $DCFL$? [duplicate]

Does $LL(K)$ grammar has one to one correspondence with $DCFL$ ? If I am understanding right, then the given statement says that $2$ distinct $LL(k)$ have one to one mapping, i.e they should not ...
Garrick's user avatar
  • 472
0 votes
0 answers
30 views

Is $LR(k) \subset SLR(k+1)$ for $k=1,2,...$? [duplicate]

I know that: Point 1: Set of languages accepted by $LR(0)$ parsers $\subset$ Set of languages accepted by $SLR(1)$ parsers Does this logic hold for higher $k$'s? That is, does following fact hold?...
RajS's user avatar
  • 1,677
8 votes
1 answer
17k views

Left-Factoring a grammar into LL(1)

I have a homework assignment where I need to convert a grammar into LL(1). I've already removed the left recursion, but I'm having trouble doing left-factoring. All of the examples I've found are ...
Kami's Aibou's user avatar
9 votes
2 answers
2k views

Correct name for a recursive descent parser that uses loops to handle left recursion?

This grammar is left recursive: ...
user71015's user avatar
3 votes
3 answers
3k views

Is this language LL(1) parseable?

I tried to find a simple example for a language that is not parseable with an LL(1) parser. I finally found this language. $$L=\{\,a^nb^m\mid n,m\in\mathbb N,\>n\ge m\,\}$$ Is my hypothesis true ...
fuz's user avatar
  • 911
6 votes
1 answer
1k views

Are LR(k) languages and DCFLs equivalent?

In the familiar book of Theory of Computation by M. Sipser, the author proved that for endmarked context-free languages, the set of languages having a LR(k) grammar for a predefined $k \in \mathbb{N}$ ...
Vincent J. Ruan's user avatar
5 votes
2 answers
155 views

Is the set of LL(*) grammars the same as the set of CFG grammars?

Is the set of LL(*) grammars the same as the set of context-free grammars?
ninjagecko's user avatar
2 votes
1 answer
1k views

If a parser can parse a non-deterministic grammar, is the parser non-deterministic?

I've written a recursive-descent parser generator, and I'm trying to classify it (call me a cowboy coder if you must). According to wikipedia, S → 0S0 | 1S1 | ε, ...
Brent's user avatar
  • 2,553
0 votes
0 answers
1k views

Show that any LL(k) grammar is unambiguous

I am confused on several areas of this. First, this is so obvious I am finding it hard to prove. Second, what are some definitions, axioms, or lemmas of an ll(k) grammar that I can use to build up a ...
bmc's user avatar
  • 119
0 votes
1 answer
232 views

Is there a LL(K) Grammar which is not LALR(K) Grammar?

It is easy to know that there are LALR(K) grammars which are not LL(K) because any grammar with left recursion which is LALR(K), is not LL(K) because all LL(K) grammar must be left recursion free. And ...
user's user avatar
  • 215
2 votes
1 answer
388 views

Does my grammar contradict LL ⊆ LR(1)?

This answer claims that $ LL \subseteq LR \left( 1 \right )$ where $LL = \bigcup_k LL(k)$. But is this true? Is this grammar a valid counterexample? $ S \rightarrow a | Aaa $, $ A \rightarrow \...
Daniel's user avatar
  • 23
0 votes
2 answers
638 views

LR(1) grammar that can not be transformed an LL(1) grammar

Looking for an example of a LR(1) grammar that can not be turned into an LL(1) grammar that parsers the same language.
clinux's user avatar
  • 247
1 vote
2 answers
244 views

What is the difference between language hierarchy and Grammar hierarchy for LL and LR?

Till now I have believed that a LL language is a language generated by a LL grammar. Same goes for LR. Now I know some of the hierarchies such as $LL(1)\subset LR(1)$. I used to think that the ...
Kishan Kumar's user avatar
0 votes
0 answers
104 views

Rules language / DSL expressivity measure

Languages to express domain rules are quite diverse from very simple and inexpressive to Turing-complete programming languages. If we consider developing some DSL (domain-specific language), is there ...
Roman Susi's user avatar
0 votes
2 answers
125 views

Which Type of Grammar is this?

I am learning Compiler Design. Can somebody explain what type of Grammar this is? The answer given is $LL(1)$ but there exists a left recursion in the grammar so it cannot be $LL(1)$. I derived the ...
Nikhil Mahajan's user avatar

15 30 50 per page