Berechnung von First- und Followmengen in erweiterten kontextfreien Grammatiken und Generierung eines ELL(1)-Parsers

(Computation of First and Follow Sets in Extended Context-Free Grammars and Generation of an ELL(1)-Parser)

Reinhold Heckmann

Deutsche Version dieser Seite

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 /