Linked Questions
17 questions linked to/from Language theoretic comparison of LL and LR grammars
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 ...
- 452
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?...
- 1,597
8
votes
1
answer
16k
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 ...
- 183
8
votes
2
answers
2k
views
Correct name for a recursive descent parser that uses loops to handle left recursion?
This grammar is left recursive:
...
- 81
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 ...
- 866
6
votes
1
answer
949
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}$ ...
- 173
4
votes
2
answers
147
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?
- 151
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 | ε, ...
- 2,535
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 ...
- 119
0
votes
1
answer
211
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 ...
- 215
2
votes
1
answer
350
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 \...
- 23
1
vote
2
answers
232
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 ...
- 675
0
votes
2
answers
347
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.
- 227
0
votes
0
answers
101
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 ...
- 263
0
votes
2
answers
120
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 ...
