Próbuję nauczyć się używania żubra. Bizon manpage (1) mówi o bizonie:
Wygeneruj deterministyczny analizator składni LR lub uogólniony analizator składni LR (GLR), korzystając z tabel analizatora składni LALR (1), IELR (1) lub kanonicznej LR (1).
Co to jest parser IELR? Wszystkie istotne artykuły, które znalazłem w sieci WWW, są płatne.
Odpowiedzi:
Algorytm parsowania IELR (1)
Algorytm (1) parsowanie IELR został opracowany w 2008 roku przez Joel E. Denny jako część jego Ph.D. badania pod nadzorem Briana A. Malloya na Uniwersytecie Clemson. Algorytm IELR (1) jest odmianą tak zwanego „minimalnego” algorytmu LR (1) opracowanego przez Davida Pagera w 1977 r. , Który sam jest odmianą algorytmu analizy LR (k) wynalezionego przez Donalda Knutha w 1965 r . IE w IELR (1) oznacza eliminację nieadekwatności (patrz ostatni rozdział).
Algorytmy LR (1)
Część LR (1) w IELR (1) oznacza L eft po prawej, R pochodna najwyższa z 1 znacznikiem wyprzedzającym. Parsery LR (1) są również nazywane parserami kanonicznymi. W tej klasie algorytmów analizowania zastosowano strategię analizy typu bottom-up, redukuj przesunięcie, a tabela stosu i przejścia stanu określają następne działanie, które należy podjąć podczas analizy.
Historycznie algorytmy LR (1) były niekorzystne z powodu dużych wymagań pamięciowych dla ich tabel przejścia. Ulepszenie Pager polegało na opracowaniu metody łączenia stanów przejściowych podczas generowania tabeli przejściowej, znacznie zmniejszając jej rozmiar. Tak więc algorytm Pagera sprawia, że parsery LR (1) są konkurencyjne w stosunku do innych strategii analizowania pod względem wydajności przestrzennej i czasowej. Wyrażenie „minimalny parser LR (1)” odnosi się do minimalnego rozmiaru tabeli przejścia wprowadzonego przez algorytm Pager.
Ograniczenia algorytmu Pager'a
Minimalne algorytmy LR (1) tworzą tabelę przejścia na podstawie konkretnej gramatyki wejściowej dla analizowanego języka. Różne gramatyki mogą tworzyć ten sam język. Rzeczywiście, gramatyka inna niż LR (1) jest w stanie wytworzyć język analizowalny LR (1). W praktyce generatory parsera LR (1) akceptują gramatykę inną niż LR (1) ze specyfikacją rozwiązywania konfliktów między dwoma możliwymi przejściami stanu („konflikty redukujące przesunięcie”), aby uwzględnić ten fakt. Denny i Malloy odkryli, że algorytm Pager nie generuje parserów wystarczająco silnych, aby parsować języki LR (1), pod warunkiem, że niektóre gramatyki inne niż LR (1) generują język LR (1).
Denny i Malloy pokazują, że to ograniczenie nie jest jedynie akademickie, pokazując, że Gawk i Gpic, oba powszechnie używane, dojrzałe oprogramowanie, wykonują nieprawidłowe działania parsera.
Ulepszenia IELR (1)
Denny i Malloy zbadali źródło wad algorytmu Pager, porównując tabelę przejścia wygenerowaną przez algorytm Pager z tabelą przejścia o równoważnej gramatyce LR (1) i zidentyfikowali dwa źródła, które nazywają niedoskonałościami, które pojawiają się w tabeli przejścia z Pager'a algorytm, ale nie ma go w tabeli przejścia LR (1). Algorytm Denny i Malloya IELR (1) ( Inadequacy Elimination LR (1)) jest algorytmem zaprojektowanym w celu wyeliminowania tych niedociągnięć podczas generowania tabeli przejścia, która jest praktycznie identyczna pod względem wielkości z algorytmem Pager.
źródło
Artykuł, który twierdzi, że go wprowadza: IELR (1): Praktyczne tabele parsera LR (1) dla gramatyki spoza LR (1) z rozwiązywaniem konfliktów (via archive.org) autorstwa Joela E. Denny'ego i Briana A. Malloya z Clemson University , jest bezpłatnie dostępny na stronie Malloy.
Są warte tego, na co nie mogę odpowiedzieć. (Osobiście nie rozumiem potrzeby takiego okaleczającego analizowania CFG - po co ograniczać swoją moc ekspresyjną, kiedy można po prostu użyć GLR ? Dla mnie to ma sens jak TAG lub PEG (wydają się naturalne i dodają mocy ekspresyjnej) lub drzewo gramatyki (dla języków takich jak XML, w których rozpoznawanie parsowanych drzew jest z założenia bezproblemowe).
źródło