В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 4
Текст из файла (страница 4)
Язык — это любое подмножество цепочек. Из теории множеств известно, что множество всех подмножеств счетногомножества несчетно. Хотя мы и не дали строгого определения того, что́является конечным представлением, интуитивно ясно, что любое разумноеопределение этого понятия ведет только к счетному множеству конечныхпредставлений, поскольку нужно иметь возможность записать такое конечноепредставление в виде строки символов конечной длины. Поэтому языковзначительно больше, чем конечных представлений.В-третьих, можно спросить: какова структура тех классов языков, длякоторых существует конечное представление?16Глава 2.
Языки и их представление2.2. Представление языковПроцедура — это конечная последовательность инструкций, которые могут быть механически выполнены. Примером может служить машинная программа. Процедура, которая всегда заканчивается, называется алгоритмом.Один из способов представления языка — дать алгоритм, определяющий,принадлежит ли цепочка языку.
Более общий способ состоит в том, чтобыдать процедуру, которая останавливается с ответом «да» для цепочек, принадлежащих языку, и либо останавливается с ответом «нет», либо вообще неостанавливается для цепочек, не принадлежащих языку. Говорят, что такаяпроцедура или алгоритм распознает язык.Такой метод представляет язык с точки зрения распознавания. Язык можно также представить методом порождения.
А именно, можно дать процедуру,которая систематически порождает в определенном порядке цепочки языка.Если мы можем распознать цепочки языка над алфавитом V либо с помощью процедуры, либо с помощью алгоритма, то мы можем и генерироватьязык, поскольку мы можем систематически генерировать все цепочки из V ∗ ,проверять каждую цепочку на принадлежность языку и выдавать список только цепочек языка. Но если процедура не всегда заканчивается при проверкецепочки, то мы не сдвинемся дальше первой цепочки, на которой процедуране заканчивается.
Эту проблему можно обойти, организовав проверку такимобразом, чтобы процедура никогда не продолжала проверять одну цепочкубесконечно. Для этого введем следующую конструкцию.Предположим, что V имеет p символов. Мы можем рассматривать цепочкииз V ∗ как числа, представленные в базисе p, плюс пустая цепочка e. Можнозанумеровать цепочки в порядке возрастания длины и в «числовом» порядкедля цепочек одинаковой длины.Пусть P — процедура для проверки принадлежности цепочки языку L.Предположим, что P может быть представлена дискретными шагами, так чтоимеет смысл говорить об i-м шаге процедуры для любой данной цепочки.Прежде чем дать процедуру перечисления цепочек языка L, дадим процедурунумерации пар положительных чисел.Все упорядоченные пары положительных чисел можно взаимнооднозначно отобразить на множество положительных чисел и тем самымупорядочить.
Теперь можно дать процедуру перечисления цепочек 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)2.3.
Грамматики17будет сгенерирована цепочка с номером i. Легко видеть, что эта процедураперечисляет все цепочки L.Если мы имеем процедуру генерации цепочек языка, то мы всегда можемпостроить процедуру распознавания предложений языка, но не всегда алгоритм. Для определения того, принадлежит ли x языку L, просто нумеруемпредложения L и сравниваем x с каждым предложением. Если сгенерировано x, то процедура останавливается, распознав, что x принадлежит L.Конечно, если x не принадлежит L, то процедура никогда не закончится.Язык, предложения которого могут быть сгенерированы процедурой, называется рекурсивно перечислимым. Язык рекурсивно перечислим, еслиимеется процедура, распознающая предложения языка. Говорят, что языкрекурсивен, если существует алгоритм для распознавания языка.
Класс рекурсивных языков является собственным подмножеством класса рекурсивноперечислимых языков. Мало того, существуют языки, не являющиеся дажерекурсивно перечислимыми.2.3. Грамматики2.3.1. Формальное определение грамматики. Для нас наибольшийинтерес представляет одна из систем генерации языков — грамматики.Понятие грамматики изначально было формализовано лингвистами для естественных языков. Предполагалось, что это может помочь при машинномпереводе. Однако наилучшие результаты в этом направлении достигнуты приописании не естественных языков, а языков программирования.
Примеромможет служить способ описания синтаксиса языков программирования припомощи БНФ — формы Бэкуса–Наура.Определение 2.1. Грамматика — это четверка G = (N , T , P , S), где:1) N — алфавит нетерминальных символов;2) T — алфавит терминальных символов, N ∩ T = ∅;3) P — конечное множество правил вида α → β , где α ∈ (N ∪ T )∗ N (N ∪∪ T )∗ , β ∈ (N ∪ T )∗ ;4) S ∈ N — начальный знак (или аксиома) грамматики.Мы будем использовать большие латинские буквы для обозначения нетерминальных символов, малые латинские буквы из начала алфавита для обозначения терминальных символов, малые латинские буквы из конца алфавитадля обозначения цепочек из T ∗ и, наконец, малые греческие буквы дляобозначения цепочек из (N ∪ T )∗ .Будем использовать также сокращенную запись A → α1 |α2 | .
. . |αn | дляобозначения группы правил A → α1 , A → α2 , . . . , A → αn .18Глава 2. Языки и их представлениеОпределим на множестве (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 ,где α = γ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 → 0S 1, S → 01}, S).Легко видеть, что цепочка 000111 ∈ L(G), так как существует выводS ⇒ 0S 1 ⇒ 00S 11 ⇒ 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.
Типы грамматик и их свойства. Рассмотрим классификациюграмматик (предложенную Н. Хомским), основанную на виде их правил.2.3. Грамматики19Определение 2.2. Пусть дана грамматика G = (N , T , P , S). Тогда:1) если на правила грамматики не наложены никакие ограничения, то ееназывают грамматикой типа 0, или грамматикой без ограничений.2) еслиа) каждое правило грамматики, кроме S → e, имеет вид α → β , где|α| 6 |β|, иб) в том случае, когда 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.Построим новую грамматику G′ = (N ′ , T , P ′ , S ′ ) следующим образом.1.
Если в P есть правило вида A → α0 B1 α1 . . . Bk αk , где k > 0, Bi ⇒ ++e для 1 6 i 6 k, и ни из одной цепочки αj (0 6 j 6 k) не выводится e,то включить в P ′ все правила (кроме A → e) видаA → α0 X1 α1 . . . Xk αk ,где Xi — это либо Bi , либо e.2. Если S ⇒ + e, то включить в P ′ правила S ′ → S , S ′ → e и положить′N = N ∪ {S ′ }; в противном случае положить N ′ = N и S ′ = S .Порождает ли грамматика пустую цепочку, можно установить следующимпростым алгоритмом.20Глава 2. Языки и их представлениеШ а г 1 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
