Aus Informatik

ACHTUNG SPOILER ... wer das liest, dem is am Montag während meinem Referat langweilig ;-)

Inhaltsverzeichnis

1 Bearbeitungsplan
2 Problem
3 LookAhead Parser
4 Quellen

Bearbeitungsplan

Aneignung der Theorie -check
Aufstellen eines Konzeptes (agile methology) -check
grobes Design aufstellen -check
Schreiben des Hauptprogramms -check
- erkennen der First und Follow Mengen -check
- Ausgabe der First und Follow Mengen -check
- (Ausgabe einer Parsingtabelle) -check
- (Anwendung der Parsingtabelle in einem Parser)
Refactoring -check
Verfeinerung des Designs
Erstellen der Präsentation -check

Problem

Beginnt ein Wort mit a wird die erste, sonst die zweite Alternative für S gewählt. Soll B abgeleitet werden, kann man auch immer am ersten Zeichen entscheiden, welche Produktion angewendet werden muss.

Das funktioniert bei der folgenden Grammatik nicht:

Wenn man einen Satz ableiten will, der mit ccc beginnt, kann man mit dem ersten c nicht entscheiden, ob angewendet werden soll.

Lösung des Problems : ein LookAhead Parser

LookAhead Parser

benötigt: kontextfreie Grammatik ohne Linksrekursion

Der LookAhead Parser erstellt First & Follow Mengen, mit deren Hilfe er eine LookAhead Menge / Parsingtabelle generiert. Mit dieser Tabelle können Grammatiken rekursivfrei geparst werden.

Umsetzung:

First Menge

Definintion:

First(X) soll alle Terminale liefern, mit welchen X beginnen könnte.

Regeln für die Bestimmung der First Mengen:

Für alle Produktion werden folgende Regeln solange angewendet bis sich nichts mehr an den First Mengen ändert.

Beispiel:

Als erstes werden die First Mengen mit {} initialisiert

FIRST(E) = {}
FIRST(E') = {}
FIRST(T) = {}
FIRST(T') = {}
FIRST(F) = {}

Für T' → ε und E' → ε wenden wir die 2. Regel an.

FIRST(E) = {}
FIRST(E') = {ε}
FIRST(T) = {}
FIRST(T') = {ε}
FIRST(F) = {}

Wir benutzen Regel 3 für E' → +TE', hier fügen wir alles in First(+TE') bei First(E') ein.

Da First(+) Regel 1 benötigt fügen wir + in First(E') ein.

FIRST(E) = {}
FIRST(E') = {+,ε}
FIRST(T) = {}
FIRST(T') = {ε}
FIRST(F) = {}

Wir benutzen Regel 3 für T' → *FT', hier fügen wir alles in First(*FT') bei First(T') ein.

Da First(*) Regel 1 benötigt fügen wir * in First(T') ein.

FIRST(E) = {}
FIRST(E') = {+,ε}
FIRST(T) = {}
FIRST(T') = {*,ε}
FIRST(F) = {}

Zwei andere Produktionen beginnen mit Terminalen F → (E) und F → id, wenn wir hier auch die 3. Regel anwenden erhalten wir folgendes...

FIRST(E) = {}
FIRST(E') = {+,ε}
FIRST(T) = {}
FIRST(T') = {*,ε}
FIRST(F) = {'(',id}

Jetzt wenden wir die 3. Regel auch für T → FT' an, hier können wir First(FT') zu First(T)hinzufügen.

Da First(F) nicht ε erhält, ist First(FT') nur First(F)

FIRST(E) = {}
FIRST(E') = {+,ε}
FIRST(T) = {'(',id}
FIRST(T') = {*,ε}
FIRST(F) = {'(',id}

Nun wenden wir die 3. Regel auf E → TE' an, hier können wir First(TE') zu First(E) hinzufügen.

Da First(T) nicht ε enthält, ist First(TE') nur First(T).

FIRST(E) = {'(',id}
FIRST(E') = {+,ε}
FIRST(T) = {'(',id}
FIRST(T') = {*,ε}
FIRST(F) = {'(',id}

Da alles andere die Mengen nicht verändert sind wir fertig.

Umsetzung

       /// <summary>
       ///  erstellt die Firstsets
       /// </summary>
       private void createFirstSets()
       {
           string tempString;
           for (int i=0; i < (DGV_console.Rows.Count-1); i++)
           {
               tempString = Convert.ToString(DGV_console[0, i].Value);   
               // DGV_console[0,i] = Zeilen Tabelle in der die Produktion steht
               first(tempString.Substring(0, (tempString.IndexOf('-'))).Trim(), tempString.Substring((tempString.IndexOf('>') + 1), 
(tempString.Length - (tempString.IndexOf('-') + 2))).Trim());
               //first(linke Seite der Produktion, rechte Seite der Produktion)
           }
       }

       /// <summary>
       ///  hier werde die Firstmengen gebildet 
       /// und in ein Array firsets geschrieben
       /// </summary>
       /// <param name="nonterm"></param>
       /// <param name="term"></param>
       private void first(string nonterm, string term)
       {
           List<string> splittedterm = splitup(term);
           string tempFirstsets;
           bool containsEpsilon = true;
           int xtemp = 0;
           int  splittedtermCount = splittedterm.Count - 1; // kommt immer ein Element mehr vor als wirklich drin is
           if (terminals.isTerminal(splittedterm[0])) // wenn das erst Element terminal ist
           {
               firstsets[nonTerminals.getNonterminalIndex(nonterm)] = firstsets[nonTerminals.getNonterminalIndex(nonterm)] + 
splittedterm[0];
           }
           else
           {
               bool epsilon = true;
               int i = 0;
               string tempFirst ="";
               while (epsilon & (i < splittedtermCount))
               {
                   if (nonTerminals.isNonterminal(splittedterm[i]))
                   {
                       tempFirst = firstsets[nonTerminals.getNonterminalIndex(splittedterm[i])];
                       if (tempFirst.IndexOf('ε') < 0)
                       {
                           firstsets[nonTerminals.getNonterminalIndex(nonterm)] = 
firstsets[nonTerminals.getNonterminalIndex(nonterm)] + tempFirst;
                           epsilon = false;
                       }
                       else firstsets[nonTerminals.getNonterminalIndex(nonterm)] = 
firstsets[nonTerminals.getNonterminalIndex(nonterm)] + tempFirst.Remove(tempFirst.IndexOf('ε'),1);
                   }
                   else 
                       if(terminals.isTerminal(splittedterm[i]))
                       {
                           if (splittedterm[i] == "ε")
                           {
                               //nichts
                           }
                           else
                           {
                               firstsets[nonTerminals.getNonterminalIndex(nonterm)] = 
firstsets[nonTerminals.getNonterminalIndex(nonterm)] + splittedterm[i];
                               epsilon = false;
                           }
                       }
                   i++;
               }
               if (epsilon & (i >= splittedtermCount))
                   firstsets[nonTerminals.getNonterminalIndex(nonterm)] = firstsets[nonTerminals.getNonterminalIndex(nonterm)] + 'ε';
           }    
       }

Follow Menge

Für ein Nichterminal X liefert Follow(X) alle Terminale die direkt hinter X stehen können.

Regeln zur Bestimmung der Follow Mengen

Folgende Regeln werden auf alle Produktionen angwendet bis sich nichts mehr an den Follow Mengen ändert.

Beispiel

Die Mengen mit {} erstellen und $ bei S hinzufügen

Wir wenden Regel 2 auf F -> (E) an, hier wird First(')') zu Follow(E) hinzugefügt.

Wir wenden Regel 3 auf E -> TE' an, hier wir alles aus Follow(E) zu Follow(E') hinzugefügt.

Da First(E') ε enthalten kann, wird Follow(E) bei Follow(T) hinzugefügt

Da E' auf T folgt wird First(E')\ ε bei Follow(T) hinzugefügt.

Die Produktion T -> FT' endet mit T', deswegen fügt, wegen Regel 3, Follow(T) bei Follow(T') hinzu.

Bei der Produktion T' -> *FT' kann First(T') ε werden, deswegen wird Follow(F) Follow(T') hinzugefügt.

Da bei der Produktion T -> FT' - T' auf F folgt - wird First(T')\ε zu Follow(F) hinzugefügt.

Umsetzung

       private void createFollowsets()
       {
           string tempString;
           followsets[nonTerminals.getNonterminalIndex(TB_start.Text)] = "$";
           for (int i = 0; i < (DGV_console.Rows.Count - 1); i++)
           {
               tempString = Convert.ToString(DGV_console[0, i].Value);
               follow(tempString.Substring(0, (tempString.IndexOf('-'))).Trim(), tempString.Substring((tempString.IndexOf('>') + 1),
 (tempString.Length - (tempString.IndexOf('-') + 2))).Trim());
           }
       }

       private void follow(string nonterm, string term)
       {
           List<string> splittedTerm = splitup(term);
           for (int i = 0; i < (splittedTerm.Count -1); i++)
           {
               if (nonTerminals.isNonterminal(splittedTerm[i]))
               {
                   if ((i + 1) < splittedTerm.Count -1)
                   {
                       if (terminals.isTerminal(splittedTerm[(i + 1)]))
                       {
                           followsets[nonTerminals.getNonterminalIndex(splittedTerm[i])] = 
followsets[nonTerminals.getNonterminalIndex(splittedTerm[i])] + splittedTerm[(i + 1)];
                       }
                       if (nonTerminals.isNonterminal(splittedTerm[(i + 1)]))
                       {
                           int x = (i + 1);
                           bool epsilon = true;
                           while ((x < (splittedTerm.Count - 1))& epsilon)
                           {
                               if (nonTerminals.isNonterminal(splittedTerm[x]))
                               {
                                   string tempFirst = firstsets[nonTerminals.getNonterminalIndex(splittedTerm[x])];
                                   if (tempFirst.IndexOf('ε') < 0)
                                   {
                                       followsets[nonTerminals.getNonterminalIndex(splittedTerm[i])] = followsets[nonTerminals.getNonterminalIndex(splittedTerm[i])] + tempFirst;
                                       epsilon = false;
                                   }
                                   else
                                   {
                                       followsets[nonTerminals.getNonterminalIndex(splittedTerm[i])] = 
followsets[nonTerminals.getNonterminalIndex(splittedTerm[i])] + tempFirst.Remove(tempFirst.IndexOf('ε'),1) + 
followsets[nonTerminals.getNonterminalIndex(nonterm)];
                                   }
                               }
                               if (terminals.isTerminal(splittedTerm[x]))
                               {
                                   followsets[nonTerminals.getNonterminalIndex(splittedTerm[i])] = followsets[nonTerminals.getNonterminalIndex(splittedTerm[i])] + splittedTerm[x];  
                               }
                               x++;
                           }
                       }
                   }
                   if (i == (splittedTerm.Count-2))
                   {
                       followsets[nonTerminals.getNonterminalIndex(splittedTerm[i])] = 
followsets[nonTerminals.getNonterminalIndex(splittedTerm[i])] + followsets[nonTerminals.getNonterminalIndex(nonterm)];
                   }
               }
               
           
           }
     }

LookAhead Menge / Parsingtabelle

Erläuterung

Beispiel

M[v,t] wird mit {} initialisiert

Da ε nicht in First(T) enthalten ist, gilt Regel 4.1.

Weil ε nicht in First(+) enthalten ist, gilt Regel 4.1.

Da First(ε) ε enthält, wird die Produktion zu allen Elementen der Follow Mengen hinzugefügt.

Da First(F) nicht ε enthält, gilt Regel 4.1.

Da First(*) nicht ε enthält, gilt Regel 4.1.

Da First(ε) ε enthält, wird die Produktion zu allen Elementen der Follow Mengen hinzugefügt.

Da First('(') nicht ε enthält, gilt Regel 4.1.

Da First(id) nicht ε enthält, gilt Regel 4.1.

Wenn es jetzt keine Mehrfacheinträge gibt, kann man für jede Kombination von Symbolen entscheiden, welche Produktion angewendet werden soll.

---> Ausgangsproblem gelöst!

Umsetzung

       private void createLASets()
       {
           string leftside = "";
           List<string> rightside;
           string temprightside = "";
           List<string> splittedFirst;
           List<string> splittedFollow;
           for (int i = 0; i < (DGV_console.Rows.Count -1); i++)
           { 
               leftside = DGV_console[0,i].Value.ToString().Substring(0,DGV_console[0,i].Value.ToString().IndexOf('-')).Trim();
               temprightside = DGV_console[0, i].Value.ToString().Substring((DGV_console[0, i].Value.ToString().IndexOf('>') + 
1)).Trim(); 
               rightside = splitup(temprightside);
               if (terminals.isTerminal(rightside[0]))
               {
                   if (!(rightside[0] == "ε"))
                       DGV_laSets[(terminals.getTerminalIndex(rightside[0])+1), nonTerminals.getNonterminalIndex(leftside)].Value = DGV_console[0, i].Value;
                   else
                   {
                       splittedFollow = splitup(followsets[nonTerminals.getNonterminalIndex(leftside)]);
                       for (int y = 0; y < (splittedFollow.Count - 1); y++)
                       {
                           if (!(splittedFollow[y] == "$"))
                           {
                               DGV_laSets[(terminals.getTerminalIndex(splittedFollow[y])+1), 
nonTerminals.getNonterminalIndex(leftside)].Value = DGV_console[0, i].Value;
                           }
                           else
                           {
                               DGV_laSets[((DGV_laSets.Columns.Count-1)), nonTerminals.getNonterminalIndex(leftside)].Value = 
DGV_console[0, i].Value;
                           }
                       }
                   }
               }
               else
               {
                   splittedFirst = splitup(firstsets[nonTerminals.getNonterminalIndex(rightside[0])]);
                   for(int x = 0; x < (splittedFirst.Count-1) ; x++)
                   {
                       if(splittedFirst[x] == "ε")
                       {
                           splittedFollow = splitup(followsets[nonTerminals.getNonterminalIndex(leftside)]);
                           for (int y = 0; y < (splittedFollow.Count - 1); y++)
                           {
                               if (!(splittedFollow[y] == "$"))
                               { 
                                   DGV_laSets[(terminals.getTerminalIndex(splittedFollow[y])+1), 
nonTerminals.getNonterminalIndex(leftside)].Value =  DGV_console[0, i].Value;
                               }
                           }
                       }
                       else
                       {
                           DGV_laSets[(terminals.getTerminalIndex(splittedFirst[x])+1), 
nonTerminals.getNonterminalIndex(leftside)].Value =  DGV_console[0, i].Value;
                       }
                   }
               }
           }
       }