Repository files navigation

Thell1 tool performs a small set of analyses on acontext-free grammarin order to determine whether it isLL(1), and thus suitablefor implementationvia apredictive parseralgorithm. Running a grammar throughll1 can help you catchleft recursion and otherconflictsthat could ruin your day if they pop up later during parser implementation.

ll1 parses a CFG in an 'un-adorned'GNU Bison format. The use of%empty is absolutely mandatory for writing epsilon productions. Characterliterals are also accepted as tokens, so the following grammar:

%%/* left-recursive!*/expr :expr'+'term|expr'-'term|term ;/* left-recursive!*/term :term'*'factor|term'/'factor|factor ;factor :ID|NUM ;%%

would be perfectly acceptable input, even though it will causell1to pitch a fit about predict set overlaps between productions of thesame nonterminal.;)

However,ll1 will be tickled pink to accept this input:

%%/* tail-recursive... :)*/expr :termexpr_next ;term :factorterm_next ;expr_next :'+'expr|'-'expr| %empty ;term_next :'*'term|'/'term| %empty ;factor :ID|NUM ;%%

In addition toLL(1) conflict reports,ll1 will also output informationabout:

• Terminal symbols
• Nonterminal symbols
• Nonterminals deriving%empty
• Recapitulation of the input grammar
• First,follow andpredict sets

It's neither perfect nor complete, but it helps provide some basic insights.

I wrotell1 in a day, and only passed it through valgrind a handful oftimes to check for serious errors. Given the fact that most of the datastructures are patterned after the null-termination patterns of C strings,there has to be a bug or two in there...somewhere...

Anyways, if you run into one, let me know and I'll push a patch.

Thell1 source code is released under theMIT license. See theLICENSE.md file for the complete license terms.

And as always, enjoy!

*~ Brad.*