DmitrySoshnikov / syntax

Syntactic analysis toolkit, language-agnostic parser generator.
MIT License
605 stars 85 forks source link

First / Follow calculation is incorrect for recursive epsilon #138

Open DmitrySoshnikov opened 1 year ago

DmitrySoshnikov commented 1 year ago
%%

S
  : A B C
  ;

A
  : "a"
  ;

B
  : B "b" C
  | /* empty */
  ;

C
  : "c" A
  ;

First set:

Follow set:

./bin/syntax -g ~/test.bnf -m lalr1 --sets all

First set:

┌────────┬───────────┐
│ Symbol │ First set │
├────────┼───────────┤
│ S      │ "a"       │
├────────┼───────────┤
│ A      │ "a"       │
├────────┼───────────┤
│ B      │ ε         │   <-- BUG
├────────┼───────────┤
│ C      │ "c"       │
└────────┴───────────┘

Follow set:

┌────────┬─────────────┐
│ Symbol │ Follow set  │
├────────┼─────────────┤
│ S      │ $           │
├────────┼─────────────┤
│ A      │ "c", $, "b" │
├────────┼─────────────┤
│ C      │ $, "c", "b" │
├────────┼─────────────┤
│ B      │ "c", "b"    │  <-- BUG
└────────┴─────────────┘

Predict set:

┌─────────────────┬─────────────┐
│ Production      │ Predict set │
├─────────────────┼─────────────┤
│ 1. S -> A B C   │ "a"         │
├─────────────────┼─────────────┤
│ 2. A -> "a"     │ "a"         │
├─────────────────┼─────────────┤
│ 3. B -> B "b" C │ "b"         │
├─────────────────┼─────────────┤
│ 5. C -> "c" A   │ "c"         │
└─────────────────┴─────────────┘
ahmedriza commented 4 months ago

Actually, I believe the Follow sets above are correct. The bug is in First(B) which should be {b, ε}.