Follow Sets are not correct

[Islidius]

The Follow Sets are not computed correctly. For Example the following grammar has a wrong following set:

E -> "i" T | eps
T -> "+" E | eps
A -> E ","

with A being the starting symbol.

This is the follow set being computed

Follow set:

┌─────────┬────────────┐
│ Symbol  │ Follow set │
├─────────┼────────────┤
│ $accept │            │
├─────────┼────────────┤
│ E       │ ","        │
├─────────┼────────────┤
│ T       │            │
├─────────┼────────────┤
│ A       │ $          │
└─────────┴────────────┘

but is should have "," in the follow set of T as FOLLOW(T) = FOLLOW(E).
This results in a wrong parsing table (even the follow set table is newly generated)

Grammar:

    1. E -> "i" T
    2.    | ε
    3. T -> + E
    4.    | ε
    5. A -> E ","

LL(1) parsing table:

┌───┬─────┬─────┬───┬───┐
│   │ "i" │ "," │ + │ $ │
├───┼─────┼─────┼───┼───┤
│ E │ 1   │ 2   │   │   │
├───┼─────┼─────┼───┼───┤
│ T │     │     │ 3 │   │
├───┼─────┼─────┼───┼───┤
│ A │ 5   │ 5   │   │   │
└───┴─────┴─────┴───┴───┘

which cannot parse the string "i,"

This seems to be a problem with the caching in the recursion returning an incomplete value.

followOf(E)
   -> followOf(T)
      -> followOf(E) -> returns empty cache
   add "," to FOLLOW(E) as in rule 5.

=> FOLLOW(E) = {","}, FOLLOW(T) = {}

[DmitrySoshnikov]

@Islidius, thanks, good catch. Yes, we'll need to fix the caching issue. I'll take a look later, and will appreciate a PR for this as well.

[DmitrySoshnikov]

Another example of the mutually-recursive non-terminals: https://gist.github.com/DmitrySoshnikov/924ceefb1784b30c5ca6#gistcomment-3000804

[Islidius]

I think i found a solution to this problem using a two pass approach: https://gist.github.com/DmitrySoshnikov/924ceefb1784b30c5ca6#gistcomment-3004304