GLR elemző (az angol nyelvből. Általánosított balról jobbra jobb szélső levezetési elemző - Általános növekvő áruházi elemző ) - a számítástechnikában egy kiterjesztett LR elemző algoritmus , amelyet nem determinisztikus és kétértelmű nyelvtanok elemzésére terveztek . Masaru Tomita írta le először 1984 -ben , és "párhuzamos értelmezőnek" is nevezik .
Mivel ez az algoritmus az LR elemzőből származik, működési elvei változatlanok maradtak: Tomita a természetes nyelven írt szövegek gyors és hatékony felismerését tűzte ki célul . A normál LR elemző nem képes feloldani a természetes nyelvek határozatlanságát és kétértelműségét, míg a GLR algoritmus igen.
A GLR algoritmus pontosan úgy működik, mint az LR algoritmus , azzal a különbséggel, hogy egy adott nyelvtan esetében a GLR elemző a bemeneti szekvencia összes lehetséges értelmezését dolgozza fel szélességi kereséssel . A GLR elemző generátorok az eredeti nyelvtant értelmező táblákká alakítják, akárcsak az LR elemző generátorok. De míg az LR elemző táblák csak egy állapotátmenetet tesznek lehetővé (az elemző kezdeti állapota és a bemeneti terminál szimbóluma határozza meg), addig a GLR elemző táblák sok eredő állapotot tesznek lehetővé. Ennek eredményeként a GLR algoritmus lehetővé teszi az ütközések eltolását/csökkentését és csökkentését/csökkentését.
Ütközés esetén az elemző verem (tároló összecsukása) két vagy több párhuzamos verembe ágazik, amelyek felső állapotai az egyes lehetséges átmeneteknek felelnek meg. A következőkben a következő bemeneti szimbólumot használjuk a következő átmenetek meghatározására a verem egyes ágainak felső állapotaiban. Ebben az esetben ismét szükséges lehet a verem elágazása. Ha bármely felső állapothoz és bemeneti szimbólumhoz nincs átmenet (az elemző táblában), akkor a verem ezen ága hibásnak minősül és eldobásra kerül.
Az optimalizálás alapja a verem egyes részei megosztása annak több ágával, ami csökkenti a bemeneti sorozat elemzéséhez szükséges teljes memória mennyiségét. Az optimalizálás eredményeként kapott összetett struktúra miatt a verem jobban hasonlít egy irányított aciklikus gráfhoz , mint egy fához.
A GLR algoritmus a legrosszabb esetben ugyanolyan bonyolultságú, mint a Kok-Younger-Kasami algoritmus és az Earley algoritmus - O ( n³ ). A GLR algoritmusnak azonban két előnye van:
A gyakorlatban a legtöbb programozási nyelv determinisztikus vagy "majdnem determinisztikus". Ez azt jelenti, hogy a non-determinizmus általában feloldható kis (bár korlátlan számú) bemeneti karakter beolvasásával. Összehasonlítva más olyan algoritmusokkal, amelyek képesek feldolgozni a kontextusmentes nyelvtanok teljes osztályát (mint például az Early algoritmus vagy a Kok-Younger-Kasami algoritmus), a GLR algoritmus jobban teljesít az ilyen „majdnem determinisztikus” nyelvtanokon, mivel csak egy ága van. a verem.