In extended [context-free] grammars,
the right-hand sides of the productions are regular expressions.
This feature allows for more elegant and shorter
syntax definitions with less direct recursion
than in conventional [context-free] grammars.
In this talk, extended grammars are introduced,
first1 sets are defined by means of the usual regular left derivation,
and the main properties of first1 sets are presented.
Then, it will turn out that there are problems in defining follow1 sets.
These difficulties can be solved by a novel kind of derivation.
An algorithm for the computation of first and follow sets
will be presented, the runtime of which
is linear in the size of the grammar and the time
needed for the union of two sets of terminal symbols.
First and follow sets can be used to check
whether the grammar is ELL(1),
and if so, to generate an ELL(1) parser table.
Reinhold Heckmann / heckmann@absint.com