## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

#### D.1.1 Top-down Parsing

Problem 1.1.1  Is this a LL(1) grammar?

```0. S‘–> S#            3. A –> abS
1. S –> aAa           4. A –>  c
2. S –> empty
```

First of all, we note that it is a CFG (single NT's on the LHS of all rules), it has ∊-rule, there is no left recursion. So it is a candidate for being an LL(1) grammar. In FIRST(A), the RHS are disjoint, so we need test only productions from S.As one of the S productions is an ∊-rule, we find the FOLLOW(S)= {#,a}. Now, FIRST(aAaFOLLOW(S)) ∩ FIRST(∊FOLLOW(S)) = {a}∩{#, a}≠ Ø. Therefore, this is not an LL(1) grammar.

For example, consider a string “aaba…#”. The productions for this strings can be: S#aAa#aabSa#.

Now at this stage, we do not know whether to use rule 1 or rule 2 for the ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required