Parser GLR

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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

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

Dobrze zaimplementowany GLR ma taką samą złożoność pesymistyczną jak np. algorytm CYK czyli O(n3). 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.