Лекция Тақырыбы: Алфавиттер, тізбектер және тілдер

Лекция 15 Тақырыбы:Жоғарыдан төмен қарай талдау

жүктеу/скачать 1.44 Mb.

бет	7/13
Дата	14.06.2016
өлшемі	1.44 Mb.
	#135164
түрі	Лекция

1 2 3 4 5 6 7 8 9 10 ... 13

Лекция 15

Тақырыбы:Жоғарыдан төмен қарай талдау

1. Жоғарыдан төмен қарай талдау алгоритмі.

2. Мысал қарастыру. Болжаушы анализатор кестесі

Айталық КБ-грамматика G = (N, T, P, S) берілсін. G грамматикасы үшін болжаушы талдауды (немесе жоғарыдан-төменге қарай) қарастырамыз.

Болжаушы талдаудың негізгі мәселесі – бұл бейтерминалға қолдану керек болатын шығару ережесін анықтау. Болжаушы талдау процессі талдау ағашы тұрғысынан былайша бейнелеуге болады (сур 4.1).

Сур. 4.1:

Ағаштың құрылып бітпеген бөліктері сентенциалды формаларға сәйкес келеді. Алғашқыда ағаш S аксиомаға сәйкес келетін бір ғана төбеден тұрады. Бұл кезде енуші тізбектің бірінші символы бойынша болжаушы анализатор S-ке қолданылуға тиіс S

X₁X₂... ережені анықтауы керек. Бұдан соң X₁–ге қолданатын ережені анықтау керек, осылайша сол жақ шығаруға сәйкес келетін сентенциалды форманы құру барысында Y

a...ережесі қолданғанша жалғаса береді. Бұл процесс бұдан соң келесі сентенциалды форманың ең сол жақтағы бейтерминал символ үшін қолданылады.

4.2 суретте кезектегі ережені кесте көмегімен анықтайтын болжаушы анализатордың құрылымы келтірілген. Мұндай кестені тікелей грамматикадан да құруға болады.

Сур. 4.2:

Кестелік-басқарылатын болжаушы анализатор енуші лентадан, басқару құрылғысы (программа), талдау кестесі, магазин (стек) және шығушы ленталардан тұрады.

Енуші лентада $ символы – қатар соңы маркерімен аяқталған талдау жасалынатын қатар бар болады. Шығушы лентада қолданылған шығару ережелерінің тізбегі беріледі.

Талдау кестесі – бұл екіөлшемді M[A, a] массиві, мұнда A - бейтерминал, және a - терминал немесе $ символы. M[A, a]-ң мәні болып грамматиканың қайсыбір ережесі немесе «қате» элементі болуы мүмкін.

Магазин түбінде $-мен бірге символдар тізбегі болуы мүмкін. Бастапқы моментте магазиннің төбесінде грамматиканың бастапқы символы ал, түбінде $ символы ғана бар болады.

Анализатор былай жұмыс істейді. Бастапқыда анализатор конфигурациясы мынадай болады: магазинде S$ бар, ал енуші лентада w$ (w – талданатын тізбек), шығушы лента бос. Әрбір тактта анализатор магазин төбесінен Х-символын және ағымдағы енуші а символын қарастырады. Осы екі символ анализатор әрекетін анықтайды. Мынадай мүмкін әрекеттер бар:

1. Егер X = a = $ болса, анализатор тоқтайды да талдаудың сәтті аяқталғандығын хабарлап, шығушы лентаның мәнін береді.

2. Егер X = a$ болса, анализатор X-ті магазиннен алып тастап, ену көрсеткішін келесі енуші символға жылжытып қояды.

3. Егер X - терминал, және Xa болса, онда анализатор тоқтайды да, енуші тізбектің тілге тиісті еместігі туралы хабарлайды.

4. Егер X – бейтерминал болса, анализатор M[X, a] кестесіне назар салады. Екі жағдай болуы мүмкін:

M[X, a]-ң мәні Х-ке арналған ереже болып табылады. Бұл жағдайда анализатор магазин төбесіндегі Х-ті осы ереженің оң жағымен ауыстырады, ал ереженің өзін шығушы лентаға орналастырады. Ену көрсеткіші жылжытылмайды.
M[X, a] мәні «қателік» болып табылады. Бұл жағдайда анализатор тоқтап, енуші тізбек берілген тілге тиісті емес деп хабарлайды.

Анализатор жұмысы мына программа арқылы берілуі мүмкін.

do
   {X=магазиннің жоғарғы символы;
    if (X - терминал || X=="$")
        if (X==InSym)
            {Магазиннен X-ті жою;
             InSym=кезектегі символ;
            }
        else error();
    else /*X - бейтерминал*/
        if (M[X,InSym]=="X->Y1Y2...Yk")
            { Магазиннен X-ті жою;
            Yk,Yk-1,...Y1-ді магазинге орналастыру
                (Y1-ді магазин төбесіне орналастыру);
              X->Y1Y2...Yk ережесін шығару;
            }
        else error(); /* M кестесінің кірісі бос*/
   }
while (X!=$) /*магазин бос*/

ОБСӨЖ

Мысал 4.3. Арифметикалық өрнек грамматикасын қарастырамыз G = ({E, E', T, T', F}, {id, +, *, (, )}, P, E) және ережелері:

E TE'

T'*FT'

E' +TE'

T' e

E' e

F (E)

T FT'

F id

Бұл грамматика үшін болжаушы анализатор кестесі төменде келтірілген. Кестенің бос ұяшықтары «қателік» элементіне сәйкес келеді.

Рис. 4.3:

Енуші id + id * id$ тізбегін талдау барысында анализатор 4.4-суретте бейнеленген қадамдарды орындайды. Анализатордың дәлме-дәл сол жақ шығарды орындағанын байқаймыз. Қарастырылып қойылған енуші символдардың артынан магазинде грамматика символдарын орналастырсақ дәлме-дәл сол жақ сентенциалды шығару формасын аламыз. Бұл тізбек үшін талдау ағашы 4.5 суретте келтірілген.

сур. 4.4:

Сур. 4.5:

жүктеу/скачать 1.44 Mb.

Достарыңызбен бөлісу:

1 2 3 4 5 6 7 8 9 10 ... 13