Generate FIRST/FOLLOW/PREDICT Set from BNF.
We can use it to study parser theory.
Feature
- FirstSet generate. Output pretty.
- FollowSet generate. Output pretty.
- LL(1) Predicate Parsing Table. Output pretty.
Usage
You can use demo input to generate FirstSet/FollowSet/PredictTable
cd cmd
go run main.go
Output to the terminal default
FirstSet:
FIRST(D) = {g ε f}
FIRST(E) = {g ε}
FIRST(F) = {f ε}
FIRST(S) = {a}
FIRST(B) = {c}
FIRST(C) = {b ε}
FollowSet:
FOLLOW(F) = {h}
FOLLOW(S) = {$}
FOLLOW(B) = {g h f}
FOLLOW(C) = {g h f}
FOLLOW(D) = {h}
FOLLOW(E) = {f h}
PredictTable:
+---+----------------+------------+------------+------------+------------+------------+---+
| # | a | b | c | f | g | h | $ |
+---+----------------+------------+------------+------------+------------+------------+---+
| S | S -> {a B D h} | | | | | | |
+---+----------------+------------+------------+------------+------------+------------+---+
| B | | | B -> {c C} | | | | |
+---+----------------+------------+------------+------------+------------+------------+---+
| C | | C -> {b C} | | C -> {ε} | C -> {ε} | C -> {ε} | |
+---+----------------+------------+------------+------------+------------+------------+---+
| D | | | | D -> {E F} | D -> {E F} | D -> {E F} | |
+---+----------------+------------+------------+------------+------------+------------+---+
| E | | | | E -> {ε} | E -> {g} | E -> {ε} | |
+---+----------------+------------+------------+------------+------------+------------+---+
| F | | | | F -> {f} | | F -> {ε} | |
+---+----------------+------------+------------+------------+------------+------------+---+
Or use your own bnf grammar.
cd cmd
go run main.go -grammar your_own_grammar_file
Note
- use
ε
indicateEPSILON
(unicode is'\u03B5'
) - use
$
indicateinput right end marker
. - use UpperCase letter indicate
Nonterminal
- use lowerCase letter indicate
Terminal
BNF
format with|
support alternate.- use
->
distinguishLHS
andRHS
More demo see the cmd/demo.bnf
, or testdata
Ref
- FirstFollow
- Compiler Construction
- Parsing Topics Note: some example is confused(some letter is not printed in the web page. so maybe confused when reading it.)
- Online calculate FIRST/FOLLOW/PREDICT.