В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов, страница 3

Можно просто перечислить его цепочки. Если языкбесконечен, необходимо найти для него конечное представление. Это конечное представление, в свою очередь, будет строкой символов над некоторым алфавитом вместе с некоторой интерпретацией, связывающей этопредставление с языком.2.2. ПРЕДСТАВЛЕНИЕ ЯЗЫКОВ15Во-вторых, для любого ли языка существует конечное представление? Можно предположить, что ответ отрицателен. Мы увидим, что множество всех цепочек над алфавитом счетно. Язык – это любое подмножество цепочек. Из теории множеств известно, что множество всех подмножеств счетного множества несчетно.

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

Примером может служить машинная программа. Процедура, которая всегда заканчивается, называетсяалгоритмом.Один из способов представления языка – дать алгоритм, определяющий, принадлежит ли цепочка языку. Более общий способ состоит втом, чтобы дать процедуру, которая останавливается с ответом “да” дляцепочек, принадлежащих языку, и либо останавливается с ответом “нет”,либо вообще не останавливается для цепочек, не принадлежащих языку. Говорят, что такая процедура или алгоритм распознает язык.Такой метод представляет язык с точки зрения распознавания.Язык можно также представить методом порождения.

А именно, можно дать процедуру, которая систематически порождает в определенномпорядке цепочки языка.Если мы можем распознать цепочки языка над алфавитом V либо спомощью процедуры, либо с помощью алгоритма, то мы можем и генерировать язык, поскольку мы можем систематически генерировать всецепочки из V ∗ , проверять каждую цепочку на принадлежность языкуи выдавать список только цепочек языка. Но если процедура не всегдазаканчивается при проверке цепочки, мы не сдвинемся дальше первойцепочки, на которой процедура не заканчивается. Эту проблему можнообойти, организовав проверку таким образом, чтобы процедура никогдане продолжала проверять одну цепочку бесконечно. Для этого введемследующую конструкцию.Предположим, что V имеет p символов.

Мы можем рассматривать цепочки из V ∗ как числа, представленные в базисе p, плюс пустая цепочкаe. Можно занумеровать цепочки в порядке возрастания длины и в “числовом” порядке для цепочек одинаковой длины. Такая нумерация дляцепочек языка {a, b, c}∗ приведена на рис.

2.1, а.ГЛАВА 2. ЯЗЫКИ И ИХ ПРЕДСТАВЛЕНИЕ16Пусть P – процедура для проверки принадлежности цепочки языку L. Предположим, что P может быть представлена дискретными шагами, так что имеет смысл говорить об i-ом шаге процедуры для любой данной цепочки. Прежде чем дать процедуру перечисления цепочекязыка L, дадим процедуру нумерации пар положительных чисел.Все упорядоченные пары положительных чисел (x, y) можно отобразить на множество положительных чисел следующей формулой:z = (x + y − 1)(x + y − 2)/2 + yПары целых положительных чисел можно упорядочить в соответствии со значением z (рис. 2.1, б).123456789...eabcaaabacbabb...yx1 2 3 4 51 1 3 6 10 152 2 5 9 143 4 8 134 7 125 11z(x, y)абРис. 2.1:Теперь можно дать процедуру перечисления цепочек L.

Нумеруемупорядоченные пары целых положительных чисел – (1,1), (2,1), (1,2),(3,1), (2,2), ... . При нумерации пары (i, j) генерируем i-ю цепочку изV ∗ и применяем к цепочке первые j шагов процедуры P. Как только мыопределили, что сгенерированная цепочка принадлежит L, добавляемцепочку к списку элементов L. Если цепочка i принадлежит L, это будет определено P за j шагов для некоторого конечного j. При перечислении (i, j) будет сгенерирована цепочку с номером i. Легко видеть, чтоэта процедура перечисляет все цепочки L.Если мы имеем процедуру генерации цепочек языка, то мы всегдаможем построить процедуру распознавания предложений языка, но невсегда алгоритм.

Для определения того, принадлежит ли x языку L, просто нумеруем предложения L и сравниваем x с каждым предложением. Если сгенерировано x, процедура останавливается, распознав, что xпринадлежит L. Конечно, если x не принадлежит L, процедура никогдане закончится.Язык, предложения которого могут быть сгенерированы процедурой,называется рекурсивно перечислимым.

Язык рекурсивно перечислим,если имеется процедура, распознающая предложения языка. Говорят,2.3. ГРАММАТИКИ17что язык рекурсивен, если существует алгоритм для распознавания языка. Класс рекурсивных языков является собственным подмножествомкласса рекурсивно перечислимых языков. Мало того, существуют языки, не являющиеся даже рекурсивно перечислимыми.2.32.3.1ГрамматикиФормальное определение грамматикиДля нас наибольший интерес представляет одна из систем генерацииязыков – грамматики. Понятие грамматики изначально было формализовано лингвистами при изучении естественных языков. Предполагалось, что это может помочь при их автоматической трансляции. Однако, наилучшие результаты в этом направлении достигнуты при описании не естественных языков, а языков программирования.

Примеромможет служить способ описания синтаксиса языков программированияпри помощи БНФ – формы Бэкуса-Наура.Определение. Грамматика – это четверка G = (N, T, P, S), где(1) N – алфавит нетерминальных символов;(2) T – алфавит терминальных символов, N ∩ T = ∅;(3) P – конечное множество правил вида α → β, где α ∈ (N ∪ T )+ ,β ∈ (N ∪ T )∗ ;(4) S ∈ N – начальный символ (или аксиома) грамматики.Мы будем использовать большие латинские буквы для обозначениянетерминальных символов, малые латинские буквы из начала алфавита для обозначения терминальных символов, малые латинские буквыиз конца алфавита для обозначения цепочек из T ∗ и, наконец, малыегреческие буквы для обозначения цепочек из (N ∪ T )∗ .Будем использовать также сокращенную запись A → α1 |α2 | ...

|αn дляобозначения группы правил A → α1 , A → α2 , ... , A → αn .Определим на множестве (N ∪T )∗ бинарное отношение выводимости⇒ следующим образом: если δ → γ ∈ P , то αδβ ⇒ αγβ для всех α, β ∈(N ∪ T )∗ . Если α1 ⇒ α2 , то говорят, что цепочка α2 непосредственновыводима из α1 .Мы будем использовать также рефлексивно-транзитивное и транзитивное замыкания отношения ⇒, а также его степень k > 0 (обозначаемые соответственно ⇒∗ , ⇒+ и ⇒k ). Если α1 ⇒∗ α2 (α1 ⇒+ α2 , α1 ⇒k α2 ),то говорят, что цепочка α2 выводима (нетривиально выводима, выводима за k шагов) из α1 .Если α ⇒k β (k > 0), то существует последовательность шаговγ0 ⇒ γ1 ⇒ γ2 ⇒ ...

⇒ γk−1 ⇒ γkГЛАВА 2. ЯЗЫКИ И ИХ ПРЕДСТАВЛЕНИЕ18где α = γ0 и β = γk . Последовательность цепочек γ0 , γ1 , γ2 , ... , γk в этомслучае называют выводом β из α.Сентенциальной формой грамматики G называется цепочка, выводимая из ее начального символа.Языком, порождаемым грамматикой G (обозначается L(G)), называется множество всех ее терминальных сентенциальных форм, т.е.L(G) = {w|w ∈ T ∗ , S ⇒+ w}Грамматики G1 и G2 называются эквивалентными, если они порождают один и тот же язык, т.е.

L(G1 ) = L(G2 ).Пример 2.5. Грамматика G = ({S, B, C}, {a, b, c}, P, S), гдеP = {S → aSBC, S → aBC, CB → BC, aB → ab, bB → bb, bC → bc, cC → cc},порождает язык L(G) = {an bn cn |n > 0}.Действительно, применяем n − 1 раз правило 1 и получаем an−1 S(BC)n−1 ,затем один раз правило 2 и получаем an (BC)n , затем n(n − 1)/2 раз правило 3 иполучаем an B n C n .Затем используем правило 4 и получаем an bB n−1 C n . Затем применяем n − 1раз правило 5 и получаем an bn C n . Затем применяем правило 6 и n − 1 раз правило 7 и получаем an bn cn . Можно показать, что язык L(G) состоит из цепочектолько такого вида.Пример 2.6.

Рассмотрим грамматику G = ({S}, {0, 1}, {S → 0S1, S → 01}, S).Легко видеть, что цепочка 000111 ∈ L(G), так как существует выводS ⇒ 0S1 ⇒ 00S11 ⇒ 000111Нетрудно показать, что грамматика порождает язык L(G) = {0n 1n |n > 0}.Пример 2.7. Рассмотрим грамматику G = ({S, A}, {0, 1}, {S → 0S,S → 0A, A → 1A, A → 1}, S). Нетрудно показать, что грамматика порождаетязык L(G) = {0n 1m |n, m > 0}.2.3.2Типы грамматик и их свойстваРассмотрим классификацию грамматик (предложенную Н.Хомским),основанную на виде их правил.Определение. Пусть дана грамматика G = (N, T, P, S).

Тогда(1) если правила грамматики не удовлетворяют никаким ограничениям, то ее называют грамматикой типа 0, или грамматикой без ограничений.(2) еслиа) каждое правило грамматики, кроме S → e, имеет вид α → β,где |α| 6 |β|, и2.3. ГРАММАТИКИ19б) в том случае, когда S → e ∈ P , символ S не встречается в правых частях правил,то грамматику называют грамматикой типа 1, или неукорачивающей.(3) если каждое правило грамматики имеет вид A → β, где A ∈ N ,β ∈ (N ∪T )∗ , то ее называют грамматикой типа 2, или контекстносвободной (КС-грамматикой).(4) если каждое правило грамматики имеет вид либо A → xB, либоA → x, где A, B ∈ N , x ∈ T ∗ то ее называют грамматикой типа 3,или праволинейной.Легко видеть, что грамматика в примере 2.5 – неукорачивающая, впримере 2.6 – контекстно-свободная, в примере 2.7 – праволинейная.Язык, порождаемый грамматикой типа i, называют языком типа i.Язык типа 0 называют также языком без ограничений, язык типа 1 –контекстно-зависимым (КЗ), язык типа 2 – контекстно-свободным (КС),язык типа 3 – праволинейным.Теорема 2.1.

Каждый контекстно-свободный язык может быть порожден неукорачивающей грамматикой.Доказательство. Пусть L – контекстно-свободный язык. Тогда существует контекстно-свободная грамматика G = (N, T, P, S), порождающая L.Построим новую грамматику G0 = (N 0 , T, P 0 , S 0 ) следующим образом:1. Если в P есть правило вида A → α0 B1 α1 ...