Yacc2TT

Mit dem TextTransformer-Projekt Yacc2TT.ttp können Yacc-Grammatiken in eine Form gebracht werden, die für LL-Parsergeneratoren geeignet ist. Es wird eine tti-Datei erzeugt, die direkt in den TextTransformer importiert werden kann.

Einleitung

Es gibt eine Menge von Grammatiken, für den Parsergenerator "Yacc" und es wäre schön, wenn man sie für den TextTransformer verwenden könnte. Eine Konvertierung dieser Grammatiken ist aber nicht trivial, weil der TextTransformer einen LL Parser-Algorithmus benutzt und Yacc einen LR Parser-Algorithmus. Diese Algorithmen erfordern einen verschiedenen logischen Aufbau der Grammatiken.

Während beide Algorithmen den Eingabetext von links nach rechts lesen, wofür das erste 'L' in "LL" bzw. "LR" steht, wird die Übereinstimmung mit einer Grammatikregel in unterschiedlicher Richtung getestet. Im LL-Parser wird bereits nach der Erkennung des nächsten Tokens die dazu passende Regel gefunden, während dies beim LR-Algorithmus meist erst nach der Erkennung mehrer Token möglich ist, die dann rückwärts ausgewertet werden.

Damit der LL-Parser die passende Regel sofort finden kann, muss das Regelsystem (die Grammatik) so formuliert sein, dass es zu einem gegebenen Token nicht mehrere alternative Produktionen gibt. Alle Alternativen müssen mit verschiedenen, nicht überlappenden Tokenmengen beginnen.

Die Schritte die gemäß diesem Prinzip bei Konvertierung der Yacc-Grammatiken erforderlich sind, sollen im Folgenden demonstriert werden. Zugleich wird erläutert, wie diese Transformationen im TextTransformer durchgeführt werden.

Als Beispiel dient folgende Yacc-Regel:

direct_declarator
	: IDENTIFIER
	| '(' declarator ')'
	| direct_declarator '[' constant_expression ']'
	| direct_declarator '[' ']'
	| direct_declarator '(' parameter_type_list ')'
	| direct_declarator '(' identifier_list ')'
	| direct_declarator '(' ')'
	;

Diese Definition stammt aus einer Grammatik C von Jeff Lee für die Programmiersprache C.

http://www.lysator.liu.se/c/ANSI-C-grammar-l.html

Repräsentation der Regeln durch Baumstrukturen

Die Grammatik von Yacc2TT ist abgeleitet aus "Appendix B: Yacc Input Syntax" des Yacc manuals. Neben der Grammatik gibt es in Yacc2TT gibt es das Element:

mstrdnode m_nRules

Dies ist eine map, in der zu jedem Regelnamen ein Regelbaum gespeichert wird. Die Konstruktion der Bäume erfolgt in der rule-Produktion und in den von ihr aufgerufenen Produktionen. Der Baum für obiges Beispiel sieht zunächst so aus:

  T : IDENTIFIER	
	T : '(' 
	  NT : declarator 
	     T ')'
	NT : direct_declarator 
	   T : '[' 
	     NT : constant_expression 
	        T : ']'
	NT : direct_declarator 
	   T : '[' 
	     T : ']'
	NT : direct_declarator 
	   T : '(' 
	     NT : parameter_type_list 
	        T : ')'
	NT : direct_declarator 
	   T : '(' 
	     NT : identifier_list 
	        T : ')'
	NT : direct_declarator 
	   T : '(' 
	     T : ')'

"T" und "NT" sind hierin die Label für Terminale und Non-Terminale. Der Baum wurde so erzeugt, dass Alternativen durch Nachbar-Knoten ausgedrückt werden, während Kind-Knoten für die Nachfolgerelation stehen. Diese Bäume werden nun Schritt für Schritt so umgeformt, dass schließlich eine LL-Grammatik daraus erzeugt werden kann.

Links Ausklammern

Der erste Schritt zur Vermeidung von Alternativen mit gleichen terminalen Anfängern, besteht darin gemeinsame Anfänge von Alternativen auszuklammern. Das ergibt folgenden Baum:

  T : IDENTIFIER	
	T : '(' 
	  NT : declarator 
	     T ')'
	NT : direct_declarator 
	   T : '[' 
	     NT : constant_expression 
	        T : ']'
	      T : ']'
	   T : '(' 
	     NT : parameter_type_list 
	        T : ')'
	     NT : identifier_list 
	        T : ')'
	     T : ')'

Gruppierung

Zur Vorbereitung des wichtigen nächsten Schritts, der Elimination von Linksrekursionen, werden zunächst Alternativen, die auf einen gemeinsamen Vorgänger folgen, zu Gruppen zusammengefasst. Dazu werden Markierungs-Knoten mit den Labels "ALT_BEGIN" und "ALT_END" in den Baum eingefügt. Durch diese Klammerung ist es dann später auch leichter möglich die Operatoren, z.B. den Wiederholungsoperator '*', der EBNF-Syntax des TextTransformers anzuwenden.

  T : IDENTIFIER	
	T : '(' 
	  NT : declarator 
	     T ')'
	NT : direct_declarator 
	   ALT_BEGIN
	   T : '[' 
	     ALT_BEGIN
	     NT : constant_expression 
	        T : ']'
	      T : ']'
	     ALT_END 
	   T : '(' 
	     ALT_BEGIN
	     NT : parameter_type_list 
	        T : ')'
	     NT : identifier_list 
	        T : ')'
	     T : ')'
	     ALT_END   
	   ALT_END

Linksrekursionen beseitigen

Linksrekursive Regeln wie:

a = a C | B

sind für LL-Parser nicht zulässig. Sie führen in einen unendlichen Regreß. Die Regel ist aber aber logisch Äquivalent mit:

a = B C*

wobei '*' der schon genannte Wiederholungsoperator ist. In Yacc2TT wird diese Umformung automatisch ausgeführt und liefert:

  ALT_BEGIN
  T : IDENTIFIER	
	T : '(' 
	 NT : declarator 
	    T ')'
	ALT_END    
	  OREP_BEGIN 
	    T : '[' 
	      ALT_BEGIN
	      NT : constant_expression 
	         T : ']'
	       T : ']'
	      ALT_END
	    T : '(' 
	      ALT_BEGIN
	      NT : parameter_type_list 
	         T : ')'
	      NT : identifier_list 
	         T : ')'
	      T : ')'
	      ALT_END
	  OREP_END

Leere Alternativen entfernen

Bei Regeln, die leere Alternativen enthalten, führt Yacc2TT noch eine weitere Umformung durch. Z.B. würde:

a | b |

umgeschrieben zu:

( a | b )?

TextTransformer Import-Datei

Zu guter Letzt wird vom Yacc2TT-Projekt eine Ausgabedatei mit den umgeformeten Yacc-Regeln erzeugt. Sie sollte mit der Erweiterung "tti" abgespeichert werden und kann dann direkt in den TextTransformer importiert werden. Die "direct_declarator" Regel erscheint darin als:

direct_declarator()
(>
  (
      IDENTIFIER
      "("
      declarator
      ")"
  )
  (
      "["
      (
          constant_expression
          "]"
        | "]"
      )
    | "("
      (
          parameter_type_list
          ")"
        | identifier_list
          ")"
        | ")"
      )
  )
<)

Schluss

Es gibt immer noch Möglichkeiten die Regeln zu verbessern. Insbesondere ein Problem wird von Yacc2TT nicht behandelt: die einzelnen Regeln für sich haben zwar nun eine für LL-Parsergeneratoren passende Form, nicht aber die Regeln untereinander.
Die Grammatik-Tests des TextTransformers zeigen, wo es solche KOnflikte gibt. Innerhalb der IDE lassen sie sich vergleichsweise leicht von Hand beseitigen.
Anhand der C-Grammatik wird vorgeführt, wie dies geht.

Letztes Update: 05.11.08

to the top