Формальные языки и грамматики

Содержание 1 Формальные языки и грамматики ....................................................................... 1.1 Операции над цепочками символов ................................................................. 1.2 Способы задания языков .................................................................................. 1.2.1 Определение языков посредством множеств ................................................ 1.2.2 Формы Бэкуса-Наура ..................................................................................... 1.2.3 Диаграммы Вирта .......................................................................................... 1.2.4 Формальные грамматики............................................................................... 1.2.4.1 Определение формальной грамматики ....................................................... 1.2.4.2 Классификация языков и грамматик .......................................................... 1.2.4.3 Эквивалентность грамматик ....................................................................... 1.2.5 Механизмы распознавания языков ................................................................ 1.2.5.1 Определение распознавателя ...................................................................... 1.2.5.2 Схема работы распознавателя .................................................................... 1.2.5.3 Классификация распознавателей ................................................................ 2 Регулярные языки ............................................................................................... 2.1 Регулярные выражения .................................................................................... 2.2 Лемма о разрастании для регулярных языков .................................................. 2.2 Конечные автоматы .......................................................................................... 2.2.1 Определение конечного автомата ................................................................. 2.2.2 Распознавание строк конечным автоматом ................................................... 2.2.3 Преобразование конечных автоматов ........................................................... 2.2.3.1 Преобразование конечного автомата к детерминированному виду ........... 2.2.3.2 Минимизация конечного автомата ............................................................. 2.2.3.2.1 Устранение недостижимых состояний автомата ..................................... 2.2.3.2.2 Объединение эквивалентных состояний автомата .................................. 2.4 Взаимосвязь способов определения регулярных языков ................................. 2.4.1 Построение конечного автомата по регулярной грамматике ........................ 2.4.2 Построение регулярной грамматики по конечному автомату ...................... 3 Контекстно-свободные языки ............................................................................. 3.1 Задача разбора .................................................................................................. 3.1.1 Вывод цепочек............................................................................................... 3.1.2 Дерево разбора .............................................................................................. 3.1.2.1 Нисходящее дерево разбора ....................................................................... 3.1.2.2 Восходящее дерево разбора........................................................................ 3.1.3 Однозначность грамматик ............................................................................. 3.2 Преобразование КС-грамматик ....................................................................... 3.2.1 Проверка существования языка..................................................................... 3.2.2 Устранение недостижимых символов ........................................................... 3.2.3 Устранение -правил ..................................................................................... 3.2.4 Устранение цепных правил ........................................................................... 3.2.5 Левая факторизация правил........................................................................... 3.2.6 Устранение прямой левой рекурсии.............................................................. 3.3 Автомат с магазинной памятью ....................................................................... 3.3.1 Определение МП-автомата............................................................................ 3.3.2 Разновидности МП-автоматов....................................................................... 3.3.3 Взаимосвязь МП-автоматов и КС-грамматик ............................................... 3.3.3.1 Построение МП-автомата по КС-грамматике ............................................ 3.3.3.2 Построение расширенного МП-автомата по КС-грамматике..................... 3.4 Нисходящие распознаватели языков ................................................................ 3.4.1 Рекурсивный спуск........................................................................................ 3.4.1.1 Сущность метода ........................................................................................ 3.4.1.2 Достаточные условия применимости метода ............................................. 3.4.2 Распознаватели LL(k)-грамматик .................................................................. 3.4.2.1 Определение LL(k)-грамматики ................................................................. 3.4.2.2 Необходимое и достаточное условие LL(1)-грамматики ........................... 3.4.2.3 Построение множеств FIRST(1, A) ............................................................. 3.4.2.4 Построение множеств FOLLOW(1, A) ....................................................... 3.4.2.5 Алгоритм «сдвиг-свертка» для LL(1)-грамматик ....................................... 3.5 Восходящие распознаватели языков ................................................................ 3.5.1 Грамматики предшествования....................................................................... 3.5.1.1 Грамматики просторного предшествования ............................................... 3.5.1.1.1 Определение грамматики простого предшествования ............................ 3.5.1.1.2 Поиск основы сентенции ......................................................................... 3.5.1.1.3 Построение множеств L(A) и R(A) .......................................................... 3.5.1.1.4 Матрица предшествования ...................................................................... 3.5.1.1.5 Алгоритм «сдвиг-свертка» для грамматик простого предшествования .. 3.5.1.2 Грамматики операторного предшествования ............................................. 3.5.1.2.1 Определение грамматики операторного предшествования ..................... 3.5.1.2.2 Построение множеств Lt (A) и Rt (A) ......................................................... 3.5.1.2.3 Матрица операторного предшествования................................................ 3.5.1.2.4 Алгоритм «сдвиг-свертка» для грамматик простого предшествования .. 3.5.2 Распознаватели LR(k)-грамматик .................................................................. 3.6 Соотношение классов КС-грамматик............................................................... 4 Принципы построения трансляторов .................................................................. 4.1 Лексика, синтаксис и семантика языка ............................................................ 4.2 Определение транслятора, компилятора, интерпретатора и ассемблера ......... 4.3 Общая схема работы транслятора .................................................................... 4.5 Лексический анализ.......................................................................................... 4.5.1 Задачи лексического анализа......................................................................... 4.5.2 Диаграмма состояний с действиями.............................................................. 4.5.3 Функция scanner ............................................................................................ 4.6 Синтаксический анализ ................................................................................... 4.6.1 Задачи синтаксического анализа ................................................................... 4.6.2 Нисходящий синтаксический анализ ............................................................ 4.7 Семантический анализ ..................................................................................... 4.8 Генерация кода ................................................................................................. 4.8.1 Формы внутреннего представления программы ........................................... 4.8.1.1 Тетрады....................................................................................................... 4.8.1.2 Триады ........................................................................................................ 4.8.1.3 Синтаксические деревья ............................................................................. 4.8.1.4 Польская инверсная запись......................................................................... 4.8.1.5 Ассемблерный код и машинные команды .................................................. 4.8.2 Преобразование дерева операций в код на языке ассемблера ....................... 4.9 Оптимизация кода ............................................................................................ 4.9.1 Сущность оптимизации кода......................................................................... 4.9.2 Критерии эффективности результирующей объектной программы ............. 4.9.3 Методы оптимизации кода ............................................................................ 4.9.4 Оптимизация линейных участков программ ................................................. 4.9.4.1 Свертка объектного кода ............................................................................ 4.9.4.2 Исключение лишних операций................................................................... 4.9.5 Оптимизация циклов ..................................................................................... 4.9.6 Оптимизация логических выражений ........................................................... 4.9.7 Оптимизация вызовов процедур и функций.................................................. 4.9.8 Машинно-зависимые методы оптимизации .................................................. 5 Формальные методы описания перевода ............................................................ 5.1 Синтаксически управляемый перевод.............................................................. 5.1.1 Схемы компиляции........................................................................................ 5.1.2 СУ-схемы....................................................................................................... 5.1.3 МП-преобразователи ..................................................................................... 5.1.4 Практическое применение СУ-схем.............................................................. 5.2 Транслирующие грамматики............................................................................ 5.2.1 Понятие Т-грамматики .................................................................................. 5.2.2 Т-грамматика с подпрограммами .................................................................. 5.2.3 МП-преобразователь для Т-грамматики........................................................ 5.3 Атрибутные транслирующие грамматики........................................................ 5.3.1 Синтезируемые и наследуемые атрибуты ..................................................... 5.3.2 Определение и свойства АТ-грамматики ...................................................... 5.3.3 ФормированиеАТ-грамматики ..................................................................... 1 Формальные языки и грамматики 1.1 Основные понятия теории формальных языков В основе каждого языка лежит алфавит. Определение Алфавитом V называется конечное множество символов. Определение Цепочкой  в алфавите V называется любая конечная последовательность символов этого алфавита. Определение Цепочка, которая не содержит ни одного символа, называется пустой цепочкой и обозначается  . Определение Формальное определение цепочки символов в алфавите V: 1)  - цепочка в алфавите V; 2) если  - цепочка в алфавите V и а – символ этого алфавита, то  а – цепочка в алфавите V; 3)  - цепочка в алфавите V тогда и только тогда, когда она является таковой в силу утверждений 1) и 2). Определение Длиной цепочки  называется число составляющих ее символов (обозначается | |). Определение Конкатенацией (сцеплением) цепочек  и  называется цепочка =, в которой символы данных цепочек записаны друг за другом. Для любой цепочки  справедливо утверждение  = . Определение Степенью n цепочки  называется конкатенация n цепочек  . (обозначается  n). Для любой цепочки  справедливы утверждения  0= и  n= n-1 = n-1 для n1. Определение Реверсом (обращением) цепочки  называется цепочка  R, составленная из символов цепочки  , записанных в обратном порядке. Пример Пусть алфавит V={a, b, c, d}, тогда для цепочек этого алфавита  =ab и =bcd будет справедливо | |=2, ||=3, = abbcd,  2=abab, R=dcb. Обозначим через V* множество, содержащее все цепочки в алфавите V, включая пустую цепочку  , а через V+ - множество, содержащее все цепочки в алфавите V, исключая пустую цепочку  . Определение Формальным языком L в алфавите V называют произвольное подмножество множества V*. V  {1, 0} , Пример Пусть алфавит двоичных цифр тогда V *  { , 0, 1, 00, 01, 10, 11, 000, } , а V   {0, 1, 00, 01, 10, 11, 000, } . Задать язык L в алфавите V можно тремя способами: 1) перечислением всех допустимых цепочек языка (на языке множеств); 2) указанием способа порождения (генерации) цепочек языка (грамматики, формы Бэкуса-Наура и диаграммы Вирта; 3) определением метода распознавания цепочек языка (распознаватели). Пример Язык L в алфавите V  {1, 0} , состоящий из пустой строки и всевозможных строк, каждая из которых содержит строку нулей и последующую строку единиц той же длины, можно описать с помощью формальной системы определения множеств как L={0n1n | n0}. 1.2 Способы задания языков 1.2.1 Формальные грамматики 1.2.1.1 Определение формальной грамматики Формальная грамматика – это математическая система, определяющая язык посредством порождающих правил. Определение Формальной грамматикой называется четверка вида: G  (VT , VN , P, S ) , где VN - конечное множество нетерминальных символов грамматики (обычно прописные латинские буквы); VT - множество терминальных символов грамматики (обычно строчные латинские буквы, цифры, и т.п.), VT VN =; Р – множество правил вывода грамматики, являющееся конечным подмножеством множества (VT VN)+  (VT VN)*; элемент ( , ) множества Р называется правилом вывода и записывается в виде   (читается: «из цепочки  выводится цепочка »); S - начальный символ грамматики, S VN. Для записи правил вывода с одинаковыми левыми частями вида используется сокращенная форма записи   1,    2 ,,   n   1 |  2 |  |  n . Пример Грамматика G1=({0, 1}, {A, S}, P1, S), где множество Р состоит из правил вида: 1) S 0A1; 2) 0A 00A1; 3) A . * Определение Цепочка   (VTVN) непосредственно выводима из цепочки   (VT  VN )  в грамматике G  (VT , VN , P, S ) (обозначается:  ), если   1 2 и   1 2 , где 1,  2 ,   (VT  VN )* ,   (VT  VN )  и правило вывода    содержится во множестве Р. Определение Цепочка   (VTVN)* выводима из цепочки   (VT  VN )  в грамматике G  (VT , VN , P, S ) (обозначается  *), если существует последовательность цепочек (n0) такая, что  0 ,  1 , ,  n    0  1     n   . Пример В грамматике G1 S*000111, т.к. существует вывод S  0 A1  00 A11  000 A111  000111. Определение Языком, порожденным грамматикой G  (VT , VN , P, S ) , называется множество всех цепочек в алфавите VT, которые выводимы из начального символа грамматики S c помощью правил множества Р, т.е. множество L(G)  { VT* | S  *} . Пример Для грамматики G1 язык L(G1)={0n1n | n0}. Определение Цепочка   (VT  VN )* , для которой существует вывод S* , называется сентенциальной формой или сентенцией в грамматике G  (VT , VN , P, S ) . Определение Языком, порожденным грамматикой G называется множество терминальных сентенциальных форм грамматики. 1.2.1.2 Классификация языков и грамматик по Хомскому Классификация грамматик по Хомскому осуществляется по структуре их правил вывода. Выделяется четыре типа грамматик. Тип 0. Грамматика G  (VT , VN , P, S ) называется грамматикой типа 0, если на ее правила вывода не наложено никаких ограничений, кроме тех, которые указаны в определении грамматики. Тип 1. Грамматика G  (VT , VN , P, S ) называется контекстно-зависимой грамматикой (КЗ-грамматикой), если каждое правило вывода из множества Р имеет вид   , где   (VT  VN)+,   (VT  VN)* и | |  ||. Тип 2. Грамматика G  (VT , VN , P, S ) называется контекстно-свободной грамматикой (КС-грамматикой), если ее правила вывода имеют вид: A   , где AVN и  V * . Соотношение типов грамматик и языков представлено на рисунке 1.1. Р Тип 0 КЗ КС Р – регулярная грамматика; КС – контекстно-свободная грамматика; КЗ – контекстно-зависимая грамматика; Тип 0 – грамматика типа 0. Рисунок 1.1 – Соотношение типов формальных языков и грамматик Тип 3. Грамматика G  (VT , VN , P, S ) называется регулярной грамматикой (Р-грамматикой) выровненной вправо, если ее правила вывода имеют вид A  aB | a , где a VT ; A, B VN . Грамматика G  (VT , VN , P, S ) называется регулярной грамматикой (Рграмматикой) выровненной влево, если ее правила вывода имеют вид A  Ba | a , где a VT ; A, B VN . Определение Язык L(G) называется языком типа k, если его можно описать грамматикой типа k, где k – максимально возможный номер типа грамматики. Пример Примеры различных типов формальных языков и грамматик по классификации Хомского. Терминалы будем обозначать строчными символами, нетерминалы – прописными буквами, начальный символ грамматики – S. а) Язык типа 0 L(G)= {a 2b n 1 | n  1} определяется грамматикой с правилами вывода: 1) S  aaCFD; 2) AD  D; 3) F  AFB | AB; 4) Cb  bC; 5) AB  bBA; 6) CB  C; 7) Ab  bA; 8) bCD   . 2 б) Контекстно-зависимый язык L(G)={anbncn грамматикой с правилами вывода: 1) S  aSBC | abc; 2) bC  bc; 3) CB  BC; 4) cC  cc; 5) BB  bb. | n1} определяется в) Контекстно-свободный язык L(G)={(ab)n(cb)n | n>0 } определяется грамматикой с правилами вывода: 1) S  aQb | accb; 2) Q  cSc. г) Регулярный язык L(G)={  |  {a, b}+, где нет двух рядом стоящих а} определяется грамматикой с правилами вывода: 1) S  A | B; 2) A  a | Ba; 3) B  b | Bb | Ab. 1.2.1.3 Эквивалентность грамматик Определение Грамматики G1 и G2 называются эквивалентными, если они определяют один и тот же язык, т.е. L(G1)  L(G2 ) . Определение Грамматики G1 и G2 называются почти эквивалентными, если заданные ими языки различаются не более чем на пустую цепочку символов т.е. L(G1)  { }  L(G2 )  { }. Пример Для грамматики G1 эквивалентной будет грамматика G2 = ({0, 1}, {S}, P2, S), где множество правил вывода P2 содержит правила вида S  0S1 |  . Почти эквивалентной для грамматики G1 будет грамматика G3 = ({0, 1}, {S}, P3, S), где множество правил вывода P3 содержит правила вида S  0S1 | 01. 1.2.2 Формы Бэкуса - Наура Цепочки языка могут содержать метасимволы, имеющие особое назначение. Метаязык, предложенный Бэкусом и Науром (БНФ) использует следующие обозначения: - символ «::=» отделяет левую часть правила от правой (читается: «определяется как»); - нетерминалы обозначаются произвольной символьной строкой, заключенной в угловые скобки «<» и «>»; - терминалы - это символы, используемые в описываемом языке; - правило может определять порождение нескольких альтернативных цепочек, отделяемых друг от друга символом вертикальной черты «|» (читается: «или». Для повышения удобства и компактности описаний, в расширенных БНФ вводятся следующие дополнительные конструкции (метасимволы): - квадратные скобки «[» и «]» означают, что заключенная в них синтаксическая конструкция может отсутствовать; - фигурные скобки «{» и «}» означают повторение заключенной в них синтаксической конструкции ноль или более раз; - сочетание фигурных скобок и косой черты «{/» и «/}» используется для обозначения повторения один и более раз; - круглые скобки «(» и «)» используются для ограничения альтернативных конструкций; - кавычки используются в тех случаях, когда один из метасимволов нужно включить в цепочку обычным образом. Пример Правила, определяющие понятие «идентификатор» некоторого языка программирования, будут выглядеть следующим образом: <буква> ::= a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x|y|z <цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 <идентификатор> ::= <буква> { (<буква> | <цифра>) } 1.2.3 Диаграммы Вирта В метаязыке диаграмм Вирта используются графические примитивы, представленные на рисунке 1.4.1. При построении диаграмм учитывают следующие правила: - каждый графический элемент, соответствующий терминалу или нетерминалу, имеет по одному входу и выходу, которые обычно изображаются на противоположных сторонах; - каждому правилу соответствует своя графическая диаграмма, на которой терминалы и нетерминалы соединяются посредством дуг; - альтернативы в правилах задаются ветвлением дуг, а итерации - их слиянием; - должна быть одна входная дуга (располагается обычно слева или сверху), задающая начало правила и помеченная именем определяемого нетерминала, и одна выходная, задающая его конец (обычно располагается справа и снизу); - стрелки на дугах диаграмм обычно не ставятся, а направления связ ей отслеживаются движением от начальной дуги в соответствии с плавными изгибами промежуточных дуг и ветвлений. 1) А begin 2) блок 4) блок 3) 5) Рисунок 1.2 – Графические примитивы диаграмм Вирта 1) – терминальный символ, принадлежащий алфавиту языка; 2) – постоянная группа терминальных символов, определяющая название лексемы, ключевое слово и т.д.; 3) – нетерминальный символ, определяющий название правила; 4) – входная дуга с именем правила, определяющая его название; 5) – соединительные линии, обеспечивающие связь между терминальными и нетерминальными символами в правилах. Пример 1.4.1. Правила, определяющие понятие «идентификатор» некоторого языка программирования, показаны на рисунке 1.3. цифра 1 2 3 4 5 6 7 8 9 буква a g l q v b h m r w c i n s x d j o t y e k p u z f буква идентификатор буква цифра Рисунок 1.3 – Диаграмма Вирта понятия «идентификатор» 1.2.5 Механизмы распознавания языков 1.2.5.1 Определение распознавателя Обратной к задаче генерации строк языка является задача проверки принадлежности исходной строки заданному языку. Для решения этой проблемы создается механизм распознавания, или распознаватель. Определение Распознаватель – это специальный алгоритм, который позволяет определить принадлежность цепочки символов некоторому языку. Распознаватель схематично можно представить в виде совокупности входной ленты, управляющего устройства и вспомогательной памяти (рисунок 1.4). 1.2.5.2 Схема работы распознавателя Входная лента представляет собой последовательность ячеек, каждая из которых содержит один символ некоторого конечного алфавита. Входная головка в каждый момент обозревает одну ячейку. За один шаг работы распознавателя головка сдвигается на одну ячейку влево (вправо) или остается неподвижной. Распознаватель, не перемещающий входную головку влево, называется односторонним. Управляющее устройство – это программа управления распознавателем. Она задает конечное множество состояний распознавателя и определяет пер еходы из состояния в состояние в зависимости от прочитанного символа входной ленты и содержимого вспомогательной памяти. Вспомогательная память служит для хранения информации, которая зависит от состояния распознавателя. У некоторых типов распознавателей она может отсутствовать. а1 а2 … аn Входная лента Входная головка Управляющее устройство Вспомогательная память Рисунок 1.4 – Схема распознавателя Поведение распознавателя можно представить с помощью его конфигураций. Определение Конфигурация распознавателя есть совокупность следующих элементов: - состояние управляющего устройства; - содержимое входной ленты и положение входной головки; - содержимое вспомогательной памяти. Определение Управляющее устройство называется детерминированным, если для каждой конфигурации распознавателя существует не более одного возможного следующего шага, в противном случае управляющее устройство называется недетерминированным. Определение Конфигурация распознавателя называется начальной, если управляющее устройство находится в заданном начальном состоянии, входная головка обозревает самый левый символ на входной ленте и вспомогательная память имеет заранее установленное начальное состояние. Определение Конфигурация распознавателя называется заключительной, если управляющее устройство находится в одном из заранее выделенных заключительных состояний, а входная головка сошла с правого конца входной ленты. Содержимое вспомогательной памяти удовлетворяет некоторому установленному условию. Определение Входная строка  допускается распознавателем, если от начальной конфигурации, в которой цепочка  записана на входной ленте, распознаватель может выполнить последовательность шагов, заканчивающуюся заключительной конфигурацией. Определение Множество всех строк, допускаемых распознавателем, называется языком распознавателя. 1.2.5.3 Классификация распознавателей Для каждого класса грамматик из иерархии Хомского существует класс распознавателей, определяющих тот же класс языков. Чем шире класс грамматик, тем сложнее класс соответствующих распознавателей. Для языков типа 0 распознавателями являются машины Тьюринга. Распознаватели КЗ-языков называются линейными ограниченными автоматами (машины Тьюринга с конечным объемом ленты). Распознавателями для КС-языков являются автоматы с магазинной памятью. Для регулярных языков распознавателями служат конечные автоматы. 2 Регулярные грамматики и языки 2.1 Регулярные выражения Регулярный язык L в некотором алфавите V представляет собой регулярное множество строк. Определение Регулярное множество есть , либо {}, либо {а} для некоторого а V, либо множество, которое можно получить из указанных множеств путем применения конечного числа операций сцепления, объединения и итерации. В основе метода определения регулярности заданного языка лежит лемма о разрастании языка. 2.2 Лемма о разрастании языка В достаточно длинной строке регулярного языка всегда можно найти непустую подстроку, повторение которой произвольное количество раз порождает новые строки того же самого языка. Пример Язык L1 = {ambn | m, n 0} – регулярный, т.к., например, в строке aabbb повторение любой подстроки, образованной только из нулей или единиц, порождает строки (aaaabbb, aaabbb, aabbbb, aabbbbbb и т.д.) языка L1. Язык L2 = {anbn | n 1} – не регулярный, т.к. Действительно, любая итерация подстроки, состоящей только из нулей или единиц, нарушает баланс нулей и единиц. Подобные действия со смешанными подстроками, содержащими нули и единицы, приводят к нарушению порядка следования нулей и единиц. Таким образом, для языка L2 не строк, удовлетворяющих условиям леммы. Удобным средством формального определения регулярных языков являются регулярные выражения. Определение Регулярные выражения над алфавитом  определяются следующим образом: 1)  - регулярное выражение (обозначает пустоте регулярное множество ); 2)  - регулярное выражение (обозначает регулярное множество {}, состоящее из пустой строки); 3) а  - регулярное выражение (обозначает множество {а}); 4) если p и q – регулярные выражения, обозначающие множества P и Q, то посредством операций над выражениями определяются выражения следующих трех типов: а) p|q или p+q – регулярное выражение (обозначает объединение PQ), где символ | или + называют операцией или (альтернативы); б) pq или pq – регулярное выражение (обозначает множество PQ = {xy | x P, y Q}), где символ «точка» (возможно умалчиваемый) называют операцией сцепления (конкатенации); в) p* - регулярное выражение (обозначает множество P*), где символ «*» называют операцией итерации. Соотношение между регулярными языками и регулярными выражениями устанавливает теорема Клини. Теорема Клини. Каждому регулярному языку из  * соответствует регулярное выражение над множеством . Пример Примеры регулярных выражений и их значений представлены в таблице 2.1. Таблица 2.1 – Примеры регулярных выражений Регулярное выражение 01 0|1 1* (0|1)* 0|1* 0|1* (0|1)*011 Значение регулярного выражения единственная строка 01 две строки: 0 и 1 строки, образованные из единиц, включая пустую строку строки, образованные из символов 0 и 1, включая пустую строку строки, состоящие из нуля и любой строки единиц, включая пустую строки, состоящие из нуля и любой строки единиц, включая пустую строки, образованные из символов 0 и 1, включая пустую, обязательно оканчивающиеся строкой 011 В практических приложениях вводятся дополнительные соглашения относительно записи регулярных выражений, например, запись вида р+ используется для обозначения выражения рр*. 2.3 Конечные автоматы 2.3.1 Определение конечного автомата Конечный автомат – это простейший распознаватель без вспомогательной памяти. Он является эффективным способом определения регулярных языков. Определение Детерминированным конечным автоматом (ДКА) называется пятерка объектов: M  (Q, T , F , H , Z ) , где Q - конечное множество состояний автомата; T - конечное множество допустимых входных символов; F - функция переходов, отображающая множество QT во множество Q; H - конечное множество начальных состояний автомата; Z - множество заключительных состояний автомата, Z  Q. Определение Недетерминированным конечным автоматом (НКА) называется конечный автомат, в котором в качестве функции переходов используется отображение Q  T во множество всех подмножеств множества состояний автомата P(Q) , т.е. функция переходов неоднозначна, так как текущей паре (q, t ) соответствует множество очередных состояний автомата q  P(Q) . 2.3.2 Распознавание строк конечным автоматом Определение Пара (q, )  QT*, где  - текущий остаток входной строки, называется конфигурацией автомата М. Определение Конфигурация (q0, ), где  - полная входная строка, называется начальной, а пара (q,  ), где q  Z, называется заключительной конфигурацией. Шаг работы автомата можно представить отношением непосредственного следования конфигураций |-. Тогда, если F(q, t)=p, где p Q, то можно записать (q, t) |- (p, ) для всех   T*. Эта запись означает то, что если автомат находится в состоянии q и входная головка обозревает входной символ t, то автомат может делать шаг, за который он переходит в состояние p и сдвигает головку на одну ячейку вправо. Определение Автомат М допускает (принимает) строку , если существует путь по конфигурациям (q, ) |- (q,  ) для некоторого q  Z. Определение Язык L, принимаемый конечным автоматом М, формально определяется как множество: L(M) = { |   T* и (q, ) |- (q,  ) для некоторого q  Z}. Существуют следующие способы представления функции переходов: - командный способ. Каждую команду КА записывают в форме F (q, t )  p , где q, p  Q, t  T . - табличный способ. Строки таблицы переходов соответствуют входным символам автомата t  T, а столбцы – состояниям Q. Ячейки таблицы заполняются новыми состояниями, соответствующими значению функции F (q, t ) . Неопределенным значениям функции переходов соответствуют пустые ячейки таблицы. - графический способ. Строится диаграмма состояний автомата – неупорядоченный ориентированный помеченный граф. Вершины графа помечены именами состояний автомата. Дуга ведет из состояния q в состояниe p и помечается списком всех символов t  T, для которых F (q, t )  p . Вершина, соответствующая входному состоянию автомата, снабжается стрелкой. Заключительное состояние на графе обозначается двумя концентрическими окружностями. 2.3.3 Преобразование конечных автоматов Возникают две основных задачи эквивалентного преобразования КА: 1) преобразование недетерминированного конечного автомата в детерминированный конечный автомат; 2) минимизация КА. 2.3.3.1 Преобразование конечного автомата к детерминированному виду В теории КА доказано, что для любого НКА существует ДКА, принимающий тот же регулярный язык. Рассмотрим этот алгоритм. Алгоритм Преобразование НКА в ДКА Вход: НКА M  (Q, T , F , H , Z ) . Выход: ДКА M   (Q, T , F , H , Z ) . Шаг 1. Пометить первый столбец таблицы переходов M  ДКА начальным состоянием (множеством начальных состояний) НКА M . Шаг 2. Заполняем очередной столбец таблицы переходов M  , помеченный символами D , для этого определяем те состояния M , которые могут быть достигнуты из каждого символа строки D при каждом входном символе x . Поместить каждое найденное множество R (в том числе  ) в соответствующие позиции столбца D таблицы M  , т.е.: F ( D, x)  {R | R  F (t , x) для некоторого t  D } Шаг 3. Для каждого нового множества R (кроме  ), полученного в столбце D таблицы переходов M  , добавить новый столбец в таблицу, помеченный R . Шаг 4. Если в таблице переходов КА M  есть столбец с незаполненными позициями, то перейти к шагу 2. Шаг 5. Во множество Z  ДКА M  включить каждое множество, помечающее столбец таблицы переходов M  и содержащее q  Z НКА M . Шаг 6. Составить таблицу новых обозначений множеств состояний и определить ДКА M  в этих обозначениях. Этот алгоритм обеспечивает отсутствие недостижимых состояний ДКА, но не гарантирует его минимальности. Пример Пример 2.1. Дана регулярная грамматика G  ({a, b}, {S , A, B}, P, S ) с правилами P : 1) S  aB | aA; 2) B  bB | a; 3) A  aA | b . Построить по регулярной грамматике КА и преобразовать полученный автомат к детерминированному виду. Построим по НКА M из примера 2.1 ДКА M  . 1 Строим таблицу переходов для ДКА M  (таблица 2.2). Таблица 2.2 – Построение функции переходов для ДКА M  Шаг 1 2 3 4 5 6 7 F S A, B A, N B, N A N B a A, B A, N A N A N  b B, N N B N B   2 Во множество заключительных состояний автомата M  включим элементы Z   {( A, N ), ( B, N ), N} . 3 Введем следующие новые обозначения состояний автомата M  : (A,B)=С, (A, N)=D, (B, N)=E. 4 Искомый ДКА определяется следующей пятеркой объектов: Q  {S , A, B, C, D, E, N}, T  {a, b}, функция переходов задана таблицей 2.3, H  {S}, Z   {N , D, E}. Таблица 2.3 – Функция переходов для ДКА M  F a b S C  A A N С D E B N B D A N E N B Граф полученного ДКА представлен на рисунке 2.1. S b a a B C b a N a A a b E a D b b N   Рисунок 2.1 – Граф ДКА 2.3.3.2 Минимизация конечного автомата Конечный автомат может содержать лишние состояния двух типов: недостижимые и эквивалентные состояния. Определение Два различных состояния q и q в конечном автомате M  (Q, T , F , H , Z ) называются n-эквивалентными, nN{0}, если, находясь в одном их этих состояний и получив на вход любую цепочку символов  :  T*, | | n, автомат может перейти в одно и то же множество конечных состояний. Определение Состояние q КА называется недостижимым, если к нему нет пути из начального состояния автомата. Определение КА, не содержащий недостижимых и эквивалентных состояний, называется приведенным или минимальным КА. В теории КА доказано, что каждое регулярное множество распоз нается единственным для данного множества ДКА с минимальным числом состояний. Рассмотрим алгоритмы построения минимального ДКА. 2.3.3.2.1 Устранение недостижимых состояний КА Алгоритм Устранение недостижимых состояний КА Вход: КА M  (Q, T , F , H , Z ) . Выход: КА M   (Q, T , F , H , Z ) . Шаг 1. Поместить начальное состояние КА в список достижимых состояний Qд , т.е. Qд0  H . Шаг 2. Для новых элементов списка достижимых состояний пополнить список группой их состояний-приемников, отсутствующих в списке, т.е. Qдi  Qдi 1  { p | q  Qдi 1  F (q, t )  p} . Шаг 3. Повторить шаг 2, пока список достижимых состояний не перестанет меняться. То есть, если Qдi  Qдi 1 , то i=i+1, иначе Qд  Qдi . Шаг 4. Исключить из множества Q состояний КА все состояния, отсутствующие в списке Qд достижимых состояний, т.е. Q  Q  Qд . Шаг 5. Исключить недостижимые заключительные состояния и функции Z   Z  Qд , переходов, содержащие недостижимые состояния, т.е. F   F  {F (q, t )  p | q  (Q  Qд )}. Пример Устранить недостижимые состояния КА M  (Q, T , F , H , Z ) , где Q = {A, B, C, D, E, F, G}, T = {a, b}, H = {A}, Z = {D, E} и функция переходов задана таблицей 2.4. Граф исходного КА М представлен на рисунке 2.3. Таблица 2.4 – Функция переходов конечного автомата M F a b A B C a B C D E D C E b B E B D a D b a C b b a b E G F E F a A F D G b G Рисунок 2.2 – Граф исходного конечного автомата М Последовательность устранения недостижимых состояний КА имеет вид: Q0 = {A}; Q1 = {A, B, C}; Q2 = {A, B, C, D, E}; Q3 = {A, B, C, D, E}; т.к. Q2 = Q3, то Qд = {A, B, C, D, E}. Qн = {F, G }; Q = {A, B, C, D, E}; Z  = {D, E}. Функция переходов автомата M  представлена в таблице 2.6. Таблица 2.5 - Функция переходов автомата M  F a b A B C B C D E D C E E B D Граф КА M  после устранения недостижимых состояний представлен на рисунке 2.5. a b B D a A b b a C b E b Рисунок 2.3 - Граф КА M  после устранения недостижимых состояний 2.3.3.2.2 Объединение эквивалентных состояний КА Алгоритм Объединение эквивалентных состояний КА Вход: КА M   (Q, T , F , H , Z ) без недостижимых состояний. Выход: минимальный КА M   (Q, T , F , H , Z ) . Шаг 1. На первом шаге строим нулевое разбиение R(0), состоящее из двух классов эквивалентности: заключительные состояния КА - Z и не заключительные - Q-Z. Шаг 2. На очередном шаге построения разбиения R(n) в классы эквивалентности включить те состояния, которые по одинаковым входным символам переходят в n-1 эквивалентные состояния, т.е. R(n)  {ri (n) : {qij  Q : t  T F (qij , t )  r j (n  1)} i, j  N} . Шаг 3. До тех пор, пока R(n)  R(n-1) полагаем n=n+1 и идем к шагу 2. Шаг 4. Переобозначить оставшиеся неразбитые группы состояний и включить их в таблицу новых обозначений состояний автомата. Шаг 5. Определить эквивалентный КА M  в новых обозначениях. Пример Минимизировать конечный автомат из предыдущего примера. Последовательность построения разбиений будет иметь вид: R(0) = {{A, B, C}, {D, E}}, n = 0; R(1) = {{A}, {B, C}, {D, E}}, n = 1; R(2) = {{A}, {B, C}, {D, E}}, n=2. Т.к. R(1) = R(2), то искомое разбиение построено. Переобозначим оставшиеся неразбитые группы состояний: X={B, C}, Y={D, E}. Получим минимальный автомат M  , где Q ={A, X, Y}, Z  ={Y}. Функция переходов автомата M  представлена в таблице 2.7. Таблица 2.6 - Функция переходов автомата M  F a b A X X X Y Y X Y Граф переходов конечного автомата после его минимизации показан на рисунке 2.4. b a, b A b X Y a Рисунок 2.4 – Граф минимального ДКА M  2.4 Взаимосвязь способов определения грамматик Регулярные грамматики, регулярные выражения и конечные автомата – три основных способы определения регулярных языков, между которыми с уществует полное соответствие. Разработаны алгоритмы преобразования одной формы определения в другую. При работе с языками программирования наибольший практический интерес представляют преобразования регулярной грамматики в конечный автомат. Рассмотрим его. 2.4.1 Построение КА по регулярной грамматике Вход: Регулярная грамматика G  (VT , VN , P, S ) . Выход: КА M  (Q, T , F , H , Z ) . Шаг 1. Пополнить грамматику правилом A  aN , где A VN , a VT и N новый нетерминал, для каждого правила вида A  a , если в грамматике нет соответствующего ему правила A  aB , где B VN . Шаг 2. Начальный символ грамматики S принять за начальное состояние КА H . Из нетерминалов образовать множество состояний автомата Q  VN  {N} , а из терминалов – множество символов входного алфавита T  VT . Шаг 3. Каждое правило A  aB преобразовать в функцию переходов F ( A, a)  B , где A, B VN , a VT . Шаг 4. Во множество заключительных состояний включить все вершины, помеченные символами B VN из правил вида A  aB , для которых имеются соответствующие правила A  a , где A, B VN , a VT . Шаг 5. Если в грамматике имеется правило S   , где S - начальный символ грамматики, то поместить S во множество заключительных состояний. Шаг 6. Если получен НКА, то преобразовать его в ДКА. Пример Дана регулярная грамматика G  ({a, b}, {S , A, B}, P, S ) с правилами P : 1) S  aB | aA 2) B  bB | a 3) A  aA | b . Построить по регулярной грамматике конечный автомат. Решение задачи состоит из следующей последовательности действий. 1 Построим по регулярной грамматике КА. 1.1 Пополним грамматику правилами A  bN и B  aN , где N - новый нетерминал. 1.2 Начальное состояние конечного автомата H  S . Множество состояний автомата Q  VN  {S , A, B, N} , множество символов входного алфавита T  VT  {a, b}. 1.3 Значения сформированной функции переходов даны в таблице 2.7. Таблица 2.7 – Функция переходов автомата M F a b S A, B  A A N B N B N   1.4 Множество заключительных состояний Z  {N} . 1.5 Для начального символа грамматики -правила отсутствуют. Конечный автомат М - недетерминированный, граф НКА представлен на рисунке 2.5. a S b B a a b A N a Рисунок 2.5 - Граф НКА 3 Контекстно-свободные языки и грамматики 3.1 Задача разбора 3.1.1 Вывод цепочек Выводом называется процесс порождения предложения языка на основе правил определяющей язык грамматике. Чтобы дать формальное определение процессу вывода, необходимо ввести еще несколько дополнительных понятий. Определение Цепочка   (VTVN)* непосредственно выводима из цепочки   (VT  VN )  в грамматике G  (VT , VN , P, S ) (обозначается:  ), если   1 2 и   1 2 , где 1 ,  2 ,   (VT  VN ) * ,   (VT  VN ) и правило вывода    содержится во множестве Р. Определение Цепочка   (VTVN)* выводима из цепочки   (VT  VN )  в грамматике G  (VT , VN , P, S ) (обозначается  *), если существует последовательность цепочек (n0) такая, что  0 ,  1 , ,  n    0  1     n   . Такая последовательность непосредственно выводимых цепочек называется выводом или цепочкой вывода. Вывод называется правосторонним (левосторонним), если в нем на каждом шаге вывода правило грамматики применяется всегда к крайнему правому (левому) нетерминальному символу в цепочке. Вывод можно рассматривать также как процесс получения одной строки из другой. С понятием вывода тесно связано понятие разбора строки языка. С одной стороны, разбор— это задача выяснения принадлежности заданной строки языку, порождаемому заданной грамматикой. С другой стороны, разбор — это последовательность правил грамматики, определенным образом соответствующая выводу. Пример Грамматика G1=({0, 1}, {A, S}, P1, S), где множество Р состоит из правил вида: 1) S 0A1; 2) 0A 00A1; 3) A . В грамматике G1 S*000111, т.к. существует вывод S  0 A1  00 A11  000 A111  000111. 3.1.2 Дерево разбора Графическим способом отображения процесса разбора цепочек является дерево разбора (или дерево вывода). Определение дерево разбора грамматики G  (VT , V N , P, S ) называется дерево, которое соответствует некоторой цепочке вывода и удовлетворяет следующим условиям: - каждая вершина дерева обозначается символом грамматики A  (VT  VN ) ; - корнем дерева является вершина, обозначенная начальным символом грамматики S; - листьями дерева (концевыми вершинами) являются вершины, обозначенные терминальными символами грамматики или символом пустой строки ; - если некоторый узел дерева обозначен символом A  VN , а связанные с ним узлы – символами b1, b2 ,..., bn ; n  0, n  i  0 : bi  (VT  VN  { }) , то в грамматике G  (VT , V N , P, S ) существует правило A  b1, b2 ,..., bn  P Дерево разбора можно построить двумя способами: сверху вниз и снизу вверх. 3.1.2.1 Нисходящее дерево разбора При построении дерева вывода сверху вниз построение начинается с целевого символа грамматики, который помещается в корень дерева. Затем в грамматике выбирается необходимое правило, и на первом шаге вывода корневой символ раскрывается на несколько символов первого уровня. На втором шаге среди всех концевых вершин дерева выбирается крайняя (крайняя левая — для левостороннего вывода, крайняя правая — для правостороннего) вершина, обозначенная нетерминальным символом, для этой вершины выбирается нужное правило грамматики, и она раскрывается на несколько вершин следующего уровня. Построение дерева заканчивается, когда все концевые вершины обозначены терминальными символами, в противном случае надо вернуться ко второму шагу и продолжить построение. 3.1.2.2 Восходящее дерево разбора Построение дерева вывода снизу вверх начинается с листьев дерева. В качестве листьев выбираются терминальные символы конечной цепочки вывода, которые на первом шаге построения образуют последний уровень (слой) дерева. Построение дерева идет по слоям. На втором шаге построения в грамматике выбирается правило, правая часть которого соответствует крайним символам в слое дерева (крайним правым символам при правостороннем выводе и крайним левым — при левостороннем). Выбранные вершины слоя соединяются с новой вершиной, которая выбирается из левой части правила. Новая вершина попадает в слой де рева вместо выбранных вершин. Построение дерева закончено, если достигнута корневая вершина (обозначенная целевым символом), а иначе надо вернуться ко второму шагу и повторить его над полученным слоем дерева. Поскольку все известные языки программирования имеют нотацию записи «слева — направо», компилятор также всегда читает входную программу слева направо (и сверху вниз, если программа разбита на несколько строк). Поэтому для построения дерева вывода методом «сверху вниз», как правило, используется левосторонний вывод, а для построения «снизу вверх» — правосторонний вывод. На эту особенность компиляторов стоит обратить внимание. Нотация чтения программ «слева направо» влияет не только на порядок разбора программы компилятором (для пользователя это, как правило, не имеет значения), но и ни порядок выполнения операций — при отсутствии скобок большинство равноправных операций выполняются в порядке слева направо, а это уже имеет существенное значение. 3.1.3 Однозначность грамматик Грамматика называется однозначной, если для каждой цепочки символов языка, заданного этой грамматикой, можно построить единственный левосторонний (и единственный правосторонний) вывод. Или, что то же самое: грамматика называется однозначной, если для каждой цепочки символов языка, заданного этой грамматикой, существует единственное дерево вывода. В противном случае грамматика называется неоднозначной. 3.2 Преобразование КС-грамматик Определение КС-грамматика называется приведенной, если она не имеет циклов, -правил и бесполезных символов. Рассмотрим основные алгоритмы приведения КС-грамматик. Перед всеми другими исследованиями и преобразованиями КС-грамматик выполняется проверка существования языка грамматики. 3.2.1 Проверка существования языка грамматики Алгоритм Проверка существования языка грамматики Вход: КС-грамматика G  (VT , VN , P, S ) . Выход: заключение о существовании или отсутствии языка грамматики. Определим множество нетерминалов, порождающих терминальные строки N  {Z | Z VN , Z  *x, x VT*} . Шаг 1. Положить N0=Ø. Шаг 2. Вычислить Ni  Ni 1  {A | ( A   )  P и   ( Ni 1  VT )*}. Шаг 3. Если Ni  Ni 1 , то положить i=i+1 и перейти к пункту 2, иначе считать N  Ni . Если S  N , то выдать сообщение о том, что язык грамматики существует, иначе сообщить об отсутствии языка. Пример Дана грамматика G  ({0, 1}, {S , A, B}, P, S ) , где множество правил P : 1) S  AB; 2) A  0 A; 3) A  0; 4) B  1. Построим последовательность приближений множества N: N0 = Ø; N1 = {A, B}; N2 = {S, A, B}; N3 = {S, A, B}. Т.к. N2=N3, то N = {S, A, B}, следовательно, язык грамматики существует, потому что начальный символ S  N . 3.2.2 Устранение недостижимых символов Определение Бесполезными символами грамматики называют: а) нетерминалы, не порождающие терминальных строк, т.е. множество символов { X | X VN , ( X  *x), x VT*}; б) недостижимые нетерминалы, порождающие терминальные строки, т.е. множество символов { X | X VN , (S  *X ), ( X  *x);  ,  V *; x VT*}; в) недостижимые терминалы, т.е. множество символов { X | X VT , ( S  *X );  ,  V *}. Алгоритм Устранение нетерминалов, не порождающих терминальных строк Вход: КС-грамматика G  (VT , VN , P, S ) . Выход: КС-грамматика G  (VT , VN , P, S ) , такая, что L(G)  L(G) и для всех Z VN существуют выводы Z  *x , где x VT* . Шаг 1. Определить множество нетерминалов, порождающих терминальные строки, с помощью алгоритма 4.1. Шаг 2. Вычислить VN V NN , N Б  VN  VN , P  P  PБ , где PБ  P - это множество правил, содержащих бесполезные нетерминалы X  N Б . Пример Дана грамматика G  ({a, b, c}, {S , A, B, C}, P, S ) с правилами P : 1) S  ab; 2) S  AC; 3) A  AB; 4) B  b; 5) C  cb. Преобразуем ее в эквивалентную грамматику G  по алгоритму 4.2: N0 = Ø; N1 = {S, B, C}; N2 = {S, B, C}. Т.к. N1 = N2, то N = {S, B, C}. После удаления бесполезных нетерминалов и правил вывода, получим грамматику G  ({a, b, c}, {S , B, C}, P, S ) с правилами P : 1) S  ab; 2) B  b; 5) C  cb. Алгоритм Устранение недостижимых символов Вход: КС-грамматика G  (VT , VN , P, S ) . Выход: КС-грамматика G  (VT , VN , P, S ) , такая, что L(G)  L(G) и для всех Z V  существует вывод S  *Z , где  ,   (V )* . Определим множество достижимых символов Z грамматики G, т.е. множество W  {Z | Z V ,  (S  *Z );  ,  V *}. Шаг 1. Положить W0  S. Шаг 2. Вычислить очередное приближение следующим образом: Wi  Wi 1  { X | X V , ( A  X )  P, A Wi 1;  ,  V *}. Шаг 3. Если Wi  Wi 1, то положить i:=i+1 и перейти к шагу 2, иначе считать W  Wi . Шаг 4. Вычислить VN  VN  W , VT  VT  W , VБ  V  W , P  P  PБ , где PБ  P - это множество правил, содержащих недостижимые символы X VБ . Пример Дана грамматика G  ({a, b, c}, {S , B, C}, P, S ) с правилами P : 1) S  ab; 2) B  b; 5) C  cb. Преобразуем ее в эквивалентную грамматику G  по алгоритму 4.3: W0 = {S}; W1 = {S, a, b}; W2 = {S, a, b}. Т.к. W1=W2, то W={S, a, b}. Множество недостижимых символов VБ  {B, C, c}. Тогда после удаления недостижимых символов, получим грамматику G  ({a, b}, {S}, P, S ) с правилом P : S  ab. 3.2.3 Устранение -правил Алгоритм Устранение -правил Вход: КС-грамматика G  (VT , VN , P, S ) . Выход: Эквивалентная КС-грамматика G  (VT , VN , P, S ) без -правил для всех нетерминальных символов, кроме начального, который не должен встречаться в правых частях правил грамматики. Шаг 1. В исходной грамматике G найти -порождающие нетерминальные символы AVN , такие, что A  * . 1.1 Положить N0  {A | ( A   )  P}. 1.2 Вычислить Ni  Ni 1  {B | ( B   )  P,   Ni*1} . 1.3 Если Ni  Ni 1 , то положить i:=i+1 и перейти к пункту 1.2, иначе считать N  Ni . Шаг 2. Из множества P правил исходной грамматики G перенести во множество P все правила, за исключением -правил, т.е. P  P  {( A   )  P для всех AVN }. Шаг 3. Пополнить множество P правилами, которые получаются из каждого правила этого множества путем исключения всевозможных комбинаций -порождающих нетерминалов в правой части. Полученные при этом -правила во множество P не включать. Шаг 4. Если S  N , то P  P  {S    , S   S}, VN  VN  S  , где V  {S }   ; иначе VN V N , S   S. Пример Дана грамматика G  ({0, 1}, {S , A, B}, P, S ) с правилами P : 1) S  AB; 2) A  0 A |  ; 3) B  1B |  . Преобразуем ее в эквивалентную грамматику по алгоритму 4.4. Шаг 1. N0 = {A, B}; N1 = {S, A, B}; N2 = {S, A, B}. Т.к. N1 = N2, то искомое множество построено и N = {S, A, B}. Шаг 2, 3. Множество P : 1) S  AB | A | B ; 2) A  0A | 0 ; 3) B  1B | 1. Шаг 4. Т.к. S  N , то введем новый нетерминал С и пополним множество P правилом вида C  S |  . Результирующая грамматика будет иметь вид: G  ({0, 1}, {S , A, B, C}, P, C ) с правилами P : 1) C  S |  ; 2) S  AB | A | B; 3) A  0 A | 0; 4) B  1B | 1. 3.2.4 Устранение цепных правил Алгоритм Устранение цепных правил Вход: КС-грамматика G  (VT , VN , P, S ) . Выход: Эквивалентная КС-грамматика G  (VT , VN , P, S ) без цепных правил, т.е. правил вида A  B , где A, B VN . Шаг 1. Для каждого нетерминала A вычислить множество выводимых из него нетерминалов, т.е. множество N A  {B | A  *B, где B VN }. 1.1 Положить N 0A  { A}. 1.2 Вычислить NiA  NiA1  {C | ( B  C )  P, B  NiA1, C VN }. 1.3 Если NiA  NiA1, то положить i:=i+1 и перейти к пункту 1.2, иначе считать N A  N iA . Шаг 2. Построить множество P так: если ( B   )  P не является цепным правилом ( VN ) , то включить в P правило A   для каждого A , такого, что B  N A. Пример Грамматика G  ({, n}, {L, M , N}, P, L) с правилами P : 1) L  M ; 2) M  N ; 3) N  N  | n . Преобразуем ее в эквивалентную грамматику G по алгоритму 4.5. Шаг 1. N 0L  {L}; N1L  {L, M }; N 2L  {L, M , N }; N3L  {L, M , N }. Т.к. N 2L  N3L , то N L  {L, M , N }. N 0M  {M }; N1M  {M , N }; N 2M  {M , N }. Т.к. N1M  N 2M , то N M  {M , N }. N 0N  {N }; N1N  {N }. Т.к. N1N  N 0N , то N N  {N }. Шаг 2. Преобразовав правила вывода грамматики, получим грамматику G  ({, n}, {L, M , N}, P, L) с правилами P : 1) L  N  | n; 2) M  N  | n; 3) N  N  | n . 3.2.5 Левая факторизация правил Алгоритм Устранение левой факторизации правил Вход: КС-грамматика G  (VT , VN , P, S ) . Выход: Эквивалентная КС-грамматика G  (VT , VN , P, S ) без одинаковых префиксов в правых частях правил, определяющих нетерминалы. Шаг 1. Записать все правила для нетерминала X , имеющие одинаковые префиксы в виде одного правила с альтернативами:  V * , X  1 | 2 |  | n ; 1,  2 ,,  n V *. Шаг 2. Вынести за скобки влево префикс  в каждой строке-альтернативе: X   ( 1 |  2 |  |  n ). Шаг 3. Обозначить новым нетерминалом Y выражение, оставшееся в скобках: X  Y , Y  1 |  2 |  |  n . Шаг 4. Пополнить множество нетерминалов новым нетерминалом Y и заменить правила, подвергшиеся факторизации, новыми правилами для X и Y . Шаг 5. Повторить шаги 1-4 для всех нетерминалов грамматики, для которых это возможно и необходимо. Пример Дана грамматика G  ({k , l , m, n}, {S}, P, S ) с правилами P : 1) S  kSl; 2) S  kSm; 3) S  n . Преобразуем ее в эквивалентную грамматику G по алгоритму 4.6: Шаг 1. S  kSl | kSm | n . Шаг 2. S  kS(l | m) | n . Шаг 3,4. Пополнив множество нетерминалов новым нетерминалом С и заменив правила, подвергшиеся факторизации, получим грамматику G  ({k , l , m, n}, {S , C}, P, S ) с правилами P : 1) S  kSC; 2) S  n; 3) C  l; 4) C  m. 3.2.6 Устранение прямой левой рекурсии Алгоритм Устранение прямой левой рекурсии Вход: КС-грамматика G  (VT , VN , P, S ) . Выход: Эквивалентная КС-грамматика G  (VT , VN , P, S ) без прямой левой рекурсии, т.е. без правил вида A  A , A VN ,  V *. Шаг 1. Вывести из грамматики все правила для рекурсивного нетерминала X: X  X1 | X 2 |  | X m ( X VN ; 1,  2 ,, m V * ) X  1 |  2 |  |  n ( 1,  2 ,,  n V * ). Шаг 2. Внести новый нетерминал Y так, чтобы он описывал любой «хвост» строки, порождаемой рекурсивным нетерминалом X : Y  1Y |  2Y |  |  mY Y  1 |  2 |  |  m . Шаг 3. Заменить в рекурсивном правиле для X правую часть, используя новый нетерминал и все нерекурсивные правила для X так, чтобы генерируемый язык не изменился: X  1Y |  2Y |  |  nY X  1 |  2 |  |  n Y  1Y |  2Y |  |  mY Y  1 |  2 |  |  m . Шаг 4. Пополнить множество нетерминалов грамматики новым нетерминалом Y . Пополнить множество правил грамматики правилами, полученными на шаге 3. Шаг 5. Повторить действия шагов 1-4 для всех рекурсивных нетерминалов грамматики, после чего полученные множества нетерминалов и правил принять в качестве VN и P. Пример Дана грамматика G  ({a, b, c, d , z}, {S , A, B, C}, P, S ) с правилами P : 1) S  Aa; 2) A  Bb; 3) B  Cc | d ; 4) C  Ccbz | dbz . Шаг алгор. Действия и результ. C  Ccbz , C  dbz 1. Z  cbzZ , Z  cbz. 2. Z  cbzZ, Z  cbz. C  dbzZ , C  dbz, 3. 4. VN ={S,A,B,C,Z}, P’= 1) S  Aa; 2) A  Bb; 3) B  Cc | d ; 4) C  dbzZ | dbz; 5) Z  cbzZ | cbz. После устранения прямой левой рекурсии получим эквивалентную грамматику G  ({a, b, c, d , z}, {S , A, B, C, Z}, P, S ) с правилами P : 1) S  Aa; 2) A  Bb; 3) B  Cc | d ; 4) C  dbzZ | dbz; 5) Z  cbzZ | cbz. 3.3 Автомат с магазинной памятью КС-языки можно распознавать с помощью автомата с магазинной памятью (МП-автомата). 3.3.1 Определение МП-автомата Определение МП-автомат можно представить в виде семерки: M  (Q, T , N , F , q0, N0 , Z ) , где Q – конечное множество состояний автомата; T – конечный входной алфавит; N – конечный магазинный алфавит; F – магазинная функция, отображающая множество (Q  (T  { })  N ) во множество всех подмножеств множества Q  N * , т.е. F : (Q  (T  { })  N )  P(Q  N * ) ; F : q0 – начальное состояние автомата, q0 Q; N0– начальный символ магазина, N0  N; Z – множество заключительных состояний автомата, Z  Q. Определение Конфигурацией МП-автомата называется тройка вида: (q,  ,  )  (Q  T *  N * ) , где q – текущее состояние автомата, q  Q;  - часть входной строки, первый символ которой находится под входной головкой,   T *;  - содержимое магазина,   N *.  Общая схема МП-автомата представлена на рисунке 3.1. an Входная цепочка символов a1 a2 Считывающая головка УУ Управляющее устройство N1 N2 N3 … Стек (магазин) Рисунок 3.1 – Схема МП-автомата Алгоритм Функционирование МП-автомата Начальной конфигурацией МП-автомата является конфигурация (q0,  , N0). Шаг работы МП-автомата будем представлять в виде отношения непосредственного следования конфигураций (обозначается «|=») и отношения достижимости конфигураций (обозначается «|=*»). Если одним из значений магазинной функции F (q  Q, t  (T  { }), S  N ) является (q  Q,   N * ) , то записывается (q, t , S ) | (q,  ,  ) . При этом возможны следующие варианты. 1) Случай t  T. Автомат находится в текущем состоянии q, читает входной символ t, имеет в вершине стека символ S. Он переходит в очередное состояние q , сдвигает входную головку на ячейку вправо и заменяет верхний символ S строкой  магазинных символов. Вариант    означает, что S удаляется из стека. 2) Случай t   . Отличается от первого случая тем, что входной символ t просто не принимается во внимание, и входная головка не сдвигается. Такой шаг работы МП-автомата называется  -шагом, который может выполняться даже после завершения чтения входной строки. Заключительной конфигурацией МП-автомата является конфигурация (q,  ,  ), где q  Z. Определение МП-автомат допускает входную стоку  , если существует путь по конфигурациям (q0 ,  , N0 ) | *(q,  ,  ) для некоторых q  Z и   N * . Определение Язык L, распознаваемый (принимаемый) МП-автоматом М определяется как множество вида: L( M )  { |   T * и (q0 ,  , N0 ) | * (q,  ,  ) для некоторых q  Z и   N * }. 3.3.2 Разновидности МП-автоматов Иногда определяют МП-автомат, который принимает строку, если после завершения ее чтения стек автомата будет пуст. В этом случае нет необходимости выделять множество заключительных состояний Z  Q, а описание заключительной конфигурации имеет вид (q,  ,  ), где q  Q. Говорят, что такой МП-автомат принимает строку языка опустошением магазина. Пример МП-автомат M  (Q, T , N , F , q0, N0 , Z ) , где Q= {А} Т= {(,)}, N= {I,0}, qo = A, N0 = I, F={ F(A,(,I)=(A,OI) F(A,(,O)=(A,OO) F(A,),O)=(A,  ) F(A,  ,I)=(A,  )} при распознавании строки ( ( ) ( ) ) строит последовательность конфигураций: (А, (() ()), I) |- (А, () () ), 01) |- (А,) ()), OOI) |- (А, ()), OI) |- ( A , ) ) , OOI) |- (А, ),О1) |- (А,  , I) |- (А,  ,  ). Язык, принимаемый МП-автоматом в данном примере, это КС-язык парных круглых скобок. Этот же язык генерирует КС-грамматика с правилами Р = {S ->(S), S-> SS, S ->  }. Из формального определения МП-автомата следует, что он может менять каждый раз только один символ в вершине стека. Этот МП-автомат не может, кроме того, продолжать работу при пустом стеке, так как   N. Однако если использовать расширенный МП-автомат, т.е. МП-автомат с магазинной функцией F : (Q  (T  { })  N * )  P(Q  N * ) , то указанные ограничения будут сняты. Определение МП-автомат с магазинной функцией F : (Q  (T  { })  N * )  P(Q  N * ) называется расширенным МП-автоматом, т.е. автоматом, который может заменять цепочку символов конечной длины в верхушке стека на другую цепочку символов конечной длины. МП-автомат называют детерминированным (ДМП-автоматом), если, находясь в любой конфигурации, он может выбрать не более одной следующей конфигурации. Это означает, что при любых значениях q  Q, а  (T  {  }) и N0 N |N0  N* (для расширенного автомата) магазинная функция  (q, a, Z) имеет не более одного значения. В противном случае МП-автомат является недетерминированным. Доказано соответствие КС-грамматик и МП-автоматов, которое можно сформулировать так: существуют КС-языки, МП-автоматы и расширенные МПавтоматы, определяющие один и тот же КС-язык.  3.3.3 Взаимосвязь МП-автоматов и КС-грамматик 3.3.3.1 Построение МП-автомата по КС-грамматике Построим МП-автомат, выполняющий левосторонний разбор. Данный автомат обладает только одним состоянием и принимает входную строку опустошением магазина. Стек используется для размещения текущей сентенции, первоначально это начальный символ грамматики. Очередная сентенция получается заменой верхнего нетерминала стека. Вход: КС-грамматика G  (VT , VN , P, S ) . Выход: МП-автомат M  (Q, T , N , F , q0 , N 0 , Z ) такой, что L(M) = L(G). Шаг 1. Положить Q = {q}, q0 = q, Z = , N = VT  VN, T = VT, N0 = S. Шаг 2. Для каждого правила вида (А  )  P , где  V * , сформировать магазинную функцию вида F (q,  , A)  (q,  ) . Эти функции предписывают замещать нетерминал в вершине стека по правилу грамматики. Шаг 3. Для каждого t VT сформировать магазинную функцию вида F (q, t , t )  (q,  ) , которая выталкивает из стека символ, совпадающий с входным, и перемещает читающую головку. Эти функции обеспечивают опустошение стека. Пример Дана КС-грамматика: G({+, (, ), a}, {S, A}, {SS+A | A, A(S) | a}, {S}). Последовательность построения МП-автомата будет иметь вид. 1) Q = {q}, q0 = q, T = {+, (, ), a }, N = {+, (, ), a, S, A}, N0 = S, Z = . 2) F(q,  , S) = (q, S+A), F(q,  , S) = (q, A), F(q,  , A) = (q, (S)); F(q,  , A) = (q, a). 3) F(q, t, t) = (q,  ) для каждого t {+, (, ), a}. Распознавание строки (а) построенным МП-автоматом представлено в таблице 3.1. Полученный МП-автомат является недетерминированным. Таблица 3.1 – Распознавание МП-автоматом строки (а) Номер конфигурации 1 Текущее состояние q Входная строка Содержимое магазина (a) S 2 3 4 5 6 7 8 q q q q q q q (a) (a) a) a) a) )  A (S) S) A) a) )  3.3.3.2 Построение расширенного МП-автомата по КС-грамматике Построим МП-автомат, выполняющий правосторонний разбор. Данный автомат имеет единственное текущее состояние и одно заключительное состояние, в котором стек пуст. Стек содержит левую часть текущей сентенции. Первоначально в стек помещается специальный магазинный символ, маркер пустого стека #. На каждом шаге автомат по правилу грамматики замещает нетерминалом строку верхних символов стека или дописывает в вершину входной символ. Вход: КС-грамматика G  (VT , VN , P, S ) . Выход: расширенный МП-автомат M  (Q, T , N , F , q0 , N0 , Z ) такой, что L(M) = L(G). Шаг 1. Положить Q = {q, r}, q0 = q, Z = {r}, N = VT  VN  {#}, T = VT, N0 = #. Шаг 2. Для каждого правила вида ( A   )  P , где  V * , сформировать магазинную функцию вида F (q,  ,  )  (q, A) , предписывающую заменять правую часть правила в вершине стека нетерминалом из левой части, независимо от текущего символа входной строки. Шаг 3. Для каждого терминала t  T сформировать магазинную функцию вида F (q, t ,  )  (q, t ) , которая помещает символ входной строки в вершину стека, если там нет правой части правила, и перемещает читающую головку. Шаг 4. Предусмотреть магазинную функцию для перевода автомата в заключительное состояние F (q,  , # S )  (r ,  ) . Пример Для грамматики из предыдущего примера построить расширенный МП-автомат. Последовательность построения МП-автомата будет иметь вид. 1) Q = {q, r}, q0 = q, T = {+, (, ), a}, N = {+, (, ), a, S, A}, N0 = #, Z = r. 2) F(q,  , S+A) = (q, S), F(q,  , A) = (q, S), F(q,  , (S)) = (q, A), F(q,  , a) = (q, A). 3) F(q, t,  ) = (q, t) для каждого t {+, (, ), a}. 4) F(q,  , #S) = (r,  ). Распознавание строки (а) расширенным МП-автоматом представлено в таблице 3.2. Полученный МП-автомат является детерминированным. Таблица 3.2 – Распознавание расширенным МП-автоматом строки (а) Номер конфигурации 1 2 3 4 5 6 7 8 9 Текущее состояние q q q q q q q q r Входная строка Содержимое магазина (a) a) ) ) )     # #( #(a #(A #(S #(S) #A #S  3.4 Нисходящие распознаватели языков 3.4.1 Рекурсивный спуск 3.4.1.1 Сущность метода В основе метода рекурсивного спуска лежит левосторонний разбор стр оки языка. Исходной сентенциальной формой является начальный символ грамматики, а целевой – заданная строка языка. На каждом шаге разбора правило грамматики применяется к самому левому нетерминалу сентенции. Данный процесс соответствует построению дерева разбора цепочки сверху вниз (от корня к листьям). Пример Дана грамматика G({a, b, c, }, {S , A, B}, P, S ) с правилами P : 1) S  AB ; 2) A  a; 3) A  cA; 4) B  bA . Требуется выполнить анализ строки cabca. Левосторонний вывод цепочки имеет вид: S  AB  cAB  caB  cabA  cabcA  cabca  . Нисходящее дерево разбора цепочки представлено на рисунке 3.2. S A c A a B  b A c A a Рисунок 3.2 – Дерево нисходящего разбора цепочки cabca Метод рекурсивного спуска реализует разбор цепочки сверху вниз следующим образом. Для каждого нетерминального символа грамматики создается своя процедура, носящая его имя. Задача этой процедуры – начиная с указанного места исходной цепочки, найти подцепочку, которая выводится из этого нетерминала. Если такую подцепочку считать не удается, то процедура завершает свою работу вызовом процедуры обработки ошибок, которая выдает сообщение о том, что цепочка не принадлежит языку грамматики и останавливает разбор. Если подцепочку удалось найти, то работа процедуры считается нормально завершенной и осуществляется возврат в точку вызова. Тело каждой такой процедуры составляется непосредственно по правилам вывода соответс твующего нетерминала, при этом терминалы распознаются самой процедурой, а нетерминалам соответствуют вызовы процедур, носящих их имена. Пример Построим синтаксический анализатор методом рекурсивного спуска для грамматики G из предыдущего примера. Введем следующие обозначения: 1) СH – текущий символ исходной строки; 2) gc – процедура считывания очередного символа исходной строки в переменную СH; 3) Err - процедура обработки ошибок, возвращающая по коду соответствующее сообщение об ошибке. С учетом введенных обозначений, процедуры синтаксического разбора будут иметь вид. procedure S; begin A; B; if CH<> then ERR end; procedure A; begin if CH=a then gc else if CH=c then begin gc; A end else Err end; procedure B; begin if CH= b then begin gc; B end else Err end; 3.4.1.2 Достаточные рекурсивного спуска условия применимости метода Метод рекурсивного спуска применим к грамматике, если правила вывода грамматики имеют один из следующих видов: 1) A , где  (TN)*, и это единственное правило вывода для этого нетерминала; 2) Aa1 1 | a2 2 |…| an n, где ai T для каждого i=1, 2,…, n; aiaj для ij,  i(TN)*, т.е. если для нетерминала А несколько правил вывода, то они должны начинаться с терминалов, причем эти терминалы должны быть различными. Данные требования являются достаточными, но не являются необходимыми. Можно применить эквивалентные преобразования КС-грамматик, которые способствуют приведению грамматики к требуемому виду, но не гарантируют его достижения. При описании синтаксиса языков программирования часто встречаются правила, которые задают последовательность однотипных конструкций, отделенных друг от друга каким-либо разделителем. Общий вид таких правил: La | a,L или в сокращенной форме La{,a}. Формально здесь не выполняются условия метода рекурсивного спуска, т.к. две альтернативы начинаются одинаковыми терминальными символами. Но если принять соглашения, что в подобных ситуациях выбирается самая длинная подцепочка, выводимая из нетерминала L, то разбор становится детерминированным, и метод рекурсивного спуска будет применим к данному правилу грамматики. Соответствующая правилу процедура будет иметь вид: procedure L; begin if CH<>’a’ then Err else gc; while CH=’,’ do begin gc; if CH<>’a’ then Err else gc end end; 3.4.2 Распознаватели LL(k)-грамматик 3.4.2.1 Определение LL(k)-грамматики Определение КС-грамматика обладает свойством LL(k) для некоторого k>0, если на каждом шаге вывода для однозначного выбора очередной альтернативы МП-автомату достаточно знать символ на верхушке стека и рассмотреть первые k символов от текущего положения считывающей головки во входной строке. Определение КС-грамматика называется LL(k)-грамматикой, если она обладает свойством LL(k) для некоторого k>0. В основе распознавателя LL(k)-грамматик лежит левосторонний разбор строки языка. Исходной сентенциальной формой является начальный символ грамматики, а целевой – заданная строка языка. На каждом шаге разбора правило грамматики применяется к самому левому нетерминалу сентенции. Данный процесс соответствует построению дерева разбора цепочки сверху вниз (от корня к листьям). Отсюда и произошла аббревиатура LL(k): первая «L» (от слова «left») означает левосторонний ввод исходной цепочки символов, вторая «L» левосторонний вывод в процессе работы распознавателя. Определение Для построения распознавателей для LL(k)-грамматик используются два множества: - FIRST(k,  ) – множество терминальных цепочек, выводимых из цепочки  (VTVN)*, укороченных до k символов; - FOLLOW(k, A) – множество укороченных до k символов терминальных цепочек, которые могут следовать непосредственно за AVN в цепочках вывода. Формально эти множества можно определить следующим образом: - FIRST(k,  ) = {  VT* |  вывод  * и | |  k или  вывод  * x и | | = k; x,   (VTVN)*, k > 0}; - FOLLOW(k, A) = { VT* |  вывод S* A и  FIRST(k, );  , V*, AVN, k>0}. 3.4.2.2 Необходимое и достаточное условие LL(1)-грамматики Для того чтобы грамматика G(VN, VT, P, S) была LL(1)-грамматикой необходимо и достаточно, чтобы для каждого символа АVN, у которого в грамматике существует более одного правила вида А 1 |  2 |…|  n, выполнялось требование: FIRST(1,  iFOLLOW(1, A))  FIRST(1,  jFOLLOW(1, A)) = ,  ij, 0 Bj ( Bi, Bj  V), если и только если существует правило AxCBjy и вывод С*zBi или существует правило AxCDy  P и вывод С*zBi и D*Bjw, где A, C, D  VN, x, y, z, w  V*. 2) Различные правила в грамматике имеют разные правые части. Определение Отношения =, <, > называют отношениями простого предшествования для символов грамматики. В основе распознавателя для грамматик простого предшествования лежит правосторонний разбор строки языка. Исходной сентенциальной формой является заданная строка языка, а целевой – начальный символ грамматики. На каждом шаге разбора в исходной цепочке символов пытаются выделить подцепочку, совпадающую с правой частью некоторого правила вывода грамматики, и заменить ее нетерминалом, стоящим в левой части этого правила. Данная операция называется сверткой к нетерминалу, а заменяемая подстрока – основой сентенции. Описанный процесс разбора соответствует построению дерева вывода цепочки снизу вверх (от листьев к корню). Метод предшествования основан на том факте, что отношения между двумя соседними символами распознаваемой строки соответствуют трем следующим вариантам: - Bi = Bi+1, если символы Bi и Bi+1 принадлежат основе; - Bi < Bi+1, если Bi+1 – крайний левый символ некоторой основы; - Bi > Bi+1, если Bi – крайний правый символ некоторой основы. 3.5.1.1.2 Поиск основы сентенции грамматики Если грамматика является грамматикой простого предшествования, то для поиска основы каждой ее сентенции надо просматривать элементы сентенции слева направо и найти самую левую пару символов xj и xj+1, такую что xj>xj+1. Окончанием основы сентенции будет xj. Далее просматривать элементы сентенции справа налево, начиная с символа xj до тех пор, пока не будет найдена самая правая пара символов xi-1 и xi, такая что xi-1 < xi. Заголовком основы будет символ xi. Таким образом, будет найдена основа сентенции, имеющая вид xi xi+1…xj-1 xj. Схема поиска основы сентенции грамматики представлена на рисунке 3.4. Основа сентенции x1 x2 < … … xi-1 < xi = xi+1 … … xj-1 = xj > xj+1 … … > xn Рисунок 3.4 – Схема поиска основы сентенции грамматики На основе отношений предшествования строят матрицу предшествования грамматики. Строки и столбцы матрицы предшествования помечаются символами грамматики. Пустые клетки матрицы указывают на то, что данные символы не связаны отношением предшествования. Определение Построение матрицы предшествования основано на двух вспомогательных множествах, определяемых следующим образом: - L(A) = {X |  A*Xz}, AVN, XV, zV* - множество крайних левых символов относительно нетерминального символа А; - R(A) = {X |  A*zX}, AVN, XV, zV* - множество крайних правых символов относительно нетерминального символа А. Определение Отношения предшествования можно определить с помощью введенных множеств следующим образом: - Bi = Bj ( Bi, Bj  V), если и только если существует правило AxBiBjy P, где AVN, x, y V*; - Bi < Bj ( Bi, Bj  V), если и только если существует правило AxBiDyP и Bj  L(D), где A, D  VN, x, y  V*; - Bi > Bj ( Bi, Bj  V), если и только если существует правило AxCBjy и Bi  R(C) или существует правило AxCDy  P и Bi  R(C), BjL(D), где A, C, D  VN, x, y  V*. Матрицу предшествования дополняют символами н и к (начало и конец цепочки). Для них определены следующие отношения предшествования: - н < X,  X  V, если X  L(S); - к > X,  X  V, если X  R(S). 3.5.1.1.3 Построение множеств L(A) и R(A) Шаг 1. Для каждого нетерминального символа А ищем все правила, содержание А в левой части. Во множество L(A) включаем самый левый символ из правой части правил, а во множество R(A) – самый крайний правый символ из правой части, т.е.  A VN: L0(A) = {X | AXy, X  V, y  V*}, R0(A) = {X | AyX, X  V, y  V*}. Шаг 2. Для каждого нетерминального символа А: если множество L(A) содержит нетерминальные символы грамматики А, A, …, то множество L(A) надо дополнить символами, входящими в соответствующие множества L(А), L(A) и т.д., … и не входящими в L(A). Аналогичную операцию выполнить для множеств R(A), т.е.  A  VN: Li(A) = Li-1(A)Li-1(B),  B  (Li-1(A) VN), Ri(A) = Ri-1(A)Ri-1(B),  B  (Ri-1(A) VN). Шаг 3. Если на предыдущем шаге хотя бы одно множество L(A) или R(A) для некоторого символа грамматики изменилось, то вернуться к шагу 2, иначе построение закончено. Т.е. если существует AVN: Ri(A)Ri-1(A) или Li(A)Li1(A), то положить i:=i+1 и вернуться к шагу 2, иначе построение закончено и R(A) = Ri(A) и L(A) = Li(A). 3.5.1.1.5 Алгоритм «сдвиг - свертка» для грамматик простого предшествования Шаг 1. Поместить в верхушку стека символ н, считывающую головку – в начало входной цепочки символов. Шаг 2. До тех пор, пока не будет обнаружена ошибка, либо успешно завершен алгоритм разбора, сравниваем отношение простого предшествования символа на верхушке стека и очередного символа входной строки. При этом возможны следующие ситуации: если самый верхний символ стека имеет меньшее или равное предшествование, чем очередной символ входной строки, то производим операцию «сдвиг» (перенос текущего символа из входной цепочки в стек и перемещение считывающей головки на один символ вправо); - если самый верхний символ стека имеет большее предшествование, чем очередной символ входной строки, то выполняем операцию «свертка». Для этого находим на верхушке стека «основу» сентенции, т.е. все символы, имеющие равное предшествование или один символ на верхушке стека. Символы основы удаляем из стека, выбираем правило вывода грамматики, имеющее правую часть, совпадающую с основой, и помещаем в стек левую часть выбранного правила. Если такого правила вывода найти не удалось, то выдается сообщение об ошибке, и разбор завершен неудачно; - если не установлено ни одно отношение предшествования между текущим символом входной цепочки и самым верхним символом в стеке, то алгоритм прерывается сообщением об ошибке; - если в стеке остаются символы нS, а во входном буфере только символ к, то входная строка прочитана полностью, и алгоритм разбора завершен успешно. Пример Дана грамматика G({a, (, )}, {S, R}, P, S), с правилами P: 1) S(R | a; 2) RSa). Построить распознаватель для строки (((aa)a)a)к. Этап 1. Построим множества крайних левых и крайних правых символов L(A) и R(A) относительно всех нетерминальных символов грамматики (таблица 3.7). Таблица 3.7 – Построение множеств L(A) и R(A) для грамматики G Шаг 1 2 Результат Li(A) L0(S)={(, a} L0(R)={S} L1(S)={(, a} L1(R)={S, (, a} L2(S)={(, a} L2(R)={S, (, a} L(S)={(, a} L(R)={S, (, a} Ri(A) R0(S)={R, a} R0(R)={)} R1(S)={R, a, )} R1(R)={)} R2(S)={R, a, )} R2(R)={)} R(S)={R, a, )} R(R)={)} Этап 2. На основе построенных множеств и правил вывода грамматики составим матрицу предшествования символов (таблица 3.8). Поясним заполнение матрицы предшествования. В правиле грамматики S(R символ ( стоит слева от нетерминального символа R. Во множестве L(R) входят символы S, (, a. Ставим знак < в клетках матрицы, соответствующих этим символам, в строке для символа (. В правиле грамматики RSa) символ a стоит справа от нетерминального символа S. Во множество R(S) входят символы R, a, ). Ставим знак > в клетках матрицы, соответствующих этим символам, в столбце для символа a. В строке символа н ставим знак < в клетках символов, входящих во множество L(S), т.е. символов (, a. В столбце символа к ставим знак > в клетках, входящих во множество R(S), т.е. символов R, a, ). В клетках, соответствующих строке символа S и столбцу символа a, ставим знак =, т.к. существует правило RSa), в котором эти символы стоят рядом. По тем же соображениям ставим знак = в клетках строки а и столбца ), а также строки ( и столбца R. Таблица 3.8 – Матрица предшествования символов грамматики Символы S R a ( ) н S < R = a = > > < > < ( ) к = > > < > < Шаг 3. Функционирование распознавателя для цепочки (((aa)a)a) показано в таблице 3.9. Таблица 3.9 – Алгоритм работы распознавателя цепочки (((aa)a)a) Шаг 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Стек н н( н(( н((( н(((a н(((S н(((Sa н(((Sa) н(((R н((S н((Sa н((Sa) н((R н(S н(Sa н(Sa) Входной буфер (((aa)a)a)к ((aa)a)a)к (aa)a)a)к aa)a)a)к a)a)a)к a)a)a)к )a)a)к a)a)к a)a)к a)a)к )a)к a)к a)к a)к )к к Действие сдвиг cдвиг cдвиг cдвиг свертка Sa сдвиг сдвиг свертка RSa) свертка S(R сдвиг сдвиг свертка RSa) свертка S(R сдвиг сдвиг свертка RSa) 17 18 н(R нS к к свертка S(R строка принята Шаг 4. Получили следующую цепочку вывода: S(R(Sa)((Ra)((Sa)a)(((Ra)a)(((Sa)a)a)(((aa)a)a). Восходящее дерево вывода цепочки представлено на рисунке 3.5.2 S R S R S R S ( ( ( a a ) a ) a ) Рисунок 3.5 – Дерево вывода для цепочки (((aa)a)a) в грамматике G 3.5.1.2 Грамматика операторного предшествования 3.5.1.2.1 Определение грамматики операторного предшествования Определение КС-грамматика G (VN, VT, P, S) называется грамматикой операторного предшествования, если выполняются следующие условия: 1) Для каждой упорядоченной пары терминальных символов выполняется не более чем одно из трех отношений предшествования: а) а = b, если и только если существует правило A—>xaby Р или правило А->хаСbу, где a,b V T , A,C V N , x.yV*; б) а < b, если и только если существует правило А->хаСу Р и вывод C=>*bz или вывод C=>*Dbz, где a,bVT, A,C,DVN, x,y,zV*; в) а > b, если и только если существует правило А—>хСЬу Р и вывод C=>*za или вывод C=>*zaD, где a,bVT, A,C,DVN, x,y,zV*. 2) Различные правила в грамматике имеют разные правые части, -правила отсутствуют. 3) Правила грамматики операторного предшествования не могут содержать двух смежных нетерминальных символов в правой части, т.е. в грамматике операторного предшествования G(VN,VT,P,S) не может быть ни одного правила вида: А->хВСу, где A,B,CVN, x,yV* (здесь х и у — это произвольные цепочки символов, могут быть и пустыми). 3.5.1.2.2 Построение множеств Lt(A) и Rt(A) Принцип работы распознавателя для грамматики операторного предшествования аналогичен грамматике простого предшествования, но отношения предшествования проверяются в процессе разбора только между терминальными символами. Для грамматики данного вида на основе установленных отношений предшествования также строится матрица предшествования, но она содержит только терминальные символы грамматики. Для построения этой матрицы удобно ввести множества крайних левых и крайних правых терминальных символов относительно нетерминального символа А – Lt(A) или Rt(A): Lt(A) = {t |  A=>*tz или  A=>*Ctz }, где tVT, A.CVN, zV*; Rt(A)= {t |  A=>*zt или  A=>*ztC }, где tVT, A,CVN, zV*. Тогда определения отношений операторного предшествования будут выглядеть так: а) а = b, если  правило A→xaby Р или правило U->xaCby, где a,bVT, А,СVN х,уV*; б) а < b, если  правило А→хаСу Р и b Lt (C), где a,bVT, A,CVN, x,yV*; в) а > b, если  правило A→xCby Р и a Rt(C), где a,bVT, A,CVN, x,yV*. В данных определениях цепочки символов x,y,z могут быть и пустыми цепочками. Для нахождения множеств Lt(A) и Rt(A)предварительно необходимо выполнить построение множеств L(A) и R(A), как это было рассмотрено ранее. Далее для построения Lt(A) и Rt(A) используется следующий алгоритм: Шаг 1.  AVN: Rt0(A){t |  A→ytB или A→yt, tVT, BVN, yV*; Lt0(A){t |  A→Bty или A→ty, tVT, BVN, yV*; Для каждого нетерминального символа А ищем все правила, содержащие А в левой части. Во множество L(A) включаем самый левый терминальный символ из правой части правил, игнорируя нетерминальные символы, а во множество R(А) самый крайний правый терминальный символ из правой части правил. Переходим к шагу 2. Шаг 2.  AVN: Rti(A) = Rti-1(A)  Rti-1 (B),  В  (R(A)  VN), Lti(А) = Lti-1(A)  Lti-1(B),  В  (L(A)  VN). Для каждого нетерминального символа А: если множество L(A) содержит нетерминальные символы грамматики А', А", ..., то его надо дополнить символами входящими в соответствующие множества L t(А’), L t(A"), ... и не входящими в L t (А). Ту же операцию надо выполнить для множеств R(A) и Rt(А). Шаг З. Если  AVN : Rti(A)  Rti-1(A или Lti(А)  Lti-1(A), то i:=i+1 и вернутся к шагу 2, иначе построение закончено: Rt(A) = Rti(A) и Lt(A) = Lti(А). Если на предыдущем шаге хотя бы одно множество Rt(A) или Lt(A) для некоторого символа грамматики изменилось, то надо вернуться к шагу 2, иначе построение закончено. Для практического использования матрицу предшествования дополняют символами  í и  ê ( начало и конец цепочки). Для них определены следующие отношения предшествования:  í <· a,  aVT, если  S=>*ax или  S=>*Cax, где S,CVN, xV* или если a Lt(S);  ê ·> а,  aVT, если  S=>*xa или  S=>*xaC, где S,CVN, xV* или если a Rt(S). Здесь S — целевой символ грамматики. Матрица предшествования служит основой для работы распознавателя языка, заданного грамматикой операторного предшествования. Поскольку она содержит только терминальные символы, то, следовательно, будет иметь меньший размер, чем аналогичная матрица для грамматики простого предшествования. Следует отметить, что напрямую сравнивать матрицы двух грамматик нельзя — не всякая грамматика простого предшествования является грамматикой операторного предшествования, и наоборот. 3.5.1.2.4 Алгоритм «сдвиг-свертка» для грамматики операторного предшествования Этот алгоритм в целом похож на алгоритм для грамматик простого предшествования, рассмотренный выше. Он также выполняется расширенным МП-автоматом и имеет те же условия завершения и обнаружения ошибок. Основное отличие состоит в том, что при определении отношения предшествования этот алгоритм не принимает во внимание находящиеся в стеке нетерминальные символы и при сравнении ищет ближайший к верхушке стека терминальный символ. Однако после выполнения сравнения и определения границ основы при поиске правила в грамматике нетерминальные символы следует, безусловно, принимать во внимание. Алгоритм состоит из следующих шагов. Шаг 1. Поместить в верхушку стека символ  í , считывающую головку — в начало входной цепочки символов. Шаг 2. Сравнить с помощью отношения предшествования терминальный символ, ближайший к вершине стека (левый символ отношения), с текущим символом входной цепочки, обозреваемым считывающей головкой (правый символ отношения). При этом из стека надо выбрать самый верхний терминальный символ, игнорируя все возможные нетерминальные символы. Шаг 3. Если имеет место отношение <· или =, то произвести сдвиг (перенос тощего символа из входной цепочки в стек и сдвиг считывающей головки на один шаг вправо) и вернуться к шагу 2. Иначе перейти к шагу 4. Шаг 4. Если имеет место отношение ·>, то произвести свертку. Для этого надо найти на вершине стека все терминальные символы, связанные отношение («основу»), а также все соседствующие с ними нетерминальные символы (при определении отношения нетерминальные символы игнорируются). Если терминальных символов, связанных отношением =, на верхушке стека нет, то в качестве основы используется один, самый верхний в стеке терминальный символ стека. Все (и терминальные, и нетерминальные) символы, составляющие основу надо удалить из стека, а затем выбрать из грамматики правило, имеющее правую часть, совпадающую с основой, и поместить в стек левую часть выбранного правила. Если правило, совпадающее с основой, найти не удалось, то необходимо прервать выполнение алгоритма и сообщить об ошибке, иначе, если разбор не закончен, то вернуться к шагу 2. Шаг 5. Если не установлено ни одно отношение предшествования между текущим символом входной цепочки и самым верхним терминальным символом в стеке, то надо прервать выполнение алгоритма и сообщить об ошибке. Конечная конфигурация данного МП-автомата совпадает с конфигурацией при распознавании цепочек грамматик простого предшествования. Пример Дано: G({(, ), ^, &, ~, a}, {S, T, E, F}, P, S), где P: S→S^T | T T→T&E | E E→~E | F F→ (E) | a Построить: распознаватель для G. Таблица 3.10 - Построение множеств L(A) и R(A) i 1 2 Li(A) L0(S)={S, T} L0(T)={T, E} L0(E)={~, F} L0(F)={(, a} L1(S)={S, T, E} L1(T)={T, E, ~, F} L1(E)={~, F, (, a} L1(F)={(, a} L2(S)={S, T, E, ~, F, (, a} L2(T)={T, E, ~, F, (, a} L2(E)={~, F, (, a} Ri(A) R0(S)={T} R0(T)={E} R0(E)={E, F} R0(F)={), a} R1(S)={T, E} R1(T)={E, F} R1(E)={E, F, ), a} R1(F)={), a} R2(S)={T, E, F, ), a} R2(T)={E, F, ) a} R2(E)={E, F, ), a} L2(F)={(, a} L3(S)={S, T, E, ~, F, (, a} L3(T)={T, E, ~, F, (, a} L3(E)={~, F, (, a} L3(F)={(, a} 3 R2(F)={), a} R3(S)={T, E, F, ), a} R3(T)={E, F, ) a} R3(E)={E, F, ), a} R3(F)={), a} Таблица 3.11 - Построение множеств Lt(A) и Rt(A) i 1 2 Lt(A) Lt0(S)={^} Lt0(T)={&} Lt0(E)={~} Rt(A) Rt0(S)={^} Rt0(T)={&} Rt0(E)={~} Lt0(F)={(, a} Lt1(S)={^, &, ~, (, a } Lt1(T)={&, ~, (, a} Rt0(F)={), a} Rt1(S)={^, &, ~, ), a} Rt1(T)={&, ~, ), a} Lt1(E)={~, (, a} Lt1(F)={(, a} Rt1(E)={~, ), a} Rt1(F)={), a} Lt2(S)={^, &, ~, (, a } Lt2(T)={&, ~, (, a} Lt2(E)={~, (, a} Rt2(S)={^, &, ~, ), a} Rt2(T)={&, ~, ), a} Rt2(E)={~, ), a} Lt2(F)={(, a} Rt2(F)={), a} Таблица 3.12 - Матрица операторного предшествования символов грамматики Символы ^ & ~ ( ) а ê ^ & ~ ( ) а í ·> ·> ·> <· ·> ·> <· <· ·> ·> <· ·> ·> <· <· <· <· <· <· <· <· <· ·> ·> ·> = ·> ·> <· <· <· <· ·> ·> ·> <· <· ·> ·> <· Для ^ находящейся в правиле вывода слева от нетерминала Т, во множество Lt(Т) входят символы &, ~, (, a , значит в строке матрицы для ^ ставим знак меньшего предшествования в позициях этих символов. С другой стороны этот символ ^ находится справа от S. Во множество Rt(S) входят символы ^, &, ~, ), a, значит знак большего предшествования ставится в столбце для ^ в позициях этих символов. Символы ( и ) в правиле вывода находятся радом, поэтому в позиции этих символов ставится знак равного предшествования (игнорируя нетерминал Е). 3.5.2 Распознаватели LR(k)-грамматик Распознаватели LR(k)-грамматик основаны на построении дерева разбора снизу вверх и правостороннем выводе цепочек. Определение КС-грамматика обладает свойством LR(k), k>0, если на каждом шаге вывода для однозначного решения вопроса о выполняемом действии в алгоритме «сдвиг-свертка» расширенному МП-автомату достаточно знать содержимое верхней части стека и рассмотреть первые k символов от текущего положения считывающей головки автомата во входной цепочке символов. Определение Грамматика называется LR(k)-грамматикой, если она обладает свойством LR(k) для некоторого к>0. Первая литера «L» обозначает порядок чтения входной цепочки символов: слева— направо. Вторая литера «R» происходит от слова «right» и означает, что в результате работы распознавателя получается правосторонний вывод . Для того чтобы формально определить LR(k) свойство для КС-грамматик, введем понятие пополненной КС-грамматики. Определение Грамматика G' является пополненной грамматикой, построенной на основании исходной грамматики G(VT,VN,P,S), если выполняются следующие условия: 1) грамматика G' совпадает с грамматикой G, если целевой символ S не встречается нигде в правых частях правил грамматики G; 2) грамматика G' строится как грамматика G(VT ,VN  {S’},P  {S’→S},S’), если целевой символ S встречается в правой части хотя бы одного правила из множества Р в исходной грамматике G. Понятие «пополненной грамматики» введено исключительно с той целью, чтобы в процессе работы алгоритма «сдвиг-свертка» выполнение свертки к целевому символу пополненной грамматики S' служило сигналом к завершению алгоритма (поскольку в пополненной грамматике символ S' в правых частях правил нигде не встречается). Теперь рассмотрим формальное определение LR(k) свойства. Если для произвольной КС-грамматики G в ее пополненной грамматике G1 для двух произвольных цепочек вывода из условий: 1) S' =>* αAω => aβω 2) S' =>* γВх => αβу 3) FIRST(k.ω) = FIRST(k.y) следует, что αAω = γВх (то есть α = γ, А = В и ω = у), то доказано, что грамматика G обладает LR(k) свойством. Очевидно, что тогда и пополненная грамматика G' также обладает LR(k) свойством. Распознаватель для LR(k)-грамматик функционирует на основе управляющей таблицы Т. Эта таблица состоит из двух частей, называемых «действия» и «пере- ходы». По строкам таблицы распределены все цепочки символов на верхушке стека, которые могут приниматься во внимание в процессе работы распознавателя. По столбцам в части «действия» распределены все части входной цепочки символов длиной не более k (аванцепочки), которые могут следовать за считывающей головкой автомата в процессе выполнения разбора; а в части «перехо ды» — все терминальные и нетерминальные символы грамматики, которые могут появляться на верхушке стека автомата при выполнении действий (сдвигов или сверток). Клетки управляющей таблицы Т в части «действия» содержат следующие данные: «сдвиг» — если в данной ситуации требуется выполнение сдвига (переноса текущего символа из входной цепочки в стек); «успех» — если возможна свертка к целевому символу грамматики S и разбор входной цепочки завершен; целое число («свертка») — если возможно выполнение свертки (число обозначает номер правила грамматики, по которому должна выполняться свертка); «ошибка» — во всех других ситуациях. Действия, выполняемые распознавателем, можно вычислять всякий раз на основе состояния стека и текущей аванцепочки. Однако этого вычисления можно из бежать, если после выполнения действия сразу же определять, какая строка таблицы Т будет использована для выбора следующего действия. Тогда эту строку можно поместить в стек вместе с очередным символом и выбирать затем в момент, когда она понадобится. Таким образом, автомат будет хранить в стеке не только символы алфавита, но и связанные с ними строки управляющей таблицы Т. Клетки управляющей таблицы Т в части «переходы» как раз и служат для выяснения номера строки таблицы, которая будет использована для определения вы полняемого действия на очередном шаге. Эти клетки содержат следующие данные: целое число — номер строки таблицы Т; «ошибка» — во всех других ситуациях. Для удобства работы распознаватель LR(k)-грамматики использует также два специальных символа  н , и  к . Считается, что входная цепочка символов всегда начинается символом  н и завершается символом  к . Тогда в начальном состоянии работы распознавателя символ  í находится на верхушке стека, а считывающая головка обозревает первый символ входной цепочки. В конечном состоянии в стеке должны находиться символы S (целевой символ) и  н , а считывающая головка автомата должна обозревать символ  к . Алгоритм функционирования распознавателя LR(k)-грамматики можно описать следующим образом: Шаг 1. Поместить в стек символ  н и начальную (нулевую) строку управляющей таблицы Т. В конец входной цепочки поместить символ  к . Перейти к шагу 2. Шаг 2. Прочитать с вершины стека строку управляющей таблицы Т. Выбрать из этой строки часть «действие» в соответствии с аванцепочкой, обозреваемой считывающей головкой автомата. Перейти к шагу 3. Шаг 3. В соответствии с типом действия выполнить выбор из четырех вариантов: «сдвиг» — если входная цепочка не прочитана до конца, прочитать и запомнить как «новый символ» очередной символ из входной цепочки, сдвинуть считывающую головку на одну позицию вправо, иначе прервать выполнение алгоритма и сообщить об ошибке; целое число {«свертка») - выбрать правило в соответствии с номером, удалить из стека цепочку символов, составляющую правую часть выбранного правила, взять символ из левой части правила и запомнить его как «новый символ»; «ошибка» — прервать выполнение алгоритма, сообщить об ошибке; «успех» — выполнить свертку к целевому символу S, прервать выполнение алгоритма, сообщить об успешном разборе входной цепочки символов, если входная цепочка прочитана до конца, иначе сообщить об ошибке. Конец выбора. Перейти к шагу 4. Шаг 4. Прочитать с вершины стека строку управляющей таблицы Т. Выбрать из этой строки часть «переход» в соответствии с символом, который был запомнен как «новый символ» на предыдущем шаге. Перейти к шагу 5. Шаг 5. Если часть «переход» содержит вариант «ошибка», тогда прервать выполнение алгоритма и сообщить об ошибке, иначе (если там содержится номер строки управляющей таблицы Т) положить в стек «новый символ» и строку таблицы Т с выбранным номером. Вернуться к шагу 2. Рассмотрим примеры применения конкретных управляющих таблиц. Пример Распознаватель для грамматики LR(0) При k=0 распознающий расширенный МП-автомат совсем не принимает во внимание текущий символ, обозреваемый его считывающей головкой. Решение о выполняемом действии принимается только на основании содержимого стека автомата. При этом не должно возникать конфликтов между выполняемым действием (сдвиг или свертка), а также между различными вариантами при выполнении свертки. Управляющая таблица для LR(0)-грамматики строится на основании понятия «левых контекстов» для нетерминальных символов: очевидно, что после выполнения свертки для нетерминального символа А в стеке МП-автомата ниже этого символа будут располагаться только те символы, которые могут встречаться в цепочке вывода слева от А. Эти символы и составляют «левый контекст» для А. Поскольку выбор между сдвигом или сверткой, а также между типом свертки в LR(0)-грамматиках выполняется только на основании содержимого стека, то LR(0)-грамматика должна допускать однозначный выбор на основе левого контекста для каждого символа. Рассмотрим простую КС-грамматику G({a,b}, {S}, {S→aSS|b}, S). Пополненная грамматика для нее будет иметь вид G ({a,b}, {S, S’}, {S' →S, S→aSS|b}, S’). Эта грамматика является LR(0)-грамматикой. Управляющая таблица для нее приведена в табл. 3.13 Таблица 3.13 Управляющая таблица для LR(0)-грамматики Стек Действие Переход S í S a b aS aSS Сдвиг Успех, 1 Сдвиг Свертка, 3 Сдвиг Свертка, 2 1 a 2 b 3 4 2 3 5 2 3 Колонка «Стек», присутствующая в таблице, в принципе не нужна для распознавателя. Она введена исключительно для пояснения каждого состояния стека автомата. Пустые клетки в таблице соответствуют состоянию «ошибка». Правила в грамматике пронумерованы от 1 до 3 (при этом будем считать, что состоянию «успех» — свертке к нулевому символу — в пополненной грамматике всегда соответствует первое правило). Распознаватель работает, невзирая на текущий символ, обозреваемый считывающей головкой расширенного МПавтомата, поэтому колонка «Действие» в таблице имеет только один столбец, не помеченный никаким символом, — указанное в ней данное действие выполняется всегда для каждой строки таблицы. Конфигурацию расширенного МП-автомата будем отображать в виде трех компонентов: не прочитанная еще часть входной цепочки символов, содержимое стека МП-автомата, последовательность номеров примененных правил грамматики (поскольку автомат имеет только одно состояние, его можно не учитывать). В стеке МП-автомата вместе с помещенными туда символами показаны и номера строк управляющей таблицы, соответствующие этим символам в формате {символ, номер строки}. Разбор цепочки aabbb. 1 (aabbb  ê , {  í ,0}, ε) 2 (abbb  ê , {  í ,0}{а,2}, ε) 3 (bbb  ê , {  í ,0}{а,2}{а,2}, ε) 4 (bb  ê , {  í ,0}{a,2}{a,2}{b,3}, ε) 5 (bb  ê , {  í ,0}{a,2}{a,2}{S,4}, 3) 6 (b  ê , {  í ,0}{a,2}{a,2}{S,4}{b,3}, 3) 7 (b  ê , {  í ,0}{a,2}{a,2}{S,4}{S,5}, 3,3) 8 (b  ê , {  í ,0}{a,2}{S,4}, 3,3,2) 9 (  ê , {  í ,0}{a,2}{S,4}{b,3}, 3,3,2) 10 (  ê , {  í ,0}{a,2}{S,4}{S,5}, 3,3,2,3) 11 (  ê , {  í ,0}{S,l}, 3,3,2,3,2) 12 (  ê , {  í ,0}{S',*}, 3,3,2,3,2,1) - разбор завершен. Соответствующая цепочка вывода будет иметь вид (используется правосторонний вывод): S’ => S => aSS => aSb => aaSSb => aaSbb => aabbb. Пример Распознаватель для грамматики LR(1) Рассмотрим простую КС-грамматику G({а,b}, {S}, {S→SaSb|ε}, S). Пополненная грамматика для нее будет иметь вид G({a,b}, {S, S1}, {S'→S, S→SaSb|ε}. S ' ). Эта грамматика является LR(1)-грамматикой. Управляющая таблица для нее приведена в табл. 3.14 Таблица 3.14 Управляющая таблица для LR(1)-грамматики Стек í S Sa SaS SaSa SaSb SaSaS SaSaSb a свертка, 3 сдвиг свертка, 3 сдвиг свертка, 3 свертка, 2 сдвиг свертка, 2 Действие b a ê свертка, 3 успех,1 2 свертка, 3 сдвиг свертка, 3 Переход b S 1 3 4 5 6 свертка, 2 сдвиг свертка, 2 4 7 Разбор цепочки abababb. 1 (abababb  ê , {  í ,0}, ε) 2 (abababb  ê , {  í ,0}{S,1}, 3) 3 (bababb  ê , {  í ,0}{S,l}{a,2}, 3) 4 (bababb  ê , {  í ,0}{S,l}{a,2}{S3h 3,3) 5 (ababb  ê , {  í ,0}{S,l}{a,2}{S,3}{b,5}, 3,3) 6 (ababb  ê , {  í ,0}{S,1}, 3,3,2) 7 (babb  ê , {  í ,0}{S,l}{a,2}, 3,3,2) 8 (babb  ê , {  í ,0}{S,l}{a,2}{S,3}, 3,3,2,3) 9 (abb  ê , {  í ,0}{S,l}{a,2}{S,3}{b,5}, 3,3,2,3) 10 (abb  ê , {  í ,0}{S,l}, 3,3,2,3,2) 11 (bb  ê , {  í ,0}{S,l}{a,2}, 3,3,2,3,2) 12 (bb  ê , {  í ,0}{S,l}{a,2}{S,3}, 3,3,2,3,2,3) 13 (b  ê , {  í ,0}{S,l}{a,2}{S,3}{b,5}, 3,3,2,3,2,3) 14 Ошибка, нет данных для «b» в строке 5. На практике LR (k)-грамматики при k > 1 не применяются. На это имеются две причины. Во-первых, управляющая таблица для LR (k)-грамматики при k > 1 будет содержать очень большое число состояний, и распознаватель будет достаточно сложным и не столь эффективным. Во-вторых, для любого языка, определяемого LR(k)-грамматикой, существует LR(1)-грамматика, определяющая тот же язык. То есть для любой LR(k)-грамматики с k > 1 всегда существует эквивалентная ей LR(1)-грамматика. Более того, для любого детерминированного КС-языка существует LR(1)-грамматика (другое дело, что далеко не всегда такую грамматику можно легко построить). 3.6 Соотношение классов КС-грамматик и КС-языков 3.6.1 Соотношение классов КС-грамматик В общем случае можно выделить правоанализируемые и левоанализируемые КС-грамматики. Первые предполагают построение левостороннего (восходящего) распознавателя, вторые — правостороннего (нисходящего). Это вовсе не значит, что для КС-языка, заданного, например, некоторой левоанализируемой грамматикой, невозможно построить расширенный МП-автомат, который порождает правосторонний вывод. Указанное разделение грамматик относится только к по строению на их основе детерминированных МП-автоматов и детерминированных расширенных МП-автоматов. Только эти типы автоматов представляют интерес при создании компиляторов и анализе входных цепочек языков программирования. Недетерминированные автоматы, порождающие как левосторонние, так и правосторонние выводы, можно построить в любом случае для языка заданного любой КС-грамматикой, но для создания компилятора такие автоматы интереса не представляют. На рис. 3.6 изображена условная схема, дающая представление о соотношении классов левоанализируемых и правоанализируемых КС-грамматик ЛГ ПГ LR LL Рисунок 3.6 - Соотношение классов левоанализируемых и правоанализируемых КС-грамматик Классы левоанализируемых и правоанализируемых грамматик являются несопоставимыми. То есть существуют левоанализируемые КС-грамматики, на основе которых нельзя построить детерминированный расширенный МП-автомат; порождающий правосторонний вывод; и наоборот — существуют правоанализируемые КС-грамматикй, не допускающие построение МП-автомата, порождающего левосторонний вывод. Конечно, существуют грамматики, подпадающие под оба класса и допускающие построение детерминированных автоматов как с правосторонним, так и с левосторонним выводом. Следует помнить также, что все упомянутые классы КС-грамматик - это счетные, но бесконечные множества. Нельзя построить и рассмотреть все возмож- ные левоанализируемые грамматики или даже все возможные LL(1)-грамматики. Сопоставление классов КС-грамматик производится исключительно на основе анализа структуры их правил. Только на оснований такого рода анализа произвольная КС-грамматика может быть отнесена в тот или иной класс (или не сколько классов). Рассмотренный в данном пособии класс левоанализируемых LL-грамматик является собственным подмножеством класса LR-грамматик: любая LLграмматика является LR-грамматикой, но не наоборот — существуют LRграмматики, которые не являются LL-грамма-тиками. Значит, любая LLграмматика является правоанализируемой, но существуют также и другие левоанализируемые грамматики, не попадающие в класс правоанализируемых грамматик. Любой детерминированный КС-язык может быть задан, например, LR(1)грамматико, но в то же время, классы левоанализируемых и правоанализируемых грамматик несопоставимы, то напрашивается вывод: один и тот же детерминированный КС-язык может быть задан двумя или более несопоставимыми между собой грамматиками. Таким образом, можно вернуться к мысли о том, что проблема преобразования КС-грамматик неразрешима (на самом деле, конечно, наоборот: из неразрешимости проблемы преобразования КС грамматик следует возможность задать один и тот же КС-язык двумя несопоставимыми грамматиками). 3.6.2 Соотношение классов КС-языков КС-язык называется языком некоторого класса КС-языков, если он может быть задан КС-грамматикой из данного класса КС-грамматик. Например, класс LLязыков составляют все языки, которые могут быть заданы с помощью LL-грамматик. КС-языки Детерминированные КС-языки LR(1)-языки  LR-языки Языки простого предшествования Языки операторного предшествования LL-языки Рисунок 3.7– Соотношение между различными классами КС-языков Следует обратить внимание, прежде всего на то, что интересующий разработчиков компиляторов в первую очередь класс детерминированных КС- языков полностью совпадает с классом LR-языков и, более того, совпадает с классом LR(1)-языков. То есть, доказано, что для любого детерминированного КСязыка существует задающая его LR(1)-грамматика. Проблема состоит в том, что не всегда возможно найти такую грамматику, и нет формализованного алгоритма, как ее построить в общем случае. Также LL-языки являются собственным подмножеством LR-языков: всякий LL-язык является одновременно LR-языком, но существуют LR-языки, которые не являются LL-языками. Поэтому LL-языки образуют более узкий класс, чем LRязыки. Языки простого предшествования, в свою очередь, также являются собственным подмножеством LR-языков, а языки операторного предшествования собственным подмножеством языков простого предшествования. Интересно, что языки операторного предшествования представляют собой более узкий класс, чем языки простого предшествования. В то же время языки простого предшествования и LL-языки несопоставимы между собой: существуют языки простого предшествования, которые не являются LL-языками, и в то же время существуют LL-языки, которые не являются языками простого предшествования. Однако существуют языки, которые одновременно являются и языками простого предшествования, и LL-языками. Аналогичное замечание относится также к соотношению между собой языков операторного предшествования и LL-языков. Можно еще отметить, что язык арифметических выражений над символами а и b, заданный грамматикой G({+, -, /, *, a, b}, {S, T, E}, P, S), Р = {S->S+T|S-T|T, Т->Т*Е|Т/Е|Е, E->(S)|a|b), который многократно использовался в примерах в данном учебном пособии, подпадает под все указанные выше классы языков. Из приведенных ранее примеров можно заключить, что этот язык является и LLязыком, и языком операторного предшествования, а следовательно, и языком простого предшествования и, конечно, LR(1)-языком. В то же время этот язык по мере изложения материала пособия описывался различными грамматиками, не все из которых могут быть отнесены в указанные классы. Таким образом, соотношение классов КС-языков не совпадает с соотношением задающих их классов КС-грамматик. Это связано с неразрешимостью проблем преобразования и эквивалентности грамматик, которые не имеют строго формализованного решения. 4 Принципы построения языка 4.1 Лексика, синтаксис и семантика языка 4.2 Определение транслятора, компилятора, интерпретатора и ассемблера. Транслятор – это программа, которая переводит входную программу на исходном (входном) языке в эквивалентную ей выходную программу на результирующем (выходном) языке. Результатом работы транслятора будет результирующая программа, но только в том случае, если текст исходной программы является правильным — не содержит ошибок с точки зрения синтаксиса и семантики входного языка. Если исходная программа неправильная (содержит хотя бы одну ошибку), то результатом работы транслятора будет сообщение об ошибке (как правило, с дополнительными пояснениями и указанием места ошибки в исходной программе). В этом смысле транслятор сродни переводчику, например, с английского, которому подсунули неверный текст. Компилятор – это транслятор, который осуществляет перевод исходной программы в эквивалентную ей объектную программу на языке машинных команд или на языке ассемблера. Таким образом, компилятор отличается от транслятора лишь тем, что его результирующая программа всегда должна быть написана на языке машинных кодов или на языке ассемблера. Результирующая программа транслятора, в общем случае, может быть написана на любом языке — возможен, например, транслятор программ с языка Pascal на язык С. Соответственно, всякий компилятор является транслятором, но не наоборот — не всякий транслятор будет компилятором. Например, упомянутый выше транслятор с языка Pascal на С компилятором являться не будет. Ассемблер – компилятор, который переводит каждую команду исходной программы в одну машинную команду. Интерпретатор — это программа, которая воспринимает входную программу на исходном языке и выполняет ее. В отличие от трансляторов интерпретаторы не порождают результирующую программу (и вообще какого-либо результирующего кода) — и в этом принципиальная разница между ними. Интерпретатор, так же как и транслятор, анализирует текст исходной программы. Однако он не порождает результирующей программы, а сразу же выполняет исходную в соответствии с ее смыслом, заданным семантикой входного языка. Таким образом, результатом работы интерпретатора будет результат, заданный смыслом исходной программы, в том случае, если эта программа правильная, или сообщение об ошибке, если исходная программа неверна. 4.3 Общая схема работы компилятора Основные функции компилятора: 1) проверка исходной цепочки символов на принадлежность к входному языку; 2) генерация выходной цепочки символов на языке машинных команд или ассемблере. Процесс компиляции состоит из двух основных этапов: синтеза и анализа. На этапе анализа выполняется распознавание текста исходной программы и заполнение таблиц идентификаторов. Результатом этапа служит некоторое внутреннее представление программы, понятное компилятору. На этапе синтеза на основании внутреннего представления программы и информации, содержащейся в таблице идентификаторов, порождается текст результирующей программы. Результатом этого этапа является объектный код. Данные этапы состоят из более мелких стадий, называемых фазами. Состав фаз и их взаимодействие зависит от конкретной реализации компилятора. Но в том или ином виде в каждом компиляторе выделяются следующие фазы: 1) лексический анализ; 2) синтаксический анализ; 3) семантический анализ; 4) подготовка к генерации кода; 5) генерация кода. Определение Процесс последовательного чтения компилятором данных из внешней памяти, их обработки и помещения результатов во внешнюю память, называется проходом компилятора. По количеству проходов выделяют одно-, двух-, трех- и многопроходные компиляторы. В данном пособии предлагается схема разработки трехпроходного компилятора, в котором первый проход – лексический анализ, второй синтаксический, семантический анализ и генерация внутреннего представления программы, третий – интерпретация программы. Общая схема работы компилятора представлена на рисунке 4.3. Анализ Лексический анализ Синтаксически й разбор Анализ и локализация обнаруженных ошибок Сообщение об ошибке Семантически й анализ Внутреннее представление программы Синтез Подготовка к генерации кода Таблицы идентификаторов Исходная программа Рисунок 4.1– Общая схема работы компилятора 4.4 Лексический анализ Определение Лексический анализатор (ЛА) – это первый этап процесса компиляции, на котором символы, составляющие исходную программу, группируются в отдельные минимальные единицы текста, несущие смысловую нагрузку – лексемы. 4.4.1 Задачи лексического анализа Задача лексического анализа - выделить лексемы и преобразовать их к виду, удобному для последующей обработки. ЛА использует регулярные грамматики. ЛА необязательный этап компиляции, но желательный по следующим причинам: 1) замена идентификаторов, констант, ограничителей и служебных слов лексемами делает программу более удобной для дальнейшей обработки; 2) ЛА уменьшает длину программы, устраняя из ее исходного представления несущественные пробелы и комментарии; 3) если будет изменена кодировка в исходном представлении программы, то это отразится только на ЛА. В процедурных языках лексемы обычно делятся на классы: 1) служебные слова; 2) ограничители; 3) числа; 4) идентификаторы. Каждая лексема представляет собой пару чисел вида (n, k), где n – номер таблицы лексем, k - номер лексемы в таблице. Входные данные ЛА - текст транслируемой программы на входном языке. Выходные данные ЛА - файл лексем в числовом представлении. Пример Для модельного языка М таблица служебных слов будет иметь вид: 1) program; 2) var; 3) int; 4) bool; 5) begin; 6) end; 7) if; 8) then; 9) else; 10) while; 11) do; 12) read; 13) write; 14) true; 15) false. Таблица ограничителей содержит: 1) . ; 2) ; ; 3) , ; 4) : ; 5) := ; 6) (; 7) ) ; 8) + ; 9) - ; 10) * ; 11) / ; 12) ; 13)  ; 14)  ; 15) = ; 16) > ; 17) <. Таблицы идентификаторов и чисел формируются в ходе лексического анализа. Пример Описать результаты работы лексического анализатора для модельного языка М. Входные данные ЛА: program var k, sum: int; begin k:=0;… Выходные данные ЛА: (1, 1) (1, 2) (4, 1) (2, 3) (4, 2) (2, 4) (1, 3) (2, 2) (1, 5) (4, 1) (2, 5) (3, 1) (2, 2)… 4.4.2 Диаграмма состояний с действиями Анализ текста проводится путем разбора по регулярным грамматикам и опирается на способ разбора по диаграмме состояний, снабженной дополнительными пометками-действиями. В диаграмме состояний с действиями каждая дуга имеет вид, представленный на рисунке 2.4. Смысл этой конструкции: если текущим является состояние А и очередной входной символ совпадает с ti для какого либо i, то осуществляется переход в новое состояние В, при этом выполняются действия D1, D2, …, Dm. Для удобства разбора вводится дополнительное состояние диаграммы ER, попадание в которое соответствует появлению ошибки в алгоритме разбора. Переход по дуге, не помеченной ни одним символом, осуществляется по любому другому символу, кроме тех, которыми помечены все другие дуги, выходящие из данного состояния. t 1 , t 2 , …, t n А D1 , D2 , …, Dm В Рисунок 4.2 – Дуга ДС с действиями Алгоритм Разбор цепочек символов по ДС с действиями Шаг 1. Объявляем текущим начальное состояние ДС H. Шаг 2. До тех пор, пока не будет достигнуто состояние ER или конечное состояние ДС, считываем очередной символ анализируемой строки и переходим из текущего состояния ДС в другое по дуге, помеченной этим символом, выполняя при этом соответствующие действия. Состояние, в которое попадаем, становится текущим. ЛА строится в два этапа: 1) построить ДС с действиями для распознавания и формирования внутреннего представления лексем; 2) по ДС с действиями написать программу сканирования текста исхо дной программы. Пример Составим ЛА для модельного языка М. Предварительно введем следующие обозначения для переменных, процедур и функций. Переменные: 1) СН – очередной входной символ; 2) S - буфер для накапливания символов лексемы; 3) B – переменная для формирования числового значения константы; 4) CS - текущее состояние буфера накопления лексем с возможными значениями: Н - начало, I - идентификатор, N - число, С - комментарий, DV – двоеточие, О - ограничитель, V - выход, ER –ошибка; 5) t - таблица лексем анализируемой программы с возможными значениями: TW - таблица служебных слов М-языка, TL – таблица ограничителей М-языка, TI таблица идентификаторов программы, TN – чисел, используемых в программе; 6) z - номер лексемы в таблице t (если лексемы в таблице нет, то z=0). Процедуры и функции: 1) gc – процедура считывания очередного символа текста в переменную СН; 2) let – логическая функция, проверяющая, является ли переменная СН буквой; 3) digit - логическая функция, проверяющая, является ли переменная СН цифрой; 4) nill – процедура очистки буфера S; 5) add – процедура добавления очередного символа в конец буфера S; 6) look(t) – процедура поиска лексемы из буфера S в таблице t с возвращением номера лексемы в таблице; 7) put(t) – процедура записи лексемы из буфера S в таблицу t, если там не было этой лексемы, возвращает номер данной лексемы в таблице; 8) out(n, k) – процедура записи пары чисел (n, k) в файл лексем. ‘ ‘ gc H let or digit add, gc let null, add , look(TW) gc + z0 I out(1, z) digit put(TI), out(4, z) B=10*B+’CH’-‘0’, gc digit N put(TN), out(3, z) B=’CH’-‘0’, gc gc ‘{’ ‘}’ C gc ‘.’ gc E R ‘:’ ‘=’ DV gc gc, out(2, 5) out(2, 4) ‘.’ V out(2, 1) + z0 null, add,look(TL) look(TL) gc, out(2, z) - E R Рисунок 4.3 – Диаграмма состояний с действиями для модельного языка М 4.4.3 Функция scanner На основе построенной ДС с действиями для распознавания и формирования внутреннего представления лексем модельного языка М (рисунок 4.5.2) составляем функцию scanner для анализа текста исходной программы: function scanner: boolean; var CS: (H, I, N, C, DV, O, V, ER); begin gc; CS:=H; repeat case CS of H: if CH=’ ‘ then gc else if let then begin nill; add; gc; CS:= I end else if digit then begin B:=ord(CH)-ord(‘0’); gc; CS:= N end else if CH= ‘:’ then begin gc; CS:= DV end else if CH=’.’ then begin out(2,1); CS:=V end else if CH=’{‘ then begin gc; CS:=C end else CS:=O; I: if let or digit then begin add; gc end else begin look(TW); if z<>0 then begin out(1,z); CS:=H end else begin put(TI); out(4,z); CS:=H end end; N: if digit then begin B:=10*B+ord(CH)-ord(‘0’); gc end else begin put(TN); out(3,z); CS:=H end; C: if CH=’}’ then begin gc; CS:=H end else if CH=’.’ then CS:=ER else gc; DV: if CH=’=’ then begin gc; out(2,5); CS:=H end else begin out(2,4); CS:=H end; O: begin null; add; look(TL); if z<>0 then begin gc; out(2,z); CS:=H end else CS:=ER end end {case} until (CS=V) or (CS=ER); scanner:= CS=V end; 4.5 Синтаксический анализатор программы 4.5.1 Задача синтаксического анализатора Задача синтаксического анализатора (СиА) - провести разбор текста программы, сопоставив его с эталоном, данным в описании языка. Для синтаксического разбора используются контекстно-свободные грамматики (КСграмматики). 4.5.2 Нисходящий синтаксический анализ Один из эффективных методов синтаксического анализа – метод рекурсивного спуска. В основе метода рекурсивного спуска лежит левосторонний разбор строки языка. Исходной сентенциальной формой является начальный символ грамматики, а целевой – заданная строка языка. На каждом шаге разбора правило грамматики применяется к самому левому нетерминалу сентенции. Данный процесс соответствует построению дерева разбора цепочки сверху вниз (от корня к листьям). Пример Дана грамматика G({a, b, c, }, {S , A, B}, P, S ) с правилами P : 1) S  AB ; 2) A  a; 3) A  cA; 4) B  bA . Требуется выполнить анализ строки cabca. Левосторонний вывод цепочки имеет вид: S  AB  cAB  caB  cabA  cabcA  cabca  . Нисходящее дерево разбора цепочки представлено на рисунке 2.6. S A c A a B  b A c A a Рисунок 4.4 – Дерево нисходящего разбора цепочки cabca Метод рекурсивного спуска реализует разбор цепочки сверху вниз следующим образом. Для каждого нетерминального символа грамматики создается своя процедура, носящая его имя. Задача этой процедуры – начиная с указанного места исходной цепочки, найти подцепочку, которая выводится из этого нетерминала. Если такую подцепочку считать не удается, то процедура завершает свою работу вызовом процедуры обработки ошибок, которая выдает сообщение о том, что цепочка не принадлежит языку грамматики и останавливает разбор. Если подцепочку удалось найти, то работа процедуры считается нормально завершенной и осуществляется возврат в точку вызова. Тело каждой такой процедуры составляется непосредственно по правилам вывода соответс твующего нетерминала, при этом терминалы распознаются самой процедурой, а нетерминалам соответствуют вызовы процедур, носящих их имена. Пример Построим синтаксический анализатор методом рекурсивного спуска для грамматики G из примера 2.8. Введем следующие обозначения: 4) СH – текущий символ исходной строки; 5) gc – процедура считывания очередного символа исходной строки в переменную СH; 6) Err - процедура обработки ошибок, возвращающая по коду соответствующее сообщение об ошибке. С учетом введенных обозначений, процедуры синтаксического разбора будут иметь вид. procedure S; begin A; B; if CH<> then ERR end; procedure A; begin if CH=a then gc else if CH=c then begin gc; A end else Err end; procedure B; begin if CH= b then begin gc; B end else Err end; Теорема Достаточные условия применимости метода рекурсивного спуска Метод рекурсивного спуска применим к грамматике, если правила вывода грамматики имеют один из следующих видов: 1) A , где  (TN)*, и это единственное правило вывода для этого нетерминала; 2) Aa1 1 | a2 2 |…| an n, где ai T для каждого i=1, 2,…, n; aiaj для ij,  i(TN)*, т.е. если для нетерминала А несколько правил вывода, то они должны начинаться с терминалов, причем эти терминалы должны быть различными. Данные требования являются достаточными, но не являются необходимыми. Можно применить эквивалентные преобразования КС-грамматик, которые способствуют приведению грамматики к требуемому виду, но не гарантируют его достижения (см. лабораторную работу № 4) /11/. При описании синтаксиса языков программирования часто встречаются правила, которые задают последовательность однотипных конструкций, отделенных друг от друга каким-либо разделителем. Общий вид таких правил: La | a,L или в сокращенной форме La{,a}. Формально здесь не выполняются условия метода рекурсивного спуска, т.к. две альтернативы начинаются одинаковыми терминальными символами. Но если принять соглашения, что в подобных ситуациях выбирается самая длинная подцепочка, выводимая из нетерминала L, то разбор становится детерминированным, и метод рекурсивного спуска будет применим к данному правилу грамматики. Соответствующая правилу процедура будет иметь вид: procedure L; begin if CH<>’a’ then Err else gc; while CH=’,’ do begin gc; if CH<>’a’ then Err else gc end end; Пример Построим синтаксический анализатор методом рекурсивного спуска для модельного языка М. Вход – файл лексем в числовом представлении. Выход – заключение о синтаксической правильности программы или сообщение об имеющихся ошибках. Введем обозначения: 1) LEX – переменная, содержащая текущую лексему, считанную из файла лексем; 2) gl – процедура считывания очередной лексемы из файла лексем в переменную LEX; 2) EQ(S) – логическая функция, проверяющая, является ли текущая лексема LEX лексемой для S; 3) ID – логическая функция, проверяющая, является ли LEX идентификатором; 7) NUM - логическая функция, проверяющая, является ли LEX числом. Процедуры, проверяющие выполнение правил, описывающих язык М и составляющие синтаксический анализатор, будут иметь следующий вид: 1) для правила Р program D1 В. procedure Р; begin if EQ(`program`) then gl else ERR; D1; B; if not EQ(‘.’) then ERR end; 2) для правила D1 var D{;D} procedure D1; begin if EQ(‘var’) then gl else ERR; D; while EQ(‘;’) do begin gl; D end end; 3) для правила D I{,I}:(int | bool) procedure D; begin I; while EQ(‘,’) do begin gl; I end; if EQ(‘:’) then gl else ERR; if EQ(‘int’) or EQ(‘bool’) then gl else ERR end; 4) для правила F I|N|L| F|(E) procedure F; begin if ID or NUM or EQ(‘true’) or EQ(‘false’) then gl else if EQ(‘’) then begin gl; F end else if EQ(‘(‘) then begin gl; E; if EQ(‘)’) then gl else ERR end else ERR end; Аналогично составляются оставшиеся процедуры. 4.6 Семантический анализ программы В ходе семантического анализа проверяются отдельные правила записи исходных программ, которые не описываются КС-грамматикой. Эти правила носят контекстно-зависимый характер, их называют семантическими соглашениями или контекстными условиями. Рассмотрим пример построения семантического анализатора (СеА) для программы на модельном языке М. Соблюдение контекстных условий для языка М предполагает три типа проверок: 1) обработка описаний; 2) анализ выражений; 3) проверка правильности операторов. В оптимизированном варианте СиА и СеА совмещены и осуществляются параллельно. Поэтому процедуры СеА будем внедрять в ранее разработанные процедуры СиА. Вход: файл лексем в числовом представлении. Выход: заключение о семантической правильности программы или о типе обнаруженной семантической ошибки. 4.6.1 Обработка описаний Задача обработки описаний - проверить, все ли переменные программы описаны правильно и только один раз. Эта задача решается следующим обр азом. Таблица идентификаторов, введенная на этапе лексического анализа, расширяется, приобретая вид таблицы 4.1. Описание таблицы идентификаторов будет иметь вид: type --tabid = record id :string; descrid :byte; typid :string[4]; addrid :word end; var TI: array[1.. n] of tabid; Таблица 4.1 – Таблица идентификаторов на этапе СеА Номер 1 2 Идентификатор K Sum Описан 1 Тип Int … Адрес … … Поле «описан» таблицы на этапе лексического анализа заполняется нулем, а при правильном описании переменных на этапе семантического анализа заменяется единицей. При выполнении процедуры D вводится стековая переменная-массив, в которую заносится контрольное число 0. По мере успешного выполнения процедуры I в стек заносятся номера считываемых из файла лексем, под которыми они записаны в таблице идентификаторов. Как только при считывании лексем встречается лексема «:», из стека извлекаются записанные номера и по ним в таблице идентификаторов проставляется 1 в поле «описан» (к этому моменту там должен быть 0). Если очередная лексема будет «int» или «bool», то попутно в таблице идентификаторов поле «тип» заполняется соответствующим типом. Пример Пусть фрагмент описания на модельном языке имеет вид: var k, sum: int … Тогда соответствующий фрагмент файла лексем: (1, 2) (4, 1) (2, 3) (4, 2)…Содержимое стека при выполнении процедуры D представлено на рисунке 2.7. 1 2 Рисунок 4.5 – Содержимое стека при выполнении процедуры D Для реализации обработки описаний введем следующие обозначения переменных и процедур: 1) LEX – переменная, хранящая значение очередной лексемы, представляющая собой одномерный массив размером 2, т.е. для лексемы (n, k) LEX[1]=n, LEX[2]=k; 2) gl – процедура считывания очередной лексемы в переменную LEX; 3) inst(l) - процедура записи в стек числа l; 4) outst(l) – процедура вывод из стека числа l; 5) instl – процедура записи в стек номера, под которым лексема хранится в таблице идентификаторов, т.е. inst(LEX[2]); 6) dec(t) - процедура вывода всех чисел из стека и вызова процедуры decid(1, t); 7) decid(l, t) – процедура проверки и заполнения поля «описан» и «тип» таблицы идентификаторов для лексемы с номером l и типа t. Процедуры dec и decid имеют вид: procedure decid (l:..; t:...); begin if TI[l].descrid =1 then ERR else begin TI[l].descrid: = 1; TI[l].typid:= t end end; procedure dec(t: ...); begin outst(l); while l<>0 do begin decid(l, t); outst(l) end end; Правило и процедура D с учетом семантических проверок принимают вид: D  I {, I } : ( int | bool ) procedure D; begin inst(0); I; instl; while EQ(‘,’) do begin gl; I; instl end; if EQ(‘:’) then gl else ERR; if EQ(‘int’) then begin gl; dec(‘int’) end else if EQ(‘bool’) then begin gl; dec(‘bool’) end else ERR end; 4.6.2 Анализ выражений Задача анализа выражений - проверить описаны ли переменные, встречающиеся в выражениях, и соответствуют ли типы операндов друг другу и типу операции. Эти задачи решаются следующим образом. Вводится таблица двуместных операций (таблица 4.2) и стек, в который в соответствии с разбором выражения E заносятся типы операндов и знак операции. После семантической проверки в стеке оставляется только тип результата операции. В результате разбора всего выражения в стеке остается тип этого выражения. Для реализации анализа выражений введем следующие обозначения процедур и функций: 1) checkid - процедура, которая для лексемы LEX, являющейся идентификатором, проверяет по таблице идентификаторов TI, описан ли он, и, если описан, то помещает его тип в стек; 2) checkop – процедура, выводящая из стека типы операндов и знак операции, вызывающая процедуру gettype(op, t1, t2, t), проверяющая соответствие типов и записывающая в стек тип результата операции; 3) gettype(ор, t1, t2, t) – процедура, которая по таблице операций TOP для операции ор выдает тип t результата и типы t1, t2 операндов; 4) checknot – процедура проверки типа для одноместной операции «». Таблица 4.2 – Фрагмент таблицы двуместных операций TOP Операция + > … Тип 1 int int … Тип 2 int int … Тип результата int bool … Перечисленные процедуры имеют следующий вид: procedure checkid; begin k:=LEX[2]; if TI[k].descrid = 0 then ERR; inst(TI[k].typid) end; procedure checkop; begin outst(top2); outst(op); outst(top1); gettype(op, t1, t2, t); if (top1<>t1) or (top2<>t2) then ERR; inst(t) end; procedure checknot; begin outst(t); if t<> bool then ERR; inst(t) end; Правила, описывающие выражения языка М, расширенные процедурами семантического анализа, принимают вид. Е  Е1 {( > | < | = ) E1 } E1 Т {(+ | - | ) T } T F {( * | / | ) F} F I | N | L | F |(E) Пример Дано выражение a+5*b. Дерево разбора выражения и динамика содержимого стека представлены на рисунке 4.6. E E1 T + T F F * F I N I C R C a 5 b 1) int + int 2) int + int 3) * int int Рисунок 4.6 – Анализ выражения a+5*b 4.6.3 Проверка правильности операторов Задачи проверки правильности операторов: 1) выяснить, все ли переменные, встречающиеся в операторах, описаны; 2) установить соответствие типов в операторе присваивания слева и спр ава от символа «:=»; 3) определить, является ли выражение Е в операторах условия и цикла булевым. Данные задачи решаются путем включения в правило S ранее рассмотренной процедуры checkid, а также новых процедур eqtype и eqbool, имеющих следующий вид: procedure eqtype; begin outst(t2); outst(t1); if t1<>t2 then ERR end; procedure eqbool; begin outst(t); if t<>bool then ERR end; Правило S с учетом процедур СеА примет вид: S I := E | if E then S else S while E do S | write (E) | read (I ) 4.7 Генерация кода Результатом СиА должно быть некоторое внутреннее представление исходной цепочки лексем, которое отражает ее синтаксическую структуру. Программа в таком виде может либо транслироваться в объектный код, либо интерпретироваться. Генерация объектного кода - это перевод компилятором внутреннего представления программы в цепочку символов выходного языка. Генерация объектного кода порождает результирующую объектную программу на языке ассемблера или непосредственно на машинном языке (в машинных кодах). Внутреннее представление программы может иметь любую структуру в зависимости от реализации компилятора, в то время как результирующая программа всегда представляет собой линейную последовательность команд. Поэтому генерация объектного кода (объектной программы) в любом случае должна выполнять действия, связанные с преобразование сложных синтаксических структур в линейные цепочки. 4.7.1 Формы внутреннего представления программы Возможны различные формы внутреннего представления синтаксических конструкций исходной программы в компиляторе. Но формы представления, используемые на этапах синтаксического анализа, оказываются неудобными при генерации и оптимизации объектного кода. Поэтому перед оптимизацией и непосредственно перед генерацией объектного кода внутреннее представление программы может преобразовываться в одну из соответствующих форм записи. Выделяют следующие общепринятые способы внутреннего представления программы: 1) многоадресный код с явно именуемым результатом (тетрады); 2) многоадресный код с неявно именуемым результатом (триады); 3) синтаксические деревья; 4) постфиксная запись; 5) машинные команды или ассемблерный код. 4.7.1.1 Тетрады Тетрады представляют собой запись операций в форме из четырех составляющих: операция, два операнда и результат операции. Например, тетрады могут выглядеть так: <операция>(<операнд1>,<олеранд2>.<результат>). Тетрады представляют собой линейную последовательность команд. При вычислении выражения, записанного в форме тетрад, они вычисляются одна за другой последовательно. Каждая тетрада в последовательности вычисляется так: операция, заданная тетрадой, выполняется над операндами и результат ее выполнения помещается в переменную, заданную результатом тетрады. Если какой-то из операндов (или оба операнда) в тетраде отсутствует (например, если тетрада представляет собой унарную операцию), то он может быть опущен или заменен пустым операндом (в зависимости от принятой формы записи и ее реализации). Результат вычисления тетрады никогда опущен быть не может, иначе тетрада полностью теряет смысл. Порядок вычисления тетрад может быть изменен, ни только если допустить наличие тетрад, целенаправленно изменяющих этот порядок (например, тетрады, вызывающие переход па несколько шагов вперед или назад при каком-то условии). Тетрады представляют собой линейную последовательность, а потому для них несложно написать тривиальный алгоритм, который будет преобразовывать последовательность тетрад в последовательность команд результирующей программы (либо последовательность команд ассемблера). В этом их преимущество перед синтаксическими деревьями. А в отличие от команд ассемблера тетрады не зависят от архитектуры вычислительной системы, на которую ориентирована результирующая программа. Поэтому они представляют собой машинно-независимую форму внутреннего представления программы. Тетрады требуют больше памяти для своего представления, чем триады, они также не отражают явно взаимосвязь операций между собой. Кроме того, есть сложности с преобразованием тетрад в машинный код, так как они плохо отображаются в команды ассемблера и машинные коды, поскольку в наборах команд большинства современных компьютеров редко встречаются операции с тремя операндами. Например, выражение A:=B*C+D-B*10, записанное в виде тетрад, будет иметь вид: * ( B, C, T1 ) + ( T1, D, T2 ) * ( В, 10, ТЗ ) - ( Т2, ТЗ, Т4) := ( Т4, 0, А ) Здесь все операции обозначены соответствующими знаками (при этом присвоение также является операцией). Идентификаторы Т1,…,Т4 обозначают временные переменные, используемые для хранения результатов вычисления тетрад. Следует обратить внимание, что в последней тетраде (присвоение), которая требует только одного операнда, в качестве второго операнда выступает незначащий операнд «0». 4.7.1.2 Триады Триады представляют собой запись операций в форме из трех составляющих: операция и два операнда. Например, триады могут иметь вид: <операция>(<операнд1>, <операнд2>). Особенностью триад является то, что один или оба операнда могут быть ссылками на другую триаду в том случае, если в качестве операнда данной триады выступает результат выполнения другой триады. Поэтому триады при записи последовательно нумеруют для удобства указания ссылок одних триад на другие (в реализации компилятора в качестве ссылок можно использовать не номера триад, а непосредственно ссылки в виде указателей — тогда при изменении нумерации и порядка следования триад менять ссылки не требуется). Триады представляют собой линейную последовательность команд. При вычислении выражения, записанного в форме триад, они вычисляются одна за другой последовательно. Каждая триада в последовательности вычисляется так: операция, заданная триадой, выполняется над операндами, а если в качестве одного из операндов (или обоих операндов) выступает ссылка на другую триаду, то берется результат вычисления той триады. Результат вычисления триады нужно сохранять во временной памяти, так как он может быть затребован последующими триадами. Если какой-то из операндов в триаде отсутствует (например, если триада представляет собой унарную операцию), то он может быть опущен или заменен пустым операндом (в зависимости от принятой формы записи и ее реализации). Порядок вычисления триад, как и для тетрад, может быть изменен, но только если допустить наличие триад, целенаправленно изменяющих этот порядок (например, триады, вызывающие переход на несколько шагов вперед или назад при каком-то условии). Триады представляют собой линейную последовательность, а потому для них несложно написать тривиальный алгоритм, который будет преобразовывать по следовательность триад в последовательность команд результирующей программы (либо последовательность команд ассемблера). В этом их преимущество перед синтаксическими деревьями. Однако здесь требуется также и алгоритм, отвечающий за распределение памяти, необходимой для хранения промежуточных результатов вычисления, так как временные переменные для этой цели не используются. В этом отличие триад от тетрад. Так же как и тетрады, триады не зависят от архитектуры вычислительной системы, на которую ориентирована результирующая программа. Поэтому они представляют собой машинно-независимую форму внутреннего представления программы. Триады требуют меньше памяти для своего представления, чем тетрады, они также явно отражают взаимосвязь операций между собой, что делает их применение удобным. Необходимость иметь алгоритм, отвечающий за распределение памяти для хранения промежуточных результатов, не является недостатком, так как удобно распределять результаты не только по доступным ячейкам временной памяти, но и по имеющимся регистрам процессора. Это дает определенные преимущества. Триады ближе к двухадресным машинным командам, чем тетрады, а именно эти команды более всего распространены в наборах команд большинства современных компьютеров. Например, выражение A:=B*C+D-B*10. записанное в виде триад, будет иметь вид: 1) * (B, C) 2) + (^1, D) 3) * (B, 10) 4) – (^2, ^3) 5) := (A, ^4) Здесь операции обозначены соответствующим знаком (при этом присвоение также является операцией), а знак ^ означает ссылку операнда одной триады на результат другой. 4.7.1.3 Синтаксические деревья Результатом синтаксического разбора является дерево вывода. Оно содержит массу избыточной информации, которая для дальнейшей работы компилятора не требуется. Эта информация включает в себя все нетерминальные символы, содержащиеся в узлах дерева, — после того как дерево построено, они не несут никакой смысловой нагрузки и не представляют для дальнейшей работы интереса. В синтаксическом дереве внутренние узлы (вершины) соответствуют операциям, а листья представляют собой операнды. Как правило, листья синтаксического дерева связаны с записями в таблице идентификаторов. Структура синтаксического дерева отражает синтаксис языка программирования, на котором написана исходная программа. Синтаксические деревья могут быть построены компилятором для любой части входной программы. Не всегда синтаксическому дереву должен соответствовать фрагмент кода результирующей программы — например, возможно построение синтаксических деревьев для декларативной части языка. В этом случае операции, имеющиеся в дереве, не требуют порождения объектного кода, но несут информацию о действиях, которые должен выполнить сам компилятор над со ответствующими элементами. В том случае, когда синтаксическому дереву соот- ветствует некоторая последовательность операций, влекущая порождение фрагмента объектного кода, говорят о дереве операций. Дерево операций можно непосредственно построить из дерева вывода, порожденного синтаксическим анализатором. Для этого достаточно исключить из дерева вывода цепочки нетерминальных символов, а также узлы, не несущие семантической (смысловой) нагрузки при генерации кода. Примером таких узлов могут служить различные скобки, которые меняют порядок выполнения операций и операторов, но после построения дерева никакой смысловой нагрузки не несут, так как им не соответствует никакой объектный код. Алгоритм преобразования дерева семантического разбора в дерево операций можно представить следующим образом. Шаг 1 Если в дереве больше не содержится узлов, помеченных нетерминальными символами, то выполнение алгоритма завершено; иначе — перейти к шагу 2. Шаг 2 Выбрать крайний левый узел дерева, помеченный нетерминальным символом грамматики и сделать его текущим. Перейти к шагу 3. Шаг 3 Если текущий узел имеет только один нижележащий узел, то текущий узел необходимо удалить из дерева, а связанный с ним узел присоединить к узлу вышележащего уровня (исключить из дерева цепочку) и вернуться к шагу 1; иначе — перейти к шагу 4. Шаг 4 Если текущий узел имеет нижележащий узел (лист дерева), помеченный терминальным символом который не несет семантической нагрузки, тогда этот лист нужно удалить из дерева и вернуться к шагу 3; иначе - перейти к шагу 5. Шаг 5 Если текущий узел имеет один нижележащий узел (лист дерева), помеченный терминальным символом, обозначающим знак операции, а остальные узлы помечены как операнды, то лист, помеченный знаком операции, надо удалить из дерева, текущий узел пометить этим знаком операции и перейти к шагу 1; иначе — перейти к шагу 6. Шаг 6 Если среди нижележащих узлов для текущего узла есть узлы, помеченные нетерминальными символами грамматики, то необходимо выбрать крайний левый среди этих узлов, сделать его текущим узлом и перейти к шагу 3; иначе — выполнение алгоритма завершено. Пусть в результате синтаксического разбора получено дерево разбора для цепочки (a+a)*b, имеющее следующий вид: S T E ( S S ) * E b T E R + T Рисунок 4.7 Дерево разбора В результате применения алгоритма преобразования деревьев синтаксического разбора в дерево операций к дереву, представленному на рис. 4.7, получим дерево операций, представленное на рис. 4.8. * + a b a Рисунок 4.8 – Дерево операций 4.7.1.4 Польская инверсная запись Польская инверсная запись — это постфиксная запись операций. Она была предложена польским математиком Я. Лукашевичем, откуда и происходит ее название. В этой записи знаки операций записываются непосредственно за операндами. По сравнению с обычной (инфиксной) записью операций в польской записи операнды следуют в том же порядке, а знаки операций — строго в порядке их выполнения. Тот факт, что в этой форме записи все операции выполняются в том порядке, в которой они записаны, делает ее чрезвычайно удобной для вычисления выражений на компьютере. Польская запись не требует учитывать приоритет операций, в ней не употребляются скобки, и в этом ее основное преимущество. Она чрезвычайно эффективна в тех случаях, когда для вычислений используется стек. Ниже будет рассмотрен алгоритм вычисления выражений в форме обратной польской записи с использованием стека. Главный недостаток обратной польской записи также проистекает из метода вычисления выражений в ней: поскольку используется стек, то для работы с ним всегда доступна только верхушка стека, а это делает крайне затруднительной оптимизацию выражений в форме обратной польской записи. Практически выражения в форме обратной польской записи почти не поддаются оптимизации. Но там, где оптимизация вычисления выражений не требуется или не имеет большого значения, обратная польская запись оказывается очень удобным методом внутреннего представления программы. Перевод в ПОЛИЗ выражений. Пример Для выражения в обычной (инфиксной записи) a*(b+c)-(d-e)/f ПОЛИЗ будет иметь вид: abc+*de-f/-. Справедливы следующие формальные определения. Определение Если Е является единственным операндом, то ПОЛИЗ выражения Е – это этот операнд. Определение ПОЛИЗ выражения Е1  Е2, где  - знак бинарной операции, Е1 и Е – операнды для , является запись E  E  , где E  , E  - ПОЛИЗ выражений Е 1 2 2 1 2 1 и Е2 соответственно. Определение ПОЛИЗ выражения Е, где  - знак унарной операции, а Е – операнд , есть запись E  , где E  - ПОЛИЗ выражения Е. 1 Определение ПОЛИЗ выражения (Е) есть ПОЛИЗ выражения Е. Перевод в ПОЛИЗ операторов. Каждый оператор языка программирования может быть представлен как nместная операция с семантикой, соответствующей семантике оператора. Оператор присваивания I:=E в ПОЛИЗе записывается: IE:=, где «:=» - двуместная операция, I, E – операнды операции присваивания; I – означает, что операндом операции «:=» является адрес переменной I, а не ее значение. Пример Оператор x:=x+9 в ПОЛИЗе имеет вид: x x 9 + :=. Оператор перехода в терминах ПОЛИЗа означает, что процесс интерпретации необходимо продолжить с того элемента ПОЛИЗа, который указан как операнд операции перехода. Чтобы можно было ссылаться на элементы ПОЛИЗа, будем считать, что все они пронумерованы, начиная с единицы (например, последовательные элементы одномерного массива). Пусть ПОЛИЗ оператора, помеченного меткой L, начинается с номера p, тогда оператору безусловного перехода goto L в ПОЛИЗе будет соответствовать: p!, где ! – операция выбора элемента ПОЛИЗа, номер которого равен p. Условный оператор. Введем вспомогательную операцию – условный переход «по лжи» с семантикой if (not B) then goto L. Это двуместная операция с операндами B и L. Обозначим ее !F, тогда в ПОЛИЗе она будет записываться: B p !F, где p – номер элемента, с которого начинается ПОЛИЗ оператора, помеченного меткой L. С использованием введенной операции условный оператор then S1 else S2 в ПОЛИЗе будет записываться: if B B p1 !F S1 p2 ! S2, где p1 – номер элемента, с которого начинается ПОЛИЗ оператора S2, а p1 – оператора, следующего за условным оператором. Пример ПОЛИЗ оператора if x>0 then x:=x+8 else x:=x-3 представлен в таблице 4.3 Таблица 4.3 – ПОЛИЗ оператора if лексема x номер 1 2 > 3 13 !F x 4 5 6 x 7 8 8 + 9 := 18 ! x x 3 - := … 10 11 12 13 14 15 16 17 18 Оператор цикла. С учетом введенных операций оператор цикла do S в ПОЛИЗе будет записываться: while B B p1 !F S po !, где po – номер элемента, с которого начинается ПОЛИЗ выражения B, а p1 – оператора, следующего за данным оператором цикла. Операторы ввода и вывода языка М одноместные. Пусть R – обозначение операции ввода, а W – обозначение операции вывода, тогда оператор read(I) в ПОЛИЗе запишется как I R, а оператор write(E) – E W. Составной оператор begin S1; S2;...; Sn end в ПОЛИЗе записывается как S1 S2... Sn. Пример ПОЛИЗ оператора while n>3 do begin write(n*n-1); n:=n-1 end представлен в таблице 4.4 Таблица 4.4 – ПОЛИЗ оператора while лексема n 3 > 19 !F n n * 1 W n n 1 := 1 ! … номер 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 4.7.1.5 Ассемблерный код и машинные команды Машинные команды удобны тем, что при их использовании внутреннее представление программы полностью соответствует объектному коду и сложные преобразования не требуются. Команды ассемблера представляют собой лишь форму записи машинных команд, а потому в качестве формы внутреннего представления программы практически ничем не отличаются от них. Однако использование команд ассемблера или машинных команд для внутреннего представления программы требует дополнительных структур для отображения взаимосвязи операций. Очевидно, что в этом случае внутреннее представление программы получается зависимым от архитектуры вычислительной системы, на которую ориентирован результирующий код. Значит, при ориентации компилятора на другой результирующий код потребуется перестраивать как само внутреннее представление программы, так и методы его обработки (при использовании триад или тетрад этого не требуется). Тем не менее, машинные команды — это язык, на котором должна быть записана результирующая программа. Поэтому компилятор, так или иначе, должен работать с ними. Кроме того, только обрабатывая машинные команды (или их представление в форме команд ассемблера), можно добиться наиболее эффективной результирующей программы. Отсюда следует, что любой компилятор работает с представлением результирующей программы в форме машинных команд, однако их обработка происходит, как правило, на завершающих этапах фазы генерации кода. 4.7.2 Преобразование дерева операций в код на языке ассемблера В качестве языка ассемблера возьмем язык ассемблера процессоров типа Intel 80x86. При этом будем считать, что операнды могут быть помещены в 16-разрядные регистры процессора и в коде результирующей объектной программы могут использоваться регистры АХ (аккумулятор) и DX (регистр данных), а также стек для хранения промежуточных результатов. Функцию, реализующую перевод узла дерева в последовательность команд ассемблера, назовем Code. Входными данными функции должна быть информация об узле дерева операций. В ее реализации на каком-либо языке программирования эти данные можно представить в виде указателя на соответствующий узел дерева операций. Выходными данными является последовательность команд языка ассемблера. Будем считать, что она передается в виде строки, возвращаемой в качестве результата функции. Тогда четырём формам текущего узла дерева для каждой арифметической операции будут соответствовать фрагменты кода на языке ассемблера, приведенные в табл. 4.7.3. Каждой допустимой арифметической операции будет соответствовать своя команда на языке ассемблера. Если взять в качестве примера операции сложения (+), вычитания (-), умножения (*) и деления (/), то им будут соответствовать команды add, sub, mul и div. Причем в ассемблере Intel 80x86 от типа операции зависит не только тип, но и синтаксис команды (операции mul и div в качестве первого операнда всегда предполагают регистр процессора АХ, который не нужно указывать в команде). Соответствующая команда должна записываться вместо act при порождении кода в зависимости от типа узла дерева. Таблица 4.5 - Преобразование узлов дерева вывода в код на языке ассемблера для арифметических операций Вид узла дерева Результирующий код Примечание mov ax, operl act act ax, oper2 act — команда соответствующей операции operl, oper2 — операнды (листья дерева) oper 1 oper 2 Code (Узел 2) act mov dx, ax mov ax, operl Узел 2 oper 1 act Узел 1 Code (Узел 2) -код, порождаемый процедурой для нижележащего узла Code (Узел 2) act ax, орег2 Code (Узел 2) — код, порождаемый процедурой для нижележащего узла Code (Узел 2) push ax Code (УзелЗ) mov dx, ax pop ax act ax, dx Code (Узел 2) — код, порождаемый процедурой для нижележащего узла Code (Узел 3) -- код, порождаемый процедурой для нижележащего узла push и pop — команду сохранения результатов в стеке и извлечения результатов из стека oper 2 act Узел 1 act ax, dx Узел 2 -нижележащий узел (не лист!) дерева Узел 2 Код, порождаемый для операции присвоения результата, будет отличаться от кода, порождаемого для арифметических операций. Кроме того, семантика языка требует, чтобы в левой части операции присвоения всегда был операнд, поэтому для нее возможны только два типа узлов дерева, влекущие порождение кода(два других типа узлов должны приводить к сообщению об ошибке, которая в компиляторе обнаруживается синтаксическим анализатором). Фрагменты кода для этой операции приведены ниже в таблице 4.6. Таблица 4.6 - Преобразование узлов дерева вывода в код на языке ассемблера для операции присвоения Вид узла дерева := oper 1 Результирующий код mov ax, орег2 mov operl, ax Примечание Code (Узел 2) mov operl, ax Узел 2 — нижележащий узел (не лист!) дерева Code (Узел 2)-код, порождаемый процедурой для нижележащего узла operl, oper2 — операнды (листья дерева) oper 2 := oper 1 oper 2 Теперь последовательность порождаемого кода определена для всех возможных типов узлов дерева» Рассмотрим в качестве примера выражение A:-B*C+D-B*10. Соответствующее ему дерево вывода приведено на рис. 4.7. Рисунок 4.7 Дерево операций для арифметического выражения «A:=B*C+D-B*10» Построим последовательность команд языка ассемблера, соответствующую дереву операций на рис. 4.7. Согласно принципу СУ-перевода, построение начинается от корня дерева. Для удобства иллюстрации рекурсивного построения последовательности команд все узлы дерева помечены от U1 до U5. Рассмотрим последовательность построения цепочки команд языка ассемблера по шагам рекурсии. Эта последовательность приведена ниже. Шаг 1. Code(U2) mov A, ax Шаг 2. Code(U3) push ax Code(U5) mov dx, ax pop ax sub ax, dx mov A, ax Шаг 3. Code(U4) add ax, D push ax Code(U5) mov dx, ax pop ax sub ax, dx mov A, ax Шаг 4. mov ax, В mul С add ax, D push ax Code(U5) mov dx, ax pop ax sub ax, dx mov A, ax Шаг 5. mov ax, В mul С add ax, D push ax mov ax, В mul 10 mov dx, ax pop ax sub ax, dx mov A, ax 4.8 Оптимизация кода 4.8.1 Сущность оптимизации кода Полученный в результате генерации объектный код может содержать лишние команды и данные. Это снижает эффективность выполнения результирующей программы. В принципе компилятор может завершить на этом генерацию кодарацию кода, поскольку результирующая программа построена и она является эквивалентной по смыслу (семантике) программе на входном языке. Однако эффективность результирующей программы важна для ее разработчика, поэтому большинство современных компиляторов выполняют еще один этап компиляции оптимизацию результирующей программы (или просто «оптимизацию»), чтобы повысить ее эффективность насколько это возможно. Важно отметить два момента: во-первых, выделение оптимизации в отдельный этап генерации кода — это вынужденный шаг. Компилятор вынужден производить оптимизацию построенного кода, поскольку он не может выполнить семантический анализ всей входной программы в целом, оценить ее смысл и,: исходя из него, построить результирующую программу. Оптимизация нужна, поскольку результирующая программа строится не вся сразу, а поэтапно. Во вторых, оптимизация - это необязательный этап компиляции. Компилятор может вообще не выполнять оптимизацию, и при этом результирующая программа будет правильной, а сам компилятор будет полностью выполнять свои функции. Однако, практически все компиляторы так или иначе выполняют оптимизацию, поскольку их разработчики стремятся завоевать хорошие позиции на рынке средств разработки программного обеспечения. Оптимизация, которая существенно влияет на эффективность результирующей программы, является здесь немаловажным фактором. Оптимизация программы — это обработка, связанная с переупорядочиванием и изменением операций в компилируемой программе с целью получения более эффективной результирующей объектной программы. Оптимизация выполняется на этапах подготовки к генерации и непосредственно при генерации объектного кода. 4.8.2 Критерии эффективности результирующей программы В качестве показателей эффективности результирующей программы можно использовать два критерия: объем памяти, необходимый для выполнения результирующей программы (для хранения всех ее данных и кода), и скорость выполнения (быстродействие) программы. Далеко не всегда удается выполнить оптимизацию так, чтобы удовлетворить обоим этим критериям. Зачастую сокращение необхо димого программе объема данных ведет к уменьшению ее быстродействия, и наоборот. Поэтому для оптимизации обычно выбирается либо один из упомянутых критериев, либо некий комплексный критерий, основанный на них. Выбор критерия оптимизации обычно выполняет непосредственно пользователь в настройках компилятора. Но, даже выбрав критерий оптимизации, в общем случае практически невозможно построить код результирующей программы, который бы являлся самым коротким или самым быстрым кодом, соответствующим входной программе. Дело в том, что нет алгоритмического способа нахождения самой короткой или самой быстрой результирующей программы, эквивалентной заданной исходной программе. Эта задача в принципе неразрешима. Существуют алгоритмы, которые можно ускорять сколь угодно много раз для большого числа возможных входных данных, и при этом для других, наборов входных данных они окажутся неоптимальными. К тому же компилятор обладает весьма ограниченными средствами анализа семантики всей входной программы в целом. Все, что можно сделать на этапе оптимизации, — это выполнить над заданной программой последовательность преобразований в надежде сделать ее более эффективной. Чтобы оценить эффективность результирующей программы, полученной с помощью того или иного компилятора, часто прибегают к сравнению ее с эквивалентной программой (программой, реализующей тот же алгоритм), полученной из исходной программы, написанной на языке ассемблера. Лучшие оптимизирующие компиляторы могут получать результирующие объектные программы из сложных исходных программ, написанных на языках высокого уровня, почти не уступающие по качеству программам на языке ассемблера. Обычно соотношение эффективности программ, построенных с помощью компиляторов с языков высокого уровня, к эффективности программ, построенных с помощью ассемблера, составляет 1,1-1,3. То есть объектная программа, построенная с помощью компилятора с языка высокого уровня, обычно содержит на 10-30 % больше команд, чем эквивалентная ей объектная программа, построенная с помощью ассемблера, а также выполняется на 10-30 % медленнее. Это очень неплохие результаты, достигнутые компиляторами с языков высокого уровня, если сравнить трудозатраты на разработку программ на языке ассемблера и языке высокого уровня. Далеко не каждую программу можно реализовать на языке ассемблера в приемлемые сроки (а значит, и выполнить напрямую приведенное выше сравнение можно только для узкого круга программ). 4.8.3 Методы оптимизации кода Оптимизацию можно выполнять на любой стадии генерации кода, начиная от завершения синтаксического разбора и вплоть до последнего этапа, когда порождается код результирующей программы. Если компилятор использует несколько различных форм внутреннего представления программы, то каждая из них может быть подвергнута оптимизации, причем различные формы внутреннего представления ориентированы на различные методы оптимизации. Таким образом, оптимизация в компиляторе может выполняться несколько раз на этапе генерации кода. Принципиально различаются два основных вида оптимизирующих преобразований: - преобразования исходной программы (в форме ее внутреннего представления в компиляторе), не зависящие от результирующего объектного языка; - преобразования результирующей объектной программы. Первый вид преобразований не зависит от архитектуры целевой вычислительной системы, на которой будет выполняться результирующая программа. Обычно он основан на выполнении хорошо известных и обоснованных математических и логических преобразований, производимых над внутренним представлением программы. Второй вид преобразований может зависеть не только от свойств объектного языка, но и от архитектуры вычислительной системы, на которой будет выполняться результирующая программа. Так, например, при оптимизации может учитываться объем кэш-памяти и методы организации конвейерных операций центрального процессора. В большинстве случаев эти преобразования сильно зависят от реализации компилятора и являются «ноу-хау» производителей компилятора. Именно этот тип оптимизирующих преобразований позволяет существенно повысить эффективность результирующего кода. У современных компиляторов существуют возможности выбора не только общего критерия оптимизации, но и отдельных методов, которые будут использоваться при выполнении оптимизации. Методы преобразования программы зависят от типов синтаксических конструкций исходного языка. Теоретически разработаны методы оптимизации для мно гих типовых конструкций языков программирования. Оптимизация может выполняться для следующих типовых синтаксических конструкций: - линейных участков программы; - логических выражений; - вызовов процедур и функций; - других конструкций входного языка. Во всех случаях могут использоваться как машинно-зависимые, так и машиннонезависимые методы оптимизации. 4.8.4 Оптимизация линейных участков программ Линейный участок программы — это выполняемая по порядку последовательность операций, имеющая один вход и один выход. Чаще всего линейный участок содержит последовательность вычислений, состоящих из арифметических операций и операторов присвоения значений переменным. Для операций, составляющих линейный участок программы, могут применяться следующие виды оптимизирующих преобразований: - удаление бесполезных присваиваний; - исключение избыточных вычислений (лишних операций); - свертка операций объектного кода; - перестановка операций; - арифметические преобразования. Удаление бесполезных присваиваний заключается в том, что если в составе линейного участка программы имеется операция присвоения значения некоторой произвольной переменной А с номером i, а также операция присвоения значения той же переменной А с номером j, i,<константа>) для всех переменных, значения которых уже известны. Рассмотрим выполнение алгоритма свертки объектного кода для триад. Для пометки операций, не требующих порождения объектного кода, будем использо вать триады специального вида С (k, 0). Алгоритм свертки триад последовательно просматривает триады линейного участка и для каждой триады делает следующее: 1 Если операнд есть переменная, которая содержится в таблице Т, то операнд заменяется на соответствующее значение константы. 2 Если операнд есть ссылка на особую триаду типа С(k, 0), то операнд заменяется на значение константы k. 3 Если все операнды триады являются константами, то триада может быть свернута. Тогда данная триада выполняется и вместо нее помещается особая триада вида С(k,0), где k — константа, являющаяся результатом выполнения свернутой триады. (При генерации кода для особой триады объектный код не порождается, а потому она в дальнейшем может быть просто исключена.) Если триада является присваиванием типа А:=В, тогда: - если В — константа, то А со значением константы заносится в таблицу Т (если там уже было старое значение для А, то это старое значение исключается); - если В — не константа, то А вообще исключается из таблицы Т, если оно там есть. Рассмотрим пример выполнения алгоритма. Пусть фрагмент исходной программы (записанной на языке типа Pascal) имеет вид: I:=1+1; I:=3; J:=6*I+I Ее внутреннее представление в форме триад будет иметь вид: 1 +(1,1); 2 :=(I,^1); 3 := (I,3); 4 *(6,I); 5 +(^4, I); 6 :=(J,^5). Процесс выполнения алгоритма свертки показан в табл. 4.7. Таблица 4.7 Пример работы алгоритма свертки Триада Шаг 1 Шаг 2 ШагЗ Шаг 4 Шаг 5 Шаг 6 1 2 С (2, 0) := (I, ^1) С (2, 0) :=(I,2) С (2, 0) :=(I,2) С (2, 0) :=(I,2) С (2, 0) :=(I,2) С (2, 0) :=(I,2) 3 :=(I,3) :=(I,3) :=(I,3) :=(I,3) :=(I,3) :=(I,3) 4 5 *(6,I) + (^4, I) * (6,I) + (^4, I) *(6,I) + (^4, I) С (18, 0) + (^4, I) С (18, 0) С (21,0) С (18, 0) С (21, 0) 6 Т :=(J,^5) (,) :=(J,^5) (I, 2) :=(J,^5) (I,3) :=(J,^5) (I, 3) :=(J,^5) (I, 3) :=(J,21) (I, 3) (J,21) Если исключить особые триады типа С(k,0) (которые не порождают объектного кода), то в результате выполнения свертки получим следующую последовательность триад: 1 := (I, 2) 2 := (I, 3) 3 := (J, 21) 4.8.4.2 Исключение лишних операций Алгоритм исключения лишних операций просматривает операции в порядке их следования. Так же как и алгоритму свертки, алгоритму исключения лишних операций проще всего работать с триадами, потому что они полностью отражают взаимосвязь операций. Рассмотрим алгоритм исключения лишних операций для триад. Чтобы следить за внутренней зависимостью переменных и триад, алгоритм присваивает им некоторые значения, называемые числами зависимости, по следующим правилам: 1) изначально для каждой переменной ее число зависимости равно 0, так как в на чале работы программы значение переменной не зависит ни от какой триады; 2) после обработки i-й триады, в которой переменной А присваивается некоторое значение, число зависимости A (dep(A)) получает значение i, так как зна чение А теперь зависит от данной i-й триады; 3) при обработке 1-й триады ее число зависимости (depd)) принимается равным значению 1+(максимальное из чисел зависимости операндов). Таким образом, при использовании чисел зависимости триад и переменных можно утверждать, что если i-я триада идентична j-й триаде (j  ,  , где   V*,   (VN   )*; S — аксиома (начальный символ) схемы. Определение. СУ-схема называется простой, если в каждом правиле А->  ,  одноименные нетерминалы встречаются в  и  в одном и том же порядке. СУсхема называется постфиксной, если   VN *  * в каждом правиле {А->  ,  )  R. Определение. СУ-переводом  , определяемым (генерируемым) СУ-схемой T={VT, VN,  ,R,S), называется множество пар  (T )  {(w, y) | (S , S )  *(w, y), w VT* , y  *} Грамматика GBX = {VT, VN, P,S), где Р = {А ->  | (А ->  ,  )  R}, называется входной грамматикой СУ-схемы. Грамматика GВЫХ ={  ,VN, P’,S), где P’ = {А ->  | (А ->  ,  )  R}, называется выходной грамматикой СУ-схемы. Пример Рассмотрим СУ-схему Т1 перевода арифметических выражений в обратную польскую запись. В основе этой схемы лежит соответствие правил записи арифметических выражений в обычной (инфиксной) форме и в ПОЛИЗ. Для упрощенных выражений такое соответствие приводится ниже. Правила инфиксной формы Правила ПОЛИЗ S->E S->E E->E+T E->ET+ E->T E->T T->T*F T->TF* T->F T->F F->(E) F->E F-> имя F->имя СУ-схема Т1 представляется пятеркой Т1 = {VT, VN,  ,R,S), где S — аксиома, VT= {+, *, имя, (,)};  = {+, *, имя}; VN= {S, Е,T, 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 является GВХ = (VT, VN, Р, S), где множество правил Р представлено правилами инфиксной формы. GВЫХ= (  , VN, P’ , S) — выходная грамматика СУ-схемы T1, а ее правила Р’ — это правила ОПЗ. Как показывает анализ правил СУ-схемы, Т1 — простая постфиксная СУ-схема. Нетрудно убедиться также, что в ней существует, например, вывод (S, S) =>* (a+b*c, abc*+), порождающий элемент перевода (а+b*с, abc*+)   (T1). 5.1.3 МП-преобразователи МП - преобразователи позволяют формально описать соответствующие действия, связанные не только с распознаванием синтаксических конструкций, но и с построением дерева разбора (вывода) и его преобразованием, а также действия, которые имеют как синтаксический, так и семантический характер. Определение. МП - преобразователем называют восьмерку вида P  (Q,  , Ã , ,  , q0 , Z 0 , F ) Q - конечное множество состояний преобразователя;  - конечный входной алфавит; Г - конечный магазинный алфавит;  - конечный выходной алфавит;  - отображение множества (Q * (   { } * Г) в множество всех подмножеств множества (Q * Г**  *), т.е.  : (Q * (  { } * Ã )  P(Q * Ã * *) qо - начальное состояние преобразователя, q0  Q; Zo - начальное содержимое магазина, Zo  Г; F - множество заключительных состояний преобразователя, F  Q. Определение. Конфигурация МП - преобразователя — это четверка (q,w,  , у)  (Q х  * х Г* х  *). Начальная конфигурация — (q 0 ,w, Zo,  ), заключительная конфигурация — (q,  ,  , у), где q  F. Если одним из значений функции  (q, a, Z) является (q’,  , r), то шаг работы преобразователя можно представить в виде отношения на конфигурациях (q, aw, Za, у) |- (q’,wо,  а, уr) для любых w   *,   Г*, у   *. Строка у будет выходом МП - преобразователя для строки w, если существует путь от начальной до заключительной конфигурации (qо, w, Zo,  ) |-* (q,  ,  , у) для некоторых q  F и   Г*. Определение. Переводом (преобразованием)  , определяемым МП преобразователем Р, называется множество  (Р) = {(w,у) | (q 0,w, Zo,  )|-* (q,  ,  ,у) для q  F,   Г*. Определение. МП - преобразователь будет детерминированным, если, как и МП - автомат, он имеет не более одной возможной очередной конфигурации. Расширенный МП - преобразователь отличается от рассмотренного только магазинной функцией  : (Q х (   { } ) х Г*) -> P(Q х Г* х  *). Теперь обратимся к двум результатам теоретических исследований, имеющим чрезвычайно важное практическое значение. Они состоят в следующем. 1. Если T={VT, VN,  ,R,S) - простая СУ-схема с входной грамматикой LL(k), то СУ-перевод  (Т) можно осуществить детерминированным МП преобразователем. 2. Если T={VT, VN,  ,R,S) - простая постфиксная СУ-схема с входной грамматикой LR(k), то перевод  (T) можно выполнить детерминированным МП - преобразователем. Существуют алгоритмы, позволяющие построить детерминированный МП - преобразователь по заданной СУ-схеме перевода. В их основе лежат алгоритмы построения таблиц разбора. Простые СУ-переводы образуют важный класс переводов, поскольку для каждого из них можно построить детерминированный МП - преобразователь, отображающий входную строку (цепочку) в выходную строку (цепочку). Такие переводы иногда называют цепочечными. 5.1.4 Практическое применение СУ-схем СУ-схемы предполагают существование отображения f: P1 —> P2 множества правил грамматики исходного языка в множество правил грамматики объектного языка. Выделяют два метода построения объектной программы путем преобразования исходной программы: 1 СУ-компиляция – строит объектную программу по ходу синтаксического анализа. В этом случае строить полное дерево разбора исходной программы, а тем более сохранять его после синтаксического анализа не требуется. 2 СУ-перевод – строит объектную программу после синтаксического анализа по его результату, представленным в виде дерева разбора. Рассмотрим метод построения объектной программы на основе СУперевода. В основу метода положено преобразование дерева разбора строки со во входной грамматике GBX в дерево разбора выходной строки у в грамматике GBbIХ. Метод позволяет получить перевод (w, у) любой входной строки w путем последовательного решения следующих трех задач: - построить дерево разбора w в грамматике GBX; - преобразовать полученное дерево в дерево разбора соответствующей строки у в грамматике GBbIX, используя правила СУ-схемы; - получить выходную строку у, взяв крону дерева разбора строки у. Алгоритм преобразования дерева разбора входной строки Обозначим: А — произвольный нетерминал СУ-схемы, А —>  — правило входной грамматики, где  = n1…nk . Пусть нетерминалу А соответствует узел А дерева разбора (нетерминальный узел). Тогда узлы n1,n2 , . . ., nk - прямые потомки узла А. Преобразование дерева разбора начинается с его корня и состоит в следующем: 1) выбрать очередной нетерминальный узел А дерева разбора входной строки; если все узлы обработаны, завершить работу; 2) устранить листья из множества узлов n1…nk (вершины, помеченные терминалами или  ); 3) найти в СУ-схеме правило вида (А —>  ,  ) и переставить оставшихся прямых потомков узла А в соответствии с их размещением в строке  (поддеревья перемещать вместе с их корнями); 4) добавить в качестве прямых потомков узла А листья так, чтобы метки всех его прямых потомков образовали цепочку  ; 5) повторять п. 1—4 для всех прямых нетерминальных потом ков узла А по порядку, слева направо. Пример Дана СУ-схема Т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. На рис. 5.1.2а показано дерево разбора входной строки 00111. Применение алгоритма преобразования к корню S этого дерева устраняет левый лист, помеченный 0 (шаг 2). Рисунок 5.2 - Преобразование дерева разбора: а - дерево входной строки; б - дерево после однократного применения алгоритма; в - дерево выходной строки Далее, так как корню соответствует правило S -> 0AS и для этого правила  = SAa, нужно поменять местами оставшихся прямых потомков корня (шаг 3). Затем следует добавить а в качестве самого правого, третьего, прямого потомка (шаг 4). Результатом будет дерево, показанное на рис. 5.1.2б. Снова применяем алгоритм, теперь уже к первым двум потомкам корня. Обработка второго из них приводит еще к двукратному повторению алгоритма. Окончательный результат показан на рис. 5.1.2в, это дерево разбора выходной строки bbbaa. Из анализа правил СУ-схемы Т2 следует, что она является не простой постфиксной схемой. 5.2 Транслирующие грамматики 5.2.1 Понятие Т-грамматики В простых СУ-схемах можно объединить левые и правые части соответствующих правил входной и выходной грамматик. Получающиеся таким образом грамматики принято называть транслирующими грамматиками (Тграмматиками). Символы выходного алфавита А в Т-грамматике называют операционными символами. При записи Т-грамматики каждый операционный символ во избежание путаницы каким-либо образом выделяют. Будем заключать такой символ в прямоугольные скобки. Пример Определение Т-грамматики для перевода инфиксных арифметических выражений в ПОЛИЗ: VT= {+, *, (,), имя};  = {[+], [*], [имя]}; VN = {S, Е,T, F}; S — аксиома, правила R: 1)S->E 2)E->E+T[+] 3) E->T 4) T->T*F[*] 5) T->F 6) F->(E) 7) F-> имя[имя] Ясно, что результатом удаления операционных символов из Т-грамматики будет входная грамматика. Если удалить из Т-грамматики терминалы, получим выходную грамматику, или грамматику действий. Т-грамматика описывает правила образования строк из терминалов и операционных символов. Эти строки называют активными цепочками. Если удалить из активной цепочки операционные символы, то получится ее входная часть. Если удалить из активной цепочки терминалы, получится выходная часть, или, иначе, трансляция, перевод входной части. Активную цепочку можно рассматривать как программу управления работой МП - преобразователя, соответствующего Т-грамматике. При этом входной символ можно считать обозначением операции чтения этого символа, а операционный символ — обозначением операции выдачи этого символа. Пример Активная цепочка а[a]+b[b]*с[с][*][+] описывает процесс трансляции входной цепочки а + b*с (исключили из активной цепочки операционные символы) в ПОЛИЗ [а] [b] [с] [*][+] (исключили из активной цепочки терминалы). Действительно, существует вывод (левосторонний) S => Е => Е+ Т[+] => Т+ Т[+] => F+ T[+] => а[а] + Т[+] => a[a] + T*F[*][+] => a[a] + F*F[*][+] => a[a] + b [b]*F [*][+] => a[a] + b[b]* с [с ][*][+], и пара (а + b*c, [a][b][с][*][+]) принадлежит переводу инфиксных выражений в ПОЛИЗ. В этом примере каждый операционный символ обозначает просто выдачу соответствующего входного символа в выходную строку. 5.2.2 Т-грамматика с подпрограммами Рассмотрим Т-грамматику для условных операторов. Грамматика описывает перевод сокращенных и полных условных операторов в ПОЛИЗ, например оператора вида if A then В else С; в ПОЛИЗ вида А т1УПЛ В m2БП m1:С т2, где А — логическое выражение, Z и С — любые операторы, в том числе и условные. Ясно, что элементы А, В и С в ПОЛИЗ оператора также будут записаны в ПОЛИЗ. Представим грамматику G = (VT, VN,P, S) условного оператора некоторого языка программирования правилами (табл. 4.2). Это входная грамматика, в которой VT= {if then, else, z, p, ;}, VN= {U,K,H,M,O}, S = U- аксиома. Для обозримости иллюстраций полагаем, что логическое выражение р и не условный оператор z описываются в других грамматиках и считаются уже разобранными синтаксическими конструкциями. Поэтому они включены в множество терминалов VN. Таблица 5.1 Правила грамматики условного оператора Номер правила Входная грамматика G Транслирующая грамматика GT 1 U->if K U->if K 2 3 К->рН Н -> then О М; K->p[xo]H H->then[x1]O M [x3]; 4 М -> else О М -> else [X2] О 5 6 M->  O->U М ->  O->U 7 0->z O->z [X0] Теперь запишем Т-грамматику, пополнив входную грамматику операционными символами. Операционные символы подберем, исходя из сравнения форм исходных операторов и соответствующих им форм ПОЛИЗ. Возможный вариант правил R для Т-грамматики GT = (VT, VN,  , Р, S) показан в табл. 5.2.1. В этой грамматике  = {[х0], [х1], [х2], [х3]}, a VT, VN И U имеют тот же смысл, что и во входной грамматике. Операционные символы по сути своей являются подпрограммами, которые выполняются в темпе синтаксического анализа и осуществляют следующие действия: - [x0] - копирует текущий входной символ (терминал) в выходную строку; - [x1] - создает очередную метку mj, дописывает в выходную строку цепочку m j УПЛ и помещает m j . в вершину стека меток; - [x2] - создает очередную метку mj+1, дописывает в выходную строку цепочку mj+1БПmj:, где тj— метка в вершине стека меток, и замещает в стеке метку mi: меткой mj+1:; - [х3] - выталкивает метку тk из вершины стека меток в выходную строку. Транслирующая грамматика GT описывает активные цепочки. Так, входному оператору if a then b else с; будет соответствовать активная цепочка if a [X0] then[x1] b[x0] else[x2] c[x0] [x3]. 5.2.3 МП-преобразователь для Т-грамматики Активная цепочка может рассматриваться как программа управления работой МП-преобразователя. Прежде чем посмотреть, как это происходит, обратимся к методике построения МП-преобразователя по транслирующей грамматике. Затем получим, преобразователь для Т-грамматики условного оператора и проследим работу преобразователя. Рассматриваемая входная грамматика условных операторов (см. табл. 5.2.1) относится к классу LL(1)-грамматик. Поэтому вполне естественно вести здесь речь о построении преобразователя, подходящего для такого класса грамматик. Наш МП преобразователь будет использовать нисходящую стратегию анализа, он будет также детерминированным. Методика построения МП - распознавателя для LL(1)грамматик была рассмотрена ранее. Повторим здесь полностью все пункты указанной методики с учетом особенностей, которые привносит в нее Т-грамматика. Прежде всего, сохраним, по возможности, обозначения подпрограмм в управляющей таблице преобразователя: - 3 (  ,  ) - Замена символа в вершине магазина строкой  и запись в выходную строку части перевода, соответствующей цепочке  операционных символов. - П - перемещение указателя входной строки на одну позицию вправо. - И(  ) - Исключение символа из вершины магазина и вывод в выходную строку части перевода, соответствующей цепочке  операционных символов. - О - Обнаружение Ошибки в программе и завершение работы. - В - Выход, нормальное завершение работы. Если один из аргументов подпрограммы 3 отсутствует, сохраняем разделяющую запятую. При отсутствии единственного аргумента подпрограммы И пишем И(). Теперь дадим пункты методики построения ДМП-преобразователя М = (Q,  , Г,  ,  , q0, Z0, F) с одним состоянием по Т-грамматике GT = (VT , VN,  , R, S), входная грамматика G = (VT, VN, Р, S) которой обладает свойством LL(1)-грамматик. 1 . Q = { q } ; q 0 = q;F=  2.  =VT  {#}, # — концевой маркер входной строки. 3. Г= V N  {#}  {t\ t  V T ,(A ->  t  )  Р,   V + ,   V*}  {r\r   , (А- >  1 B  2 r  3 )  R, B  VN;  1  2,  3 (V   )*}, где t - не головной символ в правой части правила; r - операционный символ, слева от которого в правой части правила имеется хотя бы один нетерминал; # — маркер дна магазина. 4. Z0 = S#, S располагается в вершине магазина. 5. Заготовить управляющую таблицу преобразователя со строками Z Г и столбцами а   (одну, так как состояние одно). 6. Последовательно проанализировать правила Т-грамматики и заполнить позиции (Z, а) таблицы обозначениями подпрограмм преобразователя: а) 3(  ,fg),П—для правила вида Z->fag  ,где Z  V N ,a  V T , f,g   *;   {V   }* и h1(  )  V, т.е. головной символ строки  не должен быть операционным; б) 3(  ,f)—для правила вида Z->f  и всех a DS(Z,  ), где f  *;  =A  ,Z,A V N ;   {V   }*,    ;DS(Z,  ) вычисляется по правилам входной грамматики G; в) И(f)—для правил вида Z ->f и всех a  DS(Z,  ), где Z V N ; f   *, а   ; DS(Z,  ) вычисляется по грамматике G; г) И(fg),П—для правил вида Z->fag, где Z VN,а  VT;f, g   *. 7. Завершение заполнения позиций (Z, д) таблицы обозначениями подпрограмм преобразователя: а) И(), П — для всех позиций Z = а, где Z,a  VT; б) И — для всех позиций строки Z   ; в) В — для позиции Z = а = #; г) О — для всех оставшихся пустыми позиций. Теперь формируются заготовки текстов сообщений об ошибках, и на этом разработка МП-преобразователя завершается. Задача Построить МП-преобразователь по транслирующей грамматике условных операторов Решение 1. Q= {q};q0=q;F=  2.  ={if,then,else,z,p,;,#} 3. Г= {U,K,H,M,O,#,;,[x3]} 4. Z0= U# 5. Управляющая таблица представлена в табл. 5.2.2 6. Пояснения к заполнению табл. 5.2.2: а) правило 1 — помещаем 3(К,),П в позицию (U, if); правило 2 — помещаем 3(Н,[х0]),П в позицию (K, р); правило 3 — помещаем З((ОМ[х3];),[х1]), в позицию (H, then); правило 4 — помещаем З(О,[х2]),П в позицию (М, else); б) правило 6 — помещаем 3(U,) в позицию (О, z); в) правило 5 — помещаем И в позицию (М,;); г) правило 7 — помещаем И([х0]),П в позицию (О, z). 7. Пояснения к завершению заполнения табл. 5.2.2; а) помещаем И( ),П в позицию (;,;); б) помещаем И([xз]) во все позиции строки [xз]; в) помещаем В в позицию (#, #); г) помещаем О во все свободные позиции таблицы. Таблица 5.2 Управляющая таблица U K if 3(К,),П О then О О else О О z О О H О 3((0М[х3]; [x1]),П О O M О О 3(О,[х2]),П О р О 3(О,[х2] ),П О О ; О O # O И() О 3(U,) О О ; [х3] # О О О О O И([x3]) O И[х O 0]),П О О О O O И( 0 ),П B Задача Используя МП - преобразователь из предыдущей задачи, выполнить перевод оператора ifp1 then z1 else z2; в ОПЗ. Прежде всего обратим внимание на то, что помимо магазина наш МП преобразователь работает со стеком меток. Решение представим в табл. 5.2.3, предусмотрев в ней колонки для отображения номера шага преобразования, содержимого магазина, содержимого входной строки и записей в выходную строку преобразователя. Магазин изображается так, что его вершина расположена слева. Текущий символ входной строки также находится слева. Выходная строка формируется слева направо. Кроме того, для наглядности предусмотрены колонки для показа операционного символа, являющегося активным на текущем шаге перевода (колонка "операция"), и для представления стека меток (вершина стека слева). На каждом шаге работы преобразователя выделяется пара (символ в магазине, текущий входной символ) и выполняются действия, определенные содержимым соответствующей позиции таблицы и активным операционным символом. На выходе преобразователя получена строка р1т2УПЛz1т1БПт1:z2т2:, которая представляет собой ПОЛИЗ исходного оператора и может быть использована для генерации машинного кода или интерпретации. Таблица 5.3 Перевод условного оператора в ОПЗ Шаг Магазин перевода Входная строка 1 U# if P1 then z1 else z2 # 2 3 4 5 6 7 8 K# ## OM[x3];# М[х 2 ];# О[х3];# [x3];# ;# P2 then z2 else z2;# then z1 else z2; # z1 else z2;# else z1;# z2;# ;# ;# 9 # # Стек меток m1: m1: m1: m2: m2: Операция Запись в выходную строку [x 0 ] [x1] [x0] [x2] [x0] [х3] Р1 т1 УПЛ Z1 m2 БПm1: z2 т 2: 5.3 Атрибутные транслирующие грамматики 5.3.1 Синтезируемые и наследуемые атрибуты Каждому символу формальной грамматики присущи класс и значение. Скажем, если символом Е обозначено арифметическое выражение, то с ним может быть связано числовое значение, адрес памяти для числа, тип числа, признак обнаруженной в выражении ошибки и т.д. Все это значения символа Е. Рассмотренный ранее формализм перевода описывает перевод только той составляющей символа, которая характеризует его класс. Дальнейшее развитие теории компиляции касается значений символов. Найти значение строки КС-языка можно, вычислив так называемые атрибуты в каждом узле дерева ее разбора. Атрибуты вычисляют по формулам, связанным с правилами грамматики языка. Атрибуты подразделяют на синтезируемые и наследуемые. Синтезируемые атрибуты в некотором узле дерева зависят только от атрибутов в узлах-потомках. Значит, они служат для передачи информации по дереву снизу вверх, а в правилах грамматики — из правой части в левую. Наследуемые атрибуты в некотором узле являются функциями атрибутов его узла-предка и (или) узлов-потомков этого предка. Такие атрибуты, как видим, могут распространять информацию в противоположном направлении. Важно отметить, что КС-грамматика, снабженная атрибутами, сохраняет свои обычнее свойства и вместе с тем позволяет формально учесть контекстнозависимые условия языка. А элементы контекстной зависимости присутствуют во всех языках программирования. Рассмотрим суть синтезируемых атрибутов на примере, в котором синтаксический анализатор арифметических выражений выдает численное значение выражения. В этом простом примере операндами могут быть только константы. Т-грамматика выражений содержит единственный операционный символ (обозначим его [ЗНАЧ]) и имеет вид: 1) S ->Е[ЗНАЧ] 2)Е->Е+Т 3)E->T $)T->T*F 5) T->F 6) F->(E) 7) F->C где VN = {S, E, T, F}, VT = {+, *, (,), С}, S — аксиома; С — константа, значение которой во внутреннем представлении построил лексический анализатор. Возьмем строку (С 3 + С9)*С2 в качестве входной для синтаксического анализатора. В этом выражении подстрочными индексами указаны значения констант, которые и будем считать их атрибутами. Построим дерево разбора активной цепочки (C3+ С9)*С2[ЗНАЧ]24 и снабдим нетерминалы (в узлах дерева) значениями синтезируемых атрибутов (рис. 5.3 а). Значение выражения формируется из значений его подвыражений по правилам (формулам), соответствующим правилам грамматики. Представим эти формулы математически, для чего в каждом правиле грамматики предусмотрим различные имена для разных значений атрибутов, а затем запишем соответствующие формулы. Атрибутом снабжается каждый нетерминал правила грамматики. Имена атрибутов обычно записывают как подстрочные индексы. Например, правилу Е —> Е+ Т транслирующей грамматики соответствуют правило Ер —> Eq+Tr и формула р=- q + r. Обозначения атрибутов в различных правилах не имеют между собой ничего общего и могут быть одинаковыми. Рисунок 5.3 - а) Дерево разбора активной цепочки (С3+С9)*С2[ЗНАЧ]24 б) АТ-грамматика арифметических выражений Полученные таким образом правила называют атрибутными, а грамматику с атрибутными правилами и формулами для атрибутов — атрибутной транслирующей грамматикой (АТ-грамматикой). Атрибутная транслирующая грамматика для нашего примера дана на рис. 5.3 б. Заметим, что атрибут операционного символа [ЗНАЧ] не относится к числу синтезируемых, он — наследуемый. Теперь поясним смысл наследуемых атрибутов на примере, в котором синтаксический анализатор описания переменных помещает признак типа (real, int или boot) имени в соответствующее поле таблицы имен. Пусть Т-грамматика описания переменных имеет вид: 1) описание —> Т V [тип] список 2) список —>, V [тип] список 3) список —>  В этой грамматике символы "описание", "список*' — нетерминалы( VN); Т, V,, — терминалы (VT), [тип]   — операционный символ, где V — символ класса имен со значением, представленным указателем на элемент таблицы имен; Т— символ класса ключевых слов со значением, представленным указателем на real, int или bool. Запятая (,) — символ класса ограничителей. Операционный символ [тип] располагается в правилах вслед за именем V и предписывает поместить признак типа Т в поле "тип" записи переменной V таблицы имен. Поэтому значение [тип] определяется парой атрибутов (указ, тип), где "указ" — указатель на запись V в таблице имен, "тип" — значение Т. Введем атрибуты и формулы для их вычисления в грамматику описания переменных. Будем использовать имена ti, где i = 0, 1, 2,..., для обозначения атрибута "тип" (значение Т), именами pi обозначим атрибут "указатель" (значение V). Для передачи типа переменной из правила 1 в последующие снабдим нетерминал "список" атрибутом типа. Тогда АТ-грамматика описания переменных может выглядеть так: 1) описание —> Tr0 VP0 [тип]р1,r1 список t2 t2,t1 = t0;p1 =p0 2) cnucoкr0 -> , Vp0 [min]p1,t1 списокt2 t2,t1 = t0; р1 =р0 3)список r 0 ->  Формула t2, t1 = t0 означает, что атрибуты t2 и t1 получают значение атрибута t0. Согласно формуле р1 = р1 атрибут р1 получит значение атрибута р0. Возьмем в качестве примера описание real a, c1, abc. Синтаксический анализатор получит входную строку, которая в наших обозначениях выглядит так: Treal V1, V2 V3. Здесь 1, 2, 3 — номера позиций имен в таблице имен. Построим дерево разбора (рис. 5.1.4) соответствующей активной цепочки Рисунок 5.4 - Дерево разбора активной цепочки Как видно из рассмотренных примеров, информация о синтезируемых атрибутах распространяется вверх по дереву (см. рис. 5.3), а информация о наследуемых — вниз по дереву (рис. 5.4). 5.3.2 Определение и свойства АТ-грамматики АТ-грамматика — это транслирующая грамматика, дополненная следующим образом. 1. Каждый терминал, нетерминал и операционный символ имеет конечное множество атрибутов, и каждый атрибут имеет множество (возможно, бесконечное) допустимых значений. 2. Все атрибуты нетерминалов и операционных символов делятся на наследуемые и синтезируемые. 3. Наследуемые атрибуты вычисляются следующим образом: а) значение наследуемого атрибута из правой части правила грамматики вычисляется как функция некоторых других атрибутов символов, входящих в правую или левую часть данного правила; б) начальные значения наследуемых атрибутов аксиомы грамматики полагаются известными. 4. Синтезируемые атрибуты вычисляются так: а) значение синтезируемого атрибута нетерминала из левой части правила грамматики вычисляется как функция некоторых других атрибутов символов из левой или правой части данного правила; б) значение синтезируемого атрибута операционного символа вычисляется как функция некоторых других атрибутов этого символа. 5. Значения атрибутов терминалов считаются заданными, они не относятся ни к наследуемым, ни к синтезируемым. Исходя из этого определения и анализа грамматик, убеждаемся, что в грамматике выражений атрибуты всех нетерминалов — синтезируемые, а в грамматике описаний — наследуемые. В обоих грамматиках атрибуты операционных символов — наследуемые. Значения атрибутов терминалов устанавливает лексический анализатор. Атрибуты отдельных символов не указывались, поскольку не играли никакой роли. АТ-грамматики используют для построения атрибутных деревьев разбора, атрибутных активных цепочек и атрибутных переводов (трансляций). Атрибутное дерево строится следующим образом. 1. По Т-грамматике построить дерево разбора активной цепочки, состоящей из терминалов и операционных символов без атрибутов. 2. Присвоить значения атрибутам терминалов, входящих в дерево разбора. 3. Присвоить начальные значения наследуемым атрибутам аксиомы грамматики на дереве разбора. 4. Вычислять значения атрибутов символов на дереве, пока это возможно, по правилу: найти атрибут, которого еще нет на дереве, но аргументы для функции его вычисления уже известны; вычислить значение этого атрибута; разместить атрибут на дереве. Если по завершении п.4 значения всех атрибутов всех символов дерева оказываются вычисленными, то такое дерево называют завершенным. Причиной незавершенности дерева может оказаться так называемая круговая зависимость между атрибутами, входящими в одну формулу. АТ грамматика, обеспечивающая завершенность любого дерева разбора, называется корректной. Именно корректные грамматики представляют интерес для разработчиков трансляторов. Показано, что можно найти подклассы АТ - грамматик, которым соответствуют детерминированные МП - машины. Сформулирован ряд важных теорем, отдельные из которых дадим здесь без доказательства. Теорема 1. Любая трансляция, определяемая L-AT-грамматикой, может быть выполнена недетерминированной атрибутной МП - машиной. АТ - грамматика называется L-AT-грамматикой, если выполняются следующие условия (ограничения на АТ - грамматику). 1. Значение наследуемого атрибута символа из правой части правила может зависеть только от наследуемых атрибутов левой части правила и от любых атрибутов символов, стоящих в правой части правила левее рассматриваемого символа. 2. Значение синтезируемого атрибута нетерминала из левой части правила может зависеть только от наследуемых атрибутов этого символа и от любых атрибутов символов правой . 3. Значение синтезируемого атрибута операционного символа зависит только от наследуемых атрибутов этого символа. Условие 1 делает наследуемые атрибуты некоторого узла дерева разбора зависящими (прямо или косвенно) от атрибутов терминалов, расположенных на дереве левее данного узла. Отсюда и наименование грамматики (Left - левая). Условия 2 и 3 делают грамматику корректной. Теорема 4. Любую трансляцию, определяемую L-AT-грамматикой, у которой входная грамматика является LL(k)-грамматикой, можно выполнить на атрибутной детерминированной МП-I машине с концевым маркером. Отметим, что здесь, как и в случае с МП-распознавателем, LL(k)грамматика обеспечивает применение нисходящей стратегии анализа. Теорема 6. Всякая трансляция, определяемая некоторой S-атрибутной польской транслирующей грамматикой (S-АПТ-грамматикой) с входной LR(к)грамматикой, может быть выполнена детерминированной атрибутной МП машиной с концевым маркером. В данном случае МП - машина работает с использованием восходящей стратегии анализа. АТ - грамматика называется польской, если все операционные символы встречаются только в качестве последних символов правых частей правил грамматики. Наконец, L-AT-грамматика называется S-атрибутной, если все атрибуты нетерминалов — синтезируемые. 5.3.3 Формирование АТ-грамматики Теперь покажем, как по конкретной входной КС -грамматике можно построить АТ-грамматику и определить ее класс. Задача Дана КС-грамматика G = (VT, VN, P, S) описания вещественных переменных, где VT- {real, имя, ,}, VN = {DCL, LIST), S = DCL и P - множество правил: 1)DCL -> real имя LIST 2)LIST ->, имя LIST 3)LIST->ε Требуется сформировать АТ-грамматику описания переменных и распределения памяти под значения этих переменных в некотором блоке памяти. Адрес должен быть помещен в запись таблицы имен для соответствующей переменной. Для определенности положим, что переменной отводится одна нумерованная ячейка памяти. Решение 1. Определим класс входной грамматики G. Следуя методике, изложенной в разделе LL(k)-грамматики, устанавливаем, что грамматика G обладает свойствами LL(1)-грамматик. 2. Преобразуем входную грамматику в Т-грамматику. Адрес должен быть назначен переменной сразу после чтения во входной строке символа имя. Поэтому операционный символ, который обозначим [ALLOC], располагается в Тграмматике после каждого терминала имя: 1) DCL -> real имя [ALLOC] LIST 2)LIST-*, имя [ALLOC]LIST 3)LIST->ε 3. Определим атрибуты символов Т-грамматики. Атрибут символа имя указатель на строку таблицы имен. Атрибуты символа DCL: 1) указатель на начальную ячейку блока памяти для переменных наследуемый; 2) указатель на свободную ячейку после обработки всего описания синтезируемый (от символа LIST в правой части правила). Атрибуты символа LIST: 1) указатель на очередную свободную ячейку блока памяти - наследуемый (из левой части правила); 2) указатель на свободную ячейку после обработки всего описания — синтезируемый (от символа в левой или правой части правила). Атрибуты символа [ALLOC]: 1) указатель на строку таблицы имен — наследуемый (от левого символа имя); 2) адрес ячейки памяти для значения переменной — наследуемый (от символа в левой части правила). 4. Выберем обозначения для атрибутов символов правила, положив i=0,1, ...: pi — указатель на строку таблицы имен; bi — указатель на свободную ячейку блока памяти; ai — адрес, назначенный переменной. 5. Запишем грамматику, приписав символам атрибуты, а за тем пополнив ее комментариями для атрибутов и правилами вычисления их значений. В результате этих действий получим АТ-грамматику: /*** DCLx1,x2 - наследуемый x1, синтезируемый х2; ***/ /*** LISTy1,y2 - наследуемый y1, синтезируемый у2; ***/ /*** [ALLOC]z1,z2 - наследуемые z1 и z2. ***********/ 1) DCLb0,b1 -> real имяр0[АLLОС]p1,a0LISTb2,b3 p1 = p0, a0 = b0,b2 = b0+1, b1 = b3 2) LISTb0,b1 ->, имяр0[АLLОС]p1,a0LISTb2,b3 p1 = p0, a0 = b0,b2 = b0+1, b1 = b3 3) LISTboM -> ε b1 = b0 Поясним отдельные формулы для вычисления значений атрибутов. Предварительно еще раз уточним функцию операционного символа [ALLOC]. По своей сути это подпрограмма, которая по указателю р1 на элемент таблицы имен для информации о переменной, предшествующей [ALLOC], помещает в определенное поле этого элемента адрес a0 ячейки для значения переменной. Носителем указателя является терминал имя, отсюда формула р1 = р0. Носителем адреса является первый атрибут нетерминала в левой части правила, отсюда формула a0 = b0. Информация о текущей свободной ячейке передается к другим правилам посредством атрибута b2 нетерминала LIST в правой части правила. Номер свободной ячейки на 1 больше последней занятой (формула b2 = b0 + 1). Атрибут b0 символа LIST в правиле 3 будет содержать адрес свободной ячейки после назначения адресов всем элементам списка переменных. Поэтому второй атрибут в этом правиле должен получить значение первого (формула b1 = b0). Формула b1 = b3 позволяет передать это значение атрибуту b1 нетерминала DCL. 6. Определим класс АТ-грамматики. Для этого проверим выполнение условий для атрибутов из определения LAT-грамматики. Все эти условия выполняются. Значит, полученная грамматика есть L-AT-грамматика с входной LL(1)-грамматикой. Порядок вычисления значений атрибутов хорошо иллюстрируется с помощью дерева разбора активной атрибутной цепочки. Пример Для входной строки real имя5, имя4 и L-AT-грамматики из предыдущей задачи дерево разбора соответствующей активной атрибутной цепочки показано на рис. 5.5. В этом примере начальный адрес в блоке принят равным нулю. Рисунок 5.5 Дерево разбора активной атрибутной цепочки real имя5 [ALLOC]5 имя4 [ALLOC]4 После построения безатрибутного дерева оно заполнялось значениями атрибутов. Вычисление наследуемых атрибутов выполнялось раньше синтезируемых и велось в направлении от корня дерева к его листьям. Синтезируемые атрибуты, напротив, вычислялись при движении от листьев к корню. Интересно проследить, как пришедшая сверху информация (номер 2 очередной свободной ячейки) направляется снова вверх после применения правила 3 грамматики. Заметим также, что свойство L-атрибутной грамматики обеспечивает вычисление атрибутов в порядке, пригодном для нисходящей обработки входной строки. Атрибутную трансляцию, описанную формально АТ - грамматикой, можно выполнить с помощью атрибутного МП - преобразователя, который называют также атрибутным МП - процессором или атрибутной МП - машиной. Выполнение атрибутной трансляции предполагает следующие действия МП - преобразователя: - последовательное чтение входных символов вместе с их атрибутами; - проверку принадлежности входной строки языку, определенному входной грамматикой; - выдачу последовательности атрибутных операционных символов, соответствующей входной строке, из активной атрибутной цепочки. Атрибутный МП - преобразователь представляет собой обычный МПпреобразователь, у которого состояния, входные, выходные и магазинные символы имеют атрибуты. На каждом шаге работы преобразователя значения атрибутов нового состояния, нового верхнего символа магазина (если этот шаг — не выталкивание из магазина) и выходных символов вычисляются как функции атрибутов старого состояния, верхнего символа магазина и входного символа (если это не пустой шаг). Вопросы построения атрибутных МП - преобразователей здесь рассматривать не будем.