Система составляющих

Классификация формальных грамматик

Множество формальных грамматик можно разложить на классы в зависимости от ограничений, накладываемых на продукции. Такие ограничения формируют особые свойства грамматик и особые методы анализа и синтеза цепочек символов. Общепринятой классификацией грамматик и порождаемых ими языков является иерархия грамматик Хомского, содержащая четыре типа грамматик.

Грамматика типа 0 - грамматика произвольного типа без каких-либо ограничений на цепочки символов. Продукции этой грамматики имеют вид:

a::= b. (11)

В обеих частях продукции могут быть в произвольном порядке и любом количестве терминальные и нетерминальные символы, т.е. a, b Î V*. Такой тип грамматики порождает множество перечислимых языков, для которых существует перечисляющий алгоритм. Такой алгоритм может быть реализован на машине Тьюринга, являющейся классической моделью рекурсивной функции. Поэтому такие языки называют также рекурсивно-перечислимыми. Однако такой тип грамматики не нашел применения в языках программирования.

Пример 6. Пусть дана грамматика G₁ = á V_T; V_N; P; J ñ, где

V_T = { a; b }; V_N = { A;B;C;J };

P = { р₁ : J::= AbBb; р₂ : Ab::= Bba;

р₃ : Bb::= Cba; р₄ : Cb::= ba }.

Какие цепочки терминальных символов формирует грамматика?

К цепочке символов AbBb, заданной начальным символом J, можно применить два правила (Ab::= Bba и Bb::= Cba) и организовать два вывода: левосторонний и правосторонний.

Левосторонний вывод:

J => AbBb => BbaBb => CbaaBb => baaaBb =>baaaCba => baaabaa;

Правосторонний вывод:

J => AbBb => AbCba => Abbaa => Bbabaa => Cbaabaa => baaabaa.

Грамматика G₁ вне зависимости от направления вывода формирует для заданной начальной цепочки AbBb единственную цепочку терминальных символов языка L(G₁):

L(G₁) = { ba³ba² }.

Пример 7. Пусть дана грамматика G₂ = á V_T; V_N; P; J ñ, где

V_T = { a; b }; V_N = { A;B;C;J };

P = { р₁ : J::= AbBb; р₂ : J::= AbJBb; р₃ : Ab::= Bba;

р₄ : Bb::= Cba; р₅: Cb::= ba }.

Какие цепочки терминальных символов формирует грамматика?

В этом пример добавлено одно правило J::= AbJBb,которое существенно расширяет множество выводимых терминальных цепочек языка L(G₂).Рассмотрим только левосторонний вывод:

J =>AbBb =>BbaBb =>CbaaBb =>baaaBb =>baaaCba = (ba³)(ba²);

J =>AbJBb => BbaJBb => CbaaJBb => baaaJBb =>baaaAbBbBb => baaaBbaBbBb => baaaCbaaBbBb => baaabaaaBbBb => baaabaaaCbaBb =>

baaabaaabaaBb => baaabaaabaaCba => baaabaaabaabaa = (ba³)²(ba²)²;

J =>AbJBb => BbaJBb => CbaaJBb => baaaJBb => baaaAbJBb => baaaBbaJBb =>...=> baaabaaabaaabaabaabaa = (ba³)³(ba²)³; и т.д.

Грамматика G₂ формирует множество цепочек, используя процедуру итерации:

L(G₂) = { (ba³)ⁱ (ba²)ⁱ | i = 1;2;3;... }.

Пример 8. Пусть дана грамматика G₃ = á V_T; V_N; P; J ñ, где

V_T = { a; b }; V_N = { A;J };

P = { р₁ : J::= JAa | b; р₂ : aA::= Aa; р₃ : bA::= ab }

Какие цепочки терминальных символов формирует грамматика?

Используем также левосторонний вывод терминальных цепочек:

J => b;

J => JAa => bAa => aba;

J => JAa => JAaAa => bAaAa => abaAa => abAaa => aabaa = a²ba²;

J => JAa => JAaAa =>JAaAaAa =>... => aaabaaa = a³ba³; и т.д.

Грамматика G₃ формирует множество цепочек, также используя процедуру итерации:

L(G₃) = { aⁱbaⁱ | i = 0;1;2;3;... }.

Грамматика типа 1. - это контекстно-зависимая грамматика или грамматика непосредственных составляющих (НС-грамматика). Второе название грамматики объясняется тем, что любую цепочку можно разложить на синтаксические составляющие (члены предложения естественного языка) и выполнить разбор каждой синтаксической переменной (части речи естественного языка) в составе синтаксической составляющей. В естественных языках для этого проводят грамматической разбор структуры предложения. В языках программирования - грамматический разбор структуры программы, что всегда необходимо при трансляции исходной программы на язык вычислительной машины.

Продукции этой грамматики имеют вид:

w1Aw2::= w1bw2, (12)

где AÎV_N;

w1, w2, bÎV*,

w1 - левый контекст,

w2 - правый контекст.

Каждый шаг вывода состоит в замене одного вхождения нетерминального символа вхождением цепочки терминальных и/или нетерминальных символов. Эта замена обусловлена наличием левого и правого контекстов.

Для НС-грамматики существенным является исполнение условия:

|w1Aw2| £ |w1bw2|, 13)

где |...| означает длину цепочки символов, заключенных между вертикальными линиями.

Это требует исполнения в каждом правиле второго условия:

b ¹ e. (14)

Грамматики, в которых все правила обладают этими свойствами называют неукорачивающими.

Множество языков НС-грамматики является собственным подмножеством языков грамматики типа 0.

Для НС-грамматики возможны случаи:

1) w1A::= w1b, когда w2 = e;

2) Aw2::= bw2, когда w1 = e.

Для НС-грамматик также допустим лево- и правосторонний вывод, когда продукции грамматики применяются к самому левому или самому правому нетерминальному символу анализируемой цепочки.

Пример 9. Пусть дана грамматика G₄ = á V_T; V_N; P; J ñ, где

V_T = { a; b }; V_N = { A;B;C;D;J };

P = { р₁ : J::= ABA; р₂ : B::= ABCA | b; р₃ : bC::= bb;

р₄ : AC::= DC; р₅ : DC::= DA; р₆ : DA::= CA; р₇: A::= a }.

Какие цепочки терминальных символов формирует грамматика?

Применим левосторонний вывод терминальной цепочки:

J Þ ABA Þ a B A Þ abA Þ aba;

ß

aABCAA Þ aa B CAA Þ aabCAA Þ aabbAA Þ

ß ß

aaABCACAA aabbaA

ß ß

aaaBCACAA Þ aaabCACAA aabbaa = a²b²a²;

ß ß

aaaABCACACAA aaabbACAA

ß ß

.... aaabbDCAA

ß aaabbDAAA

ß

aaabbCAAA

ß

aaabbbAAA

ß

aaabbbaAA

ß

aaabbbaaA

ß

aaabbbaaa = a³b³a³

Грамматика G₄ формирует цепочки терминальных символов:

L(G₄) = { aⁱbⁱaⁱ| i= 1;2;3;... }.

Пример 10. Пусть дана грамматика G₅ = á V_T; V_N; P; J ñ, где

V_T = { a; b; c}; V_N = {B; C; J };

P = { р₁ : J::= aJBC | aBC; р₂ : CB::= DB;

р₃: DB::= DC; р₄: DC;;= BC; р₁₅: aB::= ab;

р₆ : bB::= bb; р₇ : bC::= bc; р₈ : cC::= cc }.

Какие цепочки терминальных символов формирует грамматика?

В каждом правиле есть либо левый, либо правый контексты.

Используем также левосторонний вывод терминальных цепочек:

J => aBC => abC => abc;

J => aJBC => aaBCBC => aabCBC =aabDBC => aabDCC => aabBCC => aabbCC => aabbcC => aabbcc = a²b²c²;

J => aJBC => aaJBCBC =>... => aaabbbccc = a³b³c³ и т.д.

Грамматика G₅ формирует цепочки терминальных символов, используя операцию итерации:

L(G₅) = { aⁱbⁱcⁱ | i = 1;2;3;... }.

Если сравнить результаты использования грамматик G₄ и G₅, то можно отметить одинаковость порождаемых ими цепочек. Это позволяет ввести отношение эквиваленции на множестве грамматик.

Грамматика типа 2 - это контекстно-свободная грамматика (КС-грамматика). Правила этой грамматики не зависят от контекста, т.е. в левой части каждого правила находится только один нетерминальный символ, а в правой части цепочка терминальных и/или нетерминальных символов.

Продукции этой грамматики имеют вид:

A::= b, (15)

где b Î V*

Каждый шаг вывода связан с заменой в цепочке одного нетерминального символа на цепочку терминальных и/или нетерминальных символов.

Множество КС-языков при выполнении условий w1 = e, w2 = e и b ¹ e является подмножеством НС-языков.

КС-грамматики наиболее эффективно описывают состав и структуру формального языка. Поэтому они нашли применение в большинстве языков программирования. Для унификации языков программирования были разработаны метаязыковые средства описания синтаксических конструкций. Особое место среди этих средств занимают формулы Бэкуса-Наура (БНФ). Основные правила и условные обозначения приведены в 1.

Для КС-грамматик также удобен фиксированный способ вывода (лево- или правосторонний).

Пример 11. Пусть дана грамматика G₆ = á V_T; V_N; P; J ñ,

где V_T = { буква; цифра}; V_N = {A; B; J };

P = { р₁ : J::= JA | JB | A;

р₂ : A::= буква;

р₃ : B::= цифра }.

Какие цепочки терминальных символов формирует грамматики?

Для удобства доказательства сохраним левосторонний вывод:

J => A => буква;

J => JA => AA => буква буква;

J => JB => AB => буква цифра;

J => JA => JAA => AAA =>... => буква буква буква;

J => JA => JBA => ABA =>... => буква цифра буква;

J => JB => JAB => AAB =>...=> буква буква цифра;

J => JB => JBB => ABB =>...=> буква цифра цифра и т.д.

Грамматика G₆ формирует следующие цепочки терминальных символов:

L(G₆) = { буква { буква | цифра } }.

Такова грамматика для формирования идентификаторов большинства языков программирования.

Пример 12. Пусть дана грамматика G₇ = á V_T; V_N; P; J ñ,

где V_T = { a; b }; V_N = { J };

P = { р₁ : J::= aJb | ab }.

Какие цепочки терминальных символов формирует грамматика?

Сохраним левосторонний вывод:

J => ab;

J => aJb =>aabb = a²b²;

J => aaJbb => aaabbb = a³b³ и т.д.

Грамматика G₇ формирует цепочки терминальных символов, используя операцию итерации:

L(G₇) = { aⁱbⁱ| i= 1;2;3;... }.

Пример 13. Пусть дана грамматика G₈ = á V_T; V_N; P; J ñ,

где V_T = { x; y; &; Ú;`ù; (;) }; V_N = { J };

P = { J::= (J & J) | (J Ú J) | `ù J | x | y }.

Какие цепочки терминальных символов формирует грамматика?

Используя приемы лево - или правостороннего вывода, получим цепочки терминальных символов

J =>`ù J => `ù x; J =>`ù J => `ù y;

J => (J Ú J) =>... => (x Ú y); J => (JÚ J) =>... => (`ù x Ú`ù y);

J => (J & J) =>... => (x & y); J => (J & J) =>...=> (`ù x & `ù y);

ù J => ù (J Ú J) =>.. =>`ù (x Ú y);

ù J => ù (J & J) =>... =>`ù (x & y) и т.д.

Грамматика G₈ представляет любые формулы булевой алгебры,т.е.

L(G₈) ={ x; y;`ù x; ù y; (x Ú y); (ù x Ú`ù y); (x & y);`ù (x Ú y); ù (x & y);...}.

Пример 14. Пусть дана грамматика G₉ = á V_T; V_N; P; J ñ,

где V_T = { a; b;+;-;´;/; (;) }; V_N = { J; T; M; S1;S2;S3;K };

P = {p1: J::= T | J S1 T; p2: T::= M | TS2M; p3: M::= K |S31J S32;

p4: S1::= "+" | "-"; p5: S2::= "´" | "/"; p61: S31::= "(";

р62: S32::= ")"; p7: K::= " a " | " b" }.

Примечание: все правила индексированы для нужд параграфа 9.

Какие цепочки терминальных символов формирует грамматика?

Применим левосторонний вывод терминальной цепочки:

J => T => M => K => a; J => T => M => K => b;

J => J S1T =>T S1T =>MS1T =>KS1T => a S1T => a + T => a + M => a + K => a + b;

J => T => TS2M => MS2M => KS2M => a S2M => a ´ M => a ´ K => a ´ b;

J => T => M => S31 JS2 => (J S32 => (JS1TS32 =>(TS1TS32=>(TS2 MS1T S32 => (MS2 MS1T S32=> (KS2 MS1T S32=> (a S2 MS1T S32 =>(a / MS1TS32=> (a / K S1T S32 =>(a / a S1TS32=>(a / a -TS32=>(a / a -MS32 =>(a / a - KS32 => (a / a - b S32 => (a / a - b);

J =>...

Грамматика G₉ представляет любые арифметические выражения, т.е. L(G₉) = { a; b; a + b; a - b; a ´ b; a / b;... }.

Грамматика типа 3 - это линейная грамматика, правила которой содержат в правой части не более одного нетерминального символа.

Продукции этой грамматики имеют вид:

A::= w1Bw2 или A::= w, (16)

где w1, w2, wÎV*\V_N.

Продукция линейной грамматики называется праволинейной (леволинейной), если единственный нетерминальный символ в правой части продукции всегда находится крайним справа (слева).

Например, А::= w1B - праволинейная продукция,

A::= Bw2 - леволинейная продукция.

Если все продукции грамматики праволинейные или леволинейные, то грамматика также называется праволинейной или леволинейной. Каждой праволинейной грамматике соответствует эквивалентная ей леволинейная грамматика. В зависимости от типа грамматики различают праволинейные и леволинейные языки.

Языки линейной грамматики представляют собственное подмножество множества КС-языков.

Cуществует тесная связь между линейными грамматиками и конечными автоматами. Каждому состоянию конечного автомата соответствует нетерминальный символ линейной грамматики, а каждому символу входного алфавита конечного автомата - терминальный символ линейной грамматики. Каждой незаключительной продукции вида A::= w1Bw2 соответствует переход автомата из одного состояния в другое, а каждой заключительной продукции вида A::= w - окончание работы. Цепочка терминальных символов на входе автомата считывается посимвольно и последовательно переводит его в заключительное состояние. В связи с этим используют и другое название линейной грамматики - автоматная грамматика.

Автоматную грамматику называют регулярной, если она удовлетворяет условиям функционирования детерминированного конечного автомата:

1) из каждой вершины графа для каждого терминального символа исходит только одна дуга (условие однозначности);

2) из каждой вершины графа исходит количество дуг равное числу символов входного алфавита (условие полноты);

3) каждая вершина графа достижима из начальной вершины (условие связности).

Пример 15. Пусть дана грамматика G₁₀ = á V_T; V_N; P; J ñ

где V_T = {a; b; c }; V_N = { A; B; J; };

P = { р₁ : J::= Bb; р₂ : A::= Aa | a; р₃ : B::= Bb | Aac | ac }.

Какие цепочки терминальных символов формирует грамматика?

Можно отметить, что все правила этой грамматики -леволинейные. Проведем левосторонний вывод терминальных цепочек:

J Þ Bb Þ acb

ß Þ Aacb Þ aacb

acbb Ü Bbb ß

ß ß ß Þ Þ Þ

ß ß ß ß

aacbb Ü Aacbb ß Aaacb Þ aaacb

ß ß ß

aaacbb Ü Aaacb ß...

ß Bbbb Þ acbbb

... ß

...

Грамматика G₁₀ формирует цепочки вида:

L(G₁₀) = { aⁱcb^j | i,j = 1;2;3;... }.

Пример 16. Пусть дана грамматика G₁₁ = á V_T; V_N; P; J ñ,

где V_T = {a; b; c }; V_N = { A; B; J; };

P = { р₁ : J::= aA | acB; р₂ : A::= aA | acB; р₃ : B::=b | bB }.

Какие цепочки терминальных символов формирует грамматика?

Все правила этой грамматики -праволинейные. Поэтому удобно выполнить правосторонний вывод терминальных цепочек:

J Þ acB Þ acb

ß ß

aacb Ü aacB Ü aA acbB Þ acbb

ß ß ß

acbb Ü aacbB ß acbbB Þ acbbb

ß ß ß

aacbbb Ü aacbbB ß...

ß ß Þ aaA Þ...

... ß

...

Грамматика G₁₁ формирует цепочки вида:

L(G₁₁) = { aⁱcb^j | i,j = 1;2;3;... }.

Сравнение результатов в примерах 15 и 16 показывает, что грамматики G₁₀ и G₁₁ формируют один и тот же язык. Следовательно, леволинейная грамматика G₁₀ эквивалентна праволинейной грамматике G₁₁.

Пример 17. Пусть дана грамматика G₁₂ = á V_T; V_N; P; J ñ,

где V_T = {a; b; c }; V_N = { A; B; J; };

P = { р₁ : J::= aA; р₂ : A::= aA |cB; р₃ : B::= b | bB }.

Какие цепочки терминальных символов формирует грамматика?

В данном примере правила также праволинейные. Применим правосторонний вывод:

J Þ aA Þ acB Þ acb

ß ß

aacb Ü aacBÜ aaA acbB Þ acbb

ß ß ß

aacbb Ü aacbB ß acbbB Þ acbbb

ß ß ß

aacbbb Ü aacbbB ß...

ß ß Þ aaaA Þ aaacB Þ aaacb

... ß ß

......

Грамматика G₁₂ формирует цепочки вида:

L(G₁₂) = { aⁱcb^j | i,j = 1;2;3;... }.

Сравнение результатов в примерах 16 и 17 показывает, что грамматики G₁₁ и G₁₂ являются праволинейными и формируют один и тот же язык. Это свидетельствует об эквивалентности грамматик G₁₁ иG₁₂.

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

Для удобства введем условные обозначения синтаксических переменных и лексем на примере подмножества правил языка Паскаль:

синтаксические переменные:лексемы:

<программа>:= J; "PROGRAM":= a1;

<заголовок-программы>:= A1: "ALGEBRA":= a2;

<идентификатор-программы>:= A2; "BEGIN":= a3;

<идентификатор-переменной>:= A3: "END":= a4;

<блок>:= B1; "I":= a5;

<раздел-операторов>:= B2; (17)

<оператор>:= B3; ":=":= b1;

<оператор-присваивания>:= B4; "+":= b2;

<переменная>:= C1; "-":= b3;

<выражение>:= C2; "x":= b4;

<терм>:= C3; "/":= b5;

<множитель>:= C4; ";":= c1;

<операция-сложения>:= D1; ".":= c2.

<операция-умножения>:= D2;

Тогда подмножество правил языка Паскаль и значений синтаксических переменных, приведенное в примере 3, может быть записано так:

J::=A1с1B1с2; C1::= A3;

A1::=a1A2; С2::= C3D1C3;

A2::=a2; C3::= C4D2C4;

A3::=I; C4::= C1; (18)

В1::=В2; D1::= b2 | b3;

B2::=a3B3a4; D2::= b4 |b5;

B3::=B4 |...;

B4::=C1b1C2.

Последовательность вывода cинтаксически правильных цепочек от начального символа J имеет вид:

J => A1c1B1c2 => a1A2c1B1c2 => a1a2c1B1c2 => a1a2c1B2c2 => a1a2c1a3B3a4c2 => a1a2c1a3B4a4c2 => a1a2c1a3C1b1C2a4c2 => a1a2c1a3A3b1C2a4c2 => a1a2c1a3ib1C2a4c2 =>...

Вывод остановлен на синтаксической переменной С2, как в примере 4.

Последовательность вывода синтаксически правильных цепочек от начального символа С2 имеет вид:

C2 => C3D1C3 => C4D2C4D1C3 => C1D2C4D1C3 => A3D2C4D1C3 =>iD2C4D1C3 => ib4C4D1C3 => ib4C1D1C3 => ib4A3D1C3 => ib4iD1C3 =>ib4ib2C3 => ib4ib2C4D2C4 => ib4ib2C1D2C4 => ib4ib2A3D2C4 => ib4ib2iD2C4 => ib4ib2ib4C4 => ib4ib2ib4C1 => ib4ib2ib4A3 => ib4ib2ib4i.

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

Следует обратить внимание, что на каждом шаге вывода длина цепочки символов увеличивается. Это свойственно большинству формальных грамматик.

Длина цепочки равна числу символов в ней. Для a:= e имеем |a| = 0,

Для a:= a1a2c1a3ib1C2a4c2 имеем |a | = 9.

Если w1 и w2 -цепочки, то a = w1w2 также является цепочкой. Приписывание цепочки w2 справа к цепочке w1 называют конкатенацией.

Например,

если w1 = a1a2c1a3ib1 и w2 = C2a4c2,

то a =w1w2 = a1a2c1a3ib1C2a4c2 = J.

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

a = e a = a e = a. (19)

Если цепочка a состоит из нескольких символов, то в ней всегда можно выделить "голову" и "хвост" цепочки.

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

{a1...; a1a2...; a1a2c1...;... }. (20)

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

{...c2;...a4c2;...C2a4c2;... }. (21)

"Голова" называется правильной, если "хвост" - не пустая цепочка.

"Хвост" называется правильным, если "голова" - не пустая цепочка.

Выделение "головы" и "хвоста" цепочки обусловлены задачами экономии памяти компьютера и ускоренного синтаксического разбора текста программы при трансляции, когда оказывается удобным показать только "голову"(a = w1...) или только "хвост" (a =... w2) цепочки.

Если цепочка w1bw2 выводима из цепочки w1aw2 c помощью одного правила Р_i : a::= b, то этот вывод записывают так:

w1aw2 => w1bw2 (22)

Если цепочка w1bw2 выводима из цепочки w1aw2 c помощью нескольких правил ai::= bi при условии a1 = a, a2 = b1, a3 => b2,,...an => b, то этот вывод записывают так:

w1aw2 => w1b1w2 => w1b2w2 =>... => w1bw (23)

Если даны две цепочки a и w и вторая цепочка входит составной частью в первую, то это вхождение может быть описано так:

в круглых скобках на первом месте указывают имя второй цепочки, а на втором месте -номер символа первой цепочки, совпадающий с первым символом "головы" второй цепочки, т.е. (w, i).

Если таких вхождений цепочки w несколько, то формируется система составляющих первой цепочки вида:

Ca = { (w; i); (w; j); (w; k);...}. (24)

Например, СС2 = { (i,1);(i,3);(i,5);(i,7)}.

Если дана цепочка a, которую можно разложить на синтаксически оформленные подцепочки w1;w2;w3;..., то система составляющих может быть записана так:

Ca= { (w1, i); (w2, j); (w3, k);... }. (25)

Например, CJ = { (i,5);(C2,7) }.

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

Например, система составляющих СС2 вложена в составляющую системы СJ.

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

Дата добавления: 2015-06-27