ВУЗ:
Составители:
37
Это можно сделать в виде таблицы, строки которой помечены нетерми-
нальными символами грамматики, столбцы – терминальными. Значение каждо-
го элемента таблицы – это нетерминальный символ, к которому можно свер-
нуть пару «нетерминал-терминал», которыми помечены соответствующие
строка и столбец.
Например, для грамматики G = ({a, b, ⊥}, {S, A, B, C}, P, S), где:
P: S → C⊥
C → Ab | Ba
A → a | Ca
B → b | Cb
такая таблица будет выглядеть следующим образом:
a b
⊥
C
A B S
A
- C -
B
C - -
S
- - -
Прочерк ставится в том случае, если для пары «терминал-нетерминал»
«свертки» нет.
Чаще информацию о возможных свертках представляют в виде диаграммы
состояний (ДС) – неупорядоченного ориентированного помеченного графа, ко-
торый строится следующим образом:
1. строят вершины графа, помеченные нетерминалами грамматики (для каж-
дого нетерминала – одну вершину), и еще одну вершину, помеченную
символом, отличным от нетерминальных (например, H). Эти вершины бу-
дем называть состояниями. H будет начальным состоянием.
2. соединяем эти состояния дугами по следующим правилам:
a) для каждого правила грамматики вида W → t соединяем дугой состоя-
ния H и W (от H к W) и помечаем дугу символом t;
б) для каждого правила вида W → Vt соединяем дугой состояния V и W
(от V к W) и помечаем дугу символом t;
Диаграмма состояний для грамматики G:
a
a
b
b
b
⊥
a
S
C
A
B
H
Алгоритм разбора по диаграмме состояний
1. объявляем текущим состояние H;
2. затем многократно (до тех пор, пока не считаем признак конца цепочки)
выполняем следующие шаги: считываем очередной символ исходной
Страницы
- « первая
- ‹ предыдущая
- …
- 33
- 34
- 35
- 36
- 37
- …
- следующая ›
- последняя »
