Раздел 13. Теория языков программирования и методы трансляции

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

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

Алфавит - это конечное множество символов. Формальным языком L над алфавитом А называется множество цепочек этого алфавита. Цепочкой символов в алфавите А называется любая конечная последовательность символов этого алфавита.

Строка над некоторым алфавитом – это конечная последова-

тельность символов, взятых из алфавита. В теории языков термины

«предложение» и «слово» часто используются как символы терми-

на «строка». Длина строки s, обычно обозначаемая как |s|, равна

количеству символов в строке. Например, длина строки banana рав-

на шести.

Пустая строка, обозначаемая как лямбда (или епсилан), представляет собой

специальную строку нулевой длины.

Язык обозначает произвольное множество строк над некоторым фиксированным алфавитом.

Операции:

L U M объединение

Множество всех слов, принадлежащих хотя бы одному из языков L или M

LM конкатенация (или сцепление)

Множество слов из языка L и к нему присоединены некоторые слова из языка M

L* замыкание Клини

Обозначает 0 или более конкатенаций языка L

L+ позитивное замыкание

Обозначает 1 или более конкатенаций языка L

Теория формальных языков и грамматик

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

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

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

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

В конце 60х годов было обнаружено, что бесконтекстные языки на базе порождающих грамматик можно представить в виде специальных метаязыков, популярных в программировании, а именно в виде БНФ-нотаций (Бэкус-Науровы формы). Это позволило изучить языки программирования и описать их синтаксис как с практической, так и с теоретической точки зрения. Были введены различные виды грамматик, изучены их свойства и предложен класс специальных распознающих автоматов на базе теории автоматов, которые активно используются в информатике.

Основные задачи:

Использование математических средств в описании искусственных языков и их организации связано с двумя разными практическими задачами:

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

• 2-я задача в некотором смысле обратная первой, заключается в том, что следующая разработка правила позволяет установить, является ли произвольная цепочка правильной конструкцией или фразой этого языка. В случае утвердительного ответа, требуется указать имена этих отдельных конструкций или определенную синтаксическую структуру этой фразы. В случае отрицательного ответа необходимо определить или указать информацию, указывающую на ошибки при описании этой конструкции, как, например, это делается при отладке языков программирования.

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

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

Формальная порождающая грамматика G - это четверка (VT, VN, P, S), где

VT - алфавит терминальных символов (терминалов),

VN - алфавит нетерминальных символов (нетерминалов), не пересекающийся с VT,

P - конечное подмножество множества (VT U VN)+ x (VT U VN)*; элемент (альфа, бета) множества P называется правилом вывода и записывается в виде альфа->бета,

S - начальный символ (цель) грамматики, S прин. VN.

Множество всех цепочек терминальных символов, выводимых из аксиом грамматики, называется языком, порождаемым этой грамматикой.

Классификация грамматик:

Тип 0: Грамматика G = (VT, VN, P, S) называется грамматикой типа 0, если на правила вывода не накладывается никаких ограничений (кроме тех, которые указаны в определении грамматики).

Тип 1: Грамматика G = (VT, VN, P, S) называется неукорачивающей грамматикой, если каждое правило из P имеет вид альфа->бета, где альфа прин (VT U VN)+, бета прин. (VT U VN)+ .

Грамматика G = (VT, VN, P, S) называется контекстно-зависимой (КЗ), если каждое правило из P имеет вид альф->бета, где альфа = епсилан1Aепсилан2; бета = епсилан1каммаЕпсилан2; A прин VN; камма прин (VT U VN)+; епсилан1,епсилан2 прин (VT U VN)*.

Грамматику типа 1 можно определить как неукорачивающую либо как контекстно-зависимую. Выбор определения не влияет на множество языков, порождаемых грамматиками этого класса, поскольку доказано, что множество языков, порождаемых неукорачивающими грамматиками, совпадает с множеством языков, порождаемых КЗ-грамматиками.

Тип 2: Грамматика G = (VT, VN, P, S) называется контекстно-свободной (КС), если каждое правило из Р имеет вид A -> бета, где A прин VN, бета прин (VT U VN)+.

Грамматика G = (VT, VN, P, S) называется укорачивающей контекстно-свободной (УКС), если каждое правило из Р имеет вид A -> бета, где A прин VN, бета прин (VT U VN)*.

Грамматику типа 2 можно определить как контекстно-свободную либо как укорачивающую контекстно-свободную. Возможность выбора обусловлена тем, что для каждой УКС-грамматики существует почти эквивалентная КС-грамматика.

Тип 3: Грамматика G = (VT, VN, P, S) называется праволинейной, если каждое правило из Р имеет вид A -> tB либо A -> t, где A прин VN, B прин VN, t прин VT.

Грамматика G = (VT, VN, P, S) называется леволинейной, если каждое правило из Р имеет вид A -> Bt либо A -> t, где A прин VN, B прин VN, t прин VT.

Грамматику типа 3 (регулярную, Р-грамматику) можно определить как праволинейную либо как леволинейную. Выбор определения не влияет на множество языков, порождаемых грамматиками этого класса, поскольку доказано, что множество языков, порождаемых праволинейными грамматиками, совпадает с множеством языков, порождаемых леволинейными грамматиками.

66. Лексический анализ: роль лексического анализатора, взаимосвязь лексического и синтаксического анализаторов, принципы построения и функции лексического анализатора, связь лексического анализа, автоматных грамматик и конечных автоматов, конечные автоматы и распознаватели, недетерминированные и детерминированные конечные автоматы, преобразования конечных автоматов, цель этих преобразований.

Лексический анализ: роль лексического анализатора, взаимосвязь лексического и синтаксического анализаторов, принципы построения и функции лексического анализатора, связь лексического анализа, автоматных грамматик и конечных автоматов, конечные автоматы и распознаватели, недетерминированные и детерминированные конечные автоматы, преобразования конечных автоматов, цель этих преобразований.

Компиляция состоит из двух основных частей: анализа и синтеза. Анализ – это разбиение исходной программы на составные части и создание ее промежуточного представления.

В процессе анализа определяются и записываются в иерархическую древовидную структуру операции, заданные исходной программой. Часто используется специальный вид дерева – синтаксическое дерево, в котором каждый узел представляет операцию, а

его дочерние узлы – аргументы операции (операнды). Синтез – это конструирование требуемой целевой программы из промежуточного представления. Процесс трансляции разбивается на несколько этапов, за выполнение каждого из которых отвечает свой блок.

10 Основные фазы трансляции: лексический анализ, синтаксический анализ, семантический анализ, синтез объектной программы.

Цели лексического анализа:

1) перевод исходной программы на внутренний язык компиля-

тора, в котором ключевые слова, идентификаторы, метки и кон-

станты приведены к одному формату и заменены условными кода-

ми: числовыми или символьными, которые называются дескрипто-

рами. Каждый дескриптор состоит из двух частей: класса-типа лек-

семы и указателя на адрес в памяти, где хранится информация о

конкретной лексеме. Эта информация организуется в виде таблиц;

2) лексический контроль – выявление в программе недопусти-

мых слов.

Цели синтаксического анализа:

1) перевод последовательности образов лексем в форму проме-

жуточной программы;

2) синтаксический контроль – выявление синтаксических оши-

бок в программе.

Лексический анализ представляет собой первую фазу компиля-

ции. Его основная задача состоит в чтении новых символов и выда-

чи последовательности лексем, используемых синтаксическим ана-

лизатором в своей работе. Лексической единицей языка является

лексема.

Лексема – это структурная единица языка, которая состоит из

элементарных символов языка и не содержит в своем составе дру-

гих структурных единиц языка.

Лексемами языков естественного языка общения между людьми

являются слова. Лексемами языков программирования являются

идентификаторы, константы, ключевые слова языка, знаки опера-

ций и т.п. Состав возможных лексем каждого конкретного языка

программирования определяется синтаксисом этого языка.

Каждый класс лексем описывается правилом, называемым шаб-

лоном.

Шаблон – правило, описывающее набор лексем, которые могут

представлять определенную лексему в исходной программе.

Лексический анализатор (или сканер) – это часть компилятора,

которая читает исходную программу и выделяет в ее тексте лексе-

мы входного языка.

На вход лексического анализатора поступает текст исходной

программы, а выходная информация передается для дальнейшей об-

работки компилятором на этапе синтаксического анализа и разбора.

С теоретической точки зрения лексический анализатор не явля-

ется обязательной частью компилятора. Все его функции могут вы-

полняться на этапе синтаксического разбора. Однако лексический

анализ включают в состав практически всех компиляторов по сле-

дующим причинам:

– применение лексического анализатора упрощает работу с тек-

стом исходной программы на этапе синтаксического разбора и со-

кращает объем обрабатываемой информации;

– для выделения в тексте и разбора лексем применяется простая

и эффективная техника анализа, в то время как на этапе синтакси-

ческого анализа конструкций исходного языка используются доста-

точно сложные алгоритмы разбора;

– при конструкции компилятора, когда лексический анализ реа-

лизован отдельно от синтаксического, для перехода от одной вер-

сии языка программирования к другой достаточно только пере-

строить относительно простой лексический анализатор.

Основные функции лексического анализатора:

1) исключение из текста исходной программы комментариев;

2) исключение из текста исходной программы незначащих про-

белов, символов-табуляций и перевода строки;

3) выделение лексем следующих типов: идентификаторов, стро-

ковых, символьных и числовых констант, ключевых (служебных)

слов входного языка, знаков операций и разделителей.

Общие принципы построения лексических анализаторов

Лексический анализатор имеет дело с такими объектами, как

различного рода константы и идентификаторы (к последним отно-

сятся и ключевые слова). Язык констант и идентификаторов в

большинстве случаев является регулярным, т. е. может быть описан

с помощью регулярных грамматик. Распознавателями для регуляр-

ных языков являются конечные автоматы. Существуют правила, с

помощью которых для любой регулярной грамматики может быть

построен недетерминированный конечный автомат, распознающий

цепочки языка, заданного этой грамматикой. Конечный автомат для

каждой входной цепочки языка дает ответ на вопрос о том, принад-

лежит или нет цепочка языку, заданному автоматом.

В общем случае задача сканера несколько шире, чем просто

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

языку. Кроме того, сканер должен выполнить следующие действия:

– четко определить границы лексемы, которые в исходном тек-

сте явно не заданы;

– выполнить действия для сохранения информации об обнару-

женной лексеме (или выдать сообщение об ошибке, если лексема

неверна).

В качестве промежуточного шага при создании лексического

анализатора можно рассматривать стилизованные блок-схемы, на-

зываемые диаграммами переходов. Диаграмма переходов изобра-

жает действия, выполняемые лексическим анализатором при вызо-

ве его синтаксическим анализатором для получения очередной лек-

семы. Позиции в диаграмме переходов изображаются кружками и

называются состояниями. Состояния соединены стрелками, назы-

ваемыми дугами. Выходящие из состояния s дуги имеют метки,

указывающие входные символы, которые могут появиться во вход-

ном потоке по достижении состояния s. Метка other означает появ-

ление любого символа, не указанного другими исходящими дугами.

Диаграммы переходов в данном случае детерминированные, т.е.

ни один символ не может быть меткой двух исходящих из одного

состояния дуг. Одно из состояний имеет метку start – это начальное

состояние диаграммы переходов в момент начала распознавания

лексемы. Некоторые состояния имеют действия, выполняемые при

их достижении. При попадании в некоторое состояние считывается

следующий входной символ. Если имеется исходящая дуга с мет-

кой, соответствующей этому символу, перемещаемся по ней в сле-

дующее состояние. Если такой дуги нет, то входящий символ не-

корректен и произошла ошибка.

Конечные автоматы

Распознавателем языка называется программа, которая получа-

ет на входе строку x и отвечает «да», если x – предложение языка,

или в противном случае – «нет». Регулярное выражение компили-

руется в распознаватель путем построения обобщенной диаграммы

переходов, называемой конечным автоматом. Такой автомат мо-

жет быть детерминированным или недетерминированным (неде-

терминированный автомат может иметь более одного перехода из

некоторого состояния при одном и том же входном символе).

Как детерминированные, так и недетерминированные конечные

автоматы способны к распознаванию точных регулярных мно-

жеств. Таким образом, они могут распознавать все, что могут обо-

значать регулярные выражения. Однако детерминированные ко-

нечные автоматы, которые приводят к более быстрому распознава-

нию, обычно больше по размеру, чем эквивалентные недетермини-

рованные. Существуют методы преобразования регулярных выра-

жений в оба типа конечных автоматов.

Недетерминированные конечные автоматы

Недетерминированный конечный автомат (НКА) A = (Q, V, ДЕЛЬТА,

q0, F) представляет собой математическую модель, состоящую:

– из множества состояний Q;

– из множества входных символов V (символов входного алфа-

вита);

– из функции переходов , которая отображает пары символ –

состояние на множество состояний;

– из состояния q0, известного как стартовое (начальное);

– из множества состояний F, известных как допускающие (ко-

нечные).

НКА может использоваться в виде помеченного ориентирован-

ного графа, так называемого графа переходов, узлы которого пред-

ставляют собой состояния, а помеченные дуги составляют функ-

цию переходов. Такой граф похож на диаграмму переходов, однако

один и тот же символ может помечать два и более переходов из од-

ного состояния, а некоторые переходы могут быть помечены спе-

циальным символом e, как обычным входным символом (e-

переходы).

Функция переходов НКА может быть реализована различными

способами. Простейший из них – таблица переходов (табл. 6), в ко-

торой строки представляют состояния, а столбцы — входные сим-

волы. Запись в строке i для символа а является множеством состоя-

ний, которые могут быть достигнуты переходом из состояния i при

входном символе а.

Детерминированный конечный автомат

Детерминированный конечный автомат (ДКА) является специ-

альным случаем недетерминированного конечного автомата, в ко-

тором:

– отсутствуют состояния, имеющие лябмда-переходы;

– для каждого состояния s и входного символа а существует не

более одной дуги, выходящей из s и помеченной как а.

Для любого входного символа детерминированный конечный

автомат имеет не более одного перехода из каждого состояния. Ес-

ли для представления функции переходов ДКА используется таб-

лица, то каждая запись в ней представляет собой единственное со-

стояние. Следовательно, очень просто проверить, допускает ли

данный ДКА некоторую строку, поскольку имеется не более одного

пути от стартового состояния, помеченного этой строкой. Следую-

щий алгоритм имитирует поведение ДКА при обработке входной

строки.

Преобразования НКА

При построении лексического анализатора, над НКА необходи-

мо выполнить ряд преобразований.

Ситуации, в которых

функция переходов многозначна, делают моделирование НКА с

помощью компьютерной программы весьма сложной задачей. Оп-

ределение допустимости утверждает только, что должен существо-

вать некоторый путь, помеченный входной строкой и ведущий от

начального состояния к заключительному. Однако когда имеется

много путей для одной и той же входной строки, возможно, при-

дется рассматривать их все, чтобы найти путь к заключительному

состоянию или выяснить, что такого пути не существует.

Алгоритм преобразования НКА в ДКА, распознающий тот же

язык, что и НКА, является алгоритмом построения подмножеств и

может использоваться при моделировании НКА компьютерной

программой.

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

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

Компиляция состоит из двух основных частей: анализа и синтеза.

Анализ – это разбиение исходной программы на составные части

и создание ее промежуточного представления.

В процессе анализа определяются и записываются в иерархичес-

кую древовидную структуру операции, заданные исходной про-

граммой. Часто используется специальный вид дерева – синтакси-

ческое дерево, в котором каждый узел представляет операцию, а

его дочерние узлы – аргументы операции (операнды).

Синтез – это конструирование требуемой целевой программы из

промежуточного представления.

Процесс трансляции разбивается на несколько этапов, за выпол-

нение каждого из которых отвечает свой блок.

10

Основные фазы трансляции: лексический анализ, синтаксичес-

кий анализ, семантический анализ, синтез объектной программы.

Цели лексического анализа:

1) перевод исходной программы на внутренний язык компиля-

тора, в котором ключевые слова, идентификаторы, метки и кон-

станты приведены к одному формату и заменены условными кода-

ми: числовыми или символьными, которые называются дескрипто-

рами. Каждый дескриптор состоит из двух частей: класса-типа лек-

семы и указателя на адрес в памяти, где хранится информация о

конкретной лексеме. Эта информация организуется в виде таблиц;

2) лексический контроль – выявление в программе недопусти-

мых слов.

Цели синтаксического анализа:

1) перевод последовательности образов лексем в форму проме-

жуточной программы;

2) синтаксический контроль – выявление синтаксических оши-

бок в программе.

Грамматика G = (VT, VN, P, S) называется контекстно-свободной (КС), если каждое правило из Р имеет вид A -> бета, где A прин VN, бета прин (VT U VN)+.

Существует два способа определения языка грамматикой:

1. Последовательность правил вывода от стартового символа к предложению языка

2. Построение дерева разбора

Вывод цепочки бета прин (VT)* из S прин VN в КС-грамматике G = (VT, VN, P, S), называется левым (левосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого левого нетерминала.

Вывод цепочки бета прин (VT)* из S прин VN в КС-грамматике G = (VT, VN, P, S), называется правым (правосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого правого нетерминала.

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

Деревом вывода (или деревом разбора) называется конечный неориентированный граф, у которого:

- одна вершина (корень дерева) соответствует стартовому символу грамматики;

- каждый внутренний узел помечается нетерминалом А, дочерние узлы помечаются с лева-направо символами из правой части продукции, использованной в порождении для замены А;

- листья дерева помечены нетерминалами или терминалами и, будучи прочитанными слева-направо, образуют сентенциальную форму.

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

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

Грамматика – средство описания синтаксиса языка. Она определяет структуру цепочек и позволяет строить цепочки определенного языка. Автомат – модель алгоритма распознавания предложений языка. Этот специальный алгоритм позволяет по заданной цепочке определяет принадлежит ли она языку.

МП-автомат состоит из входной ленты, устройства управления и вспомогательной ленты, называемой магазином или стеком.

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

Головка входной ленты может перемещаться только вправо или оставаться на месте. Она может выполнять только чтение. Головка вспомогательной ленты способна выполнять как чтение, так и запись:

- при записи головка предварительно сдвигается на одну позицию вверх, а затем символ заносится на ленту,

- при чтении символ, находящийся под головкой считывается с ленты, а затем головка сдвигается на одну позицию вниз, т.о. головка всегда установлена против последнего записанного символа.

Позицию, находящуюся в рассматриваемый момент времени под головкой, называют вершиной магазина.

Магазинный автомат М определяется следующей совокупностью семи объектов: M={A, Q, Г, дельта, q0, z0, F},

, где A – конечное множество входных символов, Q – внутренних состояний, Г– магазинных символов, q0 – начальное выделенное состояние, z0 – начальный символ стека, F – множество заключительных состояний, дельта: (А x Q x Г) -> (Q x Г)*

Каждый такт работы включает операции:

1. Операции над магазином:

ВТОЛКНУТЬ (в стек определенный символ), ВЫТОЛКНУТЬ (неопределено, x = епсилан или А, x = AY), ОСТАВИТЬ содержимое стека без изменений

2. Операции над состоянием:

Перейти в заданное новое состояние СОСТОЯНИЕ (S), Остаться в прежнем ОСТАТЬСЯ

3. Операции над входом:

СДВИГ (перейти к следующему входному символу и сделать его текущим), ДЕРЖАТЬ (оставить данных входной символ текущим до следующего такта).

Конфигурация МП-автомата может быть записана в виде (состояние, входная последовательность, состояние стека) или в виде последовательности команд вида:

(q, a, z) -> { (q1, y1), (q2, y2), …, (qn, yn)}, где qi прин Q, z прин Г, yi прин Г*, a прин A

Если среди команд нет двух одинаковых, автомат называется детерминированным. В противном случае – недетерминированным и выбор команд осуществляется случайным образом. Если нет команды, которую можно было бы применить, автомат останавливается.

Недетерминированный конечный автомат (НКА) A = (Q, V, дельта,

q0, F) представляет собой математическую модель, состоящую:

– из множества состояний Q;

– из множества входных символов V (символов входного алфа-

вита);

– из функции переходов дельта, которая отображает пары символ –

состояние на множество состояний;

– из состояния q0, известного как стартовое (начальное);

– из множества состояний F, известных как допускающие (ко-

нечные).

НКА может использоваться в виде помеченного ориентирован-

ного графа, так называемого графа переходов, узлы которого пред-

ставляют собой состояния, а помеченные дуги составляют функ-

цию переходов. Такой граф похож на диаграмму переходов, однако

один и тот же символ может помечать два и более переходов из од-

ного состояния, а некоторые переходы могут быть помечены спе-

циальным символом e, как обычным входным символом (e-

переходы).

Детерминированный конечный автомат (ДКА) является специ-

альным случаем недетерминированного конечного автомата, в ко-

тором:

– отсутствуют состояния, имеющие лямбда-переходы;

– для каждого состояния s и входного символа а существует не

более одной дуги, выходящей из s и помеченной как а.

Для любого входного символа детерминированный конечный

автомат имеет не более одного перехода из каждого состояния. Ес-

ли для представления функции переходов ДКА используется таб-

лица, то каждая запись в ней представляет собой единственное со-

стояние. Следовательно, очень просто проверить, допускает ли

данный ДКА некоторую строку, поскольку имеется не более одного

пути от стартового состояния, помеченного этой строкой. Следую-

щий алгоритм имитирует поведение ДКА при обработке входной

строки.

Ситуации, в которых

функция переходов многозначна, делают моделирование НКА с

помощью компьютерной программы весьма сложной задачей. Оп-

ределение допустимости утверждает только, что должен существо-

вать некоторый путь, помеченный входной строкой и ведущий от

начального состояния к заключительному. Однако когда имеется

много путей для одной и той же входной строки, возможно, при-

дется рассматривать их все, чтобы найти путь к заключительному

состоянию или выяснить, что такого пути не существует.

Алгоритм преобразования НКА в ДКА, распознающий тот же

язык, что и НКА, является алгоритмом построения подмножеств и

может использоваться при моделировании НКА компьютерной

программой.

68. Общие алгоритмы синтаксического анализа: методы восходящего синтаксического анализа, табличные методы синтаксического анализа, формальное определение алгоритма разбора типа "перенос-сверт­ка", грамматики простого и операторного предшествова­ния, понятие отношений «<∙ , ∙>, ∙ = » между символами грамматики, особенности построения таблиц разбора, сравнительный анализ класса грамматик предшествования с другими классами грамматик.

Основной метод восходящего синтаксического анализа – син-

таксический анализ типа «перенос/свертка» (ПС-анализ). В процес-

се ПС-анализа дерево разбора для входной строки строится начи-

ная с листа (снизу) и работает по направлению к корню дерева

(вверх). Этот процесс можно рассматривать как свертку строки w к

стартовому символу грамматики. На каждом шаге свертки некоторая подстрока, соответствующая правой части продукции, заменя-

ется символом из левой части этой продукции, и если на каждом

шаге подстроки выбираются корректно, то получается обращенное

правое порождение.

Понятие основы строки

Основа строки – это подстрока, которая совпадает с правой ча-

стью продукции и свертка которой в левую часть продукции пред-

ставляет собой один шаг обращенного правого порождения.

Во многих случаях крайняя слева подстрока бета, соответствующая

правой части некоторой продукции A, не является основой, по-

скольку свертка в соответствии с продукцией A -> бета приводит к

строке, которая не может быть свернута к стартовому символу. Ес-

ли в примере 18 заменить во второй строке aAbcde символ b нетер-

миналом А, то получим строку aAAcde, которая не может быть

свернута в S. Поэтому определение основы должно быть более точ-

ное.

Основа правосентенциальной формы y является продукцией

A -> и позицией строки бета в y, такими, что бета может быть заменена

нетерминалом А для получения предыдущей правосентенциальной

формы в правом порождении y. Таким образом, если S=>альфаAw =>

альфабетаw, то A -> бета в позиции после а представляет собой основу строки

aбетаw. Строка w справа от основы содержит только терминальные

символы. Если грамматика однозначна, то каждая правосентенци-

альная форма грамматики имеет ровно одну основу.

Стековая реализация ПС-анализа

Существует две проблемы при синтаксическом анализе методом

ПС-анализа. Первая заключается в обнаружении подстроки для

свертки в правосентенциальной форме, вторая – в определении, ка-

кая именно продукция должна быть выбрана, если имеется не-

сколько продукций с соответствующей подстрокой в правой части.

Достаточно удобный путь реализации ПС-анализатора состоит в

использовании стека для хранения символов грамматики и входно-

111

го буфера для хранения анализируемой строки. В качестве маркера

дна стека используется $, и этот же символ является маркером пра-

вого конца входной строки. Изначально стек пуст, а входной буфер

содержит строку w$:

Стек Вход

$ w$

Синтаксический анализатор работает путем переноса нуля или

нескольких символов в стек до тех пор, пока на вершине стека не

окажется основа бета. Затем он свертывает бета левой части соответст-

вующей продукции. Синтаксический анализатор повторяет этот

цикл, пока не будет обнаружена ошибка или он не придет в конфи-

гурацию, когда в стеке находится только стартовый символ, а вход-

ной буфер пуст:

Стек Вход

$S $

Попав в эту конфигурацию, синтаксический анализатор прекра-

щает работу и сообщает об успешном разборе входной строки.

Основными операциями синтаксического анализатора являются

перенос и свертка, но на самом деле ПС-анализатор может выпол-

нять четыре действия: (1) перенос, (2) свертка, (3) допуск, (4)

ошибка.

1. При переносе очередной входной символ переносится на

вершину стека.

2. При свертке синтаксический анализатор распознает правый

конец основы на вершине стека, после чего он должен найти левый

конец основы и принять решение о том, каким нетерминалом заме-

нить основу.

3. При допуске синтаксический анализатор сообщает об успеш-

ном разборе входной строки.

4. При ошибке синтаксический анализатор обнаруживает ошиб-

ку во входном потоке и вызывает программу восстановления после

ошибок.

З аме ч ание . Синтаксический анализатор для получения оче-

редной основы переносит нуль или несколько символов в стек.

Синтаксический анализатор никогда не заглядывает внутрь стека

в поисках правого края основы. Все это делает стек особенно удоб-

ным для использования в реализации ПС-анализатора.

Синтаксический анализ приоритета операторов

Принцип организации распознавателя входных цепочек языка,

заданного грамматикой предшествования, основан на том, что для

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

ется некоторое отношение, называемое отношением приоритетов.

В процессе разбора входной строки расширенный МП-автомат

сравнивает текущий символ входной цепочки с одним из символов,

находящихся на вершине стека автомата. В процессе сравнения

проверяется, какое из возможных отношений приоритетов сущест-

вует между этими двумя символами. В зависимости от найденного

отношения, выполняется либо перенос, либо свертка. При отсутст-

вии отношения приоритетов между символами алгоритм сигнали-

зирует об ошибке.

Задача состоит в том, чтобы определить эти отношения предше-

ствования между символами грамматики. При этом грамматика

может быть отнесена к одному из классов грамматик предшество-

вания (простого предшествования, расширенного предшествования,

слабого предшествования и т.д.).

Основное понятие, которое используется в грамматиках пред-

шествования, – отношение предшествования.

Пусть имеется КС-грамматика и на некотором шаге вывода по-

лучена сентенциальная форма вида E* Ei Ej E*. Символы Ei Ej стоят

рядом в сентенциальной форме. Соседство этих символов характе-

ризуется одним из отношений специального вида – отношением

предшествования.

1. Между символами Ei и Ej существует отношение Ei Ej, если

в грамматике есть правило вида A → альфа Еi Еj бета, где альфа, бета принадлежат

алфавиту V*.

2. Между символами Ei и Ej существует отношение Ei <• Ej, если в

грамматике есть правило вида A → α ξi В β и вывод вида В > Ej Y,

где α, β, γ принадлежат алфавиту V *.

3. Между символами Ei и Ej существует отношение Ei •> Ej, если в

грамматике есть правило вида A → α ВС β и выводы вида В y1 Ej

и С Ej y2 или правило вывода вида A → альфа В Ej бета и вывод В y Ei ,

где альфа, бета, y1, y2 , y принадлежат алфавиту V*.

Тип отношения предшествования показывает, что если:

Ei Ej, то оба символа принадлежат одной основе;

Ei <• Ej, то Ej – самый левый символ некоторой основы;

Ei •> Ej, то Ei – самый правый символ некоторой основы.

Если между символами Ei и Ej выполняется не более одного от-

ношения предшествования, то можно выделить основу для выпол-

нения свертки.

Грамматики простого предшествования

КС-грамматика является грамматикой простого предшествова-

ния, если она однозначна, не содержит ε-продукций и для любой

пары ее символов (терминальных и нетерминальных) выполняется

не более одного отношения предшествования.

Отношение предшествования единственно для каждой упорядо-

ченной пары символов. При этом между какими-либо двумя симво-

лами может и не быть отношения предшествования – это значит,

что они не могут находиться рядом в одном элементе разбора син-

таксически правильной цепочки.

Отношения предшествования зависят от порядка, в котором сто-

ят символы.

7.4.2. Грамматики операторного предшествования

Грамматики, у которых нет продукций, правые части которых

представляют собой или имеют два соседних нетерминала, назы-

ваются операторными.

Пр име р 23. Следующая грамматика для выражений

E → ЕАЕ | (E) | –E | id

А → + | - | * | / | ↑

не является операторной, поскольку правая часть ЕАЕ имеет два (на самом

деле – даже три) последовательных нетерминала. Однако если заменим А каж-

дой из его альтернатив, то получим операторную грамматику

E→ E + E | E – E | E * E | E/E | E↑E | (E) | – E| id

При синтаксическом анализе приоритета операторов определя-

ются три непересекающихся отношения приоритетов – <•, и •> –

между терминалами.

– правый, а находится внутри основы. Предположим, что есть

правосентенциальная форма операторной грамматики. Из того, что

у продукции не может быть двух смежных нетерминалов в правой

части, следует, что и правосентенциальная форма не может иметь

двух смежных нетерминалов. Таким образом, правосентенциаль-

ную форму можно записать в виде β0 a1 β1...an βn, где каждое β явля-

ется либо пустой строкой, либо одиночным нетерминалом, а каж-

дое а представляет собой одиночный терминал.

Предположим, что между аi и аi+1 выполняется ровно одно от-

ношение – •>, <•, . Используем для маркировки концов строки

символ $ и определим, что $ <• b для всех терминалов b. Теперь

предположим, что из строки удалили нетерминалы и поместили

одно из отношений •>, <• или между каждой парой терминалов и

между крайними терминалами и маркерами $. В правосентенци-

альной форме id + id * id отношения приоритетов показаны в табл.

14 (эти отношения выбраны при рассмотрении грамматики из при-

мера 22).

69. Общие алгоритмы синтаксического анализа: нисходящие методы синтаксического анализа, метод рекурсивного спуска, предиктивный синтаксический анализатор, определение LL(k)-грамматики, алгоритм раз­бора для LL(1)-грамматик, алгоритм построения управляющей таблицы для LL(1)-грамматики, сравнительный анализ нисходящих методов синтаксического анализа.

Нисходящий разбор можно рассматривать как попытку найти левое порождение входной строки или как попытку построить дерево разбора для входной строки, начиная с корня и создавая вершины в прямом порядке.

1. Корень – стартовый символ

2. в узле n, помеченном нетерминалом А, выбирается одна из продукций для А и строятся дочерние узлы для символов из правой части продукции

3. находится следующий узел, в котором должно быть построено поддерево.

Задача разбора состоит в том, чтобы построить оставшуюся часть дерева т.о., чтобы строка, порожденная деревом разбора, совпала с входной строкой.

Методы: с возвратами и без возвратов. (Рекурсивный, предиктивный, LL)

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

Метод рекурсивного спуска (РС-метод) реализует построение дерева разбора практически "в лоб": для каждого нетерминала грамматики создается своя процедура, носящая его имя; ее задача – начиная с указанного места исходной цепочки найти подцепочку, которая выводится из этого нетерминала. Если такую подцепочку считать не удается, то процедура завершает свою работу вызовом ошибки. В случае использования метода возвратов процедура разбора ищет первое правило, которое начинается с нужного терминала. Продукции, начинающиеся с одного терминального символа, применяются по порядку. Если правило не подходит, то возврат на предыдущий шаг.

Тело каждой такой процедуры пишется непосредственно по правилам вывода соответствующего нетерминала: для правой части каждого правила осуществляется поиск подцепочки, выводимой из этой правой части. При этом терминалы распознаются самой процедурой, а нетерминалы соответствуют вызовам процедур, носящих их имена.

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

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

Название LL произошло от слова Left, поскольку анализатор просматривает входную цепочку слева-направо , и слова Leftmost, поскольку он обнаруживает появление правила по одному или группе символов, образующих левый край цепочки.

На практике наибольшее применение имеет класс LL(1) грамматик, для которых детерминированный распознаватель работает по одному входному символу, расположенному в текущей позиции. Входной буфер содержит анализируемую строку с маркером ее правого конца ($). Стек содержит последовательность символов грамматики, дно стека обозначается специальным символом. Изначально в стеке только стартовый символ, расположенный за символом дна. Таблица разбора M представляет собой двумерный массив M [A, a], где А – нетерминал, а – терминал или $.

Программа просматривает символ на вершине стека х и некоторый входной символ а.

1. если х = а = $, СА завершает работу и сообщает об успешном разборе строки

2. если х = а не= $, СА считывает со стека х и переходит к следующему символу

3. если Х – нетерминал, программа смотрит запись в таблице разбора M [X, a], которая может продукцией или ошибкой.

Если в таблице содержится продукция Х -> RTY, то СА замещает х на вершине стека на правую часть продукции.

В случае правильного разбора на входе мы получим левое порождение входной цепочки.

Нужно построить два множества: First и Follow.

Построение множества First:

1. если х – терминал, First (х) = {х}

2. если имеется продукция Х -> епсилан, то епсилан добавляется к множеству First (Х)

3. если Х – нетерминал и имеется продукция Х -> Y1, Y2, Yk, то а прин First (Yi) и епсилан входит во все множества. Если епсилан имеется во всех множествах First (Y1)…First (Yk) то епсилан добавляется в First (Х).

Построение множества Follow:

1. помещаем епсилан во множество, где S – стартовый символ грамматики

2. если есть продукция А -> альфаВбета, все элементы множества First (бета), кроме епсилан, помещаются в Follow (В)

3. если есть продукция А -> альфаВ или А -> альфаВебта, где First (бета) содержит епсилан, все элементы множества Follow (А) помещаются в множество Follow (В).

Алгоритм заполнения таблицы:

1. для каждого терминала а из First (А) добавляем продукцию А -> альфа в ячейку M [A, a]

2. если в First (А) входит есилан, для терминала а из Follow (А) добавляем продукцию А -> альфа в ячейку M [A, a];

если епсилан входит в First (А), символ $ в Follow (А), добавляем продукцию А -> альфа в ячейку M [A, $]

3. каждая неопределенная ячейка – ошибка.

70. Общие алгоритмы синтаксического анализа: методы восходящего синтаксического анализа, табличные методы синтаксического анализа, формальное определение алгоритма разбора типа "перенос-сверт­ка", определение LR(k)-грамматики, алгоритм раз­бора для LR(k)-грамматик, алгоритм построения управляющей таблицы, преимущества класса LR(k)-грамматик перед другими методами синтаксического анализа.

Восходящий синтаксический анализ СА (свёртка) – дерево разбора строится от листьев к корню.

SLR(1) и LALR(1) грамматики. В основе этих двух методов лежит одна и та же идея.

В SLR(1) грамматиках (Simple LR(1) - простых LR(1)-грамматиках) для разрешения конфликтов используется множество FOLLOW(X)- множество терминалов, встречающихся после X. Если в состоянии имеется ситуация A:b_, свертка допускается, если только аванцепочка принадлежит FOLLOW(A).

Грамматика является SLR(1)-грамматикой, если для двух любых LR(0) ситуаций из одного состояния A:a_b и B:c_d выполняется одно из следующих условий:

- b!=e, d!=e (конфликта нет, требуется сдвиг);

- b=d=e и FOLLOW(A) не пересекается с FOLLOW(B) (конфликт "свертка/свертка" может быть устранен с учетом аванцепочки);

- b=e, d<>e и FOLLOW(A) не пересекается с EFF(tFOLLOW(B))(конфликт "сдвиг/свертка" может быть устранен с учетом аванцепочки).

LALR(1)-метод (Look Ahead - заглядывание вперед) заключается в следущем. Введем на множестве LR(1)-ситуаций отношение эквивалентности: будем считать две ситуации эквивалентными, если они различаются только аванцепочками. Например, ситуации A:Aa_Ab|e и A:Aa_Ab|a эквивалентны. Построим каноническое множество LR(1)-состояний и объединим состояния, состоящие из множества эквивалентных ситуаций.

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

Алгоритм функционирования распознавателя LR(k)-грамматики:

1) Прочитать с вершины стека строку управляющей таблицы. Выбрать из этой строки часть Action в соответствии с аванцепочкой. Перейти к шагу 2.

2) В соответствии с типом действия выполнить выбор:

• сдвиг- если входная цепочка не прочитана до конца, прочитать и запомнить как «новый символ» очередной символ из входной цепочки, сдвинуть считывающую головку на одну позицию вправо, иначе прервать выполнение алгоритма и ошибка;

• свертка – выбрать правило в соответствии с номером, удалить из стека цепочку символов, составляющую правую часть выбранного правила, взять символ из левой части правила и запомнить его как «новый символ»;

• ошибка – прервать выполнение алгоритма;

• успех – выполнить свертку к целевому символу S. Прервать выполнение алгоритма, сообщить о разборе, если входная цепочка прочитана до конца, иначе ошибка.

Перейти к 3 шагу.

3) Прочитать с вершины стека строку управляющей таблицы. Выбрать из этой строки часть Goto в соответствии с символом, который был запомнен как «новый символ» на предыдущем шаге. Перейти к шагу 4.

4) Если часть Goto содержит ошибку, тогда прервать и ошибка, иначе положить в стек «новый символ» и строку управляющей таблицы с выбранным номером. Перейти к шагу 1.

Алгоритм построения управляющей LR(1)-таблицы:

Вход. Каноническая система C = {I0, I1, ..., In} множеств допустимых LR(1)-ситуаций для грамматики G.

Выход. Функции Action и Goto, составляющие LR(1)-таблицу для грамматики G.

Метод. Для каждого состояния i функции Action[i, a] и Goto[i, X] строятся по множеству ситуаций Ii:

• Значения функции действия (Action) для состояния i определяются следующим образом:

o если [A ->альфа.a бета , b] прин. Ii (a - терминал) и goto(Ii, a) = Ij, то полагаем Action[i, a] = shift j;

o если [A альфа.,a] прин Ii, причем A не= S', то полагаем Action[i, a] = reduce A -> альфа ;

o если [S' -> S., $] прин Ii, то полагаем Action[i, $] = accept.

• Значения функции переходов для состояния i определяются следующим образом: если goto(Ii, A) = Ij, то Goto[i, A] = j (здесь A - нетерминал).

• Все входы в Action и Goto, не определенные шагами 2 и 3, полагаем равными error.

• Начальное состояние анализатора строится из множества, содержащего ситуацию [S' ->.S, $].

Пусть G = (N, T, P, S) - КС-грамматика. Пополненной грамматикой для данной грамматики G называется КС-грамматика G'=(N U {S'}, T, P u {S' -> S}, S'),

т.е. эквивалентная грамматика, в которой введен новый начальный символ S' и новое правило вывода S'-> S (для того, чтобы определить, когда анализатор должен остановить разбор и зафиксировать допуск входа). Допуск тогда и только тогда, когда анализатор готов осуществить свертку по правилу S'->S.

В процессе разбора снизу-вверх типа сдвиг-свертка (перенос-свертка) строится дерево разбора входной цепочки, начиная с листьев (снизу) к корню (вверх). Этот процесс можно рассматривать как «свертку» цепочки w к начальному символу грамматики. На каждом шаге свертки подцепочка, которую можно сопоставить правой части некоторого правила вывода, заменяется символом левой части этого правила вывода, и если на каждом шаге выбирается правильная подцепочка.

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

Грамматика однозначна, если каждая правая сентенциальная форма грамматики имеет в точности одну основу. Замена основы в сентенциальной форме на нетерминал левой части называется отсечением основы.

Грамматикой простого предшествования называют такую КС-грамматику G(VN,VT,P,S), V=VT U VN в которой:

1. Для каждой упорядоченной пары терминальных и нетерминальных символов выполняется не более чем одно из трех отношений предшествования:

• Si = Sj (для всех Si,Sj прин. V), если и только если сущ. правило U->xSiSjy прин. P, где U прин. VN, x,y прин.V*;

• Si < Sj (для всех Si,Sj прин.V), если и только если сущ. правило U->xSiDy прин P и вывод D->*Sjz, где U,D прин. VN, x,y,z прин. V*;

• Si > Sj (для всех Si,Sj прин. V) , если и только если сущ. правило U->xCSjy прин P и вывод C->*zSi или сущ правило U->xCDy прин. P и выводы C->*zSi и D->*Sjw, где U,C,D прин. VN, x,y,z,w прин. V*.

2. Различные порождающие правила имеют разные правые части.

Отношения =, < и > называют отношениями предшествования для символов. Отношение предшествования единственно для каждой упорядоченной пары символов. При этом между какими-либо двумя символами может и не быть отношения предшествования - это значит, что они не могут находиться рядом ни в одном элементе разбора синтаксически правильной цепочки. Отношения предшествования зависят от порядка, в котором стоят символы.

Метод предшествования основан на том факте, что отношения предшествования между двумя соседними символами распознаваемой строки соответствуют трем следующим вариантам:

• Si < Si+1, если символ Si+1 - крайний левый символ некоторой основы;

• Si > Si+1 , если символ Si - крайний правый символ некоторой основы;

• Si = Si+1 , если символы Si и Si+1 принадлежат одной основе.

Исходя из этих соотношений выполняется разбор строки для грамматики предшествования.

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

Матрицу предшествования грамматики можно построить, опираясь непосредственно на определения отношений предшествования, но удобнее воспользоваться двумя дополнительными множествами - множеством крайних левых и множеством крайних правых символов относительно нетерминалов грамматики. Эти множества определяются следующим образом:

• L(U) = {T | сущ U->*Tz}, U,T прин V, z прин V* - множество крайних левых символов относительно нетерминального символа U (цепочка z может быть и пустой цепочкой);

• R(U) = {T | сущ U->*zT}, U,T прин V, z прин V* - множество крайних правых символов относительно нетерминального символа U.

Тогда отношения предшествования можно определить так:

• Si = Sj (для всех Si,Sj прин. V), если сущ правило U -> xSiSjy прин. P, где U прин. VN, x,y прин. V*;

• Si < Sj (для всех Si,Sj прин. V), если сущ правило U->xSiDy прин.P и Sj прин. L(D), где U,D прин. VN, x,y прин. V*;

• Si > Sj (для всех Si,Sj прин V) , если сущ правило U->xCSjy прин.P и Si прин R(C) или сущ правило U->xCDy прин. P и Si прин R(C), Sj прин L(D), где U,C,D прин VN, x,y прин V*.

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

Отношения предшествования для грамматики операторного предшествования G(VN,VT,P,S) задаются следующим образом:

•a = b, если и только если существует правило U->xaby прин P или правило U->xaCby, где a,b прин VT, U,C прин VN, x,y принV*;

•a < b, если и только если существует правило U->xaCy принP и вывод C->*bz или вывод C->*Dbz, где a,b прин VT, U,C,D прин VN, x,y,z прин V*;

•a > b, если и только если существует правило U->xCby принP и вывод C->*za или вывод C->*zaD, где a,b принVT, U,C,D прин VN, x,y,z принV*.

В грамматике операторного предшествования различные порождающие правила имеют разные правые части. Для грамматики операторного предшествования тоже строится матрица предшествования, но она содержит только терминальные символы грамматики.

Для построения этой матрицы удобно ввести множества крайних левых и крайних правых терминальных символов относительно нетерминального символа U - Lt(U) или Rt(U):

•Lt(U) = {t | сущ U->*tz или сущ U->*Ctz }, где t прин VT, U,C прин VN, z прин V*;

•Rt(U) = {t | сущ U->*zt или сущ U->*ztC }, где t прин VT, U,C прин VN, z прин V*.

Тогда определения отношений операторного предшествования будут выглядеть так:

•a = b, если сущ правило U->xaby прин P или правило U->xaCby, где a,b прин VT, U,C прин VN, x,y прин V*;

•a < b, если сущ правило U->xaCy прин P и b прин Lt(C), где a,b прин VT, U,C прин VN, x,y прин V*;

•a > b, если сущ правило U->xCby прин P и a прин Rt(C), где a,b прин VT, U,C прин VN, x,y прин V*.

В данных определениях цепочки символов x,y,z могут быть и пустыми цепочками.

71. Общие принципы генерации кода: формальные методы описания перевода, внутренние формы программы: польская инверсная запись, представление основных конструкций языков программирования в польской инверсной записи, тетрады, триады, представление основных конструкций языков программирования с использованием тетрад и триад, косвенные триады, синтаксические деревья, ассемблерный код, особенности всех форм представления, их сравнительный анализ.

Общие принципы генерации кода

Генерация объектного кода – это перевод компилятором внут-

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

выходного языка. Генерация объектного кода порождает результи-

рующую объектную программу на языке машинных команд. Внут-

реннее представление программы может иметь любую структуру в

зависимости от реализации компилятора, в то время как результи-

рующая программа всегда представляет собой линейную последо-

вательность команд. Поэтому генерация объектного кода (объект-

ной программы) в любом случае должна выполнять действия, свя-

занные с преобразованием сложных синтаксических структур в ли-

нейные цепочки.

Генерация объектного кода выполняется после того, как выпол-

нен синтаксический анализ программы и все необходимые дейст-

вия по подготовке к генерации кода: распределено адресное про-

странство под функции и переменные, проверено соответствие

имен и типов переменных, констант.

В идеале компилятор должен выполнить синтаксический разбор

всей входной программы, затем выполнить семантический анализ,

после чего приступить к подготовке генерации и непосредственно к

генерации кода. Однако такая схема работы компилятора практичес-

ки почти никогда не применяется. В общем случае ни один семан-

тический анализатор и ни один компилятор не способны проанали-

зировать и оценить смысл всей входной программы в целом. Фор-

мальные методы анализа семантики применимы только к очень не-

значительной части возможных программ. Поэтому у компилятора

нет практической возможности порождать эквивалентную выход-

ную программу на основании всей входной программы.

Как правило, компилятор выполняет генерацию результирую-

щего кода поэтапно, на основе законченных синтаксических конст-

рукций входной программы:

1) выделяет законченную синтаксическую конструкцию из тек-

ста входной программы;

2) порождает для нее фрагмент результирующего кода и поме-

щает его в текст выходной программы;

3) переходит к следующей синтаксической конструкции.

Так продолжается до тех пор, пока не будет разобрана вся вход-

ная программа. В качестве анализируемых законченных синтакси-

ческих конструкций выступают операторы, блоки операторов, опи-

сания процедур и функций. Их конкретный состав зависит от вход-

ного языка и реализации компилятора.

Смысл (семантику) каждой такой синтаксической конструкции

входного языка можно определить, исходя из ее типа, а тип опреде-

ляется синтаксическим анализатором на основании грамматики

входного языка. Примерами типов синтаксических конструкций

могут служить операторы цикла, условные операторы, операторы

выбора и т.д. Одни и те же типы синтаксических конструкций ха-

рактерны для различных языков программирования, при этом они

различаются синтаксисом (который задается грамматикой языка),

но имеют сложный смысл (который определяется семантикой). В

зависимости от типа синтаксической конструкции выполняется ге-

нерация кода результирующей программы, соответствующего дан-

ной синтаксической конструкции. Для семантически схожих конст-

рукций различных входных языков может порождаться типовой ре-

зультирующий код.

Внутреннее представление программы

Результатом работы распознавателя КС-грамматики – входного

языка является последовательность правил грамматики, применен-

ных для построения входной цепочки. Зная тип распознавателя по

найденной последовательности, можно построить цепочку вывода

или дерево вывода. В этом случае дерево вывода выступает в каче-

стве дерева синтаксического разбора и представляет собой резуль-

тат работы синтаксического анализатора в компиляторе.

141

Однако ни цепочка вывода, ни дерево синтаксического разбора

не являются целью работы компилятора. Дерево вывода содержит

массу избыточной информации, которая для дальнейшей работы

компилятора не требуется. Эта информация включает в себя все не-

терминальные символы, содержащиеся в узлах дерева, – после того

как дерево построено, они не несут никакой смысловой нагрузки и

не представляют интереса для дальнейшей работы.

Для полного представления о типе и структуре найденной и ра-

зобранной синтаксической конструкции входного языка в принципе

достаточно знать последовательность номеров правил грамматики,

примененных для ее построения. Однако форма представления этой

информации может быть различной в зависимости от реализации

самого компилятора и от фазы компиляции. Эта форма называется

внутренним представлением программы (иногда используются так-

же термины «промежуточное представление» или «промежуточная

программа»).

Формы представления программы, используемые на этапе синтаксического анализа неудобны при генерации и оптимизации объектного кода, поэтому непосредственно перед этими этапами внутреннее представление может преобразовываться в одну или несколько (!!!) других форм записи(которые перечислены в формулировке вопроса).

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

Обратная (инверсная) польская запись: (Я. Лукашевич – математик). Идея: знаки операций записываются непосредственно за операндами(т.е. постфиксная), операнды следуют в том же порядке, что и в инфиксной, а знаки операций- строго в порядке выполнения.

Все операции выполняются в том порядке, в котором записаны -> удобно для реализации на ЭВМ. Нет скобок и не нужно вычислять приоритет операций. Очень эффективна при использовании стека.

Главный недостаток: используется стек -> для работы доступна только верхушка стека -> почти не поддается оптимизации.

Тетрады (многоадресный код с явно именуемым результатом): представляют собой запись из 4 составляющих – операция, 2 операнда и результат операции. Например, так: <Операция> (<Операнд1>, <Операнд2>, <Результат>). При вычислении выражения, записанного в форме тетрад, команды вычисляются одна за другой (последовательно, линейно). Если операция унарная – то одного из операндов может не быть (в зависимости от принятой формы записи). Результат вычисления никогда опущен быть не может (иначе тетрада теряет смысл).

Достоинства: линейное выполнение – простой алгоритм реализации (в отл. от синт. деревьев). Не зависят от арх-ры ЭВМ (в отл-е от ассемблера).

Недостатки: требуют больше памяти (чем триады), явно не отображают связь между операциями, сложны для преобразования в машинный код (в совр. машинах редко встречаются 3-операндные команды).

Пример: A:=B*C+D-B*10 1. *(B,C,T1) 2. +(T1,D,T2) 3. *(B.10,T3) 4. –(T2,T3,T4) 5. :=(T4,0,A)

в 5-й тетраде в качестве второго операнда выступает незначащий операнд «0».

Триады: вместо результата, в качестве операнда может использоваться ссылка на другую триаду (поэтому их обычно нумеруют). Последовательность – линейная. Результат триады сохраняется во временной памяти – для использования последующими триадами(косвенные триады).

Достоинства: дост-ва тетрад + проще реализовать в машинный код (ближе к 2-адресным машинным командам). Требуют меньше памяти для хранения.

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

Пример: (см. выше) 1. *(B,C) 2. +(^1,D) 3. *(B,10) 4. -(^2,^3) 5. :=(A,^4)

72. Атрибутные транслирующие грамматики: синтаксически управляемые определения и схемы трансляции как способы записи семантических правил, связанных с продукциями грамматик, понятие атрибута, синтезируемые и наследуемые атрибуты, вычисление значений атрибутов, L-атрибутные и S-атрибутные транслирующие грамматики, реализация атрибутного перевода.

СИНТАКСИЧЕСКИ УПРАВЛЯЕМАЯ ТРАНСЛЯЦИЯ

Для трансляции конструкций языка программирования компи-

лятору, помимо генерации кода, может потребоваться отследить

множество различных параметров. Например, компилятору может понадобиться информация о типе конструкции, о расположении

первой инструкции в целевом коде или количестве сгенерирован-

ных инструкций. Таким образом, можно говорить о некоторых аб-

страктных атрибутах, связанных с языковыми конструкциями: ти-

пах, строках, адресах памяти.

Значения атрибутов вычисляются согласно семантическим пра-

вилам, связанным с продукциями грамматики.

Существует два вида записи для связанных с продукциями се-

мантических правил:

1) синтаксически управляемые определения – представляют со-

бой высокоуровневые спецификации трансляции, скрывающие

множество деталей реализации и освобождающие пользователя от

явного указания порядка выполнения трансляции;

2) схемы трансляции – указывают порядок, в котором выполня-

ются семантические правила; так что эти схемы показывают опре-

деленную часть деталей реализации.

Концептуально при обоих методах разбирается входной поток

лексем, строится дерево разбора и обходится так, как необходимо

для выполнения семантических правил в узлах дерева разбора

(рис. 29). Выполнение семантических правил может генерировать

код, сохранять информацию в таблице символов, выводить сооб-

щения об ошибках или выполнять какие-либо другие действия. Ре-

зультат трансляции потока лексем будет получен путем выполне-

ния указанных семантических правил.

Концепция синтаксически управляемой трансляции

Входная строка -> Дерево разбора -> Граф зависимости -> Порядок выполнения

семантических правил

Реализация не всегда следует приведенной на рис. 29 схеме. Ча-

стные случаи синтаксически управляемых определений могут быть

реализованы за один проход выполнением семантических правил в

процессе синтаксического анализа, без явного построения дерева

разбора или графа, показывающего взаимосвязи между атрибутами.

Например, подкласс СУ-определений, именуемый L-атрибутными

определениями, включает практически все этапы трансляции, кото-

рые могут выполняться без явного построения дерева разбора.

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

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

обобщение контекстно-свободной грамматики, в которой каждый

грамматический символ имеет связанное множество атрибутов –

синтезируемые и наследуемые атрибуты. Если рассматривать узел

грамматического символа в дереве разбора как запись с полями для

хранения информации, то атрибут соответствует имени поля.

Атрибут может представлять собой все, что угодно: строку, чис-

ло, тип, адрес памяти и т.д. Значение атрибута в узле дерева разбо-

ра определяется семантическими правилами, связанными с исполь-

зуемой в данном узле продукцией.

Значение синтезируемого атрибута в узле вычисляется по зна-

чениям атрибутов в дочерних по отношению к данному узлах.

Значения наследуемых атрибутов определяются значениями ат-

рибутов соседних (т.е. узлов, дочерних по отношению к родитель-

скому узлу данного) и родительского узлов.

Семантические правила определяют зависимости между атрибу-

тами, которые представляются графом. Граф зависимости опреде-

ляет порядок выполнения семантических правил, что, в свою оче-

редь, дает значения атрибутов в узлах дерева разбора входной стро-

ки. Семантические правила могут иметь и побочные действия, на-

пример вывод значения или изменение глобальной переменной. Ес-

тественно, при реализации не обязательно явным образом строить

дерево разбора или граф зависимостей; главное, чтобы для каждой

входной строки выполнялись верные действия в правильном по-

рядке.

Дерево разбора, показывающее значения атрибутов в каждом

узле, называется аннотированным, а процесс вычисления значений

атрибутов в узлах дерева – аннотированием дерева разбора.

Вид синтаксически управляемого определения

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

грамматики А -> альфа имеет связанное с ней множество семантичес-

ких правил вида

b: = f(с1, с2, …, сk),

где f – функция: с1, с2, …, сk – атрибуты грамматических символов

продукции; b – синтезируемый атрибут символа А или наследуе-

мый атрибут одного из грамматических символов правой части

продукции.

В любом случае атрибут b зависит от атрибутов с1, с2, …, сk.

Атрибутная грамматика является синтаксически управляемым

определением, в котором функции в семантических правилах не

имеют побочных эффектов.

Функции в семантических правилах зачастую записываются как

выражения. Иногда единственная цель семантического правила в

синтаксически управляемом определении состоит именно в созда-

нии побочного эффекта. Такие семантические правила записывают-

ся как вызовы процедур или фрагменты программ. Их можно рас-

сматривать как правила, определяющие значения фиктивных син-

тезируемых атрибутов нетерминала в левой части связанной про-

дукции; фиктивный атрибут и знак присвоения «: =» при этом не

указываются.

Пр име р 30. В табл. 25 приведено синтаксически управляемое определе-

ние программы настольного калькулятора. Это определение связывает с каж-

дым из нетерминалов Е, T и F целочисленный синтезируемый атрибут vаl.

Для каждой Е-, Т- и F-продукции семантическое правило вычисляет значение

атрибута val нетерминала из левой части продукции по значениям атрибутов

нетерминалов правой части.

Синтезируемые атрибуты

Синтезируемые атрибуты часто используются на практике.

S-атрибутным определением называется синтаксически управ-

ляемое определение, использующее только синтезируемые атрибуты.

Дерево разбора для S-атрибутного определения всегда может

быть аннотировано путем выполнения семантических правил для

атрибутов в каждом узле снизу вверх, от листьев к корню.

Наследуемые атрибуты

Наследуемые атрибуты представляют собой атрибуты, значе-

ния которых в узле дерева разбора определяются атрибутами роди-

тельского и/или дочерних по отношению к родительскому узлов.

Наследуемые атрибуты удобны для выражения зависимости

конструкций языка программирования от контекста, в котором они

появляются. Например, наследуемые атрибуты используются для

отслеживания, появляется ли идентификатор слева или справа от

знака присвоения, чтобы определить, потребуется ли адрес или

значение данного идентификатора. Хотя всегда можно переписать

синтаксически управляемое определение таким образом, чтобы ис-

пользовать только синтезируемые атрибуты, зачастую более есте-

ственно воспользоваться синтаксически управляемым определени-

ем с наследуемыми атрибутами.

Восходящее выполнение S-атрибутных определений

Для определения трансляций можно использовать синтаксичес-

ки управляемые определения. Рассмотрим реализацию таких

трансляторов. Создание транслятора для произвольного синтакси-

чески управляемого определения может оказаться сложной зада-

чей; однако имеются большие классы полезных синтаксически

управляемых определений, трансляторы для которых строятся достаточно просто. К таким классам относятся S-атрибутные опреде-

ления, т.е. синтаксически управляемые определения, в которых

применяются исключительно синтезируемые атрибуты.

Синтезируемые атрибуты могут быть вычислены восходящим

синтаксическим анализатором в процессе разбора входной строки.

Синтаксический анализатор может хранить значения синтезируе-

мых атрибутов, связанных с грамматическими символами, в своем

стеке. При выполнении свертки по хранящимся в стеке атрибутам

символов из правой части сворачиваемой продукции вычисляются

значения новых синтезируемых атрибутов. Можно расширить стек

синтаксического анализатора для хранения значений этих синтези-

руемых атрибутов.

Синтезируемые атрибуты в стеке

синтаксического анализатора

Восходящий синтаксический анализатор для хранения инфор-

мации о разобранных поддеревьях использует стек. Можно исполь-

зовать дополнительные поля в стеке синтаксического анализатора

для хранения значений синтезируемых атрибутов.

осходящее выполнение S-атрибутных определений

Для определения трансляций можно использовать синтаксичес-

ки управляемые определения. Рассмотрим реализацию таких

трансляторов. Создание транслятора для произвольного синтакси-

чески управляемого определения может оказаться сложной зада-

чей; однако имеются большие классы полезных синтаксически

управляемых определений, трансляторы для которых строятся дос-

170

таточно просто. К таким классам относятся S-атрибутные опреде-

ления, т.е. синтаксически управляемые определения, в которых

применяются исключительно синтезируемые атрибуты.

Синтезируемые атрибуты могут быть вычислены восходящим

синтаксическим анализатором в процессе разбора входной строки.

Синтаксический анализатор может хранить значения синтезируе-

мых атрибутов, связанных с грамматическими символами, в своем

стеке. При выполнении свертки по хранящимся в стеке атрибутам

символов из правой части сворачиваемой продукции вычисляются

значения новых синтезируемых атрибутов. Можно расширить стек

синтаксического анализатора для хранения значений этих синтези-

руемых атрибутов.

9.7.1. Синтезируемые атрибуты в стеке

синтаксического анализатора

Восходящий синтаксический анализатор для хранения инфор-

мации о разобранных поддеревьях использует стек. Можно исполь-

зовать дополнительные поля в стеке синтаксического анализатора

для хранения значений синтезируемых атрибутов.