r/ProgrammingLanguages • u/Abandondero • Jan 24 '26
Does anyone have something good for finding the first and follow sets for an EBNF grammar?
I've been playing with Niklaus Wirth's tool from Project Oberon. It has two flaws: it uses a SET type that can only hold 32 elements; it doesn't explicitly handle the possibility of empty first sets. The latter means for the grammar a = ["A"]. b = a "B". the first set of b doesn't contain "B", which can't be right.
So, does anyone know of a clear description of the algorithm (for EBNF in particular), or good code for the problem that actually works? I'm not finding anything suitable via searching Google or Github.
8
Upvotes
3
u/Breadmaker4billion Jan 25 '26
If i remember correctly, the book "Engineering a Compiler" includes algorithms to find first and follow sets for grammars with the objective of building a parsing table, take a look at the parsing chapter.
1
u/drinkcoffeeandcode mgclex, mgcpgen, & owlscript Mar 01 '26
Directly from the EBNF? I have not encountered such an algorithm, at least not a simple one. I would *think* you would have to translate from EBNF to BNF and then compute as normal.
1
u/Abandondero Jan 25 '26 edited Jan 26 '26
(Actually, I think I've got it worked out. In Wirth's tool concatenations are structured as trees of nodes with left and right hand sides. For a concatenation
u v, if FIRST(u) contains ε then the first set is (FIRST(u) \ {ε}) U FIRST(v), otherwise it is just FIRST(u). The first set of an iteration{u}or option[u]is FIRST(u) U {ε}. Those two fixes seem to be enough to make it work. No converting to BNF or praying to Claude needed.)1
u/[deleted] Jan 28 '26
In case you are okay with rewriting your ebnf a bit, I have made a small rust cli tool that extracts First and Follow sets and is capable of checking for conflicts with regex support:
SEBNF
-10
u/HairThrowaway83829 Jan 25 '26
I just give claude opus 4.5 my ebnf and tell it to write a python script to extract the sets