"vasaktuletamiseks" - 1 õppematerjal

Teoreetilibe informaatika kordamisküsimused

Vahepealsetesse lahtritesse kirjutatakse mitteterminaal parajasti siis, kui ... Algoritmi tulemusena tekib lahtrisse mitteterminaal A, kui grammatikas G on esitatav tuletus A xjxj+1w, sõna kuulub keelde ning tipulahtris on stardisümbol. Keerukuseks n pikkuse sõna korral O(n3). 17. Earley algoritm. Ülesanne: kas sõna x kuulub grammatikaga G genereeritavasse keelde L. Üritame ehitada sõna vasaktuletust. G produktsiooni A v võib olla kasutatud sõna w = x1x2...xn (xi on terminaal) vasaktuletamiseks vaid siis, kui leidub tuletus: S =>* x1..xiA Kui sõna v koosneb alamsõnadest ja (v = ), peab leiduma tuletus: S =>* x1..xiA => x1..xi =>*x1.xi-1xi..xj (1) Earley algoritm moodustab massiivi || Iij ||, mille elementideks on punktiga produktsioonid. A . kuulub Iij koosseisu parajasti siis, kui sõna w = x1..xn vasaktuletuse võib ehitada ülalnimetatud (1) osatuletuse jätkamise teel. Sõna kuulub keelde, kui produktsioon S v kuulub maatriksi elementi I0n.