# Tag Info

3

It's true. If the CFG is not null free, and the input sentence is not null, you can remove the null from the CFG and then parse the input sentence with the resulting grammar. You already know how to do that in cubic time. If the CFG is not null free, and the input sentence is null, you can immediately tell whether the input sentence is accepted by the CFG.

1

To find the follow of S, I feel that it would be helpful to calculate all the firsts of all the variables as it helps a lot. First, let us see all the rules to find the first as they will be helpful. 1. For terminal a, First(a) = {a}. 2. For production A -> a, add 'a' to First(A). 3. For production A -> 𝜀, add '𝜀' to First(A). 4. For production A -&...

2

The left associativity of applications is only relevant when you have a sequence of applications. If it were correct to interpret y λx.x y as y (λx.x) y, then the left associativity rule would disambiguate it to (y (λx.x)) y. But that interpretation violates the rule that abstractions extend as far right as possible. Normally one never writes y λx.x y ...

1

Let's start with #3: Can you always walk the AST in any way you like after it is built? Yes, you can, and the Dragon book has an extensive discussion about how to do that for a given set of attributes; in particular, how to avoid (or detect) infinite regression. Moreover, there is really no inefficiency in doing it this way. Or, to put it another way, trying ...

2

Although the problem of detecting whether a grammar is ambiguous is, in general, undecidable, for toy grammars like this it is usually pretty easy to find ambiguities by simply enumerating the possible (left-most) derivations until you derive the same sentence in two ways. For example, $G_1$ has just three productions $S\to a S b \mid S b \mid c$, and none ...

Top 50 recent answers are included