2015-10-22
453
Для реалізації СКТ у даному випадку використаємо ПСА, додавши йому ще функції, що описані в у п. 6.1.
Нижче наведено трохи розширену, у порівнянні з п.5, граматику для арифметичних виразів і таблицю синтаксичного аналізу цієї граматики.
Граматика
1) E → TE’ 2) T → FT’ 3) E’ → є 4) E’ → PE’ 5) T’ → є 6) T’ → M
7) F → (E) 8) F → id 9) P → + 10) P → - 11) M → * 12) M → /
Таблиця предиктивного аналізатора
| Нетер-мінал | Вхідний символ | |||||||||
| id | + | - | * | / | ( | ) | $ | |||
| E | E → TE' | E → TE' | ||||||||
| E' | E' → PTE' | E' → PTE' | E' → ε | E' → ε | ||||||
| T | T → FT' | T → FT' | ||||||||
| T' | T' → ε | T' → ε | T' → MFT' | T' → MFT' | T' → ε | T' → ε | ||||
| F | F → id | F → (E) | ||||||||
| P | P → + | P → - | ||||||||
| M | M → * | M → / | ||||||||
Приклад 6.5. При вхідному потоці id1+id2*id3 предиктивний синтаксичний аналізатор здійснює послідовність переміщень, наведену у таблиці..
|
|
|
| № | Стек | Вхід | Правило | Постф | Стек2 |
| $ E | id1+id2*id3 $ | іd1 | $ | ||
| $ E'T | id1+id2*id3 $ | E → TE' | іd1 | $ | |
| $ E'T'F | id1+id2*id3 $ | T → FT' | іd1 | $ | |
| $ E'T' id | id1+id2*id3 $ | F → id | іd1 | $ | |
| $ E'T' | +id2*id3 $ | іd1 | $+ | ||
| $ E' | + id2*id3$ | T' → ε | іd1 | $+ | |
| $ E'TP | + id2*id3 $ | E' → PTE' | іd1 | $ + | |
| $ E'T+ | +id2*id3 $ | P → + | іd1 | $ + | |
| $ E'T | id2*id3 $ | іd1 іd2 | $ + | ||
| $ E'T'F | id2*id3 $ | T → FT' | іd1 іd2 | $ + | |
| $ E'T' id | id2*id3 $ | F → id | іd1 іd2 | $+ | |
| $ E'T' | *id3$ | іd1 іd2 | $ +* | ||
| $ E'T'FM | *id3$ | T' → M FT' | іd1 іd2 | $ +* | |
| $ E'T'F* | *id3$ | M → * | іd1 іd2 | $ +* | |
| $ E'T'F | id3 $ | іd1 іd2 іd3 | $+ * | ||
| $ E'T' id | id3 $ | F → id | іd1 іd2 іd3 | $ + * | |
| $ E'T' | $ | іd1 іd2 іd3 * | $ + | ||
| $ E' | $ | T' → ε | іd1 іd2 іd3 *+ | $ | |
| $ | $ | E' → ε | іd1 іd2 іd3 *+ | $ |
Рис. Переміщення синтаксичного аналізатора при вхідному рядку id + id * id
Приклад 6. 6. Вираз в інфіксній формі id1*id2 +id3
| № | Стек | Вхід | Правило | Постф | Стек2 |
| $ E | id1*id2+id3 $ | іd1 | $ | ||
| $ E'T | id1*id2+id3 $ | E → TE' | іd1 | $ | |
| $ E'T'F | id1*id2+id3 $ | T → FT' | іd1 | $ | |
| $ E'T' id | id1*id2+id3 $ | F → id | іd1 | $ | |
| $ E'T' | *id2+id3 $ | іd1 | $* | ||
| $ E'T'FM | *id2+id3 $ | M → * | іd1 | $* | |
| $ E' T'F* | *id2+id3 $ | T' → * FT' | іd1 | $* | |
| $ E' T'F | id2+id3 $ | іd1 іd2 | $* | ||
| $ E' T' id | id2+id3 $ | F → id | іd1 іd2 | $* | |
| $ E' T' | +id3 $ | іd1 іd2 | $* | ||
| $ E' T' | +id3 $ | іd1 іd2 * | $+ | ||
| $ E' | +id3 $ | T' → ε | іd1 іd2 * | $+ | |
| $ E'TP | +id3 $ | E’ → PTE’ | іd1 іd2 * | $+ | |
| $ E'T + | +id3 $ | P → + | іd1 іd2 * | ||
| $ E'T | id3 $ | T → FT’ | іd1 іd2 * іd3 | $+ | |
| $ E'T’F | id3 $ | F → id | іd1 іd2 * іd3 | $+ | |
| $ E'T’ id | id3 $ | іd1 іd2 * іd3 | $+ | ||
| $ E'T’ | $ | іd1 іd2 * іd3 | $+ | ||
| $ E' | $ | T' → ε | іd1 іd2 * іd3 + | $ | |
| $ | $ | E' → ε | іd1 іd2 * іd3 + | $ |
Приклад 6.7. При вхідному потоці (id+id)*id предиктивний синтаксичний аналізатор разом з СОТ здійснює послідовність переміщень, наведену у таблиці.
|
|
|
| № | Стек | Вхід | Правило | Постфікс | Стек2 |
| $ E | (id1+id2)*id3 $ | $( | |||
| $ E'T | (id1+id2)*id3 $ | E → TE' | $( | ||
| $ E'T'F | (id1+id2)*id3 $ | T → FT' | $( | ||
| $ E'T') Е ( | (id1+id2)*id3 $ | F → (E) | $( | ||
| $ E'T') Е | id1+id2)*id3 $ | id1 | $( | ||
| $ E'T') E'T | id1+id2)*id3 $ | E → TE' | id1 | $( | |
| $ E'T') E' T'F | id1+id2)*id3 $ | T → FT' | id1 | $( | |
| $ E'T') E' T' id | id1+id2)*id3 $ | F → id | id1 | $( | |
| $ E'T') E' T' | +id2)*id3 $ | T' → ε | id1 | $(+ | |
| $ E'T') E' | +id2)*id3 $ | id1 | $(+ | ||
| $ E'T') E'TP | +id2)*id3 $ | E' → PTE' | id1 | $(+ | |
| $ E'T') E'T + | +id2)*id3 $ | P → + | id1 | $(+ | |
| $ E'T') E'T | id2)*id3 $ | id1 id2 | $(+ | ||
| $ E'T') E' T'F | id2)*id3 $ | T → FT' | id1 id2 | $(+ | |
| $ E'T') E'T' id | id2)*id3 $ | F → id | id1 id2 | $(+ | |
| $ E'T') E' T' | )*id3 $ | id1 id2 + | $ | ||
| $ E'T') E' | )*id3 $ | T' → ε | id1 id2 + | $ | |
| $ E'T') | )*id3 $ | E' → ε | id1 id2 + | $ | |
| $ E'T' | *id3 $ | id1 id2+ | $ * | ||
| $ E'T'FM | *id3 $ | T' → MFT' | id1 id2+ | $ * | |
| $ E'T'F * | *id3 $ | M → * | id1 id2+ | $ * | |
| $ E'T'F | іd3 $ | id1 id2+ іd3 | $ * | ||
| $ E'T' id | іd3 $ | F → id | id1 id2+ | $ * | |
| $ E'T' | $ | id1 id2+id3* | $ | ||
| $ E' | $ | T' → ε | id1 id2+id3* | $ | |
| $ | $ | E' → ε | id1 id2+id3* | $ |
Приклад 6.8. При вхідному потоці id-id-id предиктивний синтаксичний аналізатор разом з СОТ здійснює послідовність переміщень, наведену у таблиці.
| № | Стек | Вхід | Правило | Постф | Стек2 |
| $ E | id1- id2 - id3 $ | іd1 | $ | ||
| $ E'T | id1- id2 - id3 $ | E → TE' | іd1 | $ | |
| $ E'T'F | id1- id2 - id3 $ | T → FT' | іd1 | $ | |
| $ E'T' id | id1- id2 - id3 $ | F → id | іd1 | $ | |
| $ E'T' | - id2 - id3 $ | іd1 | $ - | ||
| $ E' | - id2 - id3 $ | T' → ε | іd1 | $ - | |
| $ E'TP | - id2 - id3 $ | E’ → PTE' | іd1 | $ - | |
| $ E'T - | - id2 - id3 $ | P → - | іd1 | $ - | |
| $ E'T | id2 - id3 $ | іd1 | $ - | ||
| $ E' T'F | id2 - id3 $ | T → FT' | іd1 | $ - | |
| $ E' T'F | id2 - id3 $ | F → id | іd1 іd2 | $ - | |
| $ E' T' id | id2 - id3 $ | F → id | іd1 іd2 | $ - | |
| $ E' T' | - id3 $ | іd1 іd2 - | $ | ||
| $ E' T' | - id3 $ | T' → ε | іd1 іd2 - | $ - | |
| $ E' | - id3 $ | іd1 іd2 - | $ - | ||
| $ E' TP | - id3 $ | E’ → PTE' | іd1 іd2 - | $ - | |
| $ E' T - | - id3 $ | P → - | іd1 іd2– | $ - | |
| $ E'T | id3 $ | іd1 іd2–іd3 | $ - | ||
| $ E' T'F | id3 $ | T → FT' | іd1 іd2 – іd3 | $ - | |
| $ E' T' id | id3 $ | F → id | іd1 іd2 – іd3 | $ - | |
| $ E' T' | $ | іd1 іd2 – іd3 - | $ | ||
| $ E' | $ | T' → ε | іd1 іd2 – іd3 - | $ | |
| $ | $ | E' → ε | іd1 іd2 – іd3 - | $ |
