Fragen zur C-Grammatik

[Curt Clueless (Gast)]

Hier [1] ist eine Grammatik der Sprache C. Mit Produktion:

stat : labeled_stat
     | exp_stat
     | compound_stat
     | selection_stat
     | iteration_stat
     | jump_stat
     ;

und dem Symbol für eine for-Schleife ('syfor'), kann ich sofort mit der 
Produktion iteration_stat weitermachen.

So geht das mit praktisch allen anderen Produktionen auch. Das aktuelle 
Symbol führt mich zur nächsten Produktion.

Wenn die Produktionen labeled_stat, compound_stat, selection_stat, 
iteration_stat und jump_stat nicht zutreffen, weil ich als Symbol eine 
Bezeichner (Variable) habe, dann verwende ich die Produktion exp_stat.

Die Produktion exp_stat führt zu der Produktion:

exp_stat : exp';'
         | ';'
         ;

Die Produktion exp führt zu der Produktion:

exp : assignment_exp
    | exp ',' assignment_exp
    ;

Die Produktion exp führt zu der Produktion:

assignment_exp : conditional_exp
               | unary_exp assignment_operator assignment_exp
               ;
Meine Fragen:

Warum wird zwischen "conditional_exp" und "unary_exp assignment_operator 
assignment_exp" und an welchem Symbol auf dieser Ebene erkenne ich das?

Ist es nicht so, dass die Entscheidung welche Produktionen zu verfolgen 
sind, nur vom aktuellen Symbol abhängt?

[1 ]http://www.cs.man.ac.uk/~pjj/bnf/c_syntax.bnf

[Yalu X. (yalu) (Moderator)]

Du gehst offensichtlich von einem LL(1)-Parser aus. Die von dir
verlinkte Grammatik ist zwar kontextfrei, aber keine LL(1)-Grammatik.
Deswegen kann sie nicht direkt in einen LL(1)-Parser umgesetzt werden.
Ein Problem stellen bspw. linksrekursive Produktionen dar:

In

exp : assignment_exp
    | exp ',' assignment_exp
    ;

kann der Parser anhand eines einzelnen Tokens nicht entscheiden, ob er
den ersten oder den zweiten Zweig verwenden soll, da auch das exp im
zweiten Zweig ein assignment_exp sein kann. Die Entscheidung für den
zweiten Zweig kann also erst beim Lesen des ',' fallen.

Die Linksrekursion ist ein Sonderfall des FIRST/FIRST-Konflikts, den du
auch hier hast:

assignment_exp : conditional_exp
               | unary_exp assignment_operator assignment_exp
               ;

Der Konflikt entsteht dadurch, dass conditional_exp und unary_exp
mit dem gleichen Token beginnen können.

Glücklicherweise kann man aber die Grammatik gängiger Programmierspra-
chen in eine LL(1)-Grammatik umschreiben und damit solche Konflikte
auflösen. Mehr dazu steht hier:

  http://en.wikipedia.org/wiki/LL_parser#Conflicts

Parser für LR(1)-Grammatiken haben diese Probleme nicht. Aber auch LR(1)
ist nur eine Untermenge der kontextfreien Grammatiken. Die Grammatiken
von Programmiersprachen sind aber meist als LR(1)- oder LALR(1)-Gramma-
tik formuliert. Die klassichen Parsergeneratoren yacc und bison erzeugen
LALR(1)-Parser und kommen mit der verlinkten Grammatik auch ohne Umfor-
mulierung zurecht.

[Curt Clueless (Gast)]

Hallo Yalu,

vielen Dank für deinen ausführlichen Beitrag. In der Tat bin ich von 
einer LL(1)-Grammatik ausgegangen. Deine Tipps &  Hinweise werde ich 
weiter verfolgen - insbesondere den YACC.

Wenn du einen Link auf eine LL(1)-Grammatik hast, poste ihn bitte.

Kurt

[Yalu X. (yalu) (Moderator)]

Curt Clueless schrieb:
> Wenn du einen Link auf eine LL(1)-Grammatik hast, poste ihn bitte.

Hab ich leider nicht, müsste auch erst danach suchen.

[Martin M. (Gast)]

Könnte mir mal jemand sagen was das ist?
Was ist eine  LL(1)-Grammatik und wozu benötigt man das?
Habe irgendwas mit Linksableitung gelesen. Mir ist so etwas noch nie in 
C untergekommen... :)

Viele Grüße

[Karl H. (kbuchegg)]

Martin M. schrieb:
> Könnte mir mal jemand sagen was das ist?
> Was ist eine  LL(1)-Grammatik und wozu benötigt man das?

Kurz gesagt:
Eine LL(1) Grammatik ist eine, die komplett deterministisch nur durch 
Betrachten des nächsten EINEN Zeichens entscheiden kann, wie es in der 
Grammatik weitergeht um den Satz zu parsen.


zb in EBNF Schreibweise

   Expr = Tern { ( '+' | '-' ) Term } .
   Term = Factor { ( '*' | '/' ) Factor } .
   Factor = Variable | Number .

Ist der Satz zu parsen

    3 + 5 * 8

das erste Zeichen ist eine 3, also eine Number

Du beginnst oben beim Expr.
Expr fordert dass ein Term vorliegt. Also siehst du in der Term Regel 
nach. Die Term Regel erfordert, dass ein Factor vorliegt. Als siehst du 
nach was ein Factor ist. Ein Factor kann entweder eine Variable oder 
eine Number sein. Wir haben eine Number, die gilt also als erkannt, das 
nächste Zeichen ist ein '+'. Die Regel für Factor erfordert nichts mehr, 
also geht es zurück zum Aufrufer, nämlich zur Term Regel. Dort steht 
nach dem erkannten Factor (den wir ja haben) geht es weiter mit entweder 
einem '*' oder einem '/'. Wir haben keines von beiden. Das macht aber 
nichts, denn { erlaubt ja, dass der ganze { } Bereich auch komplett 
fehlen darf. Das benutzen wir und behaupten: er fehlt. Damit ist auch 
die Term Regel soweit gültig und es geht zurück zum Aufrufer - der Expr 
Regel. Term war ja erkannt und Expr sagt wie es weiter geht: die Regel 
kann durch ein '+' oder ein '-' weiter geführt werden. Unser nächstes 
Zeichen war ein '+', also geht es dort weiter. Das '+' ist damit soweit 
erkennt und wir holen das nächste Symbol vom Input. Das ist eine 5, also 
eine Number. Wie gehts in der Expr Regel weiter? Nach dem '+' wird 
wieder ein Term gefordert. Also sehen wir nach, was ein Term ist. Die 
Term Regel sagt: Das ist zunächst mal ein Factor. Und die Factor Regel 
wiederrum erlaubt für das nächste Symbol 2 Möglichkeiten: entweder eine 
Variable oder eine Number. Wir haben eine Number, die gilt daher als 
erkannt und wieder sehen wir uns das nächste Zeichen vom Input an. Das 
ist ein '*'. Factor war ja soweit fertig und es geht zum Aufrufer 
zurück, zur Term Regel. Die erlaubt ein '*' als Fortsetzung ....

Ich hör hier auf, denn es sollte klar sein wie es weiter geht. Eine 
LL(1) Grammtik ist eine, bei der ich immer nur das nächste Zeichen aus 
dem Input brauche, um in meiner Grammatik entscheiden zu können, wie es 
weitergeht.

[Robert L. (lrlr)]

> Mir ist so etwas noch nie in
>C untergekommen

ja, weil es hier nicht um programmieren in C  geht
sondern um das (selber) erstellen eine C Parser

(mittels "compiler compiler")

IMHO