Teil 4: Grammatiken und Syntaxanalyse

(Kapitel T5-T7)

449

Grammatiken und die Chomsky-Hierarchie [T5.1]

Ziel: Regelsysteme zur Erzeugung von Sprachen.

Beispiel: arithmetische Ausdrücke können definiert werden durch

• a (Variable), a+a, a·a sind arithmet. Ausdr.

• Wenn A und B arithm. Ausdr. sind, dann auch (A)+(B) und (A)·(B).

Grammatik: formalere Beschreibung solcher Regeln.

450

Bestandteile einer Grammatik

• T (oder Σ): endliche Menge von Terminalzeichen (das Alphabet der erzeugten Sprache)

• V : endliche Menge von Variablen (T∩V=∅)• S∈V : Startsymbol• P : endliche Menge von Ableitungsregeln/

ProduktionenPaare (l,r) mit l∈(V∪T )+, r∈(V∪T )*

(Schreibweise: l→r)Variante: l∈V +

451

Beispiel: arithmetische Ausdrücke

V={S}T={(,),a,+,·}P = {S→(S)+(S), S→(S)·(S),

S→a, S→ a+a, S→a·a}

Herleitung eines Wortes:S→ (S)+(S) → (S)+((S)·(S)) → (a·a)+((S)·(S))→ (a·a)+((a)·(S)) → (a·a)+((a)·(a +a))

452

Notation

• w→z⇔ z lässt sich durch Anwendung einer Ableitungsregel (l,r) aus w herleiten,d.h., es gibt in w ein Teilwort l, so dass nach Ersetzen von l durch r das Wort z entsteht.

• w→z⇔ w→w1→w2→w3→…→wn→z, d.h., z kann aus w in endlich vielen Schritten hergeleitet werden.

• L(G): Die von der Grammatik G erzeugte Sprache, also die Menge der Wörter w∈T * mit S→w.*

*

453

Notation

Variablen: Großbuchstaben.Terminale: meistens Kleinbuchstaben a,b,c,...

oder Ziffern, manchmal auch Sonderzeichen oder Klammern.

Wörter aus ( V∪T )*: Kleinbuchstaben u,v, ... oder griechische Kleinbuchstaben.

454

Weiteres BeispielL = { w | w∈{a,b,c}* und w enthält gleich viele

a´s, b´s und c´s }

Angabe einer Grammatik:V = {S,A,B,C,R}, T = {a,b,c},P = {S→R, S→ε,

R→RABC, R→ABCAB →BA, BA →AB, CA →AC, AC →CA, BC →CB, CB →BC, A →a, B →b, C →c}

455

Eingeschränkte Grammatiken

Definition T5.1.1:• Chomsky-0-Grammatiken: Grammatiken

ohne weitere Einschränkungen.• Chomsky-1-Grammatiken: Produktionen

der Form S→ε oder u→v mitu∈V +, v∈((V∪T )– {S})* und |u|�|v|.

(Beispiel: siehe vorherige Folie)

monoton oder kontextsensitiv

456

Eingeschr. Grammatiken (Forts.)

• Chomsky-2-Grammatiken: Produktionen der Form A→v mit A∈V, v∈(V∪T )*.

• Chomsky-3-Grammatiken: Produktionen der Form A→ε oder A→aB mit A,B∈V, a∈T.

kontextfrei

rechtslinear oder regulär

457

Sprachklassen

Li: Menge der von Chomsky-i-Grammatikenerzeugbaren Sprachen, genauer

L0: Chomsky-0-Sprachen (=rekursiv aufzählbare Sprachen)

L1: kontextsensitive Sprachen

L2: kontextfreie Sprachen

L3: rechtslineare Sprachen(=reguläre Sprachen)

458

Chomsky-Hierarchie

Folgerung aus der Definition:L3 ⊂ L2 und L1 ⊂ L0

Später: • L2 ⊂ L1

• Alle Inklusionen sind echt.

459

Chomsky-0-Grammatiken (T5.2)

Ziel: Chomsky-0-Sprachen = rek. aufz. Sprachen

Grammatik: S → Wort*

Turing-Maschine: Wort akz. Konfig.

D.h.: Die Rechnung einer Grammatik verläuft„anders herum“.

460

Rek. Aufz. ⇒ Chomsky-0-Grammatik

Satz T5.2.1: L rekursiv aufzählbar ⇒Es gibt Chomsky-0-Grammatik G mit L(G)=L.

Beweis: Sei L rekursiv aufzählbar und M zugehörige deterministische Turingmaschine, d.h., • x∈L⇒M akzeptiert x,• x∉L⇒M läuft endlos.

461

Vereinfachungen von MM kann modifiziert werden, so dass gilt:• Der Startzustand q0 wird nur zu Beginn der

Rechnung benutzt.• Es gibt nur einen akzept. Zustand q*.• Vor dem Akzeptieren löscht M das Band.Startkonfiguration: q0 w1 … wnAkzep. Konfiguration: q*

462

„Rückwärtsrechnung“ von GV = Q ∪ {S,L,R,X,Y} ∪ (Γ – Σ), Startsymbol S

T = ΣRegeln:1. Erzeugung der Endkonfiguration:

S → Lq*R, q* → q*B, q* → Bq*2. Rückwärtsrechnung:

– δ(q,a)=(q´,a´,1): a´q´ → qa,– δ(q,a)=(q´,a´,–1): q´ba´ → bqa f.a. b∈Γ– δ(q,a)=(q´,a´,0): q´a´ → qa.

EingabealphabetBandalphabet

463

3. Schlussregeln für den Test, ob tatsächlich eine Startkonfiguration beschrieben wird, und zum Löschen der Randmarkierungen:

Bq0 → q0

Lq0 → q0

q0a→ aX f.a. a ∈ΣXa→ aX f.a. a ∈ΣXB → YYB → YYR → εXR → εq0B → Y

Zeichen links des hergel. Wortes löschen

Zum rechten Ende deshergel. Wortes „gehen“

Zeichen rechts des hergel.Wortes löschen

Sonderfall „leeres Wort“

464

Korrektheit

1. L(M)⊆L(G).

Sei c1,…,cm eine akzeptierende Rechnung für w1…wn von M.Dann gibt es in G die HerleitungS � Lq*R� LB…Bq*B…BR = LB…BcmB…BR� LB…Bcm–1B…BR � …� LB…Bc1B…BR = LB…Bq0w1…wnB…BR � w1…wn.

*

*

465

Korrektheit

2. L(G)⊆L(M).

Sei S � Lq*R � w1…wn Herleitung in G.

• L,R, Zustandssymbol können nur mit den Schlussregeln entfernt werden ⇒ LB…Bq0w1…wnB…BR wurde erreicht.

• Die Herleitung Lq*R � LB…Bq0w1…wnB…BR entspricht einer umgekehrten Rechnung von M. ⇒M akzeptiert w1…wn.

*

*

466

Beispiel

Rechnung von M auf „ ab“:q0ab→ cq1b→ cdq2B → cq3dB → q4cBB →q*BBB

Herleitung in G:S → Lq*R → Lq*BR → Lq*BBR → Lq*BBBR→ Lq4cBBR → Lcq3dBR → Lcdq2BR→ Lcq1bBR → Lq0abBR → q0abBR → aXbBR → abXBR → abYR → ab

467

Chomsky-0-Grammatik ⇒ Rek. Aufz.

Satz T5.2.2: Wenn L durch eine Chomsky-0-Grammatik G beschrieben wird, gibt es eine NTM M, die L akzeptiert.

Beweis: Algo von M:

• Schreibe S auf freie Spur.• Iteriere:

– Führe nichtdeterministisch gewählte Ableitungsregel aus

– Vergleiche hergeleitetes Wort mit Eingabe, akzeptiere bei Gleichheit.

468

Umformung NTM �DTM

Satz T5.2.3: Wenn L durch eine NTM Makzeptiert wird, ist L rekursiv aufzählbar.

Beweis: Konstruktion einer DTM für L:For i:=0 to ∞

Sim. alle Rechenwege von M der Länge i. Falls akzeptierende Konfiguration erreicht wird, akzeptiere.

469

Charakterisierung rek. aufz. Spr.

Folgerung T5.2.4:Die Menge der rekursiv aufzählbaren

Sprachen ist gleich1. der Menge der von DTMs akzeptierten

Sprachen,2. der Menge der von NTMs akzeptierten

Sprachen,3. der Menge der von Chomsky-0-

Grammatiken erzeugten Sprachen.

470

Chomsky-3-Grammatiken (T5.3)

Ziel:Äquivalenz von Chomsky-3-Grammatiken und

DFAs.

471

DFA � Chomsky-3-Grammatik

Satz T5.3.1:Sei M ein DFA für L. Dann gibt es auch eine

rechtslineare Grammatik G für L.

Beweis:Idee: Rechnung von M mit einer Grammatik

simulieren.V=Q, T=Σ, S=q0,Ableitungsregeln: q� aq´, falls δ(q,a)=q´,

q� ε, falls q∈F.

472

Korrektheit

Rechnung des DFA auf einem Wort w1…wn:

Zustandsfolge q0,q1,…,qn mit δ(qi,wi+1)=qi+1

und qn∈F.

�„Rechnung“ der erzeugten Grammatik:q0 � w1q1 � w1w2q2 � … � w1…wnqn �

w1…wn

q� aq´, falls δ(q,a)=q´,q� ε, falls q∈F.

473

Chomsky-3-Grammatik � NFA

Satz T5.3.1:Sei G eine rechtslineare Grammatik für L.

Dann gibt es auch einen NFA M für L.

Beweis:

Sei rechtslin. Grammatik für L gegeben.

Konstruktion des NFAs:

Q=V, q0=S, F= {A | Regel A�ε vorhanden}

δ(A,a)={B | Regel A� aB vorhanden}

474

Korrektheit

Ableitung von w1…wn hat die FormS�w1A1�w1w2A2�…�w1…wnAn�w1…wn

⇔Mögliche Zustandsfolge des NFAs bei Eingabe w1,…,wn:S� A1 � A2 � … � An

Q=V, q0=S, F= {A | Regel A�ε vorhanden}

δ(A,a)={B | Regel A� aB vorhanden}

475

Charakterisierung d. reg. Sprachen

Folgerung: Die Menge der regulären Sprachen ist gleich

• der Menge der von DFAs oder NFAserkannten Sprachen,

• der Menge der Sprachen, die durch reguläre Ausdrücke beschrieben werden,

• der Menge der Sprachen, die durch Chomsky-3-Grammatiken beschrieben werden.

476

Beobachtung

Grammatiken sind ein auf natürliche Weise nichtdeterministisches Konzept.

Simulationen von Ableitungen einer Grammatik werden mit Hilfe von nichtdeterministischen Maschinen besonders einfach.

477

Kontextfreie Sprachen (Kap. T6)

Überblick:• Beispiele kontextfreier Sprachen• Chomsky-Normalform• Wortproblem für kontextfreie Sprachen• Pumping-Lemma• Mehrdeutigkeit• Algorithmen• Unentscheidbare Probleme• Greibach-Normalform• Maschinenmodell für kontextfreie Sprachen

478

Beispiel: L={0n1n | n≥1}

Haben gesehen: L nicht regulär

(Folien 338 und 346)

Kontextfreie Grammatik:

V={S}, Σ={0,1}, P={S�01, S� 0S1}

� L kontextfrei

479

Variante: L={0i1j | 1�i�j}

Kontextfreie Grammatik:V={S}, Σ={0,1}, P={S�01, S� 0S1, S�S1}

� L kontextfrei

480

Bsp: Sprache der Palindrome

L={w∈{0,1}* | w=wR}

• Haben gesehen: L nicht regulär (Folie 347)• Kontextfreie Grammatik G:

V={S}, Σ={0,1}, P={S�ε, S�0, S�1, S�0S0, S�1S1}

• Korrektheit:–G erzeugt nur Palindrome.– Alle Palindrome können durch G erzeugt

werden.

L(G)⊆L

L⊆L(G)

481

G erzeugt nur Palindrome.

Behauptung: Alle von G erzeugten Wörter wsind Palindrome.

Induktion über | w|:|w|=0 oder |w|=1: ε, 0, 1 sind Palindrome.

|w|>1: Die erste angewandte Regel ist S�0S0 oder S�1S1, d.h., w beginnt und endet mit demselben Buchstaben. Nach I.V. ist das Wort dazwischen Palindrom ⇒ w Palindrom.

V={S}, Σ={0,1}, P={S�ε, S�0, S�1, S�0S0, S�1S1}

482

Alle Palindrome w in G herleitbar.

Induktion über | w|:|w|=0 oder |w|=1: ε, 0, 1 sind herleitbar.

|w|>1: w Palindrom ⇒ w beginnt und endet mit 0 (bzw. 1); dazwischen befindet sich ein Palindrom w´, also w=0w´0 oder w=1w´1.

Nach I.V. ist w´ aus S herleitbar.⇒ S � 0S0 � 0w´0 = w bzw.

S � 1S1 � 1w´1 = w.V={S}, Σ={0,1}, P={S�ε, S�0, S�1, S�0S0, S�1S1}

**

483

Klammersprache

w=w1...wn∈{(,)}* heißt korrekt geklammert, falls

• die Anzahl „(“ ist gleich der Anzahl „)“.• in jedem Anfangsstück w1,...,wi (i�n) ist die

Anzahl „(“ nicht kleiner als die Anzahl „)“.

DefiniereL={w∈{(,)}* | w korrekt geklammert}

Nicht regulär � Folie 349f

Kontextfreie Grammatik: S�SS, S�(S), S�ε.

484

Bsp: L={w| |w|0=|w|1}

|w|0: Anzahl Nullen in w,|w|1: Anzahl Einsen in w.• Übungsaufgabe: Zeige, dass L nicht regulär.• Kontextfreie Grammatik G:

V={S}, Σ={0,1}P={S�ε, S�0S1S, S�1S0S}

• Korrektheit:–G erzeugt nur Wörter aus L.–G erzeugt alle Wörter aus L.

L(G)⊆LL⊆L(G)

485

Beispiel

Ableitung von 110010S�1S0S� 11S0S0S � 1100S� 11001S0S� 110010

P={S�ε, S�0S1S, S�1S0S}

S

1 S 0 S

1 S 0 S 1 S 0 S

ε εε ε

Syntax-baum

486

Korrektheit: L(G)⊆LG erzeugt nur Wörter aus L :

folgt, da bei jedem Ableitungsschritt gleichviele Nullen wie Einsen erzeugt werden.

P={S�ε, S�0S1S, S�1S0S}

487

Korrektheit: L⊆L(G)Induktion über |w|• |w|=0 � w=ε ∈ L(G).• |w|>0, o.B.d.A. beginne w mit 0.

Sei i>0 kleinste Zahl m. |w1…wi|0 = |w1…wi|1. Dann gilt: w1=0, wi=1, |w2…wi–1|0 = |w2…wi–1|1und |wi+1…wn|0=|wi+1…wn|1.

Also w2…wi–1∈ L und wi+1…wn∈ L und

S� 0S1S � 0w2…wi–11wi+1…wn.*

I.V.

488

Syntaxbaum

Graphische Darstellung der Ableitung eines Wortes

• Wurzel: markiert mit S.• Blätter: markiert mit Terminalen/Buchstaben

oder ε.• Innere Knoten:

– markiert mit Variablen A– Nachfolger entsprechen Anwendung einer

Ableitungsregel A�αααα1…ααααr.

489

Anmerkungen

• Zu jeder Ableitung gibt es einen Syntaxbaum.

• Zu einem Syntaxbaum kann es mehrere (äquivalente) Ableitungen geben.

• Linksableitung: Ableitung, bei der die jeweils linkeste Variable ersetzt wird.

• Rechtsableitung: Ableitung, bei der die jeweils rechteste Variable ersetzt wird.

490

Eindeutigkeit und Mehrdeutigkeit

Definition T6.1.5:Eine kontextfreie Grammatik G heißt

eindeutig , wenn es für jedes Wort w∈L(G) nur einen Syntaxbaum gibt.

Eine kontextfreie Sprache heißt eindeutig , wenn es für sie eine eindeutige kontextfreie Grammatik gibt, anderenfalls heißt sie inhärent mehrdeutig .

491

Beispiel: Klammersprache

Die Grammatik S�SS, S�(S), S�ε ist nicht eindeutig. Beispiel: ()()()

Linksableitungen: S�SS�SSS�(S)SS�()SS�()(S)S�()()S�()()(S)�()()()

S�SS�(S)S�()S�()SS�()(S)S�()()S�()()(S)�()()()

Eindeutige Grammatik: S�(S)S, S�ε

492

Weiteres Beispiel

S�ε, S�0S1S, S�1S0S ist mehrdeutig:das Wort 011001 hat die Linksableitungen

S�0S1S�01S0S1S�011S0SS0S1S�011001

undS�0S1S�01S�011S0S�0110S�

01100S1S�011001Etwas schwieriger: Konstruktion einer

eindeutigen Grammatik.

*

*

493

Beispiel

Die Grammatik S�01, S� 0S1 für L={0n1n | n≥1} ist eindeutig.

494

Motivation

• Nahe liegende Vermutung: Syntaxanalyse für eindeutige Grammatiken einfacher.

• Verschiedene Ableitungsbäume haben bei Programmiersprachen häufig verschiedene Semantiken, Beispiel: dangling else.

495

Chomsky-Normalform

Ziel: einfachere Algorithmen für kontextfreie Grammatiken.

Definition T6.2.1: Eine kontextfreie Grammatik ist in Chomsky-Normalform, wenn alle Ableitungsregeln von der FormA� BC oder A� a (mit A,B,C∈V, a∈T)sind.

496

Chomsky-Normalform

Besonderheit: ε kann nicht erzeugt werden.Im Folgenden Umformung

G G´

Kontextfreie Kontextfreie GrammatikGrammatik in Chomsky-Normalform

mit L(G´) = L(G) – {ε}

497

Umformung

Sei s(G) die Größe (Anzahl der Buchstaben in allen Produktionen) der kontextfreien Grammatik G.

Satz T6.2.2: Eine kontextfreie Grammatik Gkann in Zeit O(s(G)2) in Chomsky-Normalform umgeformt werden.

Beweis: Umformung in 4 Schritten

498

Schritt 1: Separation

Ziel: Auf den rechten Seiten der Regeln entweder

• 1 Terminal oder• nur Variablen.Dazu:• erzeuge für jedes a∈T eine neue Variable Ya

und die Regel Ya�a,

• Ersetze auf jeder rechten Seite einer Regel a durch Ya.

499

Beispiel für Schritt 1

A� AbcDeF (mit A,D,F∈V, b,c,e∈T)

wird ersetzt durch

A� AYbYcDYeF, Yb�b, Yc�c, Ye�e

500

Schritt 2: Lange rechte Seiten

A�B1…Bm (mit m≥3, A,B1,…,Bm∈V)

wird ersetzt durch

A� B1C1

C1� B2C2

Ci � Bi+1Ci+1 (für 1�i�m–3)

Cm–2 � Bm–1Bm

Dabei sind C1,…,Cm–2 neue Variablen, die nur für die betrachtete Regel eingeführt werden.

501

Resultat der Schritte 1 und 2

Nur noch Regeln der Form:A� ε (ε-Regeln)A� B (Kettenregeln)A� BC (o.k.)A� a (o.k.)

Bisher: Grammatik hat sich nur um konstanten Faktor vergrößert.

502

Schritt 3: Beseitigung der εεεε-Regeln

1. Teilschritt: Finde alle Var. A mit A�ε.Initialisierung: Variablen A mit Regel A�ε in

Mengen V ´ und Q einfügen.Solange Q≠∅

– Variable B aus Q entnehmen.

– Auf allen rechten Seiten von allen Regeln B durch ε ersetzen.

– Falls neue Regel C�ε entsteht (d.h.C∉V ´): C in V ´ und Q aufnehmen.

Ausgabe: V ´

*

503

Korrektheit des 1. Teilschritts

Behauptung: V ´ enthält genau die Variablen A mit A� ε.

„⊆“ offensichtlich.„⊇“ Induktion über die Länge l der kürzesten

Ableitung A� ε.l=1: Es gibt die Regel A� ε. Dann wird A in V ´ eingefügt.

l>1: Dann A� BC� ε oder A� B � ε.Dann haben B (und C) ε-Ableitungen mit Länge <l und kommen in V ´.

�A wird in V ´ aufgenommen.

*

*

* *

504

Beseitigung der εεεε-Regeln, 2. Teil

• Entferne alle ε-Regeln.• Für jede Regel A�BC:

Falls B∈V ´: erzeuge Regel A�C,falls C∈V ´: erzeuge Regel A�B.

Resultat: Grammatik vergrößert sich nur um konstanten Faktor.

505

Schritt 4: Entf. der Kettenregeln

1. Teilschritt: Äquivalente Variablen entfernen.

• Erzeuge Graphen:Knoten: VariablenKante A�B, falls Kettenregel A�B vorh.

• Suche mit DFS nach KreisenA1 � A2 � A3 � … � Ar � A1

Dann sind A2,…,Ar zu A1 äquivalent und können überall durch A1 ersetzt werden.

506

Schritt 4: Entf. der Kettenregeln

2. Teilschritt: Kettenregeln beseitigen• Ber. Graphen d. Kettenregeln, ist kreisfrei.• Ber. topologische Ordnung A1,…,Ar.• For i:=r downto 1 do

Seien Ai�α1,…,Ai�αs die Regeln mit linker Seite Ai.

Falls Aj�Ai mit j<i vorhanden, lösche Aj�Ai und

erzeuge Aj�α1,…,Aj�αs.

507

Beispiel für den 2. Teilschritt

Graph der Kettenregeln (auf A,B,C,D,E):A D aB E b

RSTopologische Nummerierung berechnenRegeln für E: C�b, C�RS, B�b, B�RSRegeln für D: C�a, (C�b)Regeln für C: A�a, A�b, A�RS, B�a,

B�b, B�RS

C1

2

3 4

5

508

Größenänderung im 4. Schritt

Sei A1,…,Ar die topol. Ordnung der Var.

Im ungünstigen Fall:• Alle Ar-Regeln werden zu A1-,...,Ar–1-

Regeln,• alle Ar–1-Regeln werden zu A1-,...,Ar–2-

Regeln, usw.� Höchstens Quadrierung der Größe.

509

Folgerung

Zu jeder kontextfreien Grammatik G gibt es eine äquivalente kontextsensitive Grammatik, also L2⊂L1.

Chomsky-HierarchieL3 ⊂ L2 ⊂ L1 ⊂ L0≠≠≠≠ ≠≠≠≠ ≠≠≠≠

{0n1n}

{w| |w|a=|w|b=|w|c}

Alle kontextsens.Sprachen sind rekursiv.