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

Выводом называется процесс порождения предложения языка на основе правил, определяющих язык грамматики. Цепочка β=δ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 или > цифр