Vi presenterar designen och teorin om en ny tolkningsmotor, YAKKER, som kan tillgodose de många behoven hos moderna programmerare och moderna databehandlingsapplikationer. I synnerhet, våra nya parsing motor handtag (1) full scannerless sammanhangsfri grammatik med (2) regelbundna uttryck som höger sida för att definiera icke-terminaler. YAKKER omfattar också (3) hjälpmedel för att binda variabler till mellanliggande parsresultat och (4) använda sådana bindningar inom godtyckliga begränsningar för att kontrollera tolkning. Dessa faciliteter möjliggör den typ av databeroende tolkning som vanligen behövs i systemapplikationer, särskilt de som fungerar över binära data. Dessutom kan (5) icke-terminaler parameteriseras genom godtyckliga värden, vilket ger systemet god modularitet och abstraktion egenskaper i närvaro av databeroende tolkning. Slutligen, (6) äldre tolkning bibliotek, såsom sofistikerade bibliotek för datum och tider, kan direkt införlivas i parser specifikationer. Vi illustrerar betydelsen och nyttan av denna rika samling av funktioner genom att presentera dess användning på exempel som sträcker sig från svåra programmeringsspråk grammatiker till webbserverloggar till binär dataspecifikation. Vi visar också att vår grammatik har viktiga kompositionsegenskaper och förklarar varför sådana egenskaper är viktiga i moderna tillämpningar som automatisk grammatikinduktion. När det gäller tekniska bidrag tillhandahåller vi en traditionell semantik på hög nivå för vår nya grammatikformalisering och visar hur man sammanställer grammatik till icke-deterministisk automat. Dessa automata är stack-baserade, ungefär som konventionella push-down automata, men är också utrustade med miljöer för att spåra databeroende tolkningstillstånd. Vi bevisar riktigheten i vår översättning av databeroende grammatik till dessa nya automater och visar sedan hur man implementerar automaten effektivt med hjälp av en variation av Earleys tolkningsalgoritm.
REF utvecklar en grammatikformalism och tolkningsalgoritm för att hantera databeroende grammatik.
Semantics and algorithms for data-dependent grammars
{'venue': "POPL '10", 'journal': None, 'mag_field_of_study': ['Computer Science']}