Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 41
Текст из файла (страница 41)
Ни один КА с числом состояний ровно 148 не сможет надежно принять цепочку символов длиной больше 147. Рис. 4.1. Использование регулярной грамматики в счетчике + Грамматики такого типа часто используются в сканерах (лексических анализаторах) компиляторов для распознавания отдельных лексем (идентификаторов, литералов и строк) илн ключевых слов данного языка (например, т(, Ьейт(п, ууЬ11е). В качестве примера можно рассмотреть регулярную грамматику, генерирующую идентификаторы Разса1 (которые, как вы помните, состоят нз букв и цифр, причем на первом месте стоит буква, то есть имеют вид буква(буквачцифра)*).
Она задается следующим образом: идентификатор -т ах) л вх)а Ь /х Х -т аХ!..!ХХ/0Х!..4 9Х/а Ь /т/0(4 9 14Е Глава 4. Моделирование свойств языка Контекстно-свободные грамматики (тип 2~ Правила таких грамматик являются правилами уже известных нам НФБ-грамма- тик. Они записываются в форме х — з и, где под а понимается любая последова- тельность терминальных или нетерминальных символов. Эти грамматики характеризуются следующими свойствами.
+ Многие свойства такой грамматики являются разрешимыми. (Это означает, что можно получить ответы, например, на такие вопросы: генерирует ли данная грамматика какие-либо цепочки? Сгенерирована ли этой грамматикой данная цепочка языка? Является ли язык, порожлаемый грамматикой, пустым?) + Такие грамматики можно использовать для подсчета вхождения в цепочку двух символов и последуюшего сравнения.
То есть они характеризуются цепочками вида а"сЬ" для любого л. + Контекстно-свободная грамматика может быть реализована» при помощи стеков. Для распознавания цепочки а"сЬ" из предыдущего пункта можно занести в стек цепочку а", затем проигнорировать с и сравнить содержимое стека с цепочкой Ь", чтобы удостовериться в одинаковой длине этих двух цепочек, + Как описано в главе 3, эти грамматики можно использовать для автоматического построения дерева грамматического разбора. + Грамматики типа 2 и типа 3 по большей части более не представляют интереса и не явля ются объектом исследований.
Судя по всему, все важные свойства втих грамматик уже изучены. В качестве примера приведем следующую грамматику, опрелеляюшую обыч- ное арифметическое выражение: Š— +ЕеТ / Т Т вЂ” зТ*Р ! РР— зз / гЕ) Контекстно-зависимые грамматики (тип 1) Такой тип грамматики характеризуется правилами вида: и — > В где сс — это любая цепочка, состоящая из нетерминальных символов,  — любая цепочка, состоящая из терминальных и нетерминальных символов, и количество символов в а меньше или равно количеству символов в В. Ниже перечислены некоторые свойства контекстно-зависимых грамматик: + Все цепочки, последовательно выводимые из начального символа, имеют длину не меньшую, чем предыдущая, поскольку каждое правило должно оставлять длину цепочки неизменной илн увеличивать ее'.
+ Контекстно-зависимые грамматики генерируют цепочки, для хранения которых требуется фиксированный объем памяти. Например, такие грамма- В связи с указаннзгм свойством контекстно-зависимых грамматик их еще называют неукорачивающими грамматиками. — Прииеч. наум. Ред. 4.1.
Формальные свойства языков 147 тики способны распознавать цепочки вида а'Ь"с", что нс может сделать контекстно-свободная грамматика. + Контекстно-зависимые грамматики обычно слишком сложны, чтобы быть практически полезными для моделирования языков программирования. + Некоторые свойства контекстно-зависимых грамматик до сих пор нс исследованы. В разделе 4.1.3 мы коснемся теоретической задачи доказательства НП-полноты, то есть проблемы эквивалентности детерминированных и не- детерминированных контекстно-зависимых грамматик. В качестве примера рассмотрим генерацию строки ха "Ь"с" при помощи контекстно-зависимой грамматики: х — АВСКП СВ -» ВС СА -» АС ВА -» АВ ССУ -» Сус ВСт -» Втс ВВУ ВУЬ АВУ -» АУЬ ААУ вЂ » Ауз АУ вЂ » хз Грамматики с фразовой структурой (тип О) Этот тип грамматик характеризуется ничем неограниченным набором правил вида а — з )), где а — это любая строка нетсрминальных символов, а)з — любая строка, составленная из терминальных или нетерминальных символов'.
Свойства этого типа грамматик следующие; + Они могут использоваться для распознавания любой вычислимой функции. Например, можно создать грамматику (хотя это и нс очень просто) для цепочки а'Ьн"', представляющей функцию т(п). По заданному п — числу элементов а, эта грамматика генерирует цепочку, содержащую Г(п) элементов Ь.
+ Большая часть свойств этих грамматик относится к икразрешилгым (см. раздел 4.1.3). Это означает, что не существует процесса, с помощью которого можно было бы определить, выполняется ли данное свойство для всех грамматик данного типа (например, является ли множество цепочек данного языка пустым?). Отличие от контекстно-зависимых грамматик заключается в том, что у последних о многих свойствах просто ничего нс известно — они могут быть истинными, ложными или быть неразрешимыми. 4.1.2. Неразрешимость При обсуждении иерархии Хомского вы могли заметить, что по мере продвижения от грамматик типа 3 к грамматикам типа О усложнялись соответствующие язы- В англоязычной научной литературе в связи с отсутствием ограничений на набор правил грамматики их так и называют за пгезт гатей Вгаюглагз» вЂ” »неограниченные грамматики».
— Примеч. науч. ред. 148 Главад. Моделирование свойств языка ки. Мы знаем, что современные компьютеры работают очень быстро и обладают почти невероятными способностями в области решения задач. Поэтому закономерен следую пьий вопрос существует ли какой-либо предел для вычислений с помощью компьютера? Рассмотрим следующую практическую задачу.
Вместо того чтобы тестировать программу, написанную, скажем, на языке С, нельзя ли написать некоторую другую программу, которая могла бы по описанию С-программы (например, по ее исходному файлу с текстом программы) опрелелить, произойдет ли остановка во время выполнения последней? Такая тестирующая программа была бы чрезвычайно полезна, так как с ее помощью можно было бы избежать многочисленных проверок программ, которые со временем входят в бесконечныс циклы. Но если вы попробуете написать такую тестирующую программу, вы убедитесь, что это чрезвычайно сложная, практически невыполнимая задача.
Дело не в том, что у вас для этого недостаточно знаний или способностей; написать такую программу не пол силу никому. Это ограничение — одно нз слслствий той математической системы, которая используется для написания программ, что становится ясным при изучении языков типа О. В этом разлеле мы обсудим некоторые аспекты возникшей проблемы. Машины Тьюринга Когда мы программируем на некотором языке (назовеьг этот язык Л), обычно достаточноочевилно, чтоэквивалентная программаможетбыть написана наязыке В. Например, если вы пишете программу для составления платежной ведомости на языке СОВО1., то такую же программу вы могли бы написать на языках С или ГОВТВЛ1ч; возможно, несколько сложнее было бы написать сс на Е!5Р или М1 .
Существуют ли такие программы, которые могут быть написаны только на какомто конкретном языке, то есть длн которых невозможна эквивалентная замена программой, написанной на другом языке? Например, возможны лп программы на 1 1БР или Рго!оц, для которых не существует эквивалентной программы на языке ЕОКТВАХ? Для того чтобы точнее сформулировать данный вопрос, нужно ввести понятиеуниаерсального языка ирограммириванил. Универсальный язык программирования — это такой язык, на котором можно запрограммировать л|обое вычисление. Тогда вопрос сводится к следующсму: леляюася ли все стандарглные языхи программирования универсальными? Если нет, то какие типы программ не могут быть написаны ни на каком другом языке, кроме некоторого одного? Если да, то зачем нам нужно такое количество различных языков программирования? Может быть, следует выбрать из них какой-то олин, наиболее простой, который позволит обойтись беэ всех остальных языков? В первую очередь отметим, что этот вопрос можно переформулировать в терминах функций, вычисляемых программой.
Эквивалентность некоторой программы Р на языке А какой-либо другой программе О, написанной на языке В, означает, что обе эти программы вычисляют одну и ту же функцию. Иначе говоря, в каждом конкретном случае обе программы получают одни и те же входные данные и на выходе выдают одни и те же результаты. Универсальным является такой язык и рограммирования, на котором для любой вычислимой функции может быть составлена программа. Функция называется вы числ им ой, если для нее може~ быть состав- 4.1, Формальные свойства языков 149 лена программа на каком-либо из языков программирования. Такая формулировка проблемы несколько напоминает порочный круг, так как мы сталкиваемся с фундаментальным вопросом определения того, что такое веччислимая груикция.
Интуитивно понятно, что функцию можно назвать вычислимой, если существует какая-либо процедура, которая шаг за шагом может вычислить значение этой функции. При этом подразумевается, что процедура должна быть конечна во времени. Тем не менее, чтобы определить класс всех вычислимых функций, нам нужно предложить некий универсальный виртуальный компьютер или универсальный язык программирования, на котором эти функции могут быть выражены. Теперь проблема заключается в том, что мы не знаем, как определить, что язык универсален. Оказывается, этот вопрос рассматривался еще до того, как появились первые компьютеры. В 30-е гг.
математики исследовали задачу определения класса вычислимых функпий. Некоторые ученые лля решения этой задачи предложили использовать простые абстрактные машины, или автоматы, которые могли бы служить отправной точкой для определения класса вычислимых функций. Наиболее известной из них является мишина Тьюринга, названная так в честь своего изобретателя, Ллана Тьюринга (Л!ап Тнг1пц) [114]. В машине Тьюринга имеется только одна простая структура данных — линейно-упорядоченный массив переменной длины, называемый рабочей лентой. Каждый элемент, или ячейка, рабочей ленты содержит только один символ.
Имеется также одна простая переменная-указатель, называемая улравляюи1ей головкой, которая в любой момент времени указывает на некоторую ячейку рабочей ленты. Машина Тьюринга управляется программой, в которую может входить только несколько простых операций, 1. Можно прочитать символ, хранящийся в ячейке рабочей ленты, на которую указывает управляющая голонка, или записать в эту ячейку новый символ (то есть заменить старый символ новым). В зависимости от прочитанного символа программа может совершить условный переход.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
