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:

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

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

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

Te warunki są równoważne

1. ${\displaystyle FIRST(\alpha )}$ i ${\displaystyle FIRST(\beta )}$ muszą być zbiorami rozłącznymi
2. jeśli ${\displaystyle \epsilon \in FIRST(\beta )}$ wtedy ${\displaystyle FIRST(\alpha )}$ i ${\displaystyle FOLLOW(A)}$ muszą być zbiorami rozłącznymi i analogicznie gdy ${\displaystyle \epsilon \in FIRST(\alpha )}$ wtedy ${\displaystyle FIRST(\beta )}$ i ${\displaystyle 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):

1. eliminacja lewostronnej rekursji
2. lewostronna faktoryzacja

Eliminacja lewostronnej rekursji

Mamy

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

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

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

przepisujemy na

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

Lewostronna faktoryzacja

Mamy

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

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

• Expr ${\displaystyle \to }$ number '+' Expr
• Expr ${\displaystyle \to }$ number '-' Expr
• Expr ${\displaystyle \to }$ number

Zamieniamy na

• Expr ${\displaystyle \to }$ number PlusMinusExpr
• PlusMinusExpr ${\displaystyle \to }$ '+' Expr
• PlusMinusExpr ${\displaystyle \to }$ '-' Expr
• PlusMinusExpr ${\displaystyle \to \epsilon }$

Gramatyka niejednoznaczna

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

• Stat ${\displaystyle \to }$ if Expr then Stat else Stat
• Stat ${\displaystyle \to }$ if Expr then Stat

Po lewostronnej faktoryzacji:

• Stat ${\displaystyle \to }$ if Expr then Stat ElseStat
• ElseStat ${\displaystyle \to }$ else Stat
• ElseStat ${\displaystyle \to \epsilon }$

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

• ElseStat ${\displaystyle \to }$ else Stat

bo w przeciwnym razie gdybyśmy wybrali ${\displaystyle \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ż

• Parser LR
• Zbiory First i Follow

Bibliografia

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