I.11. Классификация грамматик

Языки для компиляторов разделяются на простые и сложные. Для этого используются жесткие критерии. От того, к какому типу относится язык программирования зависит сложность компилятора для него. Чем сложнее язык, тем большие вычислительные ресурсы требует компилятор на анализ цепочек исходной программы, написанной на этом языке, тем сложнее сам компилятор. Для некоторых типов языков в принципе невозможно построить компилятор, который бы анализировал исходные тексты за определенное время. Если все без исключения правила грамматики удовлетворяют некоторой заданной структуре, то такую грамматику относят к определенному типу. Если хотя бы 1 правило не удовлетворяет этим требованиям, она не попадает в заданный тип. Выделяют 4 типа грамматики: первый тип 0 – это грамматика с фразовой структурой. На структуру этих правил не накладывается никаких ограничений.

Для грамматики G(VT,VN,P,S), V= VN∪VT правила имею следующий вид:

α → β, где α ∈V⁺, β ∈V^*.

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

Тип 1 - контекстно-зависимые (КЗ) и неукорачивающие (Н) грамматики.

КЗ гр. G(VT,VN,P,S), V= VN∪VT

имеют правила вида

α₁Aα ₂→ α₁ β α₂

α₁,α₂ ∈V^*, A∈VN,β ∈V⁺

Н. гр. G(VT,VN,P,S), V= VN∪VT

правила имеют вид

α→ β,где α,β ∈V⁺, | β | | α |

Структура правил КЗ гр. такова, что при построении предложений заданного ими языка один и тот же терминальный символ может быть заменен на одну и ту же цепочку символов, в зависимости от того, в каком контексте он встречается. Цепочки α₁ и α₂ в правилах грамматики обозначают контекст, α₁ – левый, α₂ – правый. В общем случае любая из них или обе может быть пустой, т.е. значение одного и того же символа может быть различным в зависимости от того, в каком контексте он встречается.

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

Тип 2 – КС гр. (контекстно-свободные)

КС гр. G(VT,VN,P,S), V= VN∪VT имеют правила вида

A→B, где A∈VN, B ∪ V⁺

Такие грамматики иногда называют НКС. У них в правой части всегда должен стоять как минимум 1 символ. Существует так же почти эквивалентный им класс грамматик – УКС (укорачивающие)

G(VT,VN,P,S), V= VN∪VT,

правила которых имеют вид

A→B, где A∈VN, B ∪ V^*

Разница между НКС и УКС в том, что у УКС в грамматике в правой части правил может присутствовать пустая цепочка λ, а в НКС грамматиках нет. НКС и УКС эквивалентны. КС широко используются при описании синтаксических конструкций я.п.

Тип 3 – это регулярные грамматики. К этому типу относятся два эквивалентных класса грамматик (леволинейные и праволинейные).

Леволинейные грамматики G(VT,VN,P,S), V= VN∪VT могут иметь правила двух видов

A→γ или A→Bγ,

где A,B∈VN, γ ∈VT^*

Праволинейные грамматики G(VT,VN,P,S), V= VN∪VT имеют правила тоже двух видов

A→γ β или A→γ,

где A,B∈VN, γ ∈VT^*

Эти два класса грамматики эквивалентны. Регулярные грамматики используются для конструкций простейших я.п.: идентификаторов, констант, строк, комментариев и т.д.

 

I.12. Классификация языков

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

L может быть задан G1 и G2, относящиеся типу 1, G3(тип 2),G4(тип 3), то сам язык должен относиться к типу 3 и являться регулярным.

Тип 0 - язык с фразовой структурой. Это самые сложные языки, которые могут быть заданы только грамматикой типом 0.

Тип 1 – КС язык. Время на распознавания языка этого типа зависит от цепочки символов. Применяется в анализе и переводе текстов в естественных языках. В компиляторах этот язык не используется.

Тип 2 – КС (контекстно-свободные языки). Это основа синтаксических конструкций я.п. На их основе так же функционируют сложные командные процессы. Среди многочисленных классов существуют языки, которые распознавание предложений используют линейные зависимости, что упрощает структуру компилятора.

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

 

I.13. Примеры классификаций языков и грамматик

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

Пример 1

G₁({0,1,2,3,…,9,-,+},{S,T,F},P₁,S)

правила

P₁:

S→T|+T|-T

T→F | TF

F→0|…8|9

По структуре своих правил относится к КС гр. (тип2). Ее можно отнести и к типу 0, и к типу, но максимальным возможным является тип 2. К типу 3 нельзя отнести

T→F | TF T→ TF

(нельзя допустить для типа 3)

Для того же самого языка можно построить и др. грамматику.

G₁’({0,1,2,3,…,9,-,+}, {S,T,F},Р₁’, S)

P₁’

S→T|+T|-T

T→ 0|1|…9| от |1T|…|8T|9T

По структуре своих правил является праволинейной и может быть отнесена к регулярным грамматикам (тип 3). Можно построить эквивалентную леволинейную грамматику (тип 3)

G₁’’({0,1,2,3,…,9,-,+}, {S,T,F},Р₁’’, S)

Р₁’’

T→+ | - | λ

S→T0|T1|…T9|S0|S1|…S8|S9

Следовательно язык L₁, заданный грамматиками G₁,G₁’,G₁’’, относится к регулярным языкам (тип 3)

Пример 2

G₂({0,1},{A,S},P₂,S)

P₂:

S→0A1

0A→00A

A→ λ

Относится к типу 0, определяет язык множества предложения, которое может быть записано

L(G₂)={0_n1_n| n 0}

Для этого языка можно построить так же КЗ гр.

G₂ ’({0,1},{A,S},P₂’,S)

P₂’:

S→0A1|01

0A→00A1|001

G₂’’ ({0,1},{ S},P₂’’,S)

P₂’’

S→0S1|01

L2={0n1n| n>0}

КС (тип 2)

Пример 3

G3({a,b,c},{B,C,D,S},P3,S)

P3

S → BD

B → aBbC | ab

Cb → bC

CD → Dc

bDc → bcc

abD → abc

L(G3) = {anbncn| n>0}

Эта грамматика относится к типу 1 и является неукорачивающей. Она определяет язык множества предложений, который может быть записан L(G3) = {anbncn| n>0}. Этот язык не является КС языком, поэтому для него нельзя построить грамматику типа 2 и 3. Но для того же самого языка можно построить КЗ гр.

 

G’3({a,b,c,},{B,C,D,E,F,S},P3’,S)

P3’

S→abc |AE

A→aABC|aBC

CBC→CDC

CDC→BDC

BDC→BCC

CCE→CFE

CFE→CFc

CFc→CEc

aB→ab

bB→bb

BCE→bCc

bCc→be

L3={anbncn| n>0}

Этот язык является КЗ языком (тип 1)

 

I.14. Цепочки вывода

I.14.1. Понятие о выводе

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

β = δ₁ γ δ₂ – называется непосредственно выводимой из цепочки

α = δ₁ ω δ₂

из грамматики G(VT,VN,P,S), V=VT ∪ VN, δ₁,υ, δ₂ ∈ V^* > ω ∈ V⁺

в ней существует правило

ω → υ ∈ P

Непосредственная выводимость цепочки β из цепочки α обозначается

α ⇒β

При выводе выполняется подстановка по цепочке γ вместо подцепочки ω, β –выводима из цепочки α в том случае, если можно взять несколько символов в цепочке α, заменить их на другие символы, согласно некоторому правилу грамматики и получить цепочку β. При непосредственной выводимости любая из цепочек δ₁, δ₂ может быть пустой или обе могут быть пустыми. В предельном случае цепочка α может быть заменена на цепочку β, тогда в грамматике G должно существовать правило

α ⇒β ∈ P

Цепочка β называется выводимой из цепочки α (α ⇒^*β) в том случае, если выполняется одно из двух условий:

1. β – непосредственно выводимая из α (α ⇒β)

2. γ - непосредственно выводимая из β (γ ⇒β)

∃ γ такая, что γ, выводимая из α и β, - непосредственно выводимая

γ ⇒α

β ⇒^*γ

Суть в том, что β выводимая из цепочки α (α ⇒β) или если можно построить последующие непосредственные цепочки из α ⇒β

В этой последовательности каждая последующая цепочка υ_i непосредственно выводима из предыдущей цепочки υ_i-1 .

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

α ⇒ +β

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

α ⇒⁴ β (цепочка β выводится из цепочки α за 4 шага вывода)

Пример

G({0,1,…,9,-,+},{S,T,F},P,S)

P:

S→ |+T|-T

T→F | TF

F→0|…|9

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

1) S⇒-T⇒-TF⇒-TFF⇒-FFF⇒-4FF⇒-47F⇒-479

2) S⇒T⇒TF⇒T8⇒F8 ⇒18

3) T⇒TF⇒T0⇒TF0⇒T50⇒F50⇒350

4) TFT⇒TFFT⇒TFFF⇒FFFF⇒1FFF⇒1FF4⇒-10F4 ⇒1004

5) F ⇒5

Результат

1) S ⇒^* 479 или S ⇒ + - 479 или S ⇒⁷ -479

2) S ⇒^* 18 или S ⇒+18 или S ⇒⁵18

3) T ⇒^* 350 или T ⇒ -250 или T ⇒⁶ 350

4) T ⇒^* 1004 или TFT ⇒+1004 или TFT ⇒⁷ 1004

5) F ⇒^* 5 или F 15

Выводы построены на основе грамматики G. Можно построить сколько угодно цепочек вывода.

Пример 2

G3(a,b,c),{B,C,D,S},P3}

P3

B→ aBbC|ab

Cb→bC

CD→Dc

bDc→bcc

abD→abc

L(G3)={anbncn| n>0}

aaaabbbbcccc

 

S ⇒BD ⇒ aBbCD ⇒aaBbCbCD ⇒ aaaBbCbCbCD ⇒aaaabbCbCbCD⇒ aaaabbbCCbCD ⇒

⇒aaaabbbCbCCD ⇒ aaaabbbbCCCD ⇒aaaabbbbCCDc ⇒ aaaabbbbCDcc ⇒ aaaabbbbDccc ⇒

⇒ aaaabbbbcccc

Тогда для грамматики G3 получили вывод

S⇒^* aaaabbbbcccc