Компиляторы. Формальные языки и грамматики. Цепочки вывода

Компиляторы. Формальные языки и грамматики. Классификация Хомского.

По класс. Хомского выделяют 4 грамматики:

1.Тип 0 (ноль). G=(VT,NV,P,S) V=VNUVT

V называется грамматикой типа 0, если на ее правила вывода не оказывается никаких ограничений. Правила имеют вид: α->β где αЄV*, βЄV*.

2.Тип 1. Грамматику типа 1 можно определить как контекстно зависимую, либо как неукорачивающую. Грамматика называется контекстно зависимой, если каждое правило из P имеет вид: α1A α2-> α1βα2, где α1α2βЄV* AЄVN βЄB. Грамматика называется неукорачивающей, если каждое правило из P имеет вид: α1->β, где α,βЄV+ |β|>=| α|

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

3. Тип 2. Грамматику типа 2 можно определить как контекстно свободную либо как укорачивающую контекстно свободную. Грамматика называется контекстно свободной если любое правило из P имеет вид: A-> β AЄVN β ЄV+

Грамматика называется, укорачивающей контекстно свободной, если любое правило из P имеет вид: A-> β AЄVN β ЄV+

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

4. Тип 3. Грамматику типа 3, можно определить либо как праволинейную либо как леволенейную. Грамматика называется праволенейной, если любое правило из P имеет вид: A->γβ A->γ A,BЄVN, γЄVT

Грамматика G называется леволенейной, если каждое из правил имеет вид: A->γβ A->γ A,BЄVN, γЄVT.

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

Язык L(G) является языком типа R если его можно описать грамматикой типа К. Языки классифицируются в соответствии с типами грамматик, с помощью которых они созданы.

*Тип 0 – это языки с фразовой структурой (самые сложные языки, разговорные). *Тип 1 – контекстнозависимые языки. Время на распознавание предолжений языка экспоненциально зависит от длины исходной цепочки символов. Языки и грамматики типа 1 применяются в анализе и переводе текстов на естественных языках. Распознаватели, построенные на их основе, позволяют анализировать тексты с учетом контекстной зависимости в предложениях входного языка. *Тип 2 – контекстно свободные языки. КС языки лежат в основе синтаксических конструкций большинства современных языком программирования. На их основе функционируют некоторые сложные командные процессоры, допускающие управляющие команды цикла и условия. Эти обстоятельства определяют распространенность данного класса языков. В общем случае время на распознавание предложений языка, относящегося к типу 2 полиноминально зависит от исходной цепочки символов, но среди КС языков существует много классно языков, для которых эта зависимость линейна. *Тип 3 – регулярные языки. Время на распознавание предложений всегда линейно зависит от длины исходной цепочки символов. Данные языки лежат в основе простейших конструкций языков программирования, на их основе строятся мнемокоды команд. Для работы с регулярными языками можно использовать регулярные множества и выражения, а так же конечные автоматы.

Выводом называется процесс порождения предложения языка на основе правил, определяющих язык грамматики. Цепочка β=δ1γδ2 называется непосредственно выводимой из цепочки α=δ1ωδ2 в грамматике G(VT,VN,P,S) V=VTUVN δ1γδ2ЄV*; ωЄV+, если в грамматике G существует правило ω->γЄγ

Непосредственная выводимость цепочки β из цепочки α обозначается как α=>β. Иными словами, цепочка β выводима из цепочки α в том случае, если можно взять несколько символов цепочки α, заменить их на другие символы согласно некоторому правилу грамматики можно получить цепочку β. Любая из цепочек δ1 и δ2 может быть пустой. В предельном случае вся цепочка α может быть заменена на цепочку β тогда в грамматике G должно существовать правило: Цепочка β называется выводной из цепочки α в том случае, если выполняется одной из 2-х условий: 1. α=>β 2.сущ γ такая, что α=>* γ и γ=> β

Такое определение выводимости цепочки является рекурсивным. Суть его заключается в том, что цепочка β, выводимая из α, если может построить последовательность непосредственно выводимых цепочек от α к β следующего вида: α=>γ1=> γ2=>….=> γn=>β n>=1

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

α=>+β Если известно кол-во шагов вывода то можно выводить в такой форме: α=>⁴β

Пример: G({0,1,2,3,4,5,6,7,8,9,+,-,},{S,T,F},P,S)

P: S->T |+T |-T T->F|Tf F->0|1|2|3|4|5|6|7|8|9

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

1. S=>-T=>-TF=>-TFF=>-FFF=>-4FF=>-4FF=>??

2. S=>TF=>T8=>F8=>18

3. T=>TF=>T0=>TF0=>T50=>F50=>350

4. TFT=>TFTF=>TFFF=>FFFF=>1FFF=>1FF4=>10F4

5. F=>5

1.S=>*-479 или S=>+-479 или S=>⁷-479

2. S=>*18 или S=>+18 или S=>⁵18

3. T=>*350 или T=>+350 или T=>⁶350

4. TFT=>*1004 или TFT=>+1004 или TFT=>⁷1004

5. F=>*5 или F=>¹5

Вывод называется законценым, если на основе цепочки β, полученной в результате вывода нельзя больше сделать ни одного шага вывода т.е. вывод называется законченным, если цепочка β – пустая или содержит только терминальные символы грамматики. Цепочка β, получается в результате законченного вывода, называется конечной цепочкой вывода. Цепочка символов αЄV* называется сентенциальной формой грамматики, если она выводима из целевого символа грамматики S=>*α. Если цепочка αЄVT получена в результате законченного вывода, то она называется конечной сентенциальной формой. Язык L с заданной грамматикой G(VT,VN,P,S) – это множество всех конечных сентенц-х форм грамматики G. Алфавитом такого языка L(G) будет множество терминальных символов грамматики (VT), т.к. все конечные сентец-е формы грамматики это цепочки над алфавитом VT. Вывод может быть левосторонним и правосторонним, если в нем на каждом шаге вывода правила грамматики применяются всегда к крайнему левому нетерминальному символу в цепочке т.е. вывод называется левосторонним, если на любом шаге вывода происходит подстановка цепочки символов на основании правила грамматики вместо крайнего левого нетерминального символа в исх цепочке, аналогично для правостороннего вывода. В грамматике для одной и той же цепочки может быть несколько выводов, эквивалентных в том смысле, что в них в одних и тех же местах применяются одни и те же правила вывода, но в различном порядке.

Для контекстно свободных грамматик. КС грамматика G называется неоднозначной, если сущ хотя бы одна цепочка αЄL(G), для которой може быть построено два или более различных деревьев вывода. Это утверждение эквивалентно тому, что цепочка α имеет два или более разных левосторонних или правосторонних выводов, иначе грамматика называется однозначной. Если грамматика используется для определения языка программирования то она должна быть однозначной.

Класс языка определяется классом самой простой, в смысле иерархии Хомского, из описывающих его грамматик. Для языка, определенного регулярной грамматикой всегда можно написать конекстно свободную грамматику. Одной из наиболее простых и широко используемых форм записи грамматик является нормальная форма Бэкуса-Наура (НФБН). Терминальные символы записываются как обычные символы алфавита, а нетерминальные – как имена в угловых скобках.

<число>:=<цифра>|<цифра>|<число>

<цифра>->0|1|2|3|4|5|6|7|8|9

Грамматика БНФ состоит из подмножества правил вывода, каждая из которых определяет синтаксис некоторой конструкции языка прграммирования.

<read>->READ(<id_list>)

<id_list>->id|<id_list>,id

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

Для предложения READ(VALUE) дерево должно выглядеть след образом:

<read>

|

--------------

| | <id_list> |

READ ()

{value}

Характер распознаваемых строк может намного успростить процесс лексического анализа, например любые вещественные числа могут сгенерировать посредством регулярного выражения (+/-) цифра*.цифра*. Реальное числосотавление:

1.Возможно знак

2.Последовательность из 0 или > цифр

3. (.)

4. Последовательность из 0 или > цифр

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