Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Грамматики предшествования Вирта
|
|
Отношения предшествования в грамматиках Вирта определяются между любыми символами: как терминальными, так и нетерминальными.
Алгоритм свёртки терминальных цепочек по Вирту:
1. Строится для любого нетерминального символа множество левых и правых символов.
2. Определяется отношение предшествования между символами, и заносятся в матрицу (таблицу предшествования).
3.Выполняя последовательные выделения основ для свёртки, осуществляется собственно свёртка цепочек.
4. Включается семантика в алгоритм свёртки цепочки.
Множество левых и правых символов для каждого нетерминала грамматики определяется следующим образом: L – множество левых символов:
L(u)={S|u®jÚ u®AjÙ SÎ L(A)}, где uÎ VN,, SÎ (VTÈ VN), jÎ (VTÈ VN)*
R – множество правых символов:
Отношения предшествования в грамматике по Вирту определяются следующим образом:
а) S1 
S2, если существует правило вида: u®jS1S2h, где u – нетерминал, S1, S2Î (VTÈ VN), j, hÎ (VTÈ VN)*.
б) S1< ·S2, если существует правило вида: u®jS1bh, S2Î L(B), S1, S2Î (VTÈ VN), u, BÎ VN, j, hÎ (VTÈ VN)*
в) S1 ·> S2, если существует правило вида: u®jAS2h, S1Î R(A), S1, S2Î (VTÈ VN), u, AÎ VN, j, hÎ (VTÈ VN)* или u®jABh, S1Î R(A), S2Î L(B), A, B, uÎ VN
Пример 6.1.
S®^(AB)^, A®[A]|*, B®[B]|*
Строим множество левых и правых символов.
| U | L(u) | R(u) |
| S | ^ | ^ |
| A | [* | ]* |
| B | [+ | ]+ |
Рис. 6.1.
| S | ^ | ( | A | B | ) | [ | ] | * | + | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| S | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ^ | 
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ( |
| < · | < · | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| A |
| < · |
| < · | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| B |
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ) |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| [ |
|
| < · | < · | < · | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ] | ·> | ·> | ·> | ·> | ·> | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| * | ·> | ·> | ·> | ·> | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| + | ·> | ·> |
Матрица предшествования:
Рис. 6.2.
Проверим принадлежность цепочки 
языку, выполнив свертку по Вирту: 
-
S
Рис. 6.3.
Как видно, удалось свернуть цепочку до начального выделенного символа S, значит, цепочка принадлежит языку. Зато цепочка 
языку.
При выполнении свертки по Вирту возможны следующие ошибки:
1)между двумя символами не существует отношения предшествования;
2)выделена основа для свертки, а подходящего правила для замены нет.
Следует заметить, что не существует общего алгоритма, позволяющего преобразовать произвольную КС-грамматику к грамматике предшествования, хотя существует правило, позволяющее выполнить это для некоторых КС-грамматик, действие которого показано на следующем примере:
Включение семантики осуществляется следующим образом: в соответствии с любым правилом вывода ставится некоторое семантическое действие, которое выполняется при замене основы для свертки на это правило.