En effektiv tolkningsalgoritm för förstärkt sammanhangsfri grammatik introduceras, och dess tillämpning på on-line naturliga språk gränssnitt diskuteras. Algoritmen är en generaliserad LR tolkningsalgoritm, som förkompilerar en LR skift-reducera tolkningstabell (eventuellt med flera poster) från en given förstärkt sammanhangsfri grammatik. Till skillnad från standard LR tolkning algoritm, kan den hantera godtyckliga sammanhangsfri grammatik, inklusive tvetydig grammatik, medan de flesta av LR effektivitet bevaras genom att införa begreppet en "graf-strukturerad stack". Den grafstrukturerade stacken gör det möjligt för en LR skiftreducerad parser att upprätthålla flera parser utan att tolka någon del av indata två gånger på samma sätt. Vi kan också se vår tolkningsalgoritm som en utökad diagramtolkningsalgoritm som effektivt vägleds av LR-tolktabeller. Algoritmen är snabb, på grund av LR tabell precomputation. I flera experiment med olika engelsk grammatik och meningar indikerar timing en fem-till tiofaldig hastighetsfördel jämfört med Earleys kontextfria tolkningsalgoritm. Algoritmen tolkar en mening strikt från vänster till höger on-line, det vill säga, den börjar tolka så fort användaren skriver i första ordet av en mening, utan att vänta på slutförandet av meningen. En praktisk on-line-tolk baserad på algoritmen har implementerats i Common Lisp, och körs på Symbolics och HP AI arbetsstationer. Parsern används i det flerspråkiga maskinöversättningsprojektet på CMU. Dessutom byggs en kommersiell on-line-tolk för japanska språket av Intelligent Technology Inkorporation, baserat på den teknik som utvecklats vid CMU.
Tomita REF undersökte grundidén för Earleys algoritm, LR tolkningsalgoritm.
An Efficient Augmented-Context-Free Parsing Algorithm
{'venue': 'Computational Linguistics', 'journal': None, 'mag_field_of_study': ['Computer Science']}