Рис. 3. Дерево вывода для цепочки
a
+
b
+
a
в грамматике
G
A
Для КС-грамматик можно ввести
удобное графическое представление
вывода, называемое деревом вывода,
причем для всех эквивалентных вы-
водов деревья вывода совпадают.
Деревоназывается деревом выво-
да (или деревом разбора) (рис. 3) в
КС-грамматике
G
A
=
V
N
, V
T
, S, P
,
если выполнены следующие условия.
1. Каждая вершина дерева по-
мечена символом из множества
(
V
N
∪
V
T
∪
ε
), при это м ко рень де-
рева помечен символом
S
; листья —
символами из (
V
T
∪
ε
).
2. Если вершина дерева отмечена символом
A
∈
V
N
, а ее не-
посредственные потомки — символами
a
1
, a
2
, . . . , a
n
, где каждое
a
i
∈
(
V
T
∪
V
N
)
, то
A
→
a
1
a
2
. . . a
n
— правиловывода в этой грамматике.
3. Если вершина дерева отмечена символом
A
∈
V
N
, а ее един-
ственный непосредственный потомок помечен символом
ε
, то
A
→
ε
— правиловывода в этой грамматике.
Деревовывода (рис. 3) можностроить нисходящим либовосходя-
щим способами.
При нисходящем разборе дерево вывода формируется от корня к
листьям; на каждом шаге до вершины, отмеченной нетерминальным
символом, пытаются найти такое правило вывода, чтобы имеющиеся в
нем терминальные символы “проектировались” на символы исходной
цепочки.
Метод восходящего разбора заключается в том, что исходную це-
почку пытаются “свернуть” к начальному символу
S
; на каждо м ша-
ге ищут подцепочку, которая совпадает с правой частью какого-либо
правила вывода; если такую подцепочку находят, то ее заменяют не-
терминалом из левой части этого правила.
Если грамматика однозначная, то при любом способе построения
будет полученооднои тоже дереворазбора.
Дерево разбора, описывающее обобщенный сценарий атаки по-
средством стохастической грамматики, имеет следующий вид (рис. 2):
G
A
=
V
N
, V
T
, S, P ,
где
V
N
— множество терминальных символов, которые обозначают
шаги атаки нижнегоуровня,
V
N
=
{
I, E, M, I, . . . , E
2
, E
21
, E
22
, E
23
,
E
24
, E
25
, E
26
, . . .
}
;
V
T
— множество нетерминальных символов, ко-
торые ставятся в соответствие верхним и промежуточным уровням
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2006. № 4 99
