Файл: Алферова З.В. Теория алгоритмов учеб. пособие.pdf

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

установление связи между видами языков с их структурными деревьями и формой синтаксических правил;

изучение структурных свойств языков, порождаемых некоторой формой правил (З-грамматики;

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

установление разного рода проблем разрешимости L языка от­ носительно заданной G-грамматики и класса G-грамматик;

установление мощности G-грамматики, порождающей модели­ рующий L язык в зависимости от контекста применения последнего; оценка порождающей способности G-грамматик, а следователь­ но, определение эквивалентности порождаемого разными грамма­

Наибольшее развитие получила проблема синтаксического ана­ лиза грамматик и контроля соответствующих им языков, состоя­

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

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

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

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

130

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

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

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

НВС -> НВс; НВС -> hBC; ВС -> be; HB^hb. •

Рассмотрим слово hbc. Это слово может быть разобрано двумя различными способами. Деревья грамматического разбора этого слова приведены на рис. 15.

Рис. 15

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

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

Правила грамматики языка имеют вид:

налево. В первом случае в слове выбирается первая доступная для замещения совокупность символов DE в соответствии с заданными

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

Для нашего примера просмотр слева направо дает дерево Грам­ матического разбора, представленное на рис. 16а.

B E T H D E F H

Рис. 16

Цифры в кружках означают порядок разбора. Результативные деревья идентичны. Разница состоит лишь в процессе разбора: для а — слева по строке, для б — справа по строке.

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

Канонический вид грамматического разбора — это разбор, ко­ торый применяется слева направо по строке. При этом в первую очередь разбирается крайне левая часть предложения, если это возможно, прежде чем продвинуться по строке вправо для поиска доступной разбору ситуации. На рис. а представлен канонический

грамматический разбор предложения. Однако канонически упоря­ доченный грамматический разбор не всегда может быть использо­ ван. Рассмотрим примеры:

132

Пример 1. Задана грамматика

А ->х

левая рекурсия)

А-^Ах

и строка хххх. Канонический разбор приведен на рис. 17. Пример 2. Задана грамматика

А -*• х

(правая рекурсия)

как он не может быть выполнен (приводит в тупик). Граммати­

XXI

Рис. 18

Пример 3. Задана грамматика

А ~> х

(центральная рекурсия)

А-> хАх

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

Из рассмотренных примеров 1, 2, 3 можно сделать вывод, что путь разбора предложения определяется типом рекур­ сии в правилах вывода грамматики. Пра­ вая рекурсия предопределяет граммати­ ческий разбор, начинающийся справа. Левая рекурсия предопределяет успеш­

ный канонический вид грамматическогоразбора.

ка, лишь после окончательного прохождения анализируемого тек­ ста.

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

1)правильность или ошибочность строки определяется не сразу на каждом шаге разбора, а лишь после окончания анализируемого текста;

2)правильный путь порождения находится после проверки всех возможных путей разбора;

3)выбор ложного пути требует обратного возвращения к по­ следнему, правильно определенному состоянию;

4)при реализации на машине очень трудно осуществляется связка семантических правил с синтаксическими.

Все это отрицательно сказывается на методе с точки зрения по­ тери времени.

Вместе с тем эвристическим методам присущи и некоторые пре­ имущества: возможность применения ко всем языкам, что делает их универсальными; ориентация либо «на цель», либо «от цели»,

со строки s и состоит в просмотре последовательностей, получае­ мых в результате разбора, ведущего к S (к цели). Формализованно цель такого разбора можно представить так: s => 5, т. е. в резуль­ тате грамматического разбора определяется, является ли данная строка предложением.

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

Грамматический разбор методом «сверху вниз», называемый методом «спуска» (или «рекурсивного спуска»), начинается от це­ ли S (т. е. от отправного правила порождения или вывода), и да­ лее рассматривается последовательность таких порождений, кото­ рые бы привели к s. Формализованное представление такого раз­

Оба эти метода можно представить одними и теми же деревья­ ми порождений, только в одном случае корень дерева внизу, в дру­ гом — вверху. Так, разбор слова wxyz для примера 4, приведенный обоими методами, представлен на рис. 21.

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

Разработка каждого метода привяаана к определенным классам машин (малого, среднего или большего типа) и к определенным