hrvatski

Donald Knuth: O prevođenju jezika s lijeva na desno

U posljednje vrijeme pokazano je veliko zanimanje za jezike s dovoljno jednostavnim gramatikama koje omogućavaju mehaničku izgradnju učinkovitog algoritma parsiranja s lijeva na desno. U ovom radu definiramo LR(k) gramatike, moguće najopćenitije te vrste, koje pružaju temelj razumijevanja svih onih jedinstvenih postupaka korištenih za konstrukciju algoritama parsiranja jezika jednostavne strukture, npr. algebarskih jezika. Predstavljamo algoritme odlučivanja je li zadana gramatika zadovoljava LR(k) uvjet, za zadani k, i opisujemo postupke prepoznavanja za LR(k) gramatike. Pokazujemo neodlučivost problema utvrđivanja je li neka gramatika zadovoljava LR(k) svojstvo za neki k. U zaključku rada uspostavljamo niz poveznica između LR(k) gramatika i determinističkih jezika. Posebice, LR(k) uvjet za gramatike je prirodno analogan determinističkom uvjetu za jezike.

knuth ; LR parser ; parsiranje ; formalni jezici ; kontekstno-neovisni jezici

Prijevod rada: Knuth, Donald E. “On the translation of languages from left to right.” Information and control 8.6 (1965): 607-639.