Системное программное обеспечение: Основы трансляции. Карпушин А.Н - 5 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

7
Цепочка β ∈ (VT ∪ VN)
*
непосредственно выводима из цепочки α ∈ (VT
∪ VN)
+
в грамматике G = (VT, VN, P, S) (обозначим α → β), если α = ξ
1
γξ
2
,
β = ξ
1
δξ
2
, где ξ
1
, ξ
2
, δ ∈ (VT ∪ VN)
*
, γ ∈ (VT ∪ VN)
+
и правило вывода
γ → δ содержится в P. Например, цепочка 00A11 непосредственно выводима из
0A1 в грамматике G1.
Цепочка β ∈ (VT ∪ VN)
*
выводима из цепочки α ∈ (VT ∪ VN)
+
в грам-
матике G = (VT, VN, P, S) (обозначим α ⇒ β), если существуют цепочки
γ
0
, γ
1
, ... , γ
n
(n>=0), такие, что α = γ
0
→ γ
1
→ ... → γ
n
= β.
Последовательность γ
0
, γ
1
, ... , γ
n
называется выводом длины n. Напри-
мер, S ⇒ 000A111 в грамматике G1 (см. пример выше), т.к. существует вывод
S → 0A1 → 00A11 → 000A111. Длина вывода равна 3.
Языком, порождаемым грамматикой G = (VT, VN, P, S), называется мно-
жество L(G)={α ∈ VT
*
| S ⇒ α}. Иначе, L(G) – это все цепочки в алфавите
VT, которые выводимы из S с помощью P. Например, L(G1) = {0
n
1
n
| n>0}.
Цепочка α ∈ (VT ∪ VN)
*
, для которой S ⇒ α, называется сентенциаль-
ной формой в грамматике G = (VT, VN, P, S). Таким образом, язык, порождае-
мый грамматикой, можно определить как множество терминальных сентенци-
альных форм.
Грамматики G1 и G2 называются эквивалентными, если L(G1) = L(G2).
Например, G1 = ({0,1}, {A,S}, P1, S) и G2 = ({0,1}, {S}, P2, S), где:
P1: S → 0A1 P2: S → 0S1 | 01
0A → 00A1
A → λ
эквивалентны, т.к. обе порождают язык: L(G1) = L(G2) = {0
n
1
n
| n>0}.
Грамматики G1 и G2 почти эквивалентны, если L(G1)∪{λ} = L(G2)∪{λ}.
Другими словами, грамматики почти эквивалентны, если языки, ими порож-
даемые, отличаются не более чем на λ.
Например, G1 = ({0,1}, {A,S}, P1, S) и G2 = ({0,1}, {S}, P2, S), где:
P1: S → 0A1 P2: S → 0S1 | λ
0A → 00A1
A → λ
почти эквивалентны, т.к. L(G1)={0
n
1
n
| n>0}, а L(G2)={0
n
1
n
| n>=0}, т.е.
L(G2) состоит из всех цепочек языка L(G1) и пустой цепочки, которая в L(G1)
не входит.
Способы задания схем грамматик
Схема грамматики содержит правила вывода, определяющие синтаксис
языка, или, другими словами, структуру цепочек порождаемого языка. Для за-
дания правил используются различные формы описания: символическая, форма
Бэкуса-Наура, итерационная форма и синтаксические диаграммы.
При рассмотрении общих свойств грамматик обычно применяют символи-
ческую форму задания правил. В практических применениях вместо символи-

Страницы