Nuvarande algoritmer för kontextfri tolkning skapar en kompromiss mellan lättförståelse, enkelhet i genomförandet, teoretisk komplexitet och praktiska prestationer. Ingen algoritm uppnår alla dessa egenskaper samtidigt. Kanske et al. införs tolkning med derivat, som hanterar godtycklig kontextfri grammatik samtidigt som den är både lätt att förstå och enkel att genomföra. Trots mycket inledande entusiasm och en mängd oberoende genomföranden har dess värsta komplexitet aldrig visat sig vara bättre än exponentiell. Faktum är att argument på hög nivå som hävdar att det i grunden är exponentiellt har förts fram och till och med accepterats som en del av folkloren. Föreställningen blev trög i praktiken, och denna tröghet togs som ett informellt bevis på exponentiellhet. I detta dokument omprövar vi resultatet av tolkning med derivat. Vi har upptäckt att det inte är exponentiellt utan i själva verket kubiskt. Dessutom, enkla (men kanske inte uppenbara) ändringar i genomförandet av Might et al. leda till ett genomförande som inte bara är lätt att förstå utan också i praktiken är mycket givande.
I detta dokument förstärker vi denna koppling genom att koppla den traditionella LL REF-tolkningen till en effektiv tolkning av derivat.
On the complexity and performance of parsing with derivatives
{'venue': 'PLDI 2016', 'journal': None, 'mag_field_of_study': ['Computer Science']}