Трансляторы , интерпретаторы и компиляторы

Вопрос 1

Вопрос 2

Определение: алфавит - это конечное множество символов. (Термин "символ" имеет достаточно ясный интуитивный смысл и не нуждается в дальнейшем уточнении.)

Например, алфавит A = {a, b, c, +,!} содержит 5 букв, а алфавит B = {00, 01, 10, 11} содержит 4 буквы, каждая из которых состоит из двух символов.

Определение: цепочкой символов в алфавите V называется любая конечная последовательность символов этого алфавита.

Определение: цепочка, которая не содержит ни одного символа, называется пустой цепочкой. Для ее обозначения будем использовать символ l.

Более формально цепочка символов в алфавите V определяется следующим образом:

(1) l - цепочка в алфавите V;

(2) если a - цепочка в алфавите V и a - символ этого алфавита, то aa или аa - цепочка в алфавите V;

(3) b - цепочка в алфавите V тогда и только тогда, когда она является таковой в силу (1) и (2).

Определение: если a и b - цепочки, то цепочка ab называется конкатенацией ( или сцеплением) цепочек a и b.

Например, если a = ab и b = cd, то ab = abcd.

Для любой цепочки a всегда al = la = a.

Определение: обращением ( или реверсом) цепочки a называется цепочка, символы которой записаны в обратном порядке.

Обращение цепочки a будем обозначать a^R.

Например, если a = abcdef, то a^R = fedcba.

Для пустой цепочки: l = l^R.

Определение: n-ой степенью цепочки a (будем обозначать aⁿ) называется конкатенация n цепочек a.

a⁰ = l; aⁿ = aa^n-1 = a^n-1a.

Определение: длина цепочки - это число составляющих ее символов.

Например, если a = abcdefg, то длина a равна 7.

Длину цепочки a будем обозначать |a|. Длина l равна 0.

Определение: язык в алфавите V - это подмножество цепочек конечной длины в этом алфавите.

Определение: обозначим через V^* множество, содержащее все цепочки в алфавите V, включая пустую цепочку l.

Например, если V ={0,1}, то V^* = {l, 0, 1, 00, 11, 01, 10, 000, 001, 011,...}.

Определение: обозначим через V⁺ множество, содержащее все цепочки в алфавите V, исключая пустую цепочку l.

Следовательно, V^* = V⁺ È {l}.

Ясно, что каждый язык в алфавите V является подмножеством множества V^*.

Известно несколько различных способов описания языков [3]. Один из них использует порождающие грамматики. Именно этот способ описания языков чаще всего будет использоваться нами в дальнейшем.

Определение: декартовым произведением A ´ B множеств A и B называется множество {(a,b) | a Î A, b Î B }.

Цепочкой символов (или строкой) называют произвольную последовательность символов, записанных один за другим. Цепочка – это последовательность, в которую могут входить любые допустимые символы.

Понятие символа (или буквы) является базовым в теории формальных языков и не нуждается в определении.

Цепочки символов обозначают греческими буквами: α, β, γ, …

Цепочка – это необязательно некоторая осмысленная последовательность символов. Последовательность «аввв..аагрьь,.лл» – пример цепочки символов.

Для цепочки символов важен состав и количество символов в ней, а также порядок символов в цепочке. Один и тот же символ может произвольное число раз входить в цепочку. Поэтому цепочки «а» и «аа», а также «аб» и «ба» – это разные цепочки символов. Цепочки символов α и β равны (совпадают), α = β, если они имеют один и тот же состав символов, одно и то же их количество и одинаковый порядок следования символов в цепочке.

Количество символов в цепочке называют длиной цепочки. Длина цепочки символов α обозначается как |α|. Очевидно, что если α = β, то и |α| = |β|.

Основной операцией над цепочками символов является операция конкатенации (объединения или сложения) цепочек.

Конкатенация (сложение, объединение) двух цепочек символов – это дописывание второй цепочки в конец первой. Конкатенация цепочек α и β обозначается как αβ. Выполнить конкатенацию цепочек просто: например, если α = «аб», а β = «вг», то αβ = «абвг».

Так как в цепочке важен порядок символов, то очевидно, что операция конкатенации не обладает свойством коммутативности, то есть в общем случае существуют α и β такие, что αβ ≠ βα. Также очевидно, что конкатенация обладает свойством ассоциативности, то есть (αβ)γ = α(βγ).

Можно выделить еще две операции над цепочками.

Обращение цепочки – это запись символов цепочки в обратном порядке. Обращение цепочки α обозначается как α^R. Если α = «абвг», то α^R = «гвба». Для операции обращения справедливо следующее равенство ∀α,β: (αβ)^R = β^Rα^R. Т.е. обращение конкатенации равно конкатенации обращений.

Итерация (повторение) цепочки n раз, где n є N,

n > 0 – это конкатенация цепочки самой с собой n раз. Итерация цепочки α n раз обозначается как αⁿ. Для операции повторения справедливо следующее равенство∀ α: α¹ = α, α² = αα, α³ = ααα, … и т.д.

Среди всех цепочек символов выделяется одна особенная – пустая цепочка. Пустая цепочка символов – это цепочка, не содержащая ни одного символа. Пустую цепочку обозначают греческой буквой λ (в литературе ее иногда обозначают латинской буквой е или греческой ε).

Для пустой цепочки справедливы следующие равенства:

1) |λ| = 0 – Д лина пустой цепочки; Д

2) ∀α: λα = αλ = α – К оммутативность; К

3) λ^R = λ – О бращение; О

4) ∀ n ≥ 0: λⁿ = λ – И терация; И

5) ∀ α: α⁰ = λ.

 

Вопрос3

Понятие о грамматике языка

Грамматика − это описание способа построения предложений некоторого языка. Иными словами, грамматика − это математическая система, определяющая язык.

Фактически, определив грамматику языка, мы указываем правила порождения цепочек символов, принадлежащих этому языку. Таким образом, грамматика − это генератор цепочек языка. Она относится ко второму способу определения языков − порождению цепочек символов.

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

Правило (или продукция) − это упорядоченная пара цепочек символов (α, β). В правилах очень важен порядок цепочек, поэтому их чаще записывают в виде α→β (или α: = β). Такая запись читается как «α порождает β» или «β по определению есть α».

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

Язык, заданный грамматикой G, обозначается как L(G).

Две грамматики G и G' называются эквивалентными, если они определяют один и тот же язык: L(G) = L(G'). Две грамматики G и G' называются почти эквивалентными, если заданные ими языки различаются не более чем на пустую цепочку символов: L(G) U {λ} = L(G') U {λ}.

 

 

Вопрос 4

Определение: порождающая грамматика G - это четверка (VT, VN, P, S), где

VT - алфавит терминальных символов (терминалов),

VN - алфавит нетерминальных символов (нетерминалов), не пересекающийся с VT,

P - конечное подмножество множества (VT È VN)⁺ ´ (VT È VN)^*; элемент (a, b) множества P называется правилом вывода и записывается в виде a ® b,

S - начальный символ (цель) грамматики, S Î VN.

Для записи правил вывода с одинаковыми левыми частями

a ® b_1, a ® b_2,..., a ® b_n

будем пользоваться сокращенной записью

a ® b₁ | b₂ |...| b_n.

Каждое b_i, i= 1, 2,...,n, будем называть альтернативой правила вывода из цепочки a.

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

G1 = ({0,1}, {A,S}, P, S),

где P состоит из правил

S ® 0A1

0A ® 00A1

A ® l

Определение: цепочка b Î (VT È VN)^* непосредственно выводима из цепочки a Î (VT È VN)⁺ в грамматике G = (VT, VN, P, S) (обозначим a ® b), если a = x₁gx₂, b = x₁dx₂, где x₁, x₂, d Î (VT È VN)^*, g Î (VT È VN)⁺ и правило вывода g ® d содержится в P.

Например, цепочка 00A11 непосредственно выводима из 0A1 в грамматике G1.

Определение: цепочка b Î (VT È VN)^* выводима из цепочки a Î (VT È VN)⁺ в грамматике G = (VT, VN, P, S) (обозначим a Þ b), если существуют цепочки g₀, g₁,..., g_n (n³0), такие, что a = g₀ ® g₁ ®... ® g_n= b.

Определение: последовательность g₀, g₁,..., g_n называется выводом длины n.

Например, S Þ 000A111 в грамматике G1 (см. пример выше), т.к. существует вывод S ® 0A1 ® 00A11 ® 000A111. Длина вывода равна 3.

Определение: языком, порождаемым грамматикой G = (VT, VN, P, S), называется множество L (G)={a Î VT^* | S Þ a}.

Другими словами, L(G) - это все цепочки в алфавите VT, которые выводимы из S с помощью P.

Например, L (G1) = {0ⁿ1ⁿ | n>0}.

Определение: цепочка a Î (VT È VN)^*, для которой S Þ a, называется сентенциальной формой в грамматике G = (VT, VN, P, S).

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

Определение: грамматики G1 и G2 называются эквивалентными, если L (G1) = L (G2).

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

P 1: S ® 0A1                                              P 2: S ® 0S1 | 01

       0A ® 00A1

       A ® l

эквивалентны, т.к. обе порождают язык

L (G1) = L (G2) = {0ⁿ1ⁿ | n>0}.

Определение: грамматики G1 и G2 почти эквивалентны, если
L (G1) È {l} = L (G2) È {l}.

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

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

P 1: S ® 0A1                                                             P 2:      S ® 0S1 | l

0A ® 00A1

A ® l

почти эквивалентны, т.к. L (G1)={0ⁿ1ⁿ | n>0}, а L (G2)={0ⁿ1ⁿ | n³0}, т.е. L (G2) состоит из всех цепочек языка L (G1) и пустой цепочки, которая в L (G1) не входит.

 

Вопрос 4

Способы задания схем грамматик

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

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

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

Форма Бэкуса -Наура

При описании синтаксиса конкретных языков программирования приходится вводить большое число нетерминальных символов, и символическая форма записи теряет свою наглядность. В этом случае применяют форму Бэкуса-Наура (БНФ), которая предполагает использование в качестве нетерминальных символов комбинаций слов естественного языка, заключенных в угловые скобки, а в качестве разделителя - специального знака, состоящего из двух двоеточий и равенства. Например, если правила L  ®  E L и L ®  E записаны в символической форме, и символ L соответствует синтаксическому понятию "список", а символ E - "элемент списка", то их можно представить в форме Бэкуса-Наура так:

<список>::= <элемент списка><список>,
<список>::= <элемент списка>.

Чтобы сократить описание схемы грамматики, в БНФ разрешается объединять правила c одинаковой левой частью в одно правило, правая часть которого должна включать правые части объединяемых правил, разделенные вертикальной чертой. Используя объединение правил, для рассматриваемого примера получаем:

<список>::=<элемент списка><список>|<элемент списка>.

Итерационная форма

Для получения более компактных описаний синтаксиса применяют итерационную форму описания. Она предполагает введение специальной операции, которая называется итерацией и обозначается парой фигурных скобок со звездочкой. Итерация вида {a}^* определяется как множество, включающее цепочки всевозможной длины, построенные с использованием символа a, и пустую цепочку.

{a}^* = {l, a, aa, aaa, aaaa,...}.

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

L ® E { E }*

Например, описание множества цепочек, каждая из которых должна начинаться знаком # и может состоять из произвольного числа букв x и y, может быть представлено в итерационной форме так:

I ® # { x | y }^*

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

A®x A y B z и A®x B z

могут быть записаны так:

A®x [ A y ] B z

Синтаксические диаграммы

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

1)Каждому правилу вида A ® a₁ | a₂ |...| a_k ставится в соответствие диаграмма, структура которой определяется правой частью правила.

2)Каждое появление терминального символа x в цепочке a_i изображается на диаграмме дугой, помеченной этим символом x, заключенным в кружок .

3) Каждому появлению нетерминального символа <A> в цепочке a_i ставится в соответствие на диаграмме дуга, помеченная символом, заключённым в квадрат .

4) Порождающее правило, имеющее вид:

A ® a₁a₂...a_n

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

5) Порождающее правило, имеющее вид:

A ® a₁ | a₂ |... | a_n

изображается на диаграмме так:

 

6) Если порождающее правило задано в виде итерации:

A ® {a}*,

то ему соответствует диаграмма:

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

Правила 3-6 предусматривают, что в качестве цепочки a1 на объединенной диаграмме могут быть использованы диаграммы построенные для этих цепочек. В качестве примера рассмотрим грамматику G3 с начальным символом A:

G3: ({ x, +, (,) }, {<A>, <B>, <C>}, P = { A ® x | (B), B ® AC, C ® {+A}* }, S).

Синтаксические диаграммы для такой грамматики имеют вид:

Заменяя нетерминальные символы, соответствующими диаграммами, получаем объединенную диаграмму в виде:

Вопрос 5

ТИП 0:                                            

Грамматика G = (VT, VN, P, S) называется грамматикой типа 0, если на правила вывода не накладывается никаких ограничений (кроме тех, которые указаны в определении грамматики).

ТИП 1:

Грамматика G = (VT, VN, P, S) называется неукорачивающей грамматикой, если каждое правило из P имеет вид a ® b, где a Î (VT È VN)⁺, b Î (VT È VN)⁺ и | a | £ | b |.

Грамматика G = (VT, VN, P, S) называется контекстно-зависимой (КЗ), если каждое правило из P имеет вид a ® b, где a = x₁Ax₂; b = x₁gx₂; A Î VN; g Î (VT È VN)⁺; x₁,x₂ Î (VT È VN)^*.

Грамматику типа 1 можно определить как неукорачивающую либо как контекстно-зависимую.

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

ТИП 2:

Грамматика G = (VT, VN, P, S) называется контекстно-свободной (КС), если каждое правило из Р имеет вид A ® b, где A Î VN, b Î (VT È VN)⁺.

Грамматика G = (VT, VN, P, S) называется укорачивающей контекстно-свободной (УКС), если каждое правило из Р имеет вид A ® b, где A Î VN, b Î (VT È VN)^*.

Грамматику типа 2 можно определить как контекстно-свободную либо как укорачивающую контекстно-свободную.

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

ТИП 3:

Грамматика G = (VT, VN, P, S) называется праволинейной, если каждое правило из Р имеет вид A ® tB либо A ® t, где A Î VN, B Î VN, t Î VT.

Грамматика G = (VT, VN, P, S) называется леволинейной, если каждое правило из Р имеет вид A ® Bt либо A ® t, где A Î VN, B Î VN, t Î VT.

Грамматику типа 3 (регулярную, Р-грамматику) можно определить как праволинейную либо как леволинейную.

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

Соотношения между типами грамматик:

любая регулярная грамматика является КС-грамматикой;

любая регулярная грамматика является УКС-грамматикой;

любая КС-грамматика является КЗ-грамматикой;

любая КС-грамматика является неукорачивающей грамматикой;

любая КЗ-грамматика является грамматикой типа 0.

любая неукорачивающая грамматика является грамматикой типа 0.

Замечание: УКС-грамматика, содержащая правила вида A ® l, не является КЗ-грамматикой и не является неукорачивающей грамматикой.

Определение: язык L (G) является языком типа k, если его можно описать грамматикой типа k.

Замечание: следует подчеркнуть, что если язык задан грамматикой типа k, то это не значит, что не существует грамматики типа k’ (k’>k), описывающей тот же язык. Поэтому, когда говорят о языке типа k, обычно имеют в виду максимально возможный номер k.

 

Вопрос 6 *КАША* думайте сами что и куда писать

Постановка задачи разбора

Грамматики и распознаватели – два независимых метода, которые реально

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

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

В общем виде распознаватель можно отобразить в виде условной схемы,

состоящей из следующих основных компонентов:

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

2. Устройства управления, которое координирует работу распознавателя,

имеет некоторый набор состояний и конечную память (для хранения своего состояния и некоторой промежуточной информации);

3. Внешней (рабочей) памяти, которая может хранить некоторую информацию в процессе работы распознавателя и в отличие от памяти устройства

управления может иметь неограниченный объем.

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

По видам считывающего устройства распознаватели могут быть двусторонние и односторонние.

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

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

По видам устройства управления распознаватели бывают детерминированные и недетерминированные.

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

В противном случае распознаватель называется недетерминированным.

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

По видам внешней памяти распознаватели бывают следующих типов:

1. распознаватели без внешней памяти;

2. распознаватели с ограниченной внешней памятью; 

3. распознаватели с неограниченной внешней памятью.

 

Разработчики трансляторов всегда имеют дело с уже определенным языком программирования. Грамматика для синтаксических конструкций этого языка известна. Она, как правило, четко описана в стандарте языка, и хотя форма описания может быть произвольной, ее всегда можно преобразовать к требуемому виду (например, к форме Бэкуса-Наура). Задача разработчиков заключается в том, чтобы построить распознаватель для заданного языка, который затем будет основой синтаксического анализатора в трансляторе.

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

Задача разбора в общем виде может быть решена не для всех типов языков.

Но как было сказано выше, разработчиков трансляторов интересуют, прежде

всего, контекстно-свободные и регулярные языки. Для данных типов языков

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

Кроме того, если входная цепочка символов не принадлежит заданному

языку – исходная программа содержит ошибку, – разработчику программы не

интересно просто  узнать сам факт наличия ошибки. В данном случае задача

разбора также расширяется: распознаватель в составе компилятора должен не

только установить факт присутствия ошибки во входной программе, но и по

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

встречается.

Вопрос 6. Парт 2

Разбор цепочек

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

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

С практической точки зрения наибольший интерес представляет разбор по контекстно-свободным (КС и УКС) грамматикам. Их порождающей мощности достаточно для описания большей части синтаксической структуры языков программирования. Для различных подклассов КС-грамматик имеются хорошо разработанные практически приемлемые способы решения задачи разбора.

Рассмотрим основные понятия и определения, связанные с разбором по КС-грамматике.

Определение: вывод цепочки b Î (VT)^* из S Î VN в КС-грамматике G = (VT, VN, P, S), называется левым (левосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого левого нетерминала.

Определение: вывод цепочки b Î (VT)^* из S Î VN в КС-грамматике G = (VT, VN, P, S), называется правым (правосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого правого нетерминала.

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

Например, для цепочки a+b+a в грамматике

G = ({a,b}, {S,T}, {S ® T | T+S; T ® a|b}, S)

можно построить выводы:

(1)   S®T+S®T+T+S®T+T+T®a+T+T®a+b+T®a+b+a

(2)   S®T+S®a+S®a+T+S®a+b+S®a+b+T®a+b+a

(3)   S®T+S®T+T+S®T+T+T®T+T+a®T+b+a®a+b+a

Здесь (2) - левосторонний вывод, (3) - правосторонний, а (1) не является ни левосторонним, ни правосторонним, но все эти выводы являются эквивалентными в указанном выше смысле.

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

Определение: дерево называется деревом вывода ( или деревом разбора) в КС-грамматике G = { VT, VN, P, S), если выполнены следующие условия:

(1)   каждая вершина дерева помечена символом из множества (VN È VT È l), при этом корень дерева помечен символом S; листья - символами из (VT È l);

(2)   если вершина дерева помечена символом A Î VN, а ее непосредственные потомки - символами a₁, a₂,..., a_n, где каждое a_i Î (VT È VN), то A ® a₁a₂...a_n - правило вывода в этой грамматике;

(3)   если вершина дерева помечена символом A Î VN, а ее единственный непосредственный потомок помечен символом l, то A ® l - правило вывода в этой грамматике.

Пример дерева вывода для цепочки a+b+a в грамматике G на рис.2.1:

Определение: КС-грамматика G называется неоднозначной, если существует хотя бы одна цепочка a Î L (G), для которой может быть построено два или более различных деревьев вывода. В противном случае грамматика называется однозначной.

Это утверждение эквивалентно тому, что цепочка a имеет два или более разных левосторонних (или правосторонних) выводов.

Рис.2.1. Дерево вывода для цепочки a+b+a

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

Пример неоднозначной грамматики:

G = ({if, then, else, a, b}, {S}, P, S),

где P = {S ® if b then S else S | if b then S | a}.

В этой грамматике для цепочки if b then if b then a else a можно построить два дерева вывода.

Однако это не означает, что язык L (G) обязательно неоднозначный. Определенная нами неоднозначность - это свойство грамматики, а не языка, т.е. для некоторых неоднозначных грамматик существуют эквивалентные им однозначные грамматики. Если грамматика используется для определения языка программирования, то она должна быть однозначной. В приведенном выше примере разные деревья вывода предполагают соответствие else разным then. Если договориться, что else должно соответствовать ближайшему к нему then, и подправить грамматику G, то неоднозначность будет устранена:

S ® if b then S | if b then S’ else S | a

S’ ® if b then S’ else S’ | a

Проблема, порождает ли данная КС-грамматика однозначный язык(т.е. существует ли эквивалентная ей однозначная грамматика),является алгоритмически неразрешимой.

Преобразования грамматик

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

Определение: символ A Î VN называется бесплодным в грамматике G = (VT, VN, P, S), если множество { a | a Î VT^*, A Þ a} пусто.

Алгоритм удаления бесплодных символов:

Вход: КС-грамматика G = (VT, VN, P, S).

Выход: КС-грамматика G’ = (VT, VN’, P’, S), не содержащая бесплодных символов, для которой L (G) = L (G’).

Метод:

Рекурсивно строим множества N₀, N₁,...

1. N₀ = Æ, i = 1.

2. N_i = {A | (A ® a) Î P и a Î (N_i-1 È VT)^*} È N_i-1.

3. Если N_i ¹ N_{i -1}, то i = i+1 и переходим к шагу 2, иначе VN ’ = N_i; P ’ состоит из правил множества P, содержащих только символы из VN ’ È VT; G’ = (VT, VN ’, P ’, S).

Определение: символ x Î (VT È VN) называется недостижимым в грамматике G = (VT, VN, P, S), если он не появляется ни в одной сентенциальной форме этой грамматики.

Алгоритм удаления недостижимых символов:

Вход: КС-грамматика G = (VT, VN, P, S)

Выход: КС-грамматика G’ = (VT’, VN’, P’, S), не содержащая недостижимых символов, для которой L(G) = L(G’).

Метод:

1. V₀ = {S}; i = 1.

2. V_i = {x | x Î (VT È VN), (A ® axb) Î P и A Î V_i-1} È V_i-1.

3. Если V_i ¹ V_i-1, то i = i+1 и переходим к шагу 2, иначе VN’ =
V_i Ç VN; VT’ = V_i Ç VT; P’ состоит из правил множества P, содержащих только символы из Vi; G’ = (VT’, VN’, P’, S).

Определение: КС-грамматика G называется приведенной, если в ней нет недостижимых и бесплодных символов.

Алгоритм приведения грамматики:

(1) обнаруживаются и удаляются все бесплодные нетерминалы.

(2) обнаруживаются и удаляются все недостижимые символы.

Удаление символов сопровождается удалением правил вывода, содержащих эти символы.

Замечание: е сли в этом алгоритме переставить шаги (1) и (2), то не всегда результатом будет приведенная грамматика.

Для описания синтаксиса языков программирования стараются использовать однозначные приведенные КС-грамматики.

Исключение цепных правил

Определение. Правило грамматики вида A ® B, где A,B Î V N, называется цепным.

Утверждение. ДляКС-грамматики G, содержащей цепные правила, можно построить эквивалентную ей грамматику G ', не содержащую цепных правил.

Идея доказательства заключается в следующем.

Если грамматика G имеет правила A ® B, B ® C, C ® aX, то такие правила могут быть заменены одним правилом А ® aX, поскольку вывод A Þ  B Þ C Þ aX цепочки aX в грамматике G может быть получен в грамматике G' с помощью правила A ® aX.

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

Разобьем множество правил P грамматики G на два подмножества P₁ и P₂, включая в P₁ все правила вида A ® B.

Для каждого правила из P₁ найдем множество правил S(A_i), которые строятся так:
если A_i Þ * A_j и в P₂ есть правило A_j ® a, где a - цепочка словаря (V N È V T) ^*, то в S(A_i) включим правило A_i ® a.

Построим новое множество правил P’ путем объединения правил P₂ и всех построенных множеств S(A_i). Получим грамматику G' = {VN,VT, P’, S}, которая эквивалентна заданной и не содержит правил вида A ® B.

В качестве примера выполним исключение цепных правил из грамматики G:

G = ({+,*,(,),a}, {E,T,F}, P={E ® E+T | T, T ®  T*F | F, F ® (E) | a}, E).

Вначале разобьем правила грамматики на два подмножества:

P₁ = {E ® T, T ® F},

P₂ = {E ® E+T, T ® T*F, F ®    (E) | a }

Для каждого правила из P1 построим соответствующее подмножество.

S(E) = { E ®  T*F, E ® (E) | a },

S(T) = { T ® (E) | a}

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

P2 U S(E) U S(T) = { E ® T+T | T*F | (E) | a, T ® T*F | (E) | a, F ® (E) | a }

 

Вопрос 7

Преобразование неукорачивающих грамматик

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

Определение. Правило вида A ® l называется «пустым» (аннулирующим) правилом.

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

1)схема грамматики не содержит аннулирующих правил,

2)либо схема грамматики содержит только одно правило вида S ® l, где S - начальный символ грамматики, и символ S не встречается в правых частях остальных правил грамматики.

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

Утверждение. Для каждой КС-грамматики G', содержащей аннулирующие правила, можно построить эквивалентную ей неукорачивающую грамматику G, такую что L(G')=L(G).

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