 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Побудова таблиці переходів синтаксичного LL(1)-аналізатора
В даних матеріалах розглядається методика і алгоритми побудови предикативного синтаксичного аналізатора (ПСА) для 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, ε }
Поиск по сайту: