Linked Questions

0
votes
0answers
35 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 ...
0
votes
0answers
20 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?...
6
votes
1answer
11k 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 ...
8
votes
2answers
930 views
2
votes
3answers
2k 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|n,m\in\mathbb N\land n\ge m\}$$ Is my hypothesis true or is ...
3
votes
2answers
123 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?
3
votes
1answer
520 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}$ ...
2
votes
1answer
932 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 | ε, ...
0
votes
0answers
780 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 ...
2
votes
1answer
191 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 \...
0
votes
1answer
40 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 ...
1
vote
2answers
78 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 ...
0
votes
2answers
97 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 ...
0
votes
0answers
69 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 ...