Parser LL


Parser LL w encyklopedii

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.

Spis treści

Parser sterowany tablicą | 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:

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

Warunek LL(1) | 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 A α | β : {\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. F I R S T ( α ) {\displaystyle FIRST(\alpha )} i F I R S T ( β ) {\displaystyle FIRST(\beta )} muszą być zbiorami rozłącznymi
  2. jeśli ϵ F I R S T ( β ) {\displaystyle \epsilon \in FIRST(\beta )} wtedy F I R S T ( α ) {\displaystyle FIRST(\alpha )} i F O L L O W ( A ) {\displaystyle FOLLOW(A)} muszą być zbiorami rozłącznymi i analogicznie gdy ϵ F I R S T ( α ) {\displaystyle \epsilon \in FIRST(\alpha )} wtedy F I R S T ( β ) {\displaystyle FIRST(\beta )} i F O L L O W ( A ) {\displaystyle FOLLOW(A)} muszą być zbiorami rozłącznymi

Transformacja do LL(1) | 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 kod

Mamy

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

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

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

przepisujemy na

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

Lewostronna faktoryzacja | edytuj kod

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 | edytuj kod

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 | 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 kod

Bibliografia | 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.
Na podstawie artykułu: "Parser LL" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy