New answers tagged


That website uses a different notation than what you assumed. This would be the correct input: S -> A S | b. A -> S A | a. You entered AS (and SA) which it does not recognize as A followed by S, but as a single nonterminal named AS. With that input it correctly says that the language is not $\text{LL}(1)$.


Since $A\to .Ay$ is in the state constructed for $GOTO(0, x)$, $A\to .A(y)$ and $A\to .(y)$ are also in that state. These combine with the other items for the same productions, which have lookahead $z$.


I see two flaws in this proof sketch, one related to CFLs vs CFGs, and another related to nested quantifiers and running time as a function of multiple parameters. Any time you have a high-level proof strategy that seems to lead to surprising results, it is a good idea to check it carefully by expanding each step to obtain a detailed proof. Expand each ...


As the name indicates, the parse tree is generated top-down. Specifically, you start with a place-holder node for the start symbol. Each time you predict a production, you fill in the placeholder with the right-hand side of the production, where each symbol is represented by a placeholder. Each time you shift over a token, you fill in the placeholder with ...


$\#$ here is just a symbol; it has no special significance. (It's often used in the construction of an modified language to indicate a new symbol which is not in the alphabet of the original language.) $\#^{g(x)}$ is, therefore, the unary encoding of $g(x)$; in that sense, it is a count. The double-triangle used in the later proof is just another such ...

Top 50 recent answers are included