I.15.3. Правила, задающие неоднозначность в грамматиках

Для КС гр. существуют определенного вида правила,по наличию которых все множество наличия гр. G(VT,VN,P,S) можно утверждать, что она является неоднозначной.

Правила:

1) A →AA| α

2) A→AαA| β

3)A→ αA|A β | γ

4)A→ αA|αA β A| γ

Если в заданной гр. встречается хотя бы одно правило подобного вида, то такая гр. всегда будет неоднозначной. Однако, если подобных правил во всем множестве гр. нет – это совсем не означает, что она является однозначной, т.е. это условие необходимое, но недостаточное. Установленные условия при удовлетворении которых гр. всегда является однозначной. Они справедливы для всех регулярных и многих классов КС гр. Однако известно, что эти условия являются достаточными, но необходимыми для данных грамматик.

Например, для гр. ариф. выражений с операндами a и b

a…b

G({+,-,*,/,(,),a,b},{S},P,S)

Во множестве правил

P:S→S+S|S-S|S*S|S/S|(S) |a|b

 

 

Встречаются правила 2 типа

S→S+S

S→a,

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

 

II. Принципы построения трансляторов

II.1. Определения транслятора

Всё, что до сих пор читалось, является теорией трансляторов. Транслятор – это программа, которая переводит программу на исходном входном языке в эквивалентную ей программу на результирующем выходном языке. В определении слово «программа» встречается 3 раза, что говорит о том, что в работе транслятора участвуют 3 программы.

1)Сам транслятор является программой. Это часть ПО. Он представляет собой набор машинных команд и выполняется компилятором, как и все прочие программы в ОС. Все составные части транслятора представляют собой динамичную загружаемые библиотеки и модули этой программы со своими входными и выходными данными.

2) Выходными данными транслятора является программа на результирующем языке, называемая результирующей программой. Она строится по синтаксическим правилам выходного языка транслятора. А ее смысл определяется семантикой выходного языка. Важным является эквивалентность исходной и результирующей программ, что означает совпадение их смысла с точки зрения исходного языка. Без выполнения этих требований, транслятор теряет фактический смысл. Чтобы создать транслятор, необходимо выбрать входной и выходной языки. С точки зрения преобразования предложений входного язы­ка в эквивалентные им предложения выходного языка транслятор выступает как переводчик. Результатом работы транслятора будет результирующая программа, но только в том случае, если текст исходной программы является правильным, т.е. не со­держит ошибок с точки зрения синтаксиса и семантики входного языка. Если исходная программа содержит хотя бы одну ошибку, то резуль­татом работы транслятора будет сообщение об ошибке, как правило, с допол­нительным сообщением о месте возникновения ошибки в исходной программе.

 

II.2. Определение компилятора

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

Компилятор — это транслятор, который осуществляет перевод исходной програм­мы в эквивалентную ей результирующую программу на языке машинных команд или на языке ассемблера. Компилятор отличается от транслятора лишь тем, что его ре­зультирующая программа всегда должна быть написана на языке машинных ко­дов или на языке ассемблера. Результирующая программа транслятора, в общем случае, может быть написана на любом языке (например, транслятор программ с языка Pascal на язык С). Всякий компилятор являет­ся транслятором, но не наоборот — не всякий транслятор будет компилятором. Результирующая программа компилятора называется объектной программой или объектным кодом. А исходная программа в этом случае называется исходным кодом. Файл, в который она записана, обычно называется объ­ектным файлом. Даже в том случае, когда результирующая программа порож­дается на языке машинных команд и исполняемой программой (исполняемым файлом) есть существенная разница. Порожденная компилятором программа не может непосредственно выполняться на компьютере. Компилятор составляет объектную программу из фрагментов машинных кодов, соответствующих синтаксическим конструкциям исходной программы. Результирующая программа, созданная компилятором, строится на языке машинных кодов или на языке ассемблера, ориентирована на определенную ВС, имеющую конкретную архитектуру. Существуют компиляторы, которых результирующая программа создается не на языке машинных кодов и не на языке ассемблера, а на некотором промежуточном языке, который не может непосредственно выполняться на компьютере, а требует наличия промежуточного интерпретатора для выполнения написанной на нем программы. Промежуточный язык является языком низкого уровня, будучи родственным языку машинных кодов и языку ассемб. ВС, на которой выполняется результирующая объектная пр., созданная компилятором, называется целевой ВС. В это понятие входит не только ее архитектура и ОС, а также набор динам. подключ. библиотек, необходимых для выполнения программ. Объектная пр. ориентирована на целевую ОС, но не может быть выполнена на ней без дополнительной обработки. Целевая ВС не всегда является той ВС, на которой работает сам компилятор. Бывает так, что компилятор работает на ВС одного типа, а строит объектную пр. для ВС другого типа. Все компиляторы практически создаются с помощью других компиляторов предыдущих версий.

 

II.3. Определения интерпретатора

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

 

II.4. Этапы трансляции

Они представлены на следующем рисунке

 

Процесс компиляции состоит из 2ух основных этапов: анализа и синтеза.

На этапе анализа выполняется распознавание текста исходной программы, соз­дание и заполнение таблиц идентификаторов(ТИ). Результатом работы этапа служит некое внутреннее представление программы, понятное компилятору. На этапе синтеза на основании этого представления и инфор­мации, содержащейся вТИ, порождается текст результирующей программы. Конечный результат - объектный код. В составе компилятора входит часть, ответственная за анализ и исправление ошибок, которая при наличии ошибки в тексте исходной про­граммы должна максимально полно информировать пользователя о типе ошиб­ки и месте ее возникновения. В лучшем случае компилятор может предложить пользователю вариант исправления ошибки. Эти этапы состоят из более мелких этапов, называемых фазами компиляции. Их конкрет­ная реализация и процесс взаимодействия различаются в зави­симости от версии компилятора. Компилятор, с точки зрения формальных языков, выполняет две основные функции:

1)является распознавателем для языка исходной программы, т.е. он должен получить на вход цепочку символов входного языка, проверить ее принадлежность языку и правила, по которым она была построена (генератором цепочки входно­го языка выступает пользователь — автор исходного языка);

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

 

II.5. Фазы компиляции

1.Лексический анализ — это часть компилятора, которая читает литеры программы на исходном языке и строит из них слова (лексемы) исходного язы­ка. На вход лексического анализатора поступает текст исходной программы, а выходная информация передается для дальнейшей обработки компилятором на этапе синтаксического разбора.

2.Синтаксический разбор — это основная часть компилятора. Она выполняет выделение синтаксических конструкций в тексте исходной програм­мы, обработанном лексическим анализатором. На этой же фазе компиляции проверяется синтаксическая правильность программы. Синтаксический разбор выполняет роль распознавателя текста входного языка программи­рования.

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

4.Подготовка к генерации кода. Здесь выполняются предварительные действия, непосредственно связанные с синтезом текста ре­зультирующей программы, но еще не ведущие к порождению текста на выход­ном языке. В эту фазу входят например действия, связанные с идентификацией элементов языка, распределением памяти и др.

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

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

 

II.6. ТИ (таблицы идентификаторов)