Parsery LL(k)

W tym artykule przyjrzymy się parserom LL. Zarówno LL(1) podglądającemu jeden symbol, jak i LL(k) biorącemu pod uwagę k symboli. Parsery LL(k) będziemy generować w sposób „kanoniczny” – poprzez generowanie zbiorów podglądanych symboli długości k>1 („kanoniczny” w cudzysłowie, takie określenie w literaturze jest na określenie pewnego typu parserów LR, nie spotkałem natomiast niczego takiego dotyczącego LL)
Metody analizy syntaktycznej dzielą się na :
- analizę zstępującą, produkującą lewostronne wyprowadzenia – parsery LL (Left-to-Right, Leftmost Derivation)
- analizę wstępującą, choć również przetwarza wejście od lewej do prawej, to produkującą prawostronne wyprowadzenie – parsery LR (Left-to-Right, Rightmost Derivation)

Historycznie rzecz biorąc, parsery LR, które były generowane maszynowo, np.  z użyciem Bisona (który obecnie obsługuje również GLR) były bardziej zaawansowane i obsługiwały większą klasę gramatyk. Parsery LL były głównie tworzone ręcznie dla bardzo prostych gramatyk. Obecnie np. ANTLR używa bardzo zaawansowanego i wydajnego typu parserów z podglądem dowolnej liczby symboli, jednak w tym artykule nie będę się nim zajmował, zamiast tego, będzie poświęcony podstawom oraz pewnej metodzie zwiększenia liczby podglądanych symboli.

Jakkolwiek dla danego k, parsery LL pokrywają mniejszą klasę języków, jednak ich zalety to:
- rekurencyjna implementacja za pomocą procedur
- naturalne odzwierciedlenie gramatyki
- zrozumiały kod wygenerowanego parsera
- zwykle wcześniejsza detekcja błędów
- proste drzewa parsowania,

W parserach LL często dochodzi do konfliktów LL nawet dla typowych prostych gramatyk, które jednak można rozwiązać przez automatyczną modyfikację gramatyki.