Parser LL

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Parser LL to parser czytający tekst od lewej do prawej i produkujący lewostronne wyprowadzenie metodą zstępującą. Popularne rodzaje parserów LL to parsery sterowane tablicą i rekurencyjne.

Parser sterowany tablicą[edytuj | edytuj kod]

Parsery klasy LL(k) parsują znak po znaku, utrzymując stos zawierający „spodziewane symbole”. Na początku znajdują się tam symbol startowy i znak końca pliku. Jeśli na szczycie stosu jest ten sam symbol terminalny, jaki aktualne znajduje się na wejściu, usuwa się go ze szczytu stosu i przesuwa strumień wejściowy na kolejny znak. Jeśli inny symbol terminalny zwraca się błąd. Jeśli występuje tam jakiś symbol nieterminalny, to zdejmuje się go i zależnie od tego symbolu oraz od k kolejnych znaków wejścia, umieszcza na stosie odpowiedni zestaw symboli.

LL(1) jest bardzo ubogą klasą (jednak w wielu przypadkach wystarczająca), np. tak prosta gramatyka jak:

  • Wyrażenie → liczba '+' Wyrażenie
  • Wyrażenie → liczba

już do niej nie należy, ponieważ spodziewając się Wyrażenia i widząc liczbę, nie wiemy czy zamienić ją na stosie na liczba czy liczba '+' Wyrażenie.

Na szczęście można przepisać tę gramatykę na równoważną gramatykę LL(1):

  • Wyrażenie → liczba OpcjonalnePlusWyrażenie
  • OpcjonalnePlusWyrażenie → ε
  • OpcjonalnePlusWyrażenie → '+' Wyrażenie

Zbudujmy tablicę parsingu dla gramatyki:

  • Wyrażenie → Iloczyn '+' Wyrażenie
  • Wyrażenie → Iloczyn
  • Iloczyn → liczba '*' Iloczyn
  • Iloczyn → liczba

Najpierw musimy przepisać ją do równoważnej gramatyki LL(k) (w tym przypadku k jest równe 1):

  • Wyrażenie → Iloczyn OpcjonalnePlusWyrażenie
  • OpcjonalnePlusWyrażenie → ε
  • OpcjonalnePlusWyrażenie → '+' Wyrażenie
  • Iloczyn → liczba OpcjonalneRazyIloczyn
  • OpcjonalneRazyIloczyn → ε
  • OpcjonalneRazyIloczyn → '*' Iloczyn

Tablica parsingu to:

liczba + * koniec
Wyrażenie Iloczyn OpcjonalnePlusWyrażenie błąd błąd błąd
OpcjonalnePlusWyrażenie błąd  + Wyrażenie błąd ε
Iloczyn liczba OpcjonalneRazyIloczyn błąd błąd błąd
OpcjonalneRazyIloczyn błąd ε * Iloczyn ε

I dla wyrażenia 5 + 3 * 8 * 2 + 7 * 2 parsing przebiega następująco:

Stos Wejście
Wyrażenie koniec liczba + liczba * liczba * liczba + liczba * liczba koniec
Iloczyn OpcjonalnePlusWyrażenie koniec liczba + liczba * liczba * liczba + liczba * liczba koniec
liczba OpcjonalneRazyIloczyn OpcjonalnePlusWyrażenie koniec liczba + liczba * liczba * liczba + liczba * liczba koniec
OpcjonalneRazyIloczyn OpcjonalnePlusWyrażenie koniec + liczba * liczba * liczba + liczba * liczba koniec
OpcjonalnePlusWyrażenie koniec + liczba * liczba * liczba + liczba * liczba koniec
+ Wyrażenie koniec + liczba * liczba * liczba + liczba * liczba koniec
Wyrażenie koniec liczba * liczba * liczba + liczba * liczba koniec
Iloczyn OpcjonalnePlusWyrażenie koniec liczba * liczba * liczba + liczba * liczba koniec
liczba OpcjonalneRazyIloczyn OpcjonalnePlusWyrażenie koniec liczba * liczba * liczba + liczba * liczba koniec
OpcjonalneRazyIloczyn OpcjonalnePlusWyrażenie koniec * liczba * liczba + liczba * liczba koniec
* Iloczyn OpcjonalnePlusWyrażenie koniec * liczba * liczba + liczba * liczba koniec
Iloczyn OpcjonalnePlusWyrażenie koniec liczba * liczba + liczba * liczba koniec
liczba OpcjonalneRazyIloczyn OpcjonalnePlusWyrażenie koniec liczba * liczba + liczba * liczba koniec
OpcjonalneRazyIloczyn OpcjonalnePlusWyrażenie koniec * liczba + liczba * liczba koniec
* Iloczyn OpcjonalnePlusWyrażenie koniec * liczba + liczba * liczba koniec
Iloczyn OpcjonalnePlusWyrażenie koniec liczba + liczba * liczba koniec
liczba OpcjonalneRazyIloczyn OpcjonalnePlusWyrażenie koniec liczba + liczba * liczba koniec
OpcjonalneRazyIloczyn OpcjonalnePlusWyrażenie koniec + liczba * liczba koniec
OpcjonalnePlusWyrażenie koniec + liczba * liczba koniec
+ Wyrażenie koniec + liczba * liczba koniec
Wyrażenie koniec liczba * liczba koniec
Iloczyn OpcjonalneRazyWyrażenie koniec liczba * liczba koniec koniec
liczba OpcjonalneRazyIloczyn OpcjonalneRazyWyrażenie koniec liczba * liczba koniec
OpcjonalneRazyIloczyn OpcjonalneRazyWyrażenie koniec * liczba koniec
* Iloczyn OpcjonalneRazyWyrażenie koniec * liczba koniec
Iloczyn OpcjonalneRazyWyrażenie koniec liczba koniec
liczba OpcjonalneRazyIloczyn OpcjonalneRazyWyrażenie koniec liczba koniec
OpcjonalneRazyIloczyn OpcjonalneRazyWyrażenie koniec koniec
OpcjonalneRazyWyrażenie koniec koniec
koniec koniec

Warunek LL(1)[edytuj | edytuj kod]

Aby gramatyka była klasy LL(1) dla każdego symbolu nieterminalnego, produkcja powinna być rozpoznawana i wybierana już po podejrzeniu jednego symbolu terminalnego. Oznacza to, że dla każdej pary produkcji dla jednego symbolu nieterminalnego

  1. Z i nie da się wyprowadzić tego samego symbolu terminalnego
  2. Nie można jednocześnie wyprowadzić ciągu pustego z i
  3. Jeżeli z da się wyprowadzić ciąg pusty, wówczas z nie można wyprowadzić żadnego ciągu zaczynającego się od terminala należącego FOLLOW(A). Analogicznie w drugą stronę, gdy z da się wyprowadzić ciąg pusty.

Te warunki są równoważne

  1. i muszą być zbiorami rozłącznymi
  2. jeśli wtedy i muszą być zbiorami rozłącznymi i analogicznie gdy wtedy i muszą być zbiorami rozłącznymi

Transformacja do LL(1)[edytuj | edytuj kod]

Aby gramatyka dała się przekształcić do LL(1) musi być jednoznaczna, jednak nie każda jednoznaczna da się przekształcić. Mamy dwie transformacje, które dają szansę, że dostaniemy gramatykę LL(1):

  1. eliminacja lewostronnej rekursji
  2. lewostronna faktoryzacja

Eliminacja lewostronnej rekursji[edytuj | edytuj kod]

Mamy

  • Wyrażenie → Wyrażenie '+' liczba
  • Wyrażenie → liczba

Lewostronną rekurencję da się przepisać jako prawostronną:

  • ...
  • ...

przepisujemy na

  • ...
  • ...

Lewostronna faktoryzacja[edytuj | edytuj kod]

Mamy

  • Expr number '+' Expr
  • Expr number

Patrzymy ile pierwszych symboli (terminalnych i nieterminalnych) jest identycznych. Tu mamy tylko jeden symbol – number. Prawą stronę zamieniamy na nowy symbol: nazwijmy go PlusExpr

  • Expr number PlusExpr
  • PlusExpr '+' Expr
  • PlusExpr

Gdy więcej niż dwie produkcje zaczynają się od tego samego:

  • Expr number '+' Expr
  • Expr number '-' Expr
  • Expr number

Zamieniamy na

  • Expr number PlusMinusExpr
  • PlusMinusExpr '+' Expr
  • PlusMinusExpr '-' Expr
  • PlusMinusExpr

Gramatyka niejednoznaczna[edytuj | edytuj kod]

Czasami niejednoznaczna definicja gramatyki jest konieczna jak w przypadku IF..THEN..ELSE:

  • Stat if Expr then Stat else Stat
  • Stat if Expr then Stat

Po lewostronnej faktoryzacji:

  • Stat if Expr then Stat ElseStat
  • ElseStat else Stat
  • ElseStat

Gramatyka jest niejednoznaczna dla ElseStat w przypadku napotkania symbolu else. Rozwiązujemy to przyjmując wybór zachłanny

  • ElseStat else Stat

bo w przeciwnym razie gdybyśmy wybrali mógłaby zostać część else, która nie miała by wcześniejszego if.

Parser rekurencyjny[edytuj | edytuj kod]

Parsery LL można też łatwo pisać ręcznie, za pomocą zestawu wzajemnie wywołujących się funkcji.

znak następny_znak; /* zmienna globalna */

void parsujWyrażenie() {
  if (następny_znak == liczba)
  {
    parsujIloczyn();
    parsujOpcjonalnePlusWyrażenie();
  } else {
    błąd();
  }
}

void parsujIloczyn() {
  if (następny_znak == liczba)
  {
    następny_znak = odczytaj_znak();
    parsujOpcjonalneRazyIloczyn();
  } else {
    błąd();
  }
}

void parsujOpcjonalnePlusWyrażenie() {
  if (następny_znak == '+')
  {
    następny_znak = odczytaj_znak();
    parsujWyrażenie();
  } else if (następny_znak == KONIEC_PLIKU) {
    /* pusty ciąg znaków */
  } else {
    błąd();
  }
}

void parsujOpcjonalneRazyIloczyn() {
  if (następny_znak == '*')
  {
    następny_znak = odczytaj_znak();
    parsujIloczyn();
  } else if (następny_znak == '+' || następny_znak == KONIEC_PLIKU){
    /* pusty ciąg znaków */
  } else {
    błąd();
  }
}

void parsuj()
{
  następny_znak = odczytaj_znak();
  parsujWyrażenie();
  if (następny_znak != KONIEC_PLIKU)
    błąd();
}

Zobacz też[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

  • Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman: Kompilatory. Reguły, metody i narzędzia. Warszawa: WNT, 2002. ISBN 83-204-2656-1.