Головна

Граматики простого передування. відносини передування

  1.  LL (1) - граматики.
  2.  LR - граматики
  3.  S і q - граматики
  4.  атрибутних граматики
  5.  ВИДИ простого категоричного силогізму
  6.  Глава 3. Ставлення імператора, духовенства і простого люду до астрології. Пророцтва царським особам, містах.
  7.  Говори своїми словами - і все виявиться простіше простого

Відносини передування такі ж відносини, як і логічні, диз'юнкція, і несуть сенс певних операцій.

Примітка. Тут і надалі будемо розглядати пару поруч стоять символів R, SIV = VtEVn, Тобто вважати ці символи термінальними або нетермінальнимі.

Визначення 5.3.Кажуть, що R передує S (R ·> S) (тобто R згортається раніше, ніж S), якщо R є частиною основи синтаксичного дерева, а S немає (рис. 5.22).

Мал. 5.22. R ·> S

Визначення 5.4.Кажуть, що R згортається одночасно з S (R  S), якщо обидва символи входять в основу одночасно (рис. 5.23).

Мал. 5.23. R S

Визначення 5.5.Кажуть, що S передує R (R <· S), або R згортається пізніше, ніж S, якщо S в основі, а R ще немає (ріс.5.24).

Мал. 5.24. R <· S

Властивості відносини передування. Відносини передування на відміну від всіх основних відносин, не володіють комутативними властивостями, тобто не можна застосовувати властивості симетрії до відносин передування. Дійсно, якщо ми говоримо що R передує S (R ·> S), то це зовсім не означає, що S <· R. Хоча для певних символів словника це має місце, але тільки в окремому випадку.

Сформулюємо аналітичні визначення відносин.

Визначення 5.6.Ставлення U FIRST S має місце, тоді і тільки тоді, коли має місце виводимість: U®Sa, SIVN, AIV *. (Інакше кажучи, S - перший нетермінал.)

Визначення 5.7. ОтношеніеU FIRST+ S має місце, тоді і тільки тоді, коли існує итерационная виводимість: U?+Sa, SIVN, AIV *.

Визначення 5.8.ОтношеніеU LAST S має місце, тоді і тільки тоді, коли має місце виводимість: U®aS, SIVN , AIV *.

Визначення 5.9.Ставлення U LAST+ S має місце, тоді і тільки тоді, коли існує итерационная виводимість: U?+aS, SIVN , AIV *.

Визначення відносин передування між символами по заданій граматиці проводиться у відповідності з властивостями відносин:

Властивість 1. R  S, коли в граматиці існують такі відносини:

U®aRSbIP; причому

a, bIV *; R, SIV.

Властивість 2.. R <· S, якщо в граматиці існують або мають місце такі відносини:

U®aRWb; причому

a, bIV *; W FIRST+ S; R, S, WIV.

Властивість 3..R ·> S, якщо в граматиці існують або мають місце такі відносини:

U®aQWb; причому

a, bIV *; Q LAST+ R; W FIRST+ S; R, S, W, QIV.

Для ілюстрації розглянемо граматику G[Z]:

1. Z ® bMb

2. M ® (L | a

3. L ® Ma)

Легко бачити, що G[Z] є граматикою простого передування. (Легко доводиться!)

Мова, що породжується даною граматикою:

L(G[Z]) = {bab, b (aa) b, b ((aa) a) b,. . . .}

Побудуємо сентенціальной дерева з ланцюжків належать L(G[Z]) (рис. 5.25 ... 5.27)

Мал. 5.25. 1-е сентенціальной дерево

Мал. 5.26. 2-е сентенціальной дерево

Мал. 5.27. 3-е сентенціальной дерево

В даному випадку відносини передування між символами граматики встановлено графічно, то ж саме можна було б зробити за допомогою властивостей 1,2,3 відносини FIRST, LAST, але аналітично.

Матриця передування.

Алгоритм розбору для висхідного распознавателя з використанням граматик передування. алгоритм Флойда (1963)

Матриця передування представляється у вигляді таблиці Q c елементами qij такими, що:

qij= 0, якщо Si і Sj непорівнянні;

qij= 1, якщо Si<· Sj;

qij= 2, якщо Si Sj;

qij= 3, якщо Si·> Sj.

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

Алгоритм Флойда. Символи вхідного ланцюжка проглядаються зліва направо і поміщаються в стек S до тих пір, поки символ вершини стека Si бракуватиме щодо передування "·>" з черговим аналізованих символом R, це означає, що верхній символ стека є "хвостом" основи і, отже, основа вже в стеку.

Основу знаходять у списку правил приготовленої таблиці редукцій і замінюють нетерміналом U. Процес повторюється до тих пір, поки в якості U не опиниться Z (рис. 5.28).

Мал. 5.28. До алгоритму Флойда


Мал. 5.29. Блок-схема распознавателя

Блок-схема распознавателя зображена на рис. 5.29.

Тут S - стек; i - лічильник стека; j - індекс адресації внутрішніх елементів стека; $ t1, ..., Tn$ - Формат аналізованого пропозиції; U - нетермінал, до якого наводиться основа, знайдена на кроці розбору; Z - початковий символ граматики.

Значення блоків:

1,2 - завдання початкових умов;

3,4 - виконання умови: якщо Si і R не перебувають у відношенні Si·> R, то не вся основа в стеці, тому символ R заноситься в стек і пошук триває.

5,6,7 - Si передує R (Si·> R), отже, основа вже в стеку. Необхідно знайти "голову" основи (тобто таке j, що Sj-1<· Sj ).

8,9 - перевірка ланцюжка Sj... Si ; якщо вона не є правою частиною редукції, то робота закінчена з авостом (помилкою), в іншому випадку виключити з стека Sj... Si , І занести в стек символ U, який є лівою частиною (U®Sj ... Si).

 




 Семантика цілого числа при скануванні |  Лексичний аналіз ідентифікатора |  Лексичний аналіз операцій |  Структури лінійного формату |  блокові структури |  деревовидні структури |  Хеш-адресація |  рекурсивний спуск |  метод Айронса |  Алгоритм Айронса щодо виправлення помилок |

© um.co.ua - учбові матеріали та реферати