LL(1)-Test

Grammatiktests > LL(1)-Test

Die Grammatik muss LL(1) sein. Das bedeutet, dass der Parser stets in der Lage sein muss, im Vorblick auf das nächste im Text identifizierte Symbol zu entscheiden, welche der möglichen Grammatik-Alternativen zu wählen ist. Die LL(1)-Analyse arbeitet sehr schnell und ihr Prinzip ist einfach zu verstehen. Jedoch muss bei der Formulierung der Produktionen stets auf die Einhaltung der Bedingung geachtet werden.

Beispielsweise genügt die folgende Produktion (für eine Anweisung) nicht der LL(1)-Bedingung:

ident ":=" Expression

| ident ( "(" ExpressionList ")" )?

Beide Alternativen beginnen mit dem ident Symbol und, wenn der Parser zu dieser Produktion gelangt und ident als nächstes Token erkennt, kann er die Alternativen nicht unterscheiden. (Dazu müsste er ein weiteres Symbol vorausschauen, was er aber nicht kann.) Die Produktion kann jedoch leicht so umgeformt werden, dass alle Alternativen mit unterschiedlichen Token beginnen:

ident

(  

":=" Expression

|  ( "(" ExpressionList ")"  )?

)

Es gibt LL(1)-Konflikte, die nicht so einfach aufzufinden sind, wie in obigem Beispiel. Für den Programmierer kann es sehr schwer sein, sie zu finden, wenn er kein Werkzeug benutzt, dass die Grammatik prüft. Das Ergebnis wäre ein Parser, der in einigen Situationen die falsche Alternative wählt. Der TextTransformer prüft, ob die Grammatik der LL(1)-Bedingung genügt und gibt Hinweise wo Verletzungen vorliegen und zu korrigieren sind.

Wenn LL(1)-Konflikte nicht anders zu lösen sind, können IF...ELSE...END oder WHILE...END Strukturen verwendet werden.

Diese Seite gehört zur TextTransformer Dokumentation