3
votes
Is LR(1) closed under union?
A simple example is
$$L_1 = \{a^i b^i c^j \mid i,j\ge 0\}$$
$$L_2 = \{a^i b^j c^j \mid i,j\ge 0\}$$
Clearly, both languages are $LR(1)$. (Indeed, they are $LL(1)$.) But their union is inherently ...
- 11.7k
2
votes
Accepted
How is the lookahead for an LR(1) automaton computed?
$\text{FIRST}(\beta)$ is the set of possible first tokens in a derivation from β. (It's usual to also add ε to the first set if β could derive the empty sequence.)
So $\text{FIRST}(\mathbf{+}\mathit{T}...
- 11.7k
1
vote
Equivalence of LR(k) and LL(k′) parsers
Yes, $\{a^i b^j c \mid i \ge j \ge 0\}$ can be parsed by a $LR(0)$ parser but not by any $LL(k')$ parser for any $k'$. See How does $LL(n)$ languages compare with $LR(0)$, for $n>0$?.
See also ...
D.W.♦
- 152k
1
vote
Accepted
Is there a language that has a LL(1) grammar but not LALR(1) grammar?
Every language which has an $LR(k)$ grammar for some $k$ has an $SLR(1)$ grammar (which is necessarily also $LALR(1)$ and $LR(1)$).
The proof is constructive: from the $LR(k)$ grammar, you can ...
- 11.7k
1
vote
How to disambiguate CFG with unary/binary minus and binary prefix operator
I'm going to limit myself, at least for now, to the question actually asked here: how to deal with the ambiguity between an operator which could be prefix or infix (such as unary negation) and a ...
- 11.7k
1
vote
Edit distance into a DCFL
It would appear the language edit distance problem for the class of deterministic context-free languages requires cubic time.
In Language Edit Distance Approximation via Amnesic Dynamic
Programming (...
- 699
1
vote
What is the time complexity of SLR and LALR parsers?
They all run linear time with regards to input length ($O(n)$). The different algorithms have different memory trade offs for making it easier to write grammar for. That is not all grammars that work ...
- 227
Only top scored, non community-wiki answers of a minimum length are eligible