ВУЗ:
Составители:
10
В качестве примера рассмотрим грамматику G3 с начальным символом S:
G3: ({ x, +, (, ) }, {<A>, <B>, <C>}, P = { A → x | (B), B → AC, C → {+A}* }, S).
Синтаксические диаграммы для такой грамматики имеют вид:
B
a)
х
(
)
A
b)
C
c)
A
+
Заменяя нетерминальные символы, соответствующими диаграммами, по-
лучаем объединенную диаграмму в виде:
A
х
(
)
A
+
Классификация грамматик и языков по Хомскому
В данной классификации грамматики классифицируются по виду их пра-
вил вывода.
ТИП 0:
Грамматика G = (VT, VN, P, S) называется грамматикой типа 0, если на пра-
вила вывода не накладывается никаких ограничений.
ТИП 1:
Грамматика G = (VT, VN, P, S) называется неукорачивающей, если каждое пра-
вило из P имеет вид: α → β, где α ∈ (VT ∪ VN)
+
, β ∈ (VT ∪ VN)
+
и | α | ≤ | β |.
Грамматика G = (VT, VN, P, S) называется контекстно-зависимой (КЗ), если
каждое правило из P имеет вид: α → β, где α = ξ
1
Aξ
2
; β = ξ
1
γξ
2
; A ∈ VN;
γ ∈ (VT ∪ VN)
+
; ξ
1
,ξ
2
∈ (VT ∪ VN)
*
.
Грамматику типа 1 можно определить как неукорачивающую либо как
контекстно-зависимую. Выбор определения не влияет на множество языков,
порождаемых грамматиками этого класса, поскольку доказано, что множество
языков, порождаемых неукорачивающими грамматиками, совпадает с множе-
ством языков, порождаемых КЗ-грамматиками.
Страницы
- « первая
- ‹ предыдущая
- …
- 6
- 7
- 8
- 9
- 10
- …
- следующая ›
- последняя »
