Семантическая подпрограмма
Cтраница 3
Синтаксис входного языка задается таблицей порождающих правил. Используя эту таблицу, матрицу предшествования можно построить автоматически по правилам, описанным в 5.3.4. Семантика входного языка в терминах выходного языка отражена в семантических подпрограммах, которые составляются вручную. [31]
В принципе описываемый транслятор пригоден для перевода с нескольких входных языков, грамматики которых - грамматики предшествования, на несколько выходных языков. Транслятор, переводящий с М входных языков на N выходных, должен иметь М экземпляров таблиц порождающих правил и матриц предшествования и М X N наборов семантических подпрограмм. Однако за универсальность транслятора в классе грамматик предшествования приходится платить сравнительно невысокой эффективностью алгоритмов трансляции. [32]
Распознаватель, описанный правилами подстановки, нетрудно переписать а виде набора синтаксических подпрограмм. Например, алгоритм распознавателя ( транслятора для перевода в обратную польскую запись), заданный таблицей 5.26, можно записать в виде пяти подпрограмм с именами ПО, ВО-МО-ТО, Ml, Т1 и В1, в которые включены соответствующие семантические подпрограммы ОШИБКА 1, СП1, СП2, СПЗ и ВЫХОД. [33]
В матрице переходов указаны номера подпрограмм распознавателя. В подпрограммах меткой ОШИБКА помечена подпрограмма выдачи сообщения об ошибке, меткой ВЫЗОВ - блок ВЫЗОВ распознавателя ( см. рис. 5.26), а меткой ВЫХОД - выход при успешном окончании разбора. На месте семантической подпрограммы ( или обращения к семантической подпрограмме) записан текст, описывающий действия, выполняемые семантической подпрограммой. [34]
Распознаватель также использует таблицу порождающих правил, а вместо матрицы предшествования-матрицу операторного предшествования или функции операторного предшествования. Генератор содержит набор семантических подпрограмм. [35]
Небольшие отличия имеет алгоритм распознавателя и таблица порождающих правил. Отыскивая эту фразу и выполняя редукцию, распознаватель не обращает внимания на нетерминальные символы приводимой первичной фразы. Нетерминальные символы учитываются только семантическими подпрограммами, если это необходимо. Поэтому порождающие правила, в правых частях которых имеются лишь нетерминальные символы, вообще никогда не используются распознавателем, и их можно не включать в таблицу порождающих правил распознавателя. В правых частях остальных порождающих правил все различные нетерминальные символы часто можно заменить одним символом, например символом N, обозначающим произвольный нетерминальный символ. [36]
В качестве примера в табл. 5.15 представлена таблица порождающих правил распознавателя применительно к грамматике GI. В таблицу не включены правила грамматики Gb содержащие в правых частях только нетерминальные символы ( правила В - Т и Т - М), а в правых частях всех остальных правил нетерминальные символы заменены символами N. Кроме того, таблица дополнена семантическими подпрограммами для перевода арифметиче ских выражений в обратную польскую запись. [37]
Фактически распознаватель для грамматики с операторным предшествованием без помощи семантических подпрограмм не может найти полный разбор входной строки. Он отыскивает лишь сокращенный разбор, в котором отсутствуют элементы, отличающиеся только нетерминальными символами. Следовательно, этот распознаватель без привлечения семантических подпрограмм неспособен выполнить полный синтаксический контроль. Это делает метод операторного предшествования менее надежным, чем метод предшествования. Однако неполнота разбора имеет определенное преимущество: сокращаются объем таблицы порождающих пра вил и число шагов трансляции, поскольку из разбора исключены шаги, редуцирующие части строки, состоящие только из нетерминальных символов. [38]
В матрице переходов указаны номера подпрограмм распознавателя. В подпрограммах меткой ОШИБКА помечена подпрограмма выдачи сообщения об ошибке, меткой ВЫЗОВ - блок ВЫЗОВ распознавателя ( см. рис. 5.26), а меткой ВЫХОД - выход при успешном окончании разбора. На месте семантической подпрограммы ( или обращения к семантической подпрограмме) записан текст, описывающий действия, выполняемые семантической подпрограммой. [39]
Распознаватель решает задачу разбора. В процессе синтаксического анализа распознаватель использует матрицу предшествования ( или функции предшествования) и таблицу порождающих правил грамматики входного языка. Каждая запись этой таблицы содержит одно из порождающих правил и ( для некоторых правил) имя семантической подпрограммы, которую нужно выполнить, когда это правило применяется для редукции. [40]
В матрице переходов указаны номера подпрограмм распознавателя. В подпрограммах меткой ОШИБКА помечена подпрограмма выдачи сообщения об ошибке, меткой ВЫЗОВ - блок ВЫЗОВ распознавателя ( см. рис. 5.26), а меткой ВЫХОД - выход при успешном окончании разбора. На месте семантической подпрограммы ( или обращения к семантической подпрограмме) записан текст, описывающий действия, выполняемые семантической подпрограммой. [41]
Для этого нужно прежде всего - стандартизировать лексику входных языков, т.е. правила записи служебных слов, идентификаторов и констант, а также алфавит. Алгоритм распознавателя универсален з классе грамматик предшествования. Алгоритм генератора предельно прост - - генератор вызывает требуемую семантическую подпрограмму и передает ей аргументы, определяемые элементом разбора. [42]
 |
Дерево разбора. [43] |
Второе и третье требования, как и аналогичные требования к грамматике предшествования, обеспечивают беступиковость алгоритма разбора. Строго говоря, перечисленные требования не гарантируют однозначности алгоритма разбора. Это будет видно из дальнейшего. Однако характер возможных неоднозначностей таков, что они без особого труда устраняются семантическими подпрограммами. [44]
Страницы: 1 2 3