Лекция 17. Тақырыбы: Болжаушы анализатор кестесі. LL(1)-грамматикалар

Лекция 17.

Тақырыбы: Болжаушы анализатор кестесі. LL(1)-грамматикалар

2. LL(1)-грамматикалар

1. G грамматикасы бойынша болжаушы анализатор кестесін құру үшін келесі идеяға негізделген алгоритм қолданылды. Айталық А→α - грамматиканың шығару ережесі және a FIRST(α) болсын. Онда анализатор егер енуші символ а болып табылса, онда А-ны α бойынша қайырады. Қиындық α=е немесе α =>* е болғанда туындайды. Бұл жағдайда А-ны α-ға қайыру керек, егер ағымдағы енуші символ FOLLOW(A)-ға тиісті болса немесе ену көрсеткіші $-ға (яғни тізбек соңына) жеткен және $ FOLLOW(A) болса.

Алгоритм 4.6. Болжаушы анализатор кестесін құру

Кіріс. КБ-грамматика G = (N, T, P, S).

Шығыс. Болжаушы анализатордың M[A, a] кестесі, A N, a T {$}.

Тәсіл. Грамматиканың әрбір A α шығару ережесі үшін 1 және 2-ші қадамдарды орындау. Бұдан соң 3-ші қадамда орындау.

• 
  FIRST()-дағы әрбір терминал үшін A ережесін M[A, a]-ға қосу.
  
• 
  Егер e FIRST() болса, FOLLOW(A)-ң әрбір b терминалы үшін A -ны M[A, b]-ға қосу. Бұдан бөлек, егер e FIRST() және $ FOLLOW(A) болса, A -ны M[A, $]-ға қосу.
  
• 
  Анықталмаған барлық енушілерді «қателік» деп есептеу.
  

E' +TE' шығару ережесіне сәйкес M[E', +] мәні E' +TE' –ге тең. E' e шығару ережесіне сәйкес M[E', )] және M[E', $] мәндері E' e тең, өйткені FOLLOW(E') = { ), $}.

Осы грамматика үшін 4.6 алгоритмі бойынша құрылған талдау кестесі 4.3 суретте көрсетілген.

4.3.4 LL(1)-грамматикалар

2.Болжаушы анализатор кестесі құруға арнлған 4.6 алгоритмі кез-келген КБ-грамматикаға қолданыла алады. Алайда, кебір грамматикалар үшін құрылған кесте кірісі бірмәнді анықталмауы мүмкін. Егер грамматика солрекурсивті немесе бірмәнді емес болса, онда кестенің бірмәнді анықталмаған кемінде бір кірісі бар болады.

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

LL(1)-грамматика үшін құрылған болжаушы анализатор LL(1)-анализатор деп аталады. Атаудағы бірінші L әрпі енуші тізбек солдан оңға қарай оқылатындығын білдіреді, ал екінші L әрпі енуші тізбектің сол жақ шығысы құрылатындығын білдіреді, ал 1 - әрбір қадамда шешім қабылдау үшін еніші тізбектің оқылмаған бөлігінен бір символ қолданылатындығын білдіреді.

Егер G - LL(1)-грамматика болса, онда L(G) – детерминант КС-тіл екендігін дәлелдеу қиын емес.

LL(1)-грамматиканың келесі критерийі де дұрыс. Әрбір Р-дан алынған A , A ережелер жұбы үшін (яғни, сол жағы бірдей ережелер үшін)келесі 2 шарт орындалса, сонда тек сонда ғана G = (N, T, P, S) грамматикасы LL(1)-грамматика боп табылады:

• 
  FIRST( ) FIRST( ) = ;
  
• 
  Если e FIRST( ), то FIRST( ) FOLLOW(A) = .
  

Мысал 4.6. Бірмәнді емес грамматика LL(1) болып табылмайды. Келесі грамматика мысал бола алады G = ({S, E}, {if, then, else, a, b}, P, S) ережелері:

S if E then S | if E then S else S | a

E b

Сур. 4.6:

Лекция 18.

Тақырыбы: Солжақ рекурсияны алып тастау

1. LL(1) боп табылмайтын грамматиканы эквивалентті LL(1)-грамматикаға келтіру

2. Сол жақ рекурсияны алып тастау
1. Болжаушы анализді қолданудағы негізгі қиындық – бұл енуші тіл үшін кірісі бірмәнді анықталған анализ кестесін құруға болатын грамматиканы табу. Кейде қайсыбір қарапайым түрлендірулер арқасында бірқатар қарап LL(1) боп табылмайтын грамматиканы эквивалентті LL(1)-грамматикаға келтіруге болады. Бұл түрлендірулердің арасындағы ең тиімділері сол жақ факторизация және сол жақ рекурсияны алып тастау. Бұл жерде мынаны ескерте кеткен жөн. Біріншіден, барлық грамматика да бұл түрлендірулерден кейін LL(1)-грамматика болып қалмайды, екіншіден мұндай түрлендірулерден кейін грамматика түсініксіздеу болып қалуы мүмкін.

A A түрдегі тікелей сол жақ рекурсияны келесі тәсілмен алып тастауға болады. Алдымен А-ережелерді топтастырамыз:

мұнда _i қатарлардың ешқайсысы да А-дан басталмайды.

Бұдан соң, бұл ережелер жиынын ауыстырамыз:

мұнда A' – жаңа бейтерминал. А бейтерминалынан алдыңғы тізбектерді шығаруға болады, бірақ енді сол жақ рекурсия жоқ. Дәл осылай тікелейгі сол жақ рекурсияларалынып тасталынады, бірақ екі не одан көп қадамды сол жақ рекурсиялар алынбайды. Төменде келтірілген алгоритм грамматикадан барлық сол жақ рекурсияларды алып тастайды.

 

2. Алгоритм 4.7. Сол жақ рекурсияны алып тастау.

Кіріс. e-ережелері ( A e түріндегі ереже) жоқ КЕ-грамматика G.

Шығыс. G –ға эквивалентті, сол жақ рекурсиясы жоқ КЕ-грамматика G'

Тәсіл. 1 және 2 қадамдарды орындау.

• 
  G грамматикасының бейтерминалдарын қалаған бір ретпен реттеп шығу.
  
• 
  Келесі процедураны орындау:
  

for (i=1;i<=n;i++){

for (j=1;j<=i-1;j++){

айталық A_{j 1} | ₂ | ... | _k - A_j үшін ағымдағы барлық ережелер;

A_i A_j түріндегі барлық ережелерді A_{i 1} | ₂ | ... | _k ережелеріне ауыстыру;

}

A_i A_i түріндегі ережелерді жою;

A_i арналған ережелерден тікелейгі сол жақ рекурсияны жою;

}

2-ші қадамдағы сыртқы циклдың (i - 1)-ші итерациясынан соң A_k A_s , мұнда k < i, түрдегі кез-келген ережелер үшін s > k болады. Нәтижеде келесі итерацияда келесі итерацияда (і бойынша) ішкі цикл (j бойынша) кез-келген A_i A_m ережеде m i болғанша төменгі шекараны m бойынша біртіндеп артырады. Бұдан соң, A_i-ережелер үшін тікелейгі сол жақ рекурсияны алып тастаған соң, m і-ден артық болады.

Егер грамматикаде е-ережелер (A e түріндегі ережелер) болмаса алгоритм 4.7-ні қолдануға болады. Грамматикадағы бар е-ережелер алдын-ала алып тастауға болады. Нәтижеде алынған сол жақ рекурсиясысыз грамматика е-ережелерге ие бола алады.

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

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