PPT - Розбір леволінійної граматики

509 переглядів
Uploaded on Oct 03, 2014

Розбір з ліволінійної граматики. Угоди : - для опису лексем використовуватимемо леволінійну автоматну граматику без порожніх правих частин: G = (T, N, P, S) леволінійна , якщо кожне правило з Р має вигляд A → Bt або A → t, де A  N, B  N, t  T.

Розбір з ліволінійної граматики.

- для опису лексем використовуватимемо леволінійну автоматну граматику без порожніх правих частин: G = (T, N, P, S) леволінійна, якщо кожне правило з Р має вигляд

A → Bt чи A → t, де A ? N, B ? N, t ? T.

- аналізований ланцюжок закінчується спеціальним символом  - ознакою кінця ланцюжка.

Алгоритм аналізу з леволінійної граматики:

перший символ вихідного ланцюжка a1a2. an замінюємо нетерміналом A, для якого в граматиці є правило виведення

(іншими словами, робимо "згортку" терміналу a1 до нетерміналу A)

(2) багаторазово (доки не рахуємо ознаку кінця ланцюжка) виконуємо наступні кроки: отриманий на попередньому кроці нетермінал A і розташований безпосередньо праворуч від нього черговий термінал ai вихідного ланцюжка замінюємо нетерміналом B, для якого в граматиці є правило виведення B → Aai (i = 2, 3. n);

Діаграма станів (ДС) - невпорядкований орієнтований позначений граф, який будується так:

(1) будуємо вершини графа, позначені нетерміналами граматики (для кожного нетерміналу - одну вершину), і ще одну вершину, позначену символом, відмінним від нетермінальних (наприклад, H). Ці вершини називаються станами. H – початковий стан.

(2) з'єднуємо цістану дугами за такими правилами:

a) для кожного правила виду W  t з'єднуємо дугою стану H та W

(Від H до W) і позначаємо дугу символом t;

б) для кожного правила виду W  Vt з'єднуємо дугою стану V та W

(Від V до W) і позначаємо дугу символом t;

Діаграма станів для граматики G_ex = (< a, b,  >, <

P: S  C виглядатиме так:

Алгоритм аналізу за діаграмою станів:

(1) оголошуємо поточний стан H;

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