Parser LL

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ą

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)

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 $A\Rightarrow \alpha |\beta {:}$

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

Te warunki są równoważne

$FIRST(\alpha )$ i $FIRST(\beta )$ muszą być zbiorami rozłącznymi
jeśli $\epsilon \in FIRST(\beta )$ wtedy $FIRST(\alpha )$ i $FOLLOW(A)$ muszą być zbiorami rozłącznymi i analogicznie gdy $\epsilon \in FIRST(\alpha )$ wtedy $FIRST(\beta )$ i $FOLLOW(A)$ muszą być zbiorami rozłącznymi

Transformacja do LL(1)

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):

eliminacja lewostronnej rekursji
lewostronna faktoryzacja

Eliminacja lewostronnej rekursji

Mamy

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

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

$N\to N\alpha _{1}$
...
$N\to N\alpha _{m}$
$N\to \beta _{1}$
...
$N\to \beta _{n}$

przepisujemy na

$N\to \beta _{1}N'$
...
$N\to \beta _{n}N'$
$N'\to \alpha _{1}N'$
...
$N'\to \alpha _{m}N'$
$N'\to \epsilon$

Lewostronna faktoryzacja

Mamy

Expr $\to$ number '+' Expr
Expr $\to$ 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 $\to$ number PlusExpr
PlusExpr $\to$ '+' Expr
PlusExpr $\to \epsilon$

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

Expr $\to$ number '+' Expr
Expr $\to$ number '-' Expr
Expr $\to$ number

Zamieniamy na

Expr $\to$ number PlusMinusExpr
PlusMinusExpr $\to$ '+' Expr
PlusMinusExpr $\to$ '-' Expr
PlusMinusExpr $\to \epsilon$

Gramatyka niejednoznaczna

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

Stat $\to$ if Expr then Stat else Stat
Stat $\to$ if Expr then Stat

Po lewostronnej faktoryzacji:

Stat $\to$ if Expr then Stat ElseStat
ElseStat $\to$ else Stat
ElseStat $\to \epsilon$

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

ElseStat $\to$ else Stat

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

Parser rekurencyjny

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ż

Bibliografia

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