ВУЗ:
Составители:
3.2. Контекстно-свободные грамматики и языки
Кс-грамматике соответствует полутуэвская система, в которой
имеются терминальные и нетерминальные формулы. Вывод их можно
представить с помощью графа.
Пусть задана КС-грамматика
},,,{ RSVVG
ATm
=
, где }{AV
A
= , а правила
вывода R имеют вид: 1)
asaS →
; 2)
вsвS →
; 3)
cS →
. Гра грамматики показан
на рис. 3.1.
Рис. 3.1.
Вывод конкретной цепочки соответствует пути на графе, который начинается
в вершине S и заканчивается вершиной, помеченной данной цепочкой.
Например, слову аавсваа в грамматике G
m
соответствует вывод:
11
→→aSaS
аавсвааaaSвaaвaaSaa
321
→→→ . Поэтому можно записать аавсвааS
m
G
→ .
Аналогично
вввавасававS
m
G
→ . Ясно, что грамматика G порождает в точности те
слова языка (терминальные цепочки), которые построены по схеме
1−
хсх , где
х - любая цепочка из символов а, в, а х
-1
- ее обращение. Сокращенно это
можно записать так
}*},{|{)(
1
ваxxcxGLL
mm
∈==
−
.
Однако указанный способ представления выводов не отражает
синтаксической структуры выводимых цепочек. Более наглядно такая
структура представляется при изображении выводов в виде деревьев.
Принцип построения деревьев вывода проиллюстрируем на примере.
Пример 3.2. Пусть задана грамматика
},,,{
1
RSVVG
AT
=
, где
)}(,,,/,,*,,,{ +−= cвaV
T
, },,,,{ IFTESV
A
= , S - аксиома, правила вывода имеют вид:
s
asa
aasaa aвsвa
aсa ваsaв
ввsвв ввsвв
вsв
(1)
(1)
(2)
(3)
(3)
(2)
(3)
и так далее
(2)
(1)
с
и так далее
Страницы
- « первая
- ‹ предыдущая
- …
- 49
- 50
- 51
- 52
- 53
- …
- следующая ›
- последняя »
