Skip to content

First / Follow calculation is incorrect for recursive epsilon  #138

@DmitrySoshnikov

Description

@DmitrySoshnikov
%%

S
  : A B C
  ;

A
  : "a"
  ;

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

C
  : "c" A
  ;

First set:

  • Expected: FIRST(B) should be {"b"}
  • Actual: FIRST(B) is {ε}

Follow set:

  • Expected: FOLLOW(B) should be {"c"}
  • Actual: FOLLOW(B) is {"b", "c"}
./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"         │
└─────────────────┴─────────────┘

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions