Parser LL

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, 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

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 {
    /* pusty ciąg znaków */
  }
}

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

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.