Лекция 20. Тақырыбы: Сол жақ факторизация

Лекция 20.

Тақырыбы: Сол жақ факторизация

1. Сол жақ факторизацияның негізгі идеясы

2. Сол жақ факторизация алгоритмі
1. Сол жақ факторизацияның негізгі идеясы

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

Егер A ₁ | ₂ - екі A-ереже және енуші тізбек -дан шығатын бос емес қатардан басталса, біз қайыруды бірінші немесе екінші ереже бойынша жасауды білмейміз. Былайша қайырып: A A' , шешімді қоя тұруға болады. -дан не шығатынын анализ жасап болған соң A' ₁ бойынша немесе A' ₂ бойынша қайыруға болады. Сол жақ факторизацияланған ереже мына түрге келеді:

.

2. Сол жақ факторизация алгоритмі

мұнда z – барлық -н басталмайтын алтернативаларды білдіреді, төмендегіге

ауыстырамыз, мұнда A' – жаңа бейтерминал. Бұл түрлендіруді кез-келген екі альтернатива ортақ префикске ие болмай қалғаныншақолдана береміз.

Мысал 7. 6-мысалдағы шартты операторлар мысалын қайта қарастырамыз.

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

E b

S if E then SS'| a

S' else S | e

E b

Лекция 21,22.

Тақырыбы: Жылжыту-қайыру түріндегі төменнен жоғары қарай талдау

2. LR(1)-анализаторлардың артықшылықтары

3. LR(1)-анализаторлардың құрылымы. Конфигурациясы

4. LR(1)-анализатор жұмысы

1. Жылжыту-қайыру түріндегі төменнен жоғары қарай талдау процессінде енуші тізбектің талдау ағашы жапырақтарынан (төменнен) түбіріне (жоғары) қарай құрылады. Бұл процессті w тізбегін грамматиканың бастапқы символына қарай «қайыру» деп қарастыруға болады. Қайырудың әр қадамында қайсыбір шығару ережесінің оң жағына сәйкес қоюға болатын ішкітізбек осы шығару ережесінің сол жақ бөлігімен ауыстырылады және егер әрбір қадамда дұрыс ішкітізбек таңдалатын болса, онда кері қараған ретте оң жақтан шығару байқалады (4.7 сур). Бұл жерде енуші тізбекке LL(1)-грамматикадағы сияқты аяқтаушы маркер $ жазылған.

Сур. 4.7:

Қайсыбір шығару ережесінің оң жағына сәйкес қоюға болатын сентенциалды формадағы ішкітізбекті ереженің сол жақ бөлігіне қайыру оң жақ шығаруға айналдырғанда (в обращении правостороннего вывода) бір қадамға сәйкес келсе, онда бұл ішкітізбек тізбектің негізі деп аталады. Қайсыбір A шығару ережесінің оң жағына сәйкес қойылатын ең сол жақтағы ішкітізбек негіз болып табылуы міндетті емес, өйткені A ережесі бойынша қайыру аксиомаға келтіруге болмайтын тізбек беруі мүмкін.

Формальді түрде z оң жақ сентенциалды форманың негізі – бұл A шығару ережесі және z-гі сондай тізбек табылуы мүмкін болатын позиция: сонда -ті А-ға ауыстыру нәтижесінде z оң жақ шығаруда алдыңғы (предыдущая)сентенциалды форма алынады. Осылайша, егер S _r^* A _r , онда A -дан кейінгі позицияда, бұл тізбегінің негізі. ішкі тізбегі негіздің оң жағында тек терминал символдарға ие. (Таким образом, если S _r^* A _r , то A в позиции, следующей за , это основа цепочки . Подцепочка справа от основы содержит только терминальные символы. )

Жалпы, грамматика бірмәнді болмауы мүмкін, сондықтан оң жақ шығару біреу ғана және негізде жалғыз ғана болмауы мүмкін. Егер грамматика бірмәнді болса, онда грамматиканың әрбір оңжақтағы сентенциалды формасы дәл бір негізге ие. Сентенциалды формадағы негізді сол жақтағы бейтерминалға ауыстыру негізді кесіп тастау (отсечение) деп аталады. Оңжақ шығаруды айналдыру (Обращение правостороннего вывода) негізді w бастапқы тізбектен бастап кесіп тастауды қайтадан қолдану арқылы алынуы мүмкін. Егер w –қарастырып отырған грамматикадағы сөз болса, онда w = _n, мұнда _n - әлі мәлім емес S = _{0 r 1 r}... _{r n-1 r n} = w оң жақ шығарудың n-ші оңжақ сентенциалды формасы.

Бұл шығаруды кері ретпен қайта қалпына келтіру үшін _n-нен _n негізді ажыратып аламыз және оны қайсыбір A_{n n} шығару ережесінің сол жағына ауыстырып, (n - 1)-ші _n-1 оңжақ сентенциалды форманы аламыз. Бұдан соң осы процессті қайта қайталаймыз, яғни, _n-1-ден _n-1 негізді ажыратып алып осы негізді _n-2 оңжақ сентенциалды форманы ала отырып қайырамыз. Егер, осы процессті қайталай отырып біз тек бастапқы S символынан тұратын оңжақ сентенциалды формманы алатын болсақ, онда тоқтаймыз да талдаудың сәтті аяқталғанды тууралы хабарлаймыз. Қайыруда пайдаланылған ережелер қатарының айналуы (обращение последовательности правил) бұл енуші тізбектің оңжақ шығаруы.

Осылайша жылжыту-қайыру типіндегі анализатордың басты мәселесі – бұл негізді ажыратып алу және кесіп тастау.

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

LR(1)-анализ келесі себептерге байланысты тартымды:

• 
  LR(1)-анализ – жылжыту-қайыру типіндегі қайтарымсыз анализдің ең қуатты әдісі;
  
• 
  LR(1)-анализ тиімді жүзеге асуы мүмкін;
  
• 
  LR(1)-анализаторларын программалау тілдерінің барлық конструкциялары үшін құруға болады;
  
• 
  LR(1)-әдіспен талданатын грамматикалар классы өз ішіне болжаушы анализатор(жоғарыдан төмен қарай LL(1) типті) арқылы талданатын грамматикалар классын өз ішіне алады.
  

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

Анализатор программасы әр қадамда енуші лентадан бір символ оқиды. Талдау барысында магазин пайдаланылады. Магазинде S₀X₁S₁X₂S₂...X_mS_m (S_m – магазин төбесі) түріндегі қатарлар сақталады. Әрбір X_i – грамматика символдары (терминал не бейтерминал), ал S_i- жағдай символы.

Грамматика символдары (немесе жағдайлар символы) магазинде орналасуы шарт емес. Алайда, олардың қолданылуы LR-анализатордың әрекеттерін түсінуді жеңілдетеді.

• 
  shift S (жылжу), мұнда S – жағдай символы,
  
• 
  reduce A ( грамматиканың A ережесі бойынша қайыру),
  
• 
  accept (рұқсат допуск),
  
• 
  error (қате).
  

• 
  S, мұнда S – жағдай символы,
  
• 
  error (қате).
  

Бұл конфигурация оң жақ сентенциалды формаға сәйкес келеді

Оң жақ сентенциалды форманың префикстері белсенді префикстер деп аталады. Сентенциалды форманың негізі әрдайым магазин төбесінде орналасады. Осылайша белсенді префикс – бұл оң жақ сентенциалды форманың осы форма негізінің оң жақ шекарасынан өтпейтін префиксі.

4. Анализатор жұмысының басында магазинде S₀ бастапқы жағдай символы бар болады, ал енуші лентада анализ жасалатын аяқтау (соңы) маркері бар тізбек.

Анализатордың кезектегі қадамы ағымдағы енуші a_i символымен және магазин төбесіндегі S_m жағдайы символымен былайша анықталады.

LR(1)-анализатор мына конфигурацияда болсын

Анализатор келесі қадамдардың бірін орындай алады:

• 
  Егер Action[S_m, a_i] = shift S болса, онда анализатор мына конфигурацияғв ауыса отырып жылжуды орындайды
  

• 
  Егер Аction[S_m, a_i] = reduce A → γ, онда мына конфигурацияға ауыса отырып, қайыруды орындайды ,
  

Анализатор алдымен магазиннен 2r символдарды (r жағдай символдары және r грамматика символдары) жояды, сонда магазин төбесінде S_m-r жағдайы пайда болады. Бұдан соң анализатор магазинге А-ны, яғни шығару ережесінің сол жағын және Goto[S_m-r, A] функциясымен анықталатын S жағдай символын орналастырады. Қайыру орындалатын қадамда ағымдағы енуші символ орындалмайды. LR(1)-анализаторлар үшін X_m-r+1...X_m – магазиннен жойылатын грамматика символдарының қатары әрдайым қайыру орындалатын γ-ке, яғни шығару ережесінің оң жағына сәйкес келеді.

Қайыру қадамы орындалған соң LR(1)-анализатордың шығысы генерацияланады, яғни қайыру жасалынатын ережемен байланысты семантикалық әрекеттер орындалады, мысалы қайыру жасалынатын шығару ережелері басып шығарылады (печатается).

G грамматикасы бойынша құрылған талдау кестесінің Goto функциясы іс-жүзінде G-ң белсенді префикстерін танитын детерминант шекті автоматтың ауысу функциясы болып келетіндігін ескертеміз.

• 
  Егер Action[S_m, a_i] = accept, онда талдау сәтті аяқталған.
  
• 
  Егер Action[S_m, a_i] = error, онда анализатор қателікке кездесіп, диагностика және қалпына келтіру жұмыстары орындалуда.
  

(1) E E + T

(2) E T

(3) T T * F

(4) T F

(5) F id

Кірісінде id + id * id енуші лента тізбегі және магазин жағдайлары 4.10 суретте көрсетілген. Мысалы, бірінші қатарда LR-анализатор нөлдік жағдайда тұр және енуші бірінші id символды көріп тұр. Action өрісіндегі нөлдік қатар мен id бағанындағы S6 әрекеті (сур 4.9) магазин төбесіне жылжу және жағдай символы 6-ны орналастыруды білдіреді.

Бұл екінші қатарда да бейнеленген: бірінші символ id және жағдай символы 6 магазинге орналастырылады, ал енуші лентадағы id жойылады.

Рис. 4.9:

Рис. 4.10:

Ағымдағы енуші символ енді + болады, 6 жағдайы мен + енуші сигналы бойынша әрекет – бұл F id бойынша қайыру. Магазиннан екі символ жойылады (бір жағдай символы және бір грамматика символы). Бұдан соң нөлдік жағдай талданады (анализ жасалынады). Goto нөлдік жағдайда F символы бойынша - 3 болғандықтан, F пен 3 магазинге орналастырылады. Енді үшінші қатарға сәйкес конфигурацияға иеміз. Келесі қадамдар да осылай анықталады.