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

Синтаксически управляемый перевод Материалы к лекции Формальные методы описания перевода. Вопросы: 1. Схемы компиляции 2. СУ-схемы 3. МП-преобразователи 1.4. Практическое применение СУ-схем 1. Схемы компиляции Ранее компиляция программы была охарактеризована как последовательность отдельных преобразующих действий — эта­пов компиляции. Из этой характеристики естественным об­разом следует представление о структуре компилятора как о совокупности последовательно выполняемых программных ком­понентов, каждый из которых соответствует одному этапу (рис. 1а). Назовем такую схему последовательной схемой ком­пиляции. Последовательная схема предполагает не менее одного просмотра (прохода) программы на каждом этапе. Например, при генерации кода может выполняться два просмотра, а каж­дый метод машинно-независимой оптимизации требует по край­ней мере одного просмотра. Рассмотренные методы построения промежуточной программы не требуют наличия разбора, и синтаксический анализатор может вообще не выполнять ни­какого преобразования программы. Последовательная схема, несомненно, проста и понятна, но она громоздка (по объему занимаемой памяти и времени компиляции программы) и при­меняется редко. Широкое практическое применение находят схемы компиля­ции с компонентами, выполняющимися под управлением синтак­сического анализатора. Синтаксический анализатор, осуществляя разбор программы, вызывает лексический анализатор для сбор­ки лексемы, когда в этом возникает необходимость. После завер­шения распознавания каждой синтаксической единицы програм­мы вызывается семантический анализатор для ее обработки. Глав­ная идея состоит в том, чтобы в ходе построения дерева разбора решать задачи последующих этапов компиляции для каждого вновь сформированного узла. Рис. 1. Схемы компиляции: а - последовательная, б - интегрированная Теоретически возможна полная интеграция этапов компиля­ции (рис.1б), однако этому могут препятствовать как отдель­ные средства языка программирования (например, метки и не­строгая дисциплина описаний), так и специфика некоторых эта­пов компиляции (например, оптимизации). Естественно, интеграция приводит к усложнению алгоритмов компиляции. Поэтому выбор подходящей структуры компилятора — непро­стая задача. Тем не менее обычно строят компиляторы так, что на выходе синтаксического анализатора получается, как мини­мум, промежуточная программа в той или иной форме. Подоб­ного рода схемы компиляции с этапами преобразований про­граммы, выполняемыми в ходе синтаксического анализа, будем называть интегрированными. На рис. 1б показан идеальный вариант интегрированной схемы компиляции. 2. СУ-схемы Интегрированные схемы компиляции базируются на теории перевода языков, ключевыми понятиями которой являются схема синтаксически управляемого перевода (СУ-схема), синтакси­чески управляемый перевод (СУ-перевод), преобразователь с мага­зинной памятью (МП-преобразователь). Рассмотрим эти понятия. СУ-схемой Т называется пятерка T=(VT,VN,Δ,R,S), где V T — конечный входной алфавит, терминалы; V N — конечное множество нетерминалов; Δ — конечный выходной алфавит; R — конечное множество правил вида А → , где V*,(VNΔ)*; S — аксиома (начальный символ) схемы. СУ-схема называется простой, если в каждом правиле А —> , одноименные нетерминалы встречаются в  и  в одном и том же порядке. СУ-схема называется постфиксной, если   Vn *Δ * в каждом правиле (А → ,)  R. СУ-переводом τ, определяемым (генерируемым) СУ-схемой T = (Vt, VN, Δ, R, S), называется множество пар τ(T) = {(ω, у) | (S,S) =>* (ω, у), ω  Vt, yΔ *}. Грамматика GBX = (Vt, VN,, P, S), где Р = {A → а | (А → ,)  R}, называется входной грамматикой СУ-схемы. Грамматика GBbIX = (Δ, VN, P’, S), где Р’ = {А →  | (A → ,)  R}, называется выходной грамматикой СУ-схемы. Пример 1. Рассмотрим СУ-схему Т1 перевода арифметичес­ких выражений в обратную польскую запись. В основе этой схе­мы лежит соответствие правил записи арифметических выраже­ний в обычной (инфиксной) форме и в ОПЗ. Для упрощенных выражений такое соответствие приводится ниже. СУ-схема Т1 представляется пятеркой Т1 = (VT, VN,, Δ, R,S). где S — аксиома, VT ={+, *, имя, (,)}; Δ = {+, *, имя}; VN= {S,E, Т, F} и множество R содержит следующие правила: 1)S → E,E 2)E → E+T,ET+ 3)E → T,T 4)T → T*F,TF* 5)T → F,F 6)F → (E),E 7) F → имя, имя Входной грамматикой СУ-схемы Т1 является GBX = (VT, VN ,P, S). где множество правил Р представлено правилами инфиксной формы. GВЫХ = (Δ, Vn, P', S) — выходная грамматика СУ-схемы Т1, а ее правила Р' — это правила ОПЗ. Как показывает анализ пра­вил СУ-схемы, Т1 — простая постфиксная СУ-схема. Нетрудно убедиться также, что в ней существует, например, вывод (S, S) =>* (a+b*c, abc*+), порождающий элемент перевода ( а + b*с, abc*+)  τ(T1). 3. МП-преобразователи Как формальный язык можно определить формальной грамма­тикой, с одной стороны, и распознавателем — с другой стороны, так и для описания СУ-перевода применяют СУ-схему и МП-преобразователь. С помощью МП-преобразователя формально описываются действия, связанные не только с рас­познаванием синтаксических конструкций, но и с построением дерева разбора (вывода) и его преобразованием. До сих пор мы включали некоторые из таких действий в подпрограммы таблиц разбора синтаксических анализаторов неформально, интуитив­но. СУ-схемы и МП-преобразователи по­зволяют формально описать соответствующие действия, которые имеют как синтаксический, так и семантический характер. МП-преобразователем называют восьмерку Р = (Q, , Г, Δ, , q0, Zo, F), где Q - конечное множество состояний преобразователя;  - конечный входной автомат; Г - конечный магазинный алфавит; Δ - конечный входной алфавит;  - отображение множества (Q х (  {}) x Г) в множество всех подмножеств множества (Q х Г* х Δ*), т.е.  : (Q х (  {}) x Г) → P(Q х Г* х Δ*); q0 — начальное состояние преобразователя, qoQ; Zo — начальное содержимое магазина, Zo  Г; F — множество заключительных состояний преобразователя, F Q. Конфигурация МП-преобразователя — это четверка (q, ω, α, у)  (Q х * х Г* х Δ *). Начальная конфигурация — (qo, ω, Zo, ε), заключительная конфигурация — (q, ε, α, у), где q  F. Если од­ним из значений функции 8(q, a, Z) является (q\ у, г), то шаг ра­боты преобразователя можно представить в виде отношения на конфигурациях (q0, αω, Z α, у) |- (q’, ω, γα, γr) для любых ω  *, у Г*, у  Δ *. Строка у будет выходом МП-преобразователя для строки ω, если существует путь от начальной до заключительной конфигу­рации (q0, ω, Zo, ε) |-* (q, ε, α, у) для некоторых q  F и α Г*. Переводом (преобразованием) τ, определяемым МП-преобра­зователем Р, называется множество τ (Р) = {( ω, у) | (q0, ω, Zo, ε)|-* (q, ε, α, у) для q  F, α Г*}. МП-преобразователь будет детерминированным, если, как и МП-автомат, он имеет не более одной возможной очередной кон­фигурации. Расширенный МП-преобразователь отличается от рассмотренного только магазинной функцией  : (Q х (  {}) x Г*) → P(Q х Г* х Δ*); Теперь обратимся к двум результатам теоретических исследо­ваний, имеющим чрезвычайно важное практическое значение. Они состоят в следующем [ ]. 1. Если Т = (VT, VN , Δ, R,S)— простая СУ-схема с входной грамматикой LL(k), то СУ-перевод τ (Т) можно осуществить де­терминированным МП-преобразователем. 2. Если T=(VT, VN,, Δ, R,S) — простая постфиксная СУ-схема с входной грамматикой LR(k), то перевод τ(Т) можно выполнить детерминированным МП-преобразователем. Существуют алгоритмы, позволяющие построить детерминированный МП-преобразователь по заданной СУ-схеме пере вода. В их основе лежат алгоритмы построения таблиц разбора. Входная грамматика СУ-схемы Т1 из примера 6.1 не принадлежит классу LL(1)-грамматик по очевидной причине — левой рекурсии нетерминалов Е и Т. Поэтому нисходящий детерминированный LL(1)-преобразователь для нее не существует, и для построения перевода требуется более сложный преобразователь. Показано, что входная грамматика СУ-схемы Т1 является SLR(1)-грамматикой. Простые СУ-переводы образуют важный класс переводов, поскольку для каждого из них можно построить детерминиро­ванный МП-преобразователь, отображающий входную строку (цепочку) в выходную строку (цепочку). Такие переводы иногда называют цепочечными. 1.4. Практическое применение СУ-схем СУ-схемы предполагают существование отображения f: Р1 -> P2 множества правил грамматики исходного языка в множество пра­вил грамматики объектного языка, о котором шла речь в поста­новке задачи трансляции. Даже если такое ото­бражение построено, практическая реализация синхронных вы­водов в двух грамматиках оказывается сложной и к тому же ненужной. При компиляции интерес представляет только после­дняя сентенциальная форма вывода в грамматике объектного язы­ка, т.е. строка этого языка. Существуют различные методы полу­чения объектной программы по разбору исходной программы-Некоторые методы позволяют строить объектную программу (чаще —: промежуточную, линейную) в темпе синтаксического анализа. В этом случае строить полное дерево разбора исходной программы, а тем более сохранять его после синтаксического анализа не требуется. Другие методы, напротив, ориентированы на формирование объектной программы по результатам синтаксического анализа, представленным в виде дерева разбора. И первые методы (методы СУ-компиляции), и вторые (методы СУ-перевода ) являются синтаксически управляемыми. Сейчас рассмотрим один метод построения объектной программы, использующий дерево разбора и опирающийся на существование СУ-схемы перевода. В основу метода положено преобразование дерева разбора строки со во входной грамматике GBX в дерево разбора выходной строки у в грамматике GBbIХ. Метод позволяет получить перевод (ω, у) любой входной строки со пу­тем последовательного решения следующих трех задач: • построить дерево разбора со в грамматике GBX; • преобразовать полученное дерево в дерево разбора соответ­ствующей строки у в грамматике GBЫХ , используя правила СУ-схемы; • получить выходную строку у, взяв крону дерева разбора строки у. Решение первой задачи уже рассматривалось (см. разд. 5.3.2 и 5.3.3), последняя задача достаточно проста [36]. Рассмотрим, как решается задача преобразования дерева разбора входной строки. Обозначим: А — произвольный нетерминал СУ-схемы, А —> а — правило входной грамматики, где а = n1...пk.. Пусть нетерминалу А соответствует узел А дерева разбора (нетерминальный узел). Тогда узлы п1, n2, ...., пк — прямые потомки узла А. Преобразование дерева разбора начинается с его корня и состоит в следующем [4]: 1) выбрать очередной нетерминальный узел А дерева разбора входной строки; если все узлы обработаны, завершить работу; 2) устранить листья из множества узлов п1,...,nk (вершины, помеченные терминалами или е); 3) найти в СУ-схеме правило вида (А —> а, ) и переставить оставшихся прямых потомков узла А в соответствии с их разме­щением в строке  (поддеревья перемещать вместе с их корнями); 4) добавить в качестве прямых потомков узла А листья так, чтобы метки всех его прямых потомков образовали цепочку ; 5) повторять п. 1—4 для всех прямых нетерминальных потом­ков узла А по порядку, слева направо. Пример 2. Дана СУ-схема Т2 = ({0, 1}, {S, A}, {a, b), R, S), где R содержит правила: 1)S->0AS,SAa 2)A->0SA,ASa 3)S-> 1,b 4)A->1,b. На рис. 2а показано дерево разбора входной строки 00111. Применение алгоритма преобразования к корню S этого дерева устраняет Рис. 2. Преобразование дерева разбора: а - дерево входной строки; б - дерево после однократного применения алгоритма; в - дерево выходной строки левый лист, помеченный 0 (шаг 2). Далее, так как корню соответ­ствует правило S —> 0AS и для этого правила  = SAa, нужно поме­нять местами оставшихся прямых потомков корня (шаг 3). Затем сле­дует добавить а в качестве самого правого, третьего, прямого потом­ка (шаг 4). Результатом будет дерево, показанное на рис.2б. Снова применяем алгоритм, теперь уже к первым двум потомкам корня. Обработка второго из них приводит еще к двукратному повторению алгоритма. Окончательный результат показан на рис. 2в, это дере­во разбора выходной строки bbbaa. Из анализа правил СУ-схемы T2 следует, что она является не простой постфиксной схемой.