Принцип рекурсии в правилах грамматики. Исключение левой рекурсии Левая рекурсия

Определение 10.1 Некоторый нетерминальный символ А контекстно-свободной грамматики G = (N, P, S) называется рекурсивным, если существует вывод А + А для некоторых и. Если при этом =, то А называется леворекурсивным. Аналогично, если =, то А называется праворекурсивным. Грамматика, имеющая хотя бы один леворекурсивный нетерминальный символ, называется леворекурсивной. Грамматика, в которой все нетерминальные символы, кроме, быть может, начального символа, рекурсивные, называется рекурсивной.


Заметим, что для рекурсивных грамматик в выводе А + А всегда либо, либо. Если = и =, то грамматика G является циклической грамматикой. Пример Примером праворекурсивной грамматики является грамматика со следующей схемой: 1 0 Данная грамматика порождает множество чисел, состоящих из нулей и единиц.


Пример Тот же самый язык, что и в примере порождает леворекурсивная грамматика со следующей схемой: 1 0


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


Пример Тот же самый язык, что и в примере порождает праворекурсивная грамматика со следующей схемой: А 1 0


Лемма 10.1 Пусть G = (N, P, S) – КС-грамматика, в которой для некоторого нетерминального символа А все А- правила имеют вид А A 1 | A 2 | … | A m | 1 | 2 | … | n | причем ни одна из цепочек i не начинается с А. Пусть G"=(N {A"}, P", S), где A" – новый нетерминал, а P" получается из P заменой этих А- правил следующими правилами А 1 | 2 | … | n | 1A" | 2A" | … | nA" | А" 1 | 2 | … | m | 1A" | 2A" | … | mA" Тогда L(G") = L(G). Рассмотрим алгоритм преобразования КС- грамматики, в которой имеется непосредственная левая рекурсия, к КС-грамматике без левой рекурсии.


Доказательство. Цепочки, которые можно получить в грамматике G из нетерминала А применением А- правил лишь к самому левому нетерминалу, образуют регулярное множество (… + n)(… + m)* Это в точности те цепочки, которые можно получить в грамматике G" из А с помощью правых выводов, применив один раз А-правило и несколько раз А"- правила (в результате вывод уже не будет левым). Все шаги вывода, на которых не используются А- правила, можно непосредственно сделать и в грамматике G", так как не А-правила в обеих грамматиках одни и те же. Отсюда можно заключить, что L(G) L(G").


Обратное включение доказывается аналогично. В грамматике G" берется правый вывод и рассматриваются последовательности шагов, состоящие из одного применения А-правила и нескольких применений А"-правил. Таким образом, L(G") = L(G). Грамматика примера получена из грамматики примера с использованием преобразования леммы 10.1.


Лемма 10.2 Пусть G = (N, P, S) – КС-грамматика, в которой для некоторого нетерминального символа А все А- правила имеют вид А A 1 | A 2 | … | A m | 1 | 2 | … | m причем ни одна из цепочек i не начинается с А. Пусть G"=(N, P", S), где P" получается из P заменой этих А-правил следующими правилами А 1 | 2 | … | m | 1A | 2A | … | mA Тогда L(G") = L(G). Грамматика примера получена из грамматики примера с использованием преобразования леммы 10.2.


На рисунке показано, как действуют преобразования на дерево вывода A A i1... i2 A A ik A ik A ik-1... i1


Пример Пусть G0 – обычная грамматика с правилами E E+T E T T T*F T F F (E) F a Эквивалентная ей грамматика G`


E T E TE" E" +T E" +TE" T F T FT " T " *F T " *FT " F (E) F a Рассмотрим теперь, как преобразовать приведенную леворекурсивную КС-грамматику к КС-грамматике, не имеющей левой рекурсии.


Алгоритм 10.2 Устранение левой рекурсии. Вход: Приведенная КС-грамматика G=(N,P,S) Выход: Эквивалентная КС-грамматика G` без левой рекурсии. Метод. Пусть N = {A1,…, An}, т.е. все нетерминальные символы грамматики упорядочены некоторым произвольным образом. Преобразуем G так, чтобы в правиле Ai цепочка начиналась либо с терминала, либо с такого Aj, что j i. 1) Положим i=1.


2) Пусть множество Ai – правил – это Ai Ai | … | Ai m | 1 | … | p, где ни одна из цепочек j не начинается с Ak, если k i (если это не выполнено, можно ввести новый нетерминальный символ, заменить первый символ правила этим символом и добавить дополнительное правило в грамматику). Заменим Ai–правила правилами: Ai 1 | … | p | 1Ai" | … | pAi" Ai" 1 | … | m | 1Ai" | … | mAi" где A"i новый нетерминал. Правые части всех Ai- правил начинаются теперь с терминала или с Ak для некоторого k > i. 3) Если i=n, полученную грамматику G" считать результатом и остановиться. В противном случае положить i=i+1 и j=1. i. 3) Если i=n, полученную грамматику G" считать результатом и остановиться. В противном случае положить i=i+1 и j=1.">


J, то и правая часть каж" title="4) Заменить каждое правило вида Ai Aj правилами Ai 1 |…| m, полученными в результате замены Aj правыми частями всех Aj-правил вида Aj 1|…| m. Так как правая часть каждого Aj-правила начинается уже с терминала или с Ak для k > j, то и правая часть каж" class="link_thumb"> 16 4) Заменить каждое правило вида Ai Aj правилами Ai 1 |…| m, полученными в результате замены Aj правыми частями всех Aj-правил вида Aj 1|…| m. Так как правая часть каждого Aj-правила начинается уже с терминала или с Ak для k > j, то и правая часть каждого Ai- правила будет теперь обладать этим свойством. 5) Если j=i–1, перейти к шагу (2). В противном случае положить j=j+1 и перейти к шагу (4). j, то и правая часть каж"> j, то и правая часть каждого Ai- правила будет теперь обладать этим свойством. 5) Если j=i–1, перейти к шагу (2). В противном случае положить j=j+1 и перейти к шагу (4)."> j, то и правая часть каж" title="4) Заменить каждое правило вида Ai Aj правилами Ai 1 |…| m, полученными в результате замены Aj правыми частями всех Aj-правил вида Aj 1|…| m. Так как правая часть каждого Aj-правила начинается уже с терминала или с Ak для k > j, то и правая часть каж"> title="4) Заменить каждое правило вида Ai Aj правилами Ai 1 |…| m, полученными в результате замены Aj правыми частями всех Aj-правил вида Aj 1|…| m. Так как правая часть каждого Aj-правила начинается уже с терминала или с Ak для k > j, то и правая часть каж">


Теорема 10.1 Для каждого КС-языка существует порождающая его не леворекурсивная грамматика. Доказательство есть следствие приведенных в данном разделе преобразований. Пример Пусть G есть КС-грамматика с правилами A BC a B CA Ab C AB CC a


Положим A1=A, A2=B и A3=C После каждого применения шага (2) или (4) алгоритма получаются следующие грамматики (указываем только новые правила). Шаг (2) для i=1: G не меняется Шаг (4) для i=2, j=1: B CA BCb ab Шаг (2) для i=2: B CA ab CAB abB B Cb Шаг (4) для i=3, j=1: C BCB aB CC a Шаг (4) для i=3, j=2: C CACB ab CB CAB CB ab B CB aB CC a Шаг (2) для i=3: C abCB ab B CB aB a abCBC ab B CB C aB C aC C ACB C AB CB C CC ACB AB CB C



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

В грамматике для арифметических операций применение второго правила приведет к зацикливанию процедуры разбора. Подобные грамматики называются леворекурсивными. Грамматика называется леворекурсивной, если в ней существует нетерминал А, для которого существует вывод А=>+Аa. В простых случаях левая рекурсия вызвана правилами вида

В этом случае вводят новый нетерминал и исходные правила заменяют следующими.

(если есть нетерминал А, для которого существует вывод А→+Аa за 1 или более шагов). Левой рекурсии можно избежать, преобразовав грамматику.

Например, продукции A→Aa

Можно заменить на эквивалентные:

Для такого случая существует алгоритм, исключающий левую рекурсию:

1) определяем на множестве нетерминалов какой-либо порядок (А 1 , А 2 , …, А n)

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

for i:=1 to n do

for j:=1 to i-1 do

if Ai → Ajγ then Ai→δ1γ

│ δkγ, где

Aj → δ1│ δ2│ …│ δk

3) исключаем все случаи непосредственной левой рекурсии (правило1)

Т.о. алгоритм помогает избежать зацикливания.

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

Общий вид правила исключения левой рекурсии

Левая факторизация.

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

Иногда существует возможность преобразовать грамматику к LL(1) виду, используя метод левой факторизации.

Например: S→ if B then S

│if B then S else S

Эти продукции нарушают условие LL(1)-грамматик. Эту грамматику можно преобразовать к виду LL(1).

S → if B then S Tail

В общем виде это преобразование можно определить так:

вводим новый нетерминал В, для которого



| β N Для B можно применить левую факторизацию. Эта процедура повторяется, пока остается неопределенным выбор продукции (т.е. пока в ней можно что-нибудь изменить).

Построение множества FIRST

Множество First для нетерминала определяет множество терминалов, с которых может начинаться данный нетерминал.

1. Если х - терминал, то first(x)={x}. Так как первым символом последовательности из одного терминала может являться только сам терминал.

2. Если в грамматике присутствует правило Хà e, то множество first(х) включает e. Это означает, что Х может начинаться с пустой последовательности, то есть отсутствовать вообще.

3. Для всех продукций вида XàY1 Y2 … Yk выполняем следующее. Добавляем в множество first(Х) множество first(Yi) до тех пор, пока first(Yi-1) содержит e, а first(Yi) не содержит e. При этом i изменяется от 0 до k. Это необходимо, так как если Yi-1 может отсутствовать, то необходимо выяснить, с чего будет начинаться вся последовательность в этом случае.

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

· Грамматика типа 0 (общего вида). Правила имеют вид α→β

· Грамматика типа 1 (контекстно зависимая, КЗ)

Правила имеют вид αAβ → αγβ. γ принадлежит V + , т.е. грамматика является неукорачивающей

α,β называются левым и правым контекстом

· Грамматика типа 2 (контекстно свободная, КС)

Правила имеют вид A → α. α принадлежит V*, т.е. грамматика может быть укорачивающей => КС языки не содержатся в КЗ

Наиболее близкая к БНФ

· Грамматика типа 3 (автоматная, регулярная)

Правила имеют вид A → aB, A → a, A → ε

Автоматные языки содержатся в КС языках

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

S → (S) | SS | ε

Порождение (вывод)

Обозначения

=>+ (1 или более)

=>* (0 или более)

Сентенциальная форма грамматики - это строка, которая может быть выведена из стартового символа.

Предложение (сентенция) грамматики - это сентенциальная форма, состоящая из одних терминалов.

Язык L(G) грамматики - это множество всех ее предложений.

Обозначения:

Левый, правый вывод (порождение).

Левый и правый вывод для предложения i + i * i

Дерево вывода (синтаксическое дерево, дерево разбора) строки предложения. В отличие от порождения, из него исключена информация о порядке вывода.

Крона дерева разбора - цепочка меток листьев слева направо

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

Пример неоднозначной грамматики. Грамматика арифметических выражений.

E → E+E | E*E | i

Два дерева разбора для цепочки i + i * i

Пример неоднозначной грамматики. Грамматика условного оператора

S → if b then S

| if b then S else S

Два дерева разбора для цепочки if b then if b then a

Преобразование в эквивалентную однозначную грамматику:

S → if b then S



| if b then S2 else S

S2 → if b then S2 else S2

44.Формальные языки и грамматики: непустые, конечные и бесконечные языки

45.Эквивалентность и минимизация автоматов

Эквивалентность конечных автоматов

Пусть S - алфавит (конечное множество символов) и S* - множество всех слов в алфавите S. Будем обозначать буквой eпустое слово, т.е. вовсе не содержащее букв (символов из S), а знаком × - операцию приписывания (конкатенации) слов.

Так, аав × ва = аавва. Знак × операции приписывания часто опускают.

Слова в алфавите S будем обозначать малыми греческими буквами a, b, g, .... Очевидно, e является единицей для операции приписывания:

Очевидно также, что операция приписывания ассоциативна, т.е. (ab)g = a(bg).

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

S* называют свободным моноидом над алфавитом S.

Минимизация конечного автомата

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

Эквивалентными естественно назвать два состояния автомата, которые нельзя различить никакими входными словами.

Определение 1: Два состояния р и q конечного автомата

А = (S,X,Y,s0,d,l) называются эквивалентными (обозначается p~q), если ("aÎ X*)l*(p,a) =l*(q, a)

46.Эквивалентность одноленточных и многоленточных машин Тьюринга

Очевидно, что понятие k–ленточной МТ шире, чем понятие «обычной» одноленточной машины. ОПРЕДЕЛЕНИЕ 6. (k+1)–ленточная МТ M′ с программой w симулирует k–ленточную машину M, если для любого набора входных слов (x1, x2, …, xk) результат работы M′ совпадает с результатом работы M на этих же входных данных. Предполагается, что вначале слово w записано на (k+1)-й ленте M′. Под результатом понимается состояние первых k лент МТ в момент остановки, а если на данном входе M не останавливается, то симулирующая ее машина также не должна останавливаться на данном входе.

ОПРЕДЕЛЕНИЕ 7. (k+1)–ленточная МТ M* называется универсальной машиной Тьюринга для k–ленточных машин, если для любой k- ленточной машины M существует программа w, на которой M* симулирует M. 12 Обратите внимание: в определении универсальной МТ одна и та же машина M′ должна симулировать разные k-ленточные машины (на разных программах w). Рассмотрим следующую теорему . ТЕОРЕМА 3. Для любого k≥1 существует универсальная (k+1)– ленточная машина Тьюринга. Доказательство. Теорему докажем конструктивно, т.е. покажем, как можно построить требуемую универсальную машину M*. Рассмотрим лишь общую схему построения, опустив сложные детали. Основная идея заключается в том, чтобы на дополнительную (k+1)-ю ленту разместить описание симулируемой машины Тьюринга и использовать это описание в процессе симулирования.

ОПРЕДЕЛЕНИЕ 8. Будем говорить, что машина Тьюринга M вычисляет частичную функцию f:A*→A*, если для любого x∈A*, записанного на первую ленту машины M: если f(x) определено, то M останавливается, и в момент остановки на последней ленте машины записано слово f(x); если f(x) не определено, то машина M не останавливается.

ОПРЕДЕЛЕНИЕ 9. Будем говорить, что машины M и M′ эквивалентны, если они вычисляют одну и ту же функцию. Понятие эквивалентности «слабее», чем симулирование: если машина M′ симулирует машину M, то машина M′ эквивалентна M; обратное, вообще говоря, неверно. С другой стороны, для симулирования требуется, чтобы у M′ было как минимум столько же лент, сколько и у M, в то время как для эквивалентности это не 15 обязательно. Именно это свойство позволяет нам сформулировать и доказать следующую теорему .

ТЕОРЕМА 4. Для любой k-ленточной машины M, имеющей временную сложность T(n), существует эквивалентная ей одноленточная машина M′ с временной сложностью T′ (n) = O(T 2 (n)).

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

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

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

Идея доказательства заключается в следующем. Если схема грамматики имеет вид

R = {..., ,..., , ... , a },

то такая грамматика эквивалентна грамматике со схемой

R" = {..., a,...},

поскольку вывод в грамматике со схемой R цепочки a:

a

может быть получен в грамматике со схемой R" с помощью правила a.

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

Для каждого правила из R 1 найдем множество правил S(), которые строятся так:

если * и в R 2 есть правило α, где α - цепочка словаря (V т V A)*, то в S() включим правило α.

Построим новую схему R" путем объединения правил R 2 и всех построенных множеств S(). Получим грамматику Г" = {V т, V A , I, R"}, которая эквивалентна заданной и не содержит правил вида .

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

R={ +|,

*|,

()|a }

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

R 1 = { , },

R 2 = { +, *, ()|a }

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

S() = { *, ()|a },

S() = { ()|a}

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

R 2 U S() U S() = { + | * | () | a,

* | () | a,

() | a }

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

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

49.Эквивалентные преобразования КС-грамматик: удаление бесполезных символов.

Пусть дана произвольная КС-грамматика G . Нетерминал A этой грамматики называется продуктивным , если существует такая терминальная цепочка (в том числе и пустая), что A Þ * a непродуктивным.

Теорема. Каждая КС-грамматика эквивалентна КС-грамматике без непродуктивных нетерминалов.

Нетерминал A грамматики G называется достижимым , если существует такая цепочка a , что S Þ * a . В противном случае нетерминал называется недостижимым.

Теорема. Каждая КС-грамматика эквивалентна КС-грамматике без недостижимых нетерминалов.

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

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

Пример. Устраним бесполезные символы в грамматике

S ® aC | A; A ® cAB; B ® b ; C ® a .

Шаг 1 . Строим множество достижимых символов: {S } ® {S, C, A }® {S, C, A, B }. Все нетерминалы достижимы. Недостижимых нет грамматика не меняется.

Шаг 2 . Строим множество продуктивных символов: { C, B }® {S, C, B }. Получаем, что A - не продуктивен. Выкидываем его и все правила с ним из грамматики. Получим

S ® aC ; B ® b ; C ® a .

Шаг 3 . Строим множество достижимых символов новой грамматики: {S } ® {S, C }. Получаем, что B недостижим. Выкидываем его и все правила с ним из грамматики. Получим

S ® aC ; C ® a .

Это - окончательный результат.

50. Эквивалентные преобразования КС-грамматик: устранение левой рекурсии, левая факторизация

Удаление левой рекурсии

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

Непосредственную левую рекурсию, то есть рекурсию вида , можно удалить следующим способом. Сначала группируем A -правила:

где никакая из строк не начинается с A. Затем заменяем этот набор правил на

где A" - новый нетерминал. Из нетерминала A можно вывести те же цепочки, что и раньше, но теперь нет левой рекурсии . С помощью этой процедуры удаляются все непосредственные левые рекурсии , но не удаляется левая рекурсия, включающая два или более шага. Приведенный ниже алгоритм 4.8 позволяет удалить все левые рекурсии из грамматики.

Левая факторизация

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

Если - два A -правила и входная цепочка начинается с непустой строки, выводимой из мы не знаем, разворачивать ли по первому правилу или по второму. Можно отложить решение, развернув . Тогда после анализа того, что выводимо из можно развернуть по или по . Левофакторизованные правила принимают вид

51.Язык машины Тьюринга.

В состав машины Тьюринга входит неограниченная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство (также называется головкой записи-чтения (ГЗЧ )), способное находиться в одном из множества состояний . Число возможных состояний управляющего устройства конечно и точно задано.

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

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

Машина Тьюринга называется детерминированной , если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара «ленточный символ - состояние», для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной .

(Время: 1 сек. Память: 16 Мб Сложность: 20%)

В теории формальных грамматик и автоматов (ТФГиА) важную роль играют так называемые контекстно-свободные грамматики (КС-грамматики). КС-грамматикой будем называть четверку, состоящую из множества N нетерминальных символов, множества T терминальных символов, множества P правил (продукций) и начального символа S, принадлежащего множеству N.

Каждая продукция p из P имеет форму A –> a , где A нетерминальный символ (A из N), а a – строка, состоящая из терминальных и нетерминальных символов. Процесс вывода слова начинается со строки, содержащей только начальный символ S. После этого на каждом шаге один из нетерминальных символов, входящих в текущую строку, заменяется на правую часть одной из продукций, в которой он является левой частью. Если после такой операции получается строка, содержащая только терминальные символы, то процесс вывода заканчивается.

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

Задана КС-грамматика. Требуется найти количество правил, содержащих непосредственную левую рекурсию.

Входные данные

Первая строка входного файла INPUT.TXT содержит количество n (1 ≤ n ≤ 1000) правил в грамматике. Каждая из последующих n строк содержит по одному правилу. Нетерминальные символы обозначаются заглавными буквами английского алфавита, терминальные - строчными. Левая часть продукции отделяется от правой символами –>. Правая часть продукции имеет длину от 1 до 30 символов.

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

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

В рассмотренной выше грамматике G непосредственная рекурсия присутствует в правиле: <чс>-»<чс><цифра>, а в эквивалентной ей грамматике G" - в правиле: T-VTF.

Чтобы рекурсия не была бесконечной, для участвующего в ней нетерминального символа грамматики должны существовать также и другие правила, которые оп­ределяют его, минуя самого себя, и позволяют избежать бесконечного рекурсив­ного определения (в противном случае этот символ в грамматике был бы просто не нужен). Такими правилами являются <чс>-»<цифра> - в грамматике G и T->F -в грамматике G".

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


Определение грамматики. Форма ьэкуса-маура «ЗО /

Если попытаться дать определение тому, что же является числом, то начать мож­но с того, что любая цифра сама по себе есть число. Далее можно заметить, что л юбые две цифры - это тоже число, затем - три цифры и т. д. Если строить определение числа таким методом, то оно никогда не будет закончено (в матема­тике разрядность числа ничем не ограничена). Однако можно заметить, что каж­дый раз, порождая новое число, мы просто дописываем едифру справа (посколь­ку привыкли писать слева направо) к уже написанному ряду цифр. А этот ряд цифр, начиная от одной цифры, тоже в свою очередь является числом. Тогда определение для понятия «число» можно построить таким образом: «число - это любая цифра, либо другое число, к которому справа дописана любая цифра». Именно это и составляет основу правил грамматик G и G" и отражено во второй строке правил в правилах <чс>-><цифра> [ <чс><цифра> и Т->F | TF. Другие правила в этих грамматиках позволяют добавить к числу знак (первая строка правил) и дают определение понятию «цифра» (третья строка правил). Они элементарны и не требуют пояснений.



Принцип рекурсии (иногда его называют «принцип итерации», что не меняет сути) - важное понятие в представлении о формальных грамматиках. Так или иначе, явно или неявно рекурсия всегда присутствует в грамматиках любых ре­альных языков программирования. Именно она позволяет строить бесконечное множество цепочек языка, и говорить об их порождении невозможно без пони­мания принципа рекурсии. Как правило, в грамматике реального язык? програм­мирования содержится не одно, а целое множество правил, построенных с помо­щью рекурсии.

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

Форма Бэкуса-Наура - удобный с формальной точки зрения, но не всегда дос­тупный для понимания способ записи формальных грамматик. Рекурсивные определения хороши для формального анализа цепочек языка, но не удобны с точки зрения человека. Например, то, что правила <чс>-><цифра> | <чс><цифра> отражают возможность для построения числа дописывать справа любое число цифр, начиная от одной, неочевидно и требует дополнительного пояснения.

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

Запись правил грамматик

с использованием метасимволов

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


358 Глава 9. Формальные языки и грамматики

Символы, - которые имеют особый смысл и трактуются специальным образом. В качестве таких метасимволов чаще всего используются следующие символы: () (круглые скобки), (квадратные скобки), {} (фигурные скобки), «,» (запя­тая) и "" (кавычки). Эти метасимволы имеют следующий смысл:

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

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

□ фигурные скобки означают, что указанная внутри них цепочка может не встре­
чаться в данном месте правила грамматики ни одного раза, встречаться один
раз или сколь угодно много раз;

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

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

Вот как должны выглядеть правила рассмотренной выше грамматики G, если их записать с использованием метасимволов:

<число> -» [(+.-)]<цифра>{<цифра>}

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

Вторая строка правил не нуждается в комментариях, а первое правило читается так: «число есть цепочка символов, которая может начинаться с символов + или -, должна содержать дальше одну цифру, за которой может следовать последова­тельность из любого количества цифр». В отличие от формы Бэкуса-Наура, в форме записи с помощью метасимволов, как видно, во-первых, убран из грам­матики малопонятный нетерминальный символ <чс>, а во-вторых - удалось пол­ностью исключить рекурсию. Грамматика в итоге стала более понятной.

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

Запись правил грамматик в графическом виде

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


Определение грамматики. Форма Бэкуса-Наура 359

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

В такой форме записи каждому нетерминальному символу грамматики соответ­ствует диаграмма, построенная в виде направленного графа. Граф имеет следую­щие типы вершин:

□ точка входа (на диаграмме никак не обозначена, из нее просто начинается
входная дуга графа);

□ нетерминальный символ (на диаграмме обозначается прямоугольником, в ко­
торый вписано обозначение символа);

□ цепочка терминальных символов (на диаграмме обозначается овалом, кругом
или прямоугольником с закругленными краями, внутрь которого вписана це­
почка);

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

□ точка выхода (никак не обозначена, в нее просто входит выходная дуга графа).

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

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

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

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



Глава 9. формальные языки и i рамматики


Способа довольно проста. Это можно легко заметить, если посмотреть на описа­ние понятия «число» из грамматики G с помощью диаграмм на рис. 9.1.

Рис. 9.1. Графическое представление грамматики целых десятичных чисел со знаком: вверху - для понятия «число»; внизу - для понятия «цифра»

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

Классификация языков и грамматик

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

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


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

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

 

Возможно, будет полезно почитать: