Синтаксически управляемые методы трансляции

Помечено: 

  • В этой теме 0 ответов, 1 участник, последнее обновление 1 неделя, 5 дней назад сделано Васильев Владимир Сергеевич.
Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #6277
      @admin

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

      В качестве средства формального описания языков будем использовать форму Бэкуса-Наура (Джон Бэкус – американский учёный в области компьютерных наук, Петер Наур – датский учёный в области компьютерных наук). В её обозначениях приведённое выше описание синтаксиса изображения сумм a, b и c может быть записано в виде 6 правил:

      <сумма>::= <сумма>+a| <сумма>+b| <сумма>+c|a|b|c

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

      • {a, b, c, +} – множество терминальных символов,
      • {<сумма>} – множество нетерминальных символов,
      • <сумма> – аксиома.

      Возможность построения дерева разбора для строки терминальных символов – это ещё и возможность построения вывода этой строки из аксиомы грамматики. Для строки a+b+c вывод выглядит так:

      <сумма> => <сумма>+c => <сумма>+b+c => a+b+c .

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

      Если в правилах грамматики слева от символа ::= (он читается как «это есть по определению») находится только один символ (таким символом может быть только нетерминальный), грамматика по классификации Хомского (Ноам Хомский – американский лингвист) относится к классу контекстно-свободных (КС-грамматик). Соответственно, языки, которые описываются КС-грамматиками, являются КС-языками. Синтаксически управляемые трансляторы для таких языков можно строить на базе так называемых магазинных автоматов. Построение магазинного автомата является задачей конструктора транслятора, которая решается по известным алгоритмам, использующим КС-грамматики в качестве исходных данных. Собственно, главной задачей конструктора является построение управляющей таблицы, центральной компоненты автомата. Структура магазинного автомата, как показано на рисунке, предполагает, что процесс его функционирования (трансляции) — последовательное исполнение команд, выбираемых из управляющей таблицы по координатам, указанным содержанием вершины магазина (стека) и очередным читаемым символом исходного (транслируемого) текста.

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

      Практический интерес, с точки зрения построения реальных трансляторов, представляют детерминированные магазинные автоматы. Каждая ячейка управляющей таблицы такого автомата содержит только одну команду, единственно верную в текущей конфигурации функционирования автомата (при текущем содержании стека и текущем сканируемом символе исходного текста) и позволяющую завершить трансляцию без перебора вариантов решений на отдельных шагах алгоритма и без возвратов к уже прочитанным символам исходного текста. Детерминированные магазинные автоматы могут быть сконструированы только для частных видов КС-грамматик.

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

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.