Синтаксичний аналіз. Спадний аналіз. Предиктивний аналізатор. Висхідний аналіз, страница 4

Ми скануємо рядок abbcde у пошуках підрядка, що відповідає правій частині якоїсь продукції. Такими підрядками є b і d . Виберемо крайнє зліва b і замінимо його нетерміналом A, що являє собою ліву частину продукції A→b; таким чином, одержимо рядок aAbcde. Тепер правим частинам продукцій відповідають підрядки Abc, b і d. Хоча b і є крайнім зліва підрядком, що відповідає правій частині однієї з продукцій, виберемо для заміни підрядок Abc і замінимо його нетерміналом A відповідно до продукції A→Abc. У результаті одержимо рядок aAde. Заміняючи d на B, ліву частину продукції B→d, одержуємо aABe, що відповідно до першої продукції заміняється стартовим символом S. Отже, послідовність з чотирьох згортань дозволяє привести рядок abbcde до стартового символа S. Ці скорочення являють собою обернене праве породження

S  aABe  aAde  aAbcde  abbcde.

4.7 Обрізання основ

Неформально кажучи, основа рядка – це підрядок, який збігається з правою частиною продукції і згортання якої в ліву частину продукції являє собою один крок оберненого правого породження. У багатьох випадках крайній зліва підрядок β, що відповідає правій частині деякої продукції A→β, не є основою, оскільки згортання у відповідності з продукцією A→β приводить до рядка, який не може бути згорнутий до стартового символа. Якщо в попередньому прикладі ми замінимо у другому рядку aAbcde символ b нетерміналом A, то одержимо рядок aAAcde, який не може бути згорнутий до S. Тому нам потрібно дати більш точне визначення основи.

Кажучи формально, основа правосентенціальної форми γ є продукцією A→β і позицією рядка βв γ, такими, що βможе бути замінена нетерміналом Aдля одержання попередньої правосентенціальної форми у правому породженні  γ. Таким чином, якщо SαAw αβw, то A→β в позиції після α являє собою основу рядка αβw. Рядок wправоруч від основи містить тільки термінальні символи. Відмітимо, що граматика може бути неоднозначною, з кількома правими породженнями αβw. Якщо граматика однозначна, то кожна правосентенціальна форма граматики має тільки одну основу.

У наведеному прикладі abbcde являє собою право- сентенціальну форму, основою якої є A→β в позиції 2. Аналогічно aAbcdeявляє собою правосентенціальну форму, основою якої є A→Abc в позиції 2.

Розглянемо таку граматику:

E →E + E ,              E →E * E ,

E →( E ) ,                E →id  

і праве породження

E E+E  E+E*E  E+E* id3

  E+ id2 * id3 id1 + id2 * id3 .

Для зручності тут підкреслено основи кожної правосентенціальної форми. Наприклад  id1 являє собою основу правосентенціальної форми id1+ id2*id3, оскільки id є правою частиною продукції  E→id, і заміна id1 на E приведе до попередньої правосентенціальної форми E+id2* id3.

Обернене праве породження може бути  отримане за допомогою повторного застосування “обрізання основ”. Ми починаємо процес з рядка терміналів w.  Якщо w  є  словом граматики, то w=γn, де γn – правосентенціальна форма ще невідомого правого породження

S = γ0 γ1 γ2  ... γn-1 γn = w .

Щоб відновити це породження у оберненому  порядку,  виділяємо основу βn у γn і заміняємо βn на ліву частину деякої продукції An→βn,  в результаті одержимо (n-1)-у правосентенціальну форму γn-1.

Потім  повторюємо цей процес, тобто виділяємо у γn-1 основу  βn-1 і згортаємо цю основу, одержуючи правосентенціальну форму γn-2.  Якщо, повторюючи  цей процес,  ми одержимо правосентенціальну форму, що  складається тільки з початкового символа S, то  зупиняємося  і  повідомляємо  про  успішне  завершення розбору. Обернена послідовність продукцій, використаних у згортках, є праве породження вхідного рядка.

Для вхідного рядка id1+id2 * id3 послідовність згортань наведена в табл. 4.3.

Таблиця 4.3 

Правосентенціальна форма

Основа

Продукція

для  згорання

id1+id2* id3

E+id2* id3

E+E * id3

E+E * E

E+E

E

id1

id2

id3

E * E

E+E

E →id

E →id

E →id

E → E * E

E → E + E

Зручним шляхом реалізації ПЗ-аналізатора є використання стека для зберігання символів граматики і вхідного буфера для зберігання рядка, що аналізується. Для маркера дна стека ми використовуємо $, і цей самий символ буде маркером правого кінця вхідного рядка. Спочатку стек порожній, а вхідний буфер містить рядок w.