Next: Regeln Up: Transformation der Grammatik Previous: Transformation der Grammatik

Anforderungen

Um den später beschriebenen Parser möglichst einfach und effizient zu halten, müssen Grammatikregeln, die eine Alternative der Form ausdrücken, zwei Bedingungen erfüllen []:

  1. Die First-Mengen müssen paarweise disjunkt sein: Unter versteht man dabei die Menge aller Terminalsymbole, mit denen eine Ableitung aus beginnen kann.
  2. Nur eine der Alternativen darf mit einem Nichtterminalsymbol beginnen.
Die erste Regel erlaubt einen Verzicht auf Backtracking und die Begrenzung der Vorausschau des Parsers auf ein Symbol. Die zweite bewirkt, daß in der transformierten Grammatik keine First-Mengen berechnet werden müssen. Die entsprechenden Informationen sind direkt aus den Regeln ablesbar.


Harold Boley & Michael Herfert (herfert@dfki.uni-kl.de)