Naslov
Donald Knuth: O prevođenju jezika s lijeva na desno
(Donald Knuth: On the Translation of Languages from Left to Right)

Autori
Vladimir, Klemo

Izvornik
On the Translation of Languages from Left to Right

Vrsta, podvrsta
Ostale vrste radova, prijevod

Godina
2020

Ključne riječi
knuth ; LR parser ; parsiranje ; formalni jezici ; kontekstno-neovisni jezici
(knuth ; LR parser ; parsing ; formal languages ; context-free languages)

Sažetak
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.

Izvorni jezik
Hrvatski

Znanstvena područja
Računarstvo

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

POVEZANOST RADA