Стр. 13

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

Словами данного языка может быть далеко не любая абракадабра, доступная клавиатуре. А только лексически и синтаксически (безупречно!) правильные программы. Безупречная с точки зрения грамматики программа может быть бесполезной, бессмысленной или даже вредной. Но за правильную работу программы формальная грамматика и компилятор не отвечают. (Повторим, математика обычно смыслом не занимается).

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

Для того, чтобы задать грамматику, надо задать множества ТЕРМИНАЛЬНЫХ и НЕТЕРМИНАЛЬНЫХ символов. Терминальные символы это символы используемые в языке. Нетерминальные (промежуточные) символы – это символы, используемые в создании (порождении) слов языка. А создаются слова по грамматическим правилам. И каждое слово, напомним, это с точки зрения программиста – программа, записанная исключительно терминальными символами. Далее задаются ГРАММАТИЧЕСКИЕ ПРАВИЛА. Они очень напоминают подстановки в алгорифмах Маркова. Но в отличие от последних порядок применения грамматических правил произвольный. Применение правила заключается в замене в преобразуемой строке какой-то последовательности символов, совпадающей с левой частью какого-то правила, правой частью (последовательностью символов) этого правила.

Введем в оборот из чисто эстетических соображений еще один красивый термин – СЕНТЕНЦИАЛЬНАЯ ФОРМА. Дело в том, что при построении программ в формальных грамматиках всегда танцуют от одного начального нетерминального символа. Обозначим этот символ «программа». Вместо этого символа по одному из грамматических правил происходит подстановка соответствующей правой части, которая может содержать последовательность из каких-то нетерминальных и терминальных символов. Кстати, такой процесс называется НЕПОСРЕДСТВЕННЫМ ПОРОЖДЕНИЕМ. Любой их появившихся нетерминальных символов может быть заменен по подходящему грамматическому правилу какой-то цепочкой символов. То есть начальный нетерминальный символ «программа» последовательно превращается во все более длинную цепочку символов. И так вплоть до того момента, когда в последовательности символов останутся только терминальные символы. То есть будет получено слово данного языка (по иронии судьбы называемое ПРЕДЛОЖЕНИЕМ). Все последовательности символов, которые в процессе непосредственных порождений находятся между начальным нетерминальным символом и конечным предложением и называются сентенциальными формами. А нам остается радоваться, что английский язык нам неродной.

Компилятор, получив программу, выполняет обратную работу. Пред'явленное предложение он свертывает по грамматическим правилам (теперь двигаясь от правой части правила к левой) начального символа «программа».

Обычно существует огромное количество вариантов как порождения, так и свертывания. Если свертывание потерпело неудачу, то должны исследоваться другие варианты. Слово будет признано НЕпринадлежащим данному языку (грамматике), если ни один из вариантов свертывания не приведет к удаче. Поскольку такой перебор вариантов на практике как правило неприемлем, то и грамматики пытаются придумывать не случайные, а с полезными свойствами. А способы свертывания (распознавания) используют эти хорошие свойства, чтобы минимизировать или вообще исключить блуждания.

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

Грамматики первого типа называют КОНТЕКСТНО-ЗАВИСИМЫМИ (или просто КЗ). В большинстве случаев разумно принять общее ограничение, что правило заменяет строго один нетерминальный символ. Отличительная особенность КЗ–правил в том, что замена нетерминального символа на строку допускается, когда этот символ находится в некотором окружении других символов (в контексте). Например, нетерминальный символ «оператор» может быть заменен на нетерминальный символ «пустой оператор», если в преобразуемой строке перед символом «оператор» был другой символ, за которым непосредственно следовал «оператор». А иначе такую замену делать нельзя.

Представьте например, правило официанта. Осуществлять замену грязной тарелки на выписанный счет можно при наличии опустошенного бокала. В другом контексте (при полном бокале [граненом стакане] рядом) вместо грязной тарелки клиенту предлагается новая закуска.

Для того, чтобы грамматика относилась к типу КЗ достаточно, чтобы хотя бы одно правило было именно первого типа. (Остальные могут быть других типов, кроме нулевого).

Грамматики второго типа называют КОНТЕКСТНО-СВОБОДНЫМИ (или просто КС). Каждое правило может применяться без оглядки на контекст. Вместо грязной тарелки – новая закуска (без всяких дополнительных условий)… Грамматики разных типов могут порождать один и тот же язык. Компиляторы диктуют требование приводить грамматику к типу КС. Обычно в рамках уже этого типа накладываются дополнительные ограничения, что позволяет существенно упростить грамматический разбор в компиляторе.

Грамматики последнего третьего типа называются АВТОМАТНЫМИ или РЕГУЛЯРНЫМИ. Это связано с тем, что они порождаются и распознаются автоматами (эту математическую модель ассоциируют не с Калашниковым, а с фамилиями математиков-логиков Мили Мура Трахтенбротта и т. п.) и регулярными выражениями (это, как и в регулярной армии – выражения строятся по простым правилам и просто распознаются – это тоже математическая модель).

Обычно автоматные грамматики используются на уровне лексики. Лексема, в обычном понимании – это словарная единица. Тем ни менее, с точки зрения компилятора это «символ», коль скоро «словом» будет вся программа. В данном случае, например, 345.08 может быть распознан как один символ – действительное число.

Лексический анализ в компиляторе предшествует синтаксическому анализу… Существуют знаменитые команды UNIXlex и yacc, который позволяют автоматизировать процесс написания лексического и синтаксического анализаторов компилятора.

Что– то мы очень уклонились в сторону программирования. Программирование -это тоже математика. Тоже дискретная. Но уже другая. И это другая история.

А из программирования уже, обычно, так просто не возвращаются…

Лекция 13. СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ

Мало того, что есть алгоритмически неразрешимые задачи и их бесконечно больше, чем задач алгоритмически разрешимых. С практической точки зрения нам не легче, если решение разрешимой задачи мы сможем получим через миллион лет. Раньше не закончить расчеты… Это трудно-решаемые задачи. Для нас (простых смертных) такие задачи не отличаются от задач алгоритмически неразрешимых.

А ситуация с такими задачами еще более туманная, чем с алгоритмической разрешимостью. Пока единственный, фактически, «железный» аргумент нашей беспомощности, что задача относится к трудно-решаемым, что никто пока не нашел для нее легкого решения! Даже американские политики.
Вы читаете ДИСКРЕТНАЯ МАТЕМАТИКА БЕЗ ФОРМУЛ
Добавить отзыв
ВСЕ ОТЗЫВЫ О КНИГЕ В ИЗБРАННОЕ

0

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

Отметить Добавить цитату

Материалы, присутствующие на сайте, получены с публичных (широкодоступных) ресурсов. Если вы обладаете авторским правом на какую либо информацию, размещенную на сайте onlinereadsfree.com и не согласны с её общедоступностью в будущем, то мы согласны рассмотреть предложения по удалению определенного материала, а также обсудить предложения о договоренностях, разрешающих использовать данный контент. Мы не отслеживаем действия пользователей, которые самостоятельно выкладывают источники текстов, являющиеся объектом вашего авторского права. Все данные на сайт, загружаются автоматически, не проходя заранее отбора с чьей либо стороны, что является нормой в мировом опыте размещения информации в сети интернет.

Не смотря на это, при возникновении у Вас вопросов касательно ссылок на информацию, размещенную на нашем сайте, правообладателями которой Вы являетесь, просим обращаться к нам с интересующим запросом. Для этого требуется переслать е-mail на адрес: admin@onlinereadsfree.com. В письме настоятельно рекомендуем подать такие сведения : 1.Документальное подтверждение ваших прав на материал, защищённый авторским правом: отсканированный документ с печатью, либо иная контактная информация, позволяющая однозначно идентифицировать вас, как правообладателя данного материала. 2. Прямые ссылки на страницы сайта, которые содержат ссылки на файлы, которые есть необходимость откорректировать.

Все права защищенны onlinereadsfree.com