АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Побудова таблиці переходів синтаксичного LL(1)-аналізатора

Читайте также:
  1. АлгОРитм синтаксичного розбору односкладного речення
  2. Визначення охолоджуючої здатності і швидкості руху повітря, побудова рози вітрів.
  3. Вихідні дані до практичного заняття №2. «Виявлення сезонних коливань та побудова прогнозу із використанням індексу сезонності»
  4. Вихідні дані до практичного заняття №6. «Побудова прогнозної моделі з використанням регресійно-кореляційної моделі»
  5. Властивості полів таблиці
  6. Вставка у текстовий документ таблиці
  7. Дільницю обслуговують 10 контролерів. Програму дільниці та трудомісткість контрольних операцій наведено в таблиці.
  8. Завдання 1. Створення таблиці та виконання обчислень у таблиці.
  9. Завдання за варіантами надані в таблиці.
  10. Загальна побудова і зміст облікового процесу.
  11. Задано структуру таблиці деякої бази даних. Який тип доцільно вибрати для поля Адреса?
  12. Задача 2. Побудова лінії перетину поверхонь способом допоміжних січних концентричних сфер.

В даних матеріалах розглядається методика і алгоритми побудови предикативного синтаксичного аналізатора (ПСА) для LL(1)- граматик. Перше " L " означає перегляд вхідного потоку зліва направо, друге " L "– ліве породження, а " 1 " – перегляд одного символу із вхідного потоку на кожному кроці для прийняття рішення про подальші дії.

Побудова таблиці переходів синтаксичного LL(1)- аналізатора передбачає таку послідовність робіт:

- усунення лівої рекурсії в БНФ;

- ліва факторизація;

- побудова множини FIRST;

- побудова множини FOLLOW;

- побудова таблиці переходів предикативного синтаксичного аналізатора.

Для демонстрації змісту вказаних робіт будемо використовувати граматику визначення змінних мовою Pascal, яку в.

(1) <оператор_опису_змінних>::= var <список_імен_змінних>: <тип_змінних>;

(2) <список_імен_змінних>::= іd

(3) <список_імен_змінних>::= <список_імен_змінних>, id

(4) <тип_змінних>::= char

(5) <тип_змінних>::= real

(6) <тип_змінних>::= int

(7) <тип_змінних>::= integer

Усунення лівої рекурсії в БНФ

Граматика є ліворекурсивною, якщо в ній є нетермінал А, такий, що існує породження А →+ А αдля деякого рядка α. Методи спадного розбору не в змозі працювати з ліворекурсивными граматиками, тому потрібне перетворення граматики, що усунуло б з неї ліву рекурсію. Наприклад, ліво рекурсивна пара продукцій

A::= Aα | β

може бути замінена не ліво рекурсивними продукціями

А::= βА '

А'::= α А'|ε

без зміни множини рядків, породжуваних з А. Цього правила досить для багатьох граматик мов ролграмування.

В наведеній вище граматиці Gvar є ліво рекурсивна пара продукцій

<список_імен_змінних>::= <список_імен_змінних>, id | id

Їх за наведеними правилами можна перетворити в продукції:

<список_імен_змінних>::= id <спис_імен_зм2>

<спис_імен_зм2>::=, id <спис_імен_зм2> | ε

Тоді не ліво рекурсивна граматика G1var буде такою:

(1) <оператор_опису_змінних>::= var <список_імен_змінних>: <тип_змінних>;

(2) <список_імен_змінних>::= id <спис_імен_зм2>

(3) <спис_імен_зм2>::=, id <спис_імен_зм2>

(4) <спис_імен_зм2>::= ε

(5) <тип_змінних>::= char

(6) <тип_змінних>::= real

(7) <тип_змінних>::= int

(8) <тип_змінних>::= integer

Ліва факторизація

Ліва факторизація (left factoring) являє собою перетворення граматики, що придатна для предиктивного аналізу. Основна ідея лівої факторизації полягає в тому, що коли не ясно, яка із двох або більше альтернативних продукцій повинна використатися для не термінала А, А -продукції можна переписати так, щоб відкласти ухвалення рішення доти, поки із вхідного потоку не буде прочитано достатньо символів для правильного вибору. Наприклад, якщо А:: = α β1β2 являють собою дві А -продукції й вхідний потік починається з непустого рядка, породжуваного α, то ми не можемо сказати, буде використатися перша або друга продукція. Однак можна відкласти рішення, розширивши А до α А'. У цьому випадку, після того як розглянутий вхідний потік, що виведений з α, ми працюємо з А', розширюючи його до β1 або β2. Таким чином, будучи ліво факторизованими, вихідні продукції стають

А::= α А'

А'::= β1 | β2

В наведеній вище граматиці G1var є 2 продукції, що мають загальний префікс

<тип_змінних>::= int

<тип_змінних>::= integer

Будучи ліво факторизованими, вихідні продукції стають:

<тип_змінних>::= int <тип_змін1>

<тип_змін1>::= eger

<тип_змін1>::= ε

Тоді не ліво рекурсивна та лівофакторизована граматика G2var буде такою:

(1) <оператор_опису_змінних>::= var <список_імен_змінних>: <тип_змінних>;

(2) <список_імен_змінних>::= id <спис_імен_зм2>

(3) <спис_імен_зм2>::=, id <спис_імен_зм2>

(4) <спис_імен_зм2>::= ε

(5) <тип_змінних>::= char

(6) <тип_змінних>::= real

(7) <тип_змінних>::= int <тип_змін1>

(8) <тип_змін1>::= eger

(9) <тип_змін1>::= ε

4.8.3 Побудова множин FIRST і FOLLOW

При побудові предиктивного синтаксичного аналізатора (ПСА) треба визначити дві множини, пов’язані із граматикою G, – FIRST й FOLLOW, які забезпечують заповнення таблиці предиктивного аналізу граматики G. Множини токенів, породжувані функцією FOLLOW, можуть також використатися як синхронізуючі токени в процесі відновлення після помилки в "режимі паніки".

4.8.3.1 Побудова множини FIRST

Щоб обчислити FIRST(X) для всіх символів граматики X, будемо застосовувати наступні правила доти, поки до жодної із множин FIRST не зможуть бути додані ні термінали, ні ε.

1. Якщо X – термінал, то FIRST(X) = { X }.

2. Якщо X – нетермінал та існує продукція X :: = ε, додаємо ε до FIRST(X).

3. Якщо X – нетермінал й існує продукція X::= Y1Y2... Yk, то помістимо а в FIRST(X), якщо для якогось i a ÎFIRST(Yi) і ε входить в усі множини FIRST(Y 1),…, FIRST(Yi -1), тобто Y 1··· Yi -1 * ε. Якщо ε є у всіх FIRST(Yi), і = 1…k, то додаємо ε до FIRST(X). Наприклад, усе, що перебуває в множині FIRST(Y 1), є й у множині FIRST(X). Якщо Y1 не породжує ε, то більше ми нічого не додаємо до FIRST(X), але якщо Y1 * ε, то до FIRST(X) додаємо FIRST(Y 2) і т.д.

Тепер можна обчислити FIRST для будь-якого рядка X1X2...Xn наступним чином. Додамо до FIRST(X1X2...Xn) всі не-ε символи з FIRST(X1). Додамо також всі не- ε символи з FIRST (X2), якщо ε ÎFIRST (X1), всі не-ε символи з FIRST(X3), якщо ε є як в FIRST(X1), так й в FIRST(X2) і т.д. І нарешті, додамо ε до FIRST (X1X2...Xn), якщо для всіх i FIRST(Xi) містить ε.

(1) <оператор_опису_змінних>::= var <список_імен_змінних>: <тип_змінних>;

(2) <список_імен_змінних>::= id <спис_імен_зм2>

(3) <спис_імен_зм2>::=, id <спис_імен_зм2>

(4) <спис_імен_зм2>::= ε

(5) <тип_змінних>::= char

(6) <тип_змінних>::= real

(7) <тип_змінних>::= int <тип_змін1>

(8) <тип_змін1>::= eger

(9) <тип_змін1>::= ε

FIRST(<оператор_опису_змінних>) = { var }

FIRST(<список_імен_змінних>) = { id }

FIRST(<спис_імен_зм2>)::= { “ ,”, ε }

FIRST(<тип_змінних>) = { char, real, int }

FIRST(<тип_змін1>) = { eger, ε }


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.006 сек.)