Suche Home Einstellungen Anmelden Hilfe  

2.1 Berechnen des Linksparses

Der vorgestellte Algorithmus gibt bisher nur aus, ob ein Wort w der Sprache L(G) angehört oder nicht. Für den Fall, dass w Element von L(G) möchte man außerdem wissen, welche Ableitungen möglich sind. Der folgende Algorithmus berechnet aus der gefüllten Dreiecksmatrix einen Linksparse.

Eingabe:

    G in CNF G = (N,T, P, S), deren Regeln von 1 bis p nummeriert sind, ein Eingabewort w = x1x2 · · · xn aus T* und eine Parsematrix M.

Ausgabe: Linksparse für w (falls in L(G)) oder "Fehler".

Methode:

    genLP(i,j,A) generiert den Linksparse für A=>+ xixi+1 · · · xi+j-1. (Tij enthält A, falls der Linksparse existiert)

    genLP(i,j,A) =

    1. Falls j=1 und Ageht über inai die Regel mit der Nummer m in P ist, dann gebe m aus.
      Rekursionsanfang: Zur Ableitung des Teilwortes a wurde genau eine Regel genutzt.
    2. Falls j>1: k ist die kleinste Zahl zwischen 0 und j, so dass es A geht über in BC die m-te Regel ist, Tik B und T(i+k)(j-k) C enthält. Der Parse setzt sich zusammen aus m, das gefolgt wird von den Ergebnissen aus genLP(i,k,B), gefolgt von genLP(i+k,j-k,C).
      Der Linksparse ergibt sich aus der Ableitung des Teilwortes.

Start mit genLP(1,n,S)

Der Linksparse ergibt sich beim Top-Down-Vorgehen bei der Berechnung einer Linksableitung. Während einer Linksableitung findet folgender Vorgang wiederholt statt: Eine Regel (z.B. X geht über in YZ mit der Nummer m) wird expandiert. Anschließend wird das erste Nichtterminal der rechten Regelseite (hier Y) weiter expandiert.
Somit folgen im Linksparse auf die Regelnummer m die Nummern derjenigen Regeln, die zur Ableitung des Teilwortes unter Y nötig sind. Erst danach folgen die Regeln zur Ableitung des Teilwortes unter Z.

____
i,j,k - natürliche Zahlen

Algorithmus zurück 1   2   3   4   5 weiter Üben

Benutzer: Gast • Besitzer: matthias • Zuletzt geändert am: