Die Programmiersprache C

Mit dem Texttransformer-Projekt C.ttp können C-Quelltexte geparst werden. Auch Typdefinitionen werden registriert und die entsprechenden Namen werden im anschließenden Code erkannt.

Die Quelltexte dürfen keine Präprozessor-Direktiven enthalten. Falls dies der Fall ist, können sie zunächst mit dem Cpp-Präprozessor entfernt, bzw. ersetzt werden. Diese Vorverarbeitung kann automatisch erfolgen, wenn der Präprozessor vom Benutzer in den Projektoptionen von C.ttp gesetzt wird.

Im Folgenden soll kurz darauf eingegangen werden, wie das Projekt durch Konvertierung eines vorhandenen Yacc-Programms hergestellt wurde. Die verschiedenen Stadien der Konvertierung sind als Backups in der Zip-Datei enthalten:

C_parser.zip

Erzeugung des C-Parser aus einem Yacc-Programm

Ausgangspunkt für die C-Grammatik war das Yacc-Programm:

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

1. mechanische Schritte der Konvertierung

Mit dem Yacc2TT-Projekt wurde aus der Yacc Grammatik eine Import-Datei für den TextTransformer erzeugt: Backup001. Darin wurden bereits vor dem Import die Namen der literalen Token durch die Literale selbst ersetzt: Backup002. So bleiben nur vier Token übrig, die nach dem Import als reguläre Ausdrücke definiert werden müssen:

CONSTANT
IDENTIFIER
STRING_LITERAL
TYPE_NAME

Für IDENTIFIER und STRING_LITERAL wurden die im TextTransformer verdefinierten Definitionen von ID bzw. STRING eingesetzt. TYPE_NAME wird als dynamisches Token definiert. Für CONSTANT gibt es in der Lex-Datei eine Reihe von regulären Ausdrücken, die die verschiedenen numerischen Konstanten beschreiben. Für das TextTransformer-Projekt wurde CONSTANT durch eine Produktion "constant" ersetzt, die aus diesen alternativen Token besteht:

constant ::=
  FLOAT
| INT_CONSTANT_HEX
| INT_CONSTANT_OCT
| INT_CONSTANT_DEC
| INT_CONSTANT_CHAR

Anstelle der comment-Funktion der Lex-Datei wird in den Projekteinstellungen des TextTransformers eine entsprechende comment-Produktion als Einschluss gesetzt: Backup003.

Nun kann das Projekt kompiliert werden. Dabei zeigt sich aber eine Schwäche des Yacc-Konverters: er hat zwar die einzelnen Regeln für sich in eine für den TextTransformer taugliche Form gebracht, nicht aber die Regeln untereinander. So gibt es nun einige Fehlermeldungen über Konflikte zwischen verschiedenen Produktionsalternativen.

2. "mechanische" Beseitigung von Konflikten

Eine mechanische Methode zur Beseitigung der Konflikte besteht darin, die Konflikt-Alternativen durch IF-ELSE-Alternativen zu ersetzen. Z.B. wird

external_declaration ::=
  function_definition
| declaration

ersetzt durch

external_declaration ::=
IF( function_definition())
  function_definition
ELSE
  declaration
END

Analog wird diese Prozedur auch für die Alternaitven in:

statement
assignment_expression
parameter_declaration
unary_expression
cast_expression

durchgeführt.

Nun scheint der C-Parser zu funktionieren, ist aber mit Sicherheit sehr ineffizient.

3. intelligente Beseitigung von Konflikten

Sowohl innerhalb von "unary_expression" als auch in "cast_expression" gibt es einen Konflikt zwischen "unary_expression" und einer Alternative, die ebenfalls mit der öffnenden Klammer "(" beginnt. Dass "unary_expression" mit diesem beginnen kann, liegt letztlich an der Alternative:

"(" expression ")"

in "primary_expression". Diese Alternative wird deshalb hier entfernt, in "postfix_expression" eingefügt. Diese Produktion wird damit zu:

    primary_expression postfix_expression_tail*
  | "(" expression ")" postfix_expression_tail*

mit der Hilfs-Produktion:

postfix_expression_tail ::=
  "[" expression "]"
| "(" argument_expression_list? ")"
| "." IDENTIFIER
| "->" IDENTIFIER
| "++"
| "--"

Nach dem gleichen Verfahren wird die Alternative

| "(" expression ")" postfix_expression_tail*

erneut nach außen gesetzt: Backup005.

Der Konflikt in "assignment_expression" zwischen "conditional_expression" und der mit "unary_expression" beginnenden Alternative beruht darauf, dass "conditional_expression" selbst mit "unary_expression" beginnt, vermittelt über die lange Kette:

conditional_expression
logical_or_expression
logical_and_expression
inclusive_or_expression
exclusive_or_expression
and_expression
equality_expression
relational_expression
shift_expression
additive_expression
multiplicative_expression
cast_expression
unary_expression

Aber alle Glieder dieser Kette bis zu "multiplicative_expression" sind gleich aufgebaut: sie beginnen mit dem untergeorneten Non-Terminal, auf das jeweils ein optionaler Rest folgt. "cast_expression" kann deshalb hervorgezogen werden.

Dazu kann zunächst "multiplicative_expression" an allen Stellen, wo es vorkommt ersetzt werden durch:

  cast_expression 
  multiplicative_expression_tail*

mit:

multiplicative_expression_tail ::=
(
    "*"
  | "/"
  | "%"      
)
cast_expression

Auf die gleiche Weise ist nun mit "logical_or_expression" zu verfahren, usw.: Backup005.

Yacc kennt keine Operatoren wie '?' und '+'. Unter Verwendung dieser Operatoren werden einige Regeln übersichtlicher: Backup006.

Nun können die Warnmeldungen betrachtet werden:

initializer_list: LL(1) Warnung: "," ist Strart und Nachfolger einer löschbaren Struktur

In "initializer" gibt es die Alternative:

"{" initializer_list ","? "}"

Zu dem Komma hinter der "initializer_list" kommt man aber nie, weil innerhalb dieser Produktion bei jedem Komma hinter "initializer" erneut mit der Schleife begonnen wird.

initializer_list ::=
initializer ( "," initializer )*

Eine Lösung hierfür bietet das TextTransformer "BREAK"-Symbol:

initializer_list ::=
initializer 
( 
  "," 
  (
      initializer 
    | BREAK
  )  
)*

Die Schleife nach dem Komma verlassen, wenn die schließende Klammer folgt. Das Komma in der obigen Alternative sollte nun entfernt werden:

"{" initializer_list "}"

Ebenso verhält es sich mit "parameter_type_list" und "parameter_list".

Durch weitere Umformungen wird auch "external_declaration" LL(1)-konform gemacht und "parameter_declaration" wird so umgeformt, dass etwas weniger weit vorausgeschaut werden muss, um über die richtige Alternative zu entscheiden: Backup007.

Erkennung von Typdefinitionen

In C können Namen als Bezeichner von benutzerdefinierten Typen definiert werden. Z.B.:

typedef const char* cp;

Im Anschluß an solche Definitionen lassen sich diese Namen ebenso verwenden, wie die vordefinierten Typen. Dieses Verhalten kann im TextTransformer mit "dynamischen" Token nachgebildet werden. Deshalb wurde das Token TYPE_NAME bereits als dynamisches Token definiert:

TYPE_NAME ::= {DYNAMIC}

Das "typedef"-Token ist in der Grammatik als eine der Alternativen von "storage_class_specifier" zu finden. Dort ist es schlecht plaziert. Typdefinitionen wären innerhalb einer "parameter_type_list" erlaubt, ebenso eine Wiederholung des "typedef" Schlüsselworts wie:

typedef typedef const char* cp;

Außerdem muss für die Verwendung des dynamischen Tokens semantischer Hilfcode geschrieben werden, und es wäre gut diesen Code isoliert zu halten. Während bei allen bisherigen Umformungen die formale Äquivalenz mit der ursprünglichen Yacc-Grammatik gewahrt wurde, wird diese deshalb nun ertmals durchbrochen und es wird die neue Produktion "type_definition" eingeführt.

type_definition
{{
str sTypename;
}}
"typedef" 
declaration_specifiers?
type_declarator[sTypename]
{{ AddToken(sTypename, "TYPE", ScopeStr()); }} 
";"

Die ebenfalls neue Produktion "type_declarator" stimmt syntaktisch mit der "declaration"-Produktion überein, aber sie enthält den semantischen Code, der den Namen für die Typdefinition liefert.

In "struct_or_union_specifier" und in "enum_specifier" wird ebenfalls Code eingefügt, um die Namen der definierten Strukturen bzw. Enumerationen zu registrieren.

Ein letztes Problem bleibt noch: lokal innerhalbe eines "compound_statement" definierte Typen gelten nur innerhalb dieses Bereichs. Deshalb wird innerhalb von "compound_statement" ein entsprechender bereich erzeugt, und am Ende wieder verlassen.

compound_statement ::=
"{"  {{PushScope(ScopeStr() + ".local" + itos(m_iLocalScope++)); }}
( 
    declaration_list statement_list?
  | statement_list  
)?  {{PopScope(); }}
"}"

Ebenso wird ein "exteral"-Bereich wird in "translation_unit" geschaffen.

to the top