ll1

The ll1 tool performs a small set of analyses on a
context-free grammar
in order to determine whether it is
LL(1), and thus suitable
for implementation via a
predictive parser
algorithm. Running a grammar through ll1 can help you catch
left recursion and other
conflicts
that could ruin your day if they pop up later during parser implementation.

Input format

ll1 parses a CFG in an ‘un-adorned’
GNU Bison format. The use of
%empty is absolutely mandatory for writing epsilon productions. Character
literals 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 cause ll1
to pitch a fit about predict set overlaps between productions of the
same nonterminal. ;)

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

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

In addition to LL(1) conflict reports, ll1 will also output information
about:

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

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

Caveats

I wrote ll1 in a day, and only passed it through valgrind a handful of
times to check for serious errors. Given the fact that most of the data
structures 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.

Licensing

The ll1 source code is released under the
MIT license. See the
LICENSE.md file for the complete license terms.

And as always, enjoy!

~ Brad.