Трансляторы. Структура компилятора. Лексический, синтаксический и семантический анализ.

Транслятор (англ. translator — переводчик) — это программа-переводчик. Она преобразует программу, написанную на одном из языков высокого уровня, в программу, состоящую из машинных команд

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

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

Функции компиляторов.

1. Лексический анализ – выделяет лексемы в строчке и проверяет на правильность.

2. Синтаксический анализ – проверяет порядок лексем.

3. Семантический анализ- проверка на правильность присваивания.

4. Генерация выходного текста

лексический анализатор (ЛА) группирует определенные терминальные символы (т.е. входные символы) в единые синтаксические объекты - лексемы. В простейшем случае лексема - это пара вида <тип_лексемы, значение> Функции лексического анализа:

1. Выделения численных констант

2. Выделение индификаторов

3. Выделение сложных символов: /* */ //

4. Определение ошибок ввода

Для лексического анализа используются автоматные (регулярные) грамматики. В средствах лексического анализа используются регулярные выражения.

< нетерм. символ > → [< нетерм. символ >]< терм. символ >

A→Bc B→Cc C→d

< нетерм. символ > → < терм. символ >[< нетерм. символ >]

A→eC C→cC C→c

Существует два основных типа лексических анализаторов - прямые (ПЛА) и непрямые (НЛА).

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

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

Синтаксический анализ - это процесс, в котором исследуется цепочка лексем и устанавливается, удовлетворяет ли она структурным условиям, явно сформулированным в определении синтаксиса языка. Это - самая сложная часть компилятора.

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

Выделяют 2 типа синтаксического анализа: сверху вниз и снизу вверх. Используются контекстно-свободные грамматики.

< нетерм. символ > → < цепочка символов >

Слева должен быть нетерм. символ – без контекста

Пример:

S x,x,…x f x,x,…,x

Анализ сверху вниз

1) S→sXfX

2) X→xY

3) Y→,xY

4) Y→E

s x , x f x , x , x

Анализ снизу вверх

1) S→sXfX

2) X→xY

3) X→x

4) Y→,xY

5) Y→,x

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

Атрибутная грамматика – это четверка G = <VN,VT, P, S >, в которой

VN - нетерминальный словарь (множество нетерминальных символов);

VT - терминальный словарь (множество терминальных символов ) ;

P - множество грамматических правил;

S  VN - начальный нетерминальный символ.