Parser GLR

Parser GLR (ang. Generalized Left-to-right Rightmost derivation parser) – rozszerzenie parsera LR, umożliwiające analizę składniową z użyciem gramatyk niejednoznacznych i niedeterministycznych. Parsery GLR wprowadził w 1986 roku Masaru Tomita, dlatego czasem nazywa się je też parserami Tomity. Głównym celem dla Tomity była wydajna analiza języka naturalnego.

Algorytm

Parser GLR działa podobnie do zwykłego parsera LR, ale zamiast budować jedną interpretację przetwarzanego słowa, przeszukuje wszerz przestrzeń możliwych interpretacji. Zwykły parser LR musi być deterministyczny, czyli w każdej komórce tabeli parsingu może znajdować się najwyżej jedna akcja, co oznacza brak konfliktów przesunięcie-redukcja i redukcja-redukcja.

Parser GLR może mieć kilka akcji w jednej komórce. W trakcie pracy, w momencie napotkania takiego konfliktu, stos parsera jest rozwidlany. Na każdym nowym wierzchołku umieszczany efekt zastosowania innej z dozwolonych w danej sytuacji akcji. Praca jest kontynuowana równolegle dla każdego wierzchołka stosu (co może prowadzić do dalszych rozwidleń). Jeśli któryś z wierzchołków i wczytywany symbol nie pozwalają na dalsze przejście (w normalnym parserze LR wystąpiłby błąd) to dana ścieżka jest po prostu odrzucana i analiza jest kontynuowana na pozostałych wierzchołkach.

Zalety

Dobrze zaimplementowany GLR ma taką samą złożoność pesymistyczną jak np. algorytm CYK, czyli O(n³). Jednak ma dwie ważne zalety:

• jego faktyczna złożoność zależy od niejednoznaczości gramatyki. Dla gramatyk deterministycznych działa w czasie O(n), więc tak samo jak parser LR;
• jest algorytmem online, nie musi więc wczytywać całego wejścia przed rozpoczęciem pracy.