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

Програмування предиктивного синтаксичного аналізатора (ПСА)

Читайте также:
  1. PHP – скриптова мова програмування
  2. АлгОРитм синтаксичного розбору односкладного речення
  3. Види відчуттів. Пороги відчуттів. Чутливість аналізатора. Сенсибілізація.
  4. Візуальна мова програмування Бейсік для додатків: Visual Basic for Applications (VBA)
  5. Геометричні методи та лінійне програмування.
  6. Державне програмування та прогнозування економіки.
  7. Інструментарій технології програмування
  8. Метод рекурсивного спуску програмування синтаксичних аналізаторів
  9. Мова програмування Pascal
  10. Мови програмування та мовні процесори
  11. Основи програмування в середовищі Delphi 7 0
  12. Побудова таблиці переходів синтаксичного LL(1)-аналізатора

 

Нерекурсивний предиктивнй синтаксичний аналізатор можна побудувати за допомогою явного використання стека (замість неявного при рекурсивних викликах). Ключова проблема предиктивного аналізу полягає у визначенні продукції, яку варто застосувати до нетермінала.

Нерекурсивний синтаксичний аналізатор, представлений на рис. 5.5, шукає необхідну для аналізу продукцію в таблиці розбору (далі ми побачимо, яким образом можна побудувати цю таблицю на основі граматики).

Рис. 5.5. Модель нерекурсивного предиктивного синтаксичного аналізатора

Предиктивнй синтаксичний аналізатор, керований таблицею, має вхідний буфер, стек, таблицю розбору й вихідний потік. Вхідний буфер містить аналізований рядок з маркером її правого кінця – спеціальним символом. Стек містить послідовність символів граматики з $ на дні. Завжди стек містить стартовий символ граматики безпосередньо над символом $. Таблиця розбору являє собою двомірний масив M[А,а], де А – нетермінал, a а – термінал або символ $.

Синтаксичний аналізатор керується програмою, що працює в такий спосіб. Програма розглядає X – символ на вершині стека, і а – поточній вхідний символ. Ці два символи визначають дії синтаксичного аналізатора. Є три варіанти.

1. Якщо X = а = $, синтаксичний аналізатор припиняє роботу й повідомляє про успішне завершення розбору.

2. Якщо X = а ≠ $, синтаксичний аналізатор знімає зі стеку X і переміщує покажчик вхідного потоку до наступного символу.

3. Якщо X:: = ε, синтаксичний аналізатор знімає зі стеку X, але не переміщує покажчик вхідного потоку до наступного символу.

4. Якщо X являє собою нетермінал, програма розглядає запис M[X,а] з таблиці розбору М. Цей запис являє собою або X-продукцію граматики або запис про помилку. Якщо, наприклад, M[X,а] = {X::= UVW}, синтаксичний аналізатор заміщує X на вершині стеку на WVU (з U на вершині стека). Ми вважаємо, що як вихід синтаксичний аналізатор просто виводить використану продукцію, але, звичайно ж, тут може виконуватися будь-який необхідний код.

5. Якщо M[X,а] = error, синтаксичний аналізатор викликає програму відновлення після помилки.

Розглянемо послідовність роботи ПСА для рядка var a12: char;

У наведеному рядку роль символа його закінчення виконує символ “, ”, тому ПСА буде закінчувати роботу, коли покажчик стеку досягне симолу $ (дно стеку), а покажчик сканування рядка досягне символу “, ”.

Приклад 1. var a12: char;

Вміст стеку Вхідий рядок Правило з таблиці М[X,a]
$ <оператор_опису_змінних> var a12:char;  
$<тип_змінних>:<список_імен_змінних> var var a12:char; оператор_опису_змінних>→ var <список_імен_змінних>: <тип_змінних>;
$ <тип_змінних>:<список_імен_змінних> a12: char;  
$ <тип_змінних>:<спис_імен_зм2> id a12: char; <список_імен_змінних> → id<спис_імен_зм2>;
$<тип_змінних>:<спис_імен_зм2> : char;  
$ <тип_змінних>: : char; <спис_імен_зм2> → ε;
$ <тип_змінних> char;  
$ char char; <тип_змінних> → char
$ ;  
    exit

 

Приклад 2. var a12,bc: integer;

Вміст стеку Вхідий рядок Правило з таблиці М[X,a]
$ <оператор_опису_змінних> var a12,bc: integer;  
$<тип_змінних>:<список_імен_змінних> var var a12,bc: integer; оператор_опису_змінних>→ var <список_імен_змінних>: <тип_змінних>;
$ <тип_змінних>:<спис_імен_зм2>; id a12,bc: integer; <список_імен_змінних> → id<спис_імен_зм2>;
$ <тип_змінних>:<спис_імен_зм2> ,bc: integer;  
$ <тип_змінних>:<спис_імен_зм2> id, ,bc: integer; <спис_імен_зм2> →, id<спис_імен_зм2>
$ <тип_змінних>:<спис_імен_зм2> id bc: integer;  
$ <тип_змінних>:<спис_імен_зм2> : integer;  
$ <тип_змінних>: : integer; <спис_імен_зм2> → ε
$ <тип_змінних> integer;  
$ <тип_змін2> int integer; <тип_змінних>→ int<тип_змін2>
$ <тип_змін2> eger;  
$ eger eger; <тип_змін2> → eger
$ ;  
    exit

 

 


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

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



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