Backtracking tekniker som ofta används för att förlänga rekursiv nedstigning (RD) tolkar kan ha explosiva körtider och kan inte hantera grammatik med vänster rekursion. GLL-tolkar är helt allmänna, värsta fall kubiktolkar som har rekursiv nedstigning-liknande egenskap som de är lätta att skriva och att använda för grammatik felsökning. De har det direkta sambandet med den grammatik som en RD-tolk har. I detta dokument ger vi en algoritm för att generera GLL-tolkar som bygger en SPPF-representation av härledningarna av indata, som kompletterar vår befintliga GLL-igenkänningsalgoritm, och vi visar att sådana tolkar och kännare är värsta fall kubik. Nyckelord: generaliserad tolkning, rekursiv nedstigning, GLL-tolkning, RNGLR och RIGLR-tolkning, kontextfria språk I detta dokument presenterar vi algoritmen GLL (Generalised LL) som hanterar alla sammanhangsfri grammatik, inklusive de med tvetydighet, och som vi ska bevisa har värsta möjliga kubikprestanda. Algoritmen har den "rekursivt anständiga" egenskapen: tolkar kan konstrueras enkelt för hand direkt från grammatiken, och de resulterande tolker kan lätt spåras med hjälp av ett konventionellt språk debugger eftersom de har en enkel relation till själva grammatiken. Denna enkla kartläggning mellan grammatikregler och parserfragment gör det möjligt för programmerare att tänka operativt på grammatiker samtidigt som den deklarativa karaktären hos grammatikspecifikationen bibehålls. I detta avseende är GLL-tolkar betydligt annorlunda än tillvägagångssätt baserade på bakåtspårning och lookahead förlängningar av deterministiska parsers [13, 14, 1, 24, 9, 5], inklusive algoritmer som
Scott och Johnstone [14], REF visade GLL tolkning, som är en algoritm för att generera en generaliserad tolkning med hjälp av LL tolkning.
GLL parse-tree generation
{'venue': 'Sci. Comput. Program.', 'journal': 'Sci. Comput. Program.', 'mag_field_of_study': ['Computer Science']}