Грамматики с ограничениями на правила

Некоторые свойства грамматик.

Понятие выводимости

Примеры грамматик

Грамматика, порождающая язык {0ⁿ1ⁿ | n≥0} имеет вид: G₀= ({0,1}, {S}, S, P)

T N S P

где P = {S→0S1, S→ε}.

Грамматика, порождающая язык {a^mbⁿ | m,n ≥ 0} имеет вид: G₁= ({a,b}, {S,A,B}, S, P)

T N S P

где набор правил определяется следующим образом:

P = {S→AB, A→aA, A→ε, B→bB, B→ε}

Отношение Þ_G непосредственного вывода на множестве (T È N)* – j Þ_G y означает, что y непосредственно выводима из j для грамматики G = (T, N, P, S), т. е, если abg – цепочка из множества (T È N)* и b ® d – правило из Р, то abg Þ_G adg

Транзитивное замыкание отношения Þ_G⁺ (нетривиальный вывод за один и более шагов) — j Þ_G⁺ y означает, что y выводима из j нетривиальным образом (возможно за несколько шагов).

Рефлексивное и транзитивное замыканиеотношения Þ_G^* (вывод за нуль и более шагов) — j Þ_G^* y означает, что y выводима из j.

Пусть Þ^k k-я степень отношения Þ, тогда, если a Þ^k b, то существует последовательность a₀a₁a₂a₃ ... a_k из к+1 цепочек:

a = a₀, a₁,... a_{i -1} Þ a_i,, 1 ≤ i ≤ k и a_k = b

Выводы для грамматики G1 = ({0, 1}, {A, S}, S, P):

Т N S P

S Þ 0A1 Þ 00A11 Þ 0011 — S порождает...

S Þ¹ 0A1; S Þ² 00A11; S Þ³ 0011 – i -тая степень отношения

S Þ⁺ 0A1; S Þ⁺ 00A11; S Þ⁺ 0011 – транзитивное замыкание отношения

S Þ^* S; S Þ^* 0A1; S Þ^* 00A11; S Þ^* 0011 – рефлексивное и транзитивное замыкание отношения

где 0011 Ì L(G1) – принадлежит языку L грамматики G1

Эквивалентность грамматик – это, когда различные грамматики порождают один и тот же язык, т. е. грамматики G1 и G2 будут эквивалентными, если L(G1) = L(G2).

Например, G1 = ({0,1}, {A,S}, S, P1) и G2 = ({0,1}, {S}, S, P2)

где P1: S → 0A1

P2: S → 0S1 | 01 (| – знак или)

0A → 00A1

A → ε

эквивалентны, т. к. обе порождают язык L(G1) = L(G2) = {0ⁿ1ⁿ | n>0}

Несмотря на эквивалентность определяемых языков, одна грамматика может быть значительно удобнее другой, с точки зрения ее использования в компиляторе.

Определение грамматик не накладывает никаких ограничений на количество нетерминалов в левой части правил:

Грамматика G=({a,b,c},{S,B,C},S,P), где P содержит следующие правила:

P = {S→aSBC, S→abC, CB→BC, bB→bb, bC→bc, cC→cc}

порождает язык {aⁿbⁿcⁿ, n≥1} (n>0)

В грамматике G=({0,1},{А,S},S,P), где P = {S → 0A, 0A → 00A1, S → ε} — левая часть одного из правил содержит пару из терминального и нетерминального символа.

Эквивалентная ей грамматика G1 = ({0,1}, {A,S}, S, P1), где

P1: S → 0A1

0A → 00A1

A → ε

Соглашение – альтернатива правила вывода из цепочки: для записи правил вывода с одинаковыми левыми частями α → β₁ α → β₂... α → β_n пользуются сокращенной записью через операцию или: α → β₁ | β₂ |...| β_n; каждое β_i (i= 1, 2,..., n) называется альтернативой правила вывода из цепочки α.

Несмотря на большое разнообразие грамматик, при построении трансляторов применяются только некоторые из них, имеющие ограничения, что связано с практической целесообразностью использования определенных типов правил, так как сложность их построения непосредственно влияет на сложность построения трансляторов. По виду правил выделяют несколько классов грамматик.

Дата добавления: 2014-01-11