Существуют два основных механизма определения языков [Ахо, Ульман 1978].
Грамматики образуют наиболее важный класс генераторов языков. Грамматика - это математическая система, определяющая язык. Наиболее известной иерархией грамматик и языков является иерархия Хомского. Эта иерархия включает четыре типа грамматик, последовательно вводящих все более сильные ограничения на форму правил грамматики [Фитиалов 1984]. К этим четырем типам в [Grune, Jacobs 1998] добавлен еще один (в нашей нумерации - тип 4), достаточно широко используемый.
В табл. 4.2 представлены две иерархии грамматик - Хомского (монотонная) и укорачивающая (немонотонная) [Grune, Jacobs 1998].
Таблица 4.2. Иерархия грамматик
| Типы грамматик | Иерархия Хомского (монотонная) | Немонотонная (укорачивающая) иерархия |
| Тип 0 | Грамматики без ограничений на структуру (Монотонные грамматики со стирающими правилами) | Грамматики без ограничений на структуру |
| Тип 1 | Контекстно-зависимые грамматики (Монотонные грамматики без стирающих правил) | Контекстно-зависимые грамматики с немонотонными правилами |
| Тип 2 | Контекстно-свободные грамматики без стирающих правил | Контекстно-свободные грамматики |
| Тип 3 | Регулярные грамматики (без стирающих правил) | Регулярные грамматики, регулярные выражения |
| Тип 4 | Конечный выбор | Конечный выбор |
Техника разбора позволяет связать грамматику и предложения языка. Существует две основные техники разбора, каждая из которых воплощена во многих методах.
Некоторые основные техники распознавания приведены в табл. 4.3 [Grune, Jacobs 1998].
Таблица 4.3. Техники распознавания
| Методы | Сверху вниз | Снизу вверх |
| Непрямые методы | Распознаватель Унгера | Распознаватель КЯК (Кока, Янгера, Касами) |
| Прямые методы | predict/match | shift/reduce |
| Линейно-направленные методы: сначала в ширину с шириной, ограниченной 1 | Единственный метод: - LL(k) |
Большой набор методов: - Предшествования - Контекстно - связанные - LR(k) - LALR(1) - SLR(1) |
| Эффективные методы общей направленности: максимально ограниченный поиск сначала в ширину | (нет известных методов) | Распознаватель Томита |
На рис. 4.38 представлено образное сравнение типов грамматик [Grime, Jacobs 1998]. Пусть роза на рисунке представляет язык, молекулы розы соответствуют предложениям языка. Грамматики будут обрисовывать контур розы.
На сегодняшний день существует довольно много оригинальных методов осуществления трансляций, но так и не возникло никаких серьезных подходов к созданию теории метатрансляции. Если проводить параллели с математикой, то можно сказать, что информатика находится на этапе зарождения своей собственной логики или формализованной системы, сводящей воедино все богатство накопленного "сырого материала". Данная параллель более чем уместна, т. к. один из основных объектов изучения информатики - формализованное понятие алгорифма - может быть воспринят как трансляция некоторого класса.
Во всех существующих подходах к проблеме трансляции присутствует один серьезный недостаток - трансляция всегда жестка. В каждой формализованной схеме трансляции у нас есть одна или несколько заранее зафиксированных систем, при помощи которых мы можем осуществлять трансляцию некоего входа. Как видно, переменной величиной здесь является лишь вход, и, возможно с некоторой натяжкой, проблемная область, приведшая к фиксированию именно таких, а не иных систем.
Можно посмотреть на проблему с другой стороны и считать, что мы располагаем некоторым универсальным множеством всевозможных систем, осуществляющих трансляции цепочек конкретного языка. В этом случае возникает интересный вопрос - можно ли, применив это множество к определенному входу, странслировать этот вход адаптивно, т. е. таким образом, чтобы часть его транслировалась одним способом, часть другим, и сам факт выбора некоторого механизма для трансляции части входа регулировался самим же входом и уже странслированной частью. Видимо ближе всего к этому подошел язык программирования РЕФАЛ, несмотря на то, что он позиционируется как многофункциональный язык. РЕФАЛ содержит два весьма важных понятия - конкретизационные скобки и сопоставление с образцом. Действительно, динамический характер "блуждания" конкретизационных скобок по цепочке символов, а также тот факт, что одному и тому Же формальному вхождению свободной переменной могут соответствовать разные значения (в одном и том же трансляционном "сеансе") как раз и приближает нас к решению декларированной задачи об адаптивной трансляции.
Интересная задача может возникнуть при исследовании способов компактификации спецификации некоторых подклассов контекстно-свободных грамматик. Под компактификацией понимается способ записи грамматики таким образом, чтобы сам способ "подсказывал" вид порождаемого языка. Для одного частного случая контекстно-свободных грамматик, а именно для автоматных грамматик, эта задача уже решена и ответ на нее носит название "регулярные выражения". Следует принимать во внимание также и тот факт, что нереально решить эту задачу для всего класса контекстно-свободных грамматик. Таким образом, на передний план здесь выходят эвристические приближения к идеалу.
Во многих областях современного системного и прикладного программирования приходится иметь дело с такими хорошо структурированными, наиболее просто описывающимися входными данными, как язык, специфицируемый некоторой контекстно-свободной грамматикой. Было бы неразумно отказываться от возможности автоматической генерации трансляторов с такого класса языков. Однако проблема до сих пор в полной мере не решена. На сегодняшний день в мире не существует единого, универсального подхода к вопросу спецификации семантического значения для цепочек, принадлежащих к какому-либо языку, неважно, формальному или естественному.
Математическая постановка задачи синтаксического анализа предельно проста и фактически представляет собой задачу спецификации соответствия между некоторыми двумя множествами формальных объектов. Однако существует огромная разница между подходами математика и программиста к описанию соответствий между такого рода объектами. Прежде всего, эту разницу можно объяснить тем, что для математика не так важна временная составляющая, ибо рассматриваемые им объекты существовали, существуют, и будут существовать во времени независимо от того, каким образом они были определены. Таким образом, единственной проблемой может стать установление формальной идентичности двух определений одного и того же объекта. В случае программиста мы имеем несколько иную ситуацию, а именно, все формальные объекты, с которыми ему приходится работать либо атомарны, либо создаются на основе атомарных объектов за вполне конечное время, причем обычно, крайне желательным является минимизировать количество времени, затрачиваемого на построение полной иерархии объектов, решающих ту или иную задачу.
Вообще говоря, процесс задания трансляции есть не что иное, как конструктивное описание некоторой функции, в общем случае обладающей свойством инъективности. С математической точки зрения для этого достаточно каким-либо образом описать подмножество (возможно бесконечное) декартового произведения двух множеств. С точки зрения программиста такой подход не только недопустим, но и зачастую невозможен, поскольку простое перечисление элементов такого подмножества вероятно лишь в случае его конечности. Таким образом, первоочередной проблемой становится решение задачи отыскания скрытой структуры, описывающей способ построения по каждому элементу первого множества его образа относительно интересующей нас функции во втором множестве. Иными словами, должен существовать некоторый "закон", согласно которому, рассмотрев структуру произвольного, элемента, мы сможем найти структурно подобный ему образ во втором множестве. Фактически мы разбиваем задачу на две подзадачи:
Задача синтаксического анализа, в классическом понимании, это процесс структурирования некоторого представления при помощи заранее заданной грамматики. Разумеется, существенным условием, накладываемым на грамматику, является условие конечности набора ее правил. Множество же представлений, напротив, чаще всего оказывается бесконечным. Мы не будем углубляться здесь в теоретические и философские аспекты задачи синтаксического анализа, а лишь отметим, что методы, используемые для ее решения, вообще говоря, мажорируют методы синтаксически управляемой трансляции. То есть, мы можем синтезировать образы лишь тех представлений, чью структуру мы в состоянии распознать. Отметим также, что на практике под грамматиками понимают грамматики в смысле Хомского, причем для большинства задач, связанных с формальными языками, оказывается достаточным ограничиться классом контекстно-свободных грамматик. Следствием такого ограничения является тот факт, что структура представлений носит ярко выраженный иерархический характер, наилучшим образом описываемый деревом вывода в заданной грамматике.
При введенных выше ограничениях задача трансляции превращается в проблему спецификации механизма, строящего некоторое представление по дереву вывода в заданной грамматике. Спецификация такого рода наиболее просто осуществляется при помощи привязки семантических атрибутов и способов их преобразования к каждому правилу грамматики. Таким образом, каждый узел дерева вывода оказывается снабженным собственным семантическим атрибутом, а под результатом трансляции мы понимаем семантический атрибут, приписанный корневой вершине. Данный подход носит название атрибутивных грамматик.
Приведем описание языка спецификации грамматик для системы, реализующей синтаксически управляемую трансляцию. Это система yacc, входной язык которой принадлежит к классу LR(1) или, более точно, LALR(1). Подробно система будет рассмотрена в разд. 5.2.4.3.
Входные данные для системы определяются одним или несколькими ASCII-файлами, содержащими спецификацию грамматики входного языка в расширенной формальной системе обозначений Бэкуса-Наура (RBNF). Любой входной файл обязан иметь следующую структуру:
%{
<секция операторов языка>
%}
<секция описаний>
%%
<секция грамматических правил и семантических процедур>
%%
<вторая секция операторов языка >
Символы %% - являются специальными синтаксическими разделителями.
<секция операторов языка C> является необязательной. Она может содержать операторы типа #include, описания и т. п.
<секция описаний> содержит лексемы, грамматические переменные, информацию о приоритетах и ассоциативности:
<секция грамматических правил и семантических процедур> представляет собой набор строчек, определяющих отдельные правила, которые могут включать семантические процедуры.
<вторая секция операторов языка C> также является необязательной. Она может Содержать операторы типа main (){...; yyparse () ; . . . }, yylex (){...} и др.
Входные данные преобразуются в функцию разбора с именем yyparse () и записываются в виде файла на языке программирования С. Далее эту функцию можно откомпилировать, связать с другими программами и выполнить.
|
|
 |
