Структура трансляторов

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

Функции транслятора: распознать во входном тексте отдельные лексемы. Та часть транслятора которая это делает называется лексическим анализатором или сканером. Сам этап –

2. ???

Рис

3. сгенерировать для каждой правильной грамматической конструкции соответствующий набор команд – генерация кода. ???

Разновидность транслятора:

Компиляторы и интерпретаторы

Компиляторы – трансляторы, которые н7а вход принимают текст программы, на выход код.

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

30.04.

Лекция №

Структура входного языка для описания простейших арифметических выражений

Арифметические выражения будут работать только с целыми числами.

Язык будет состоять из символов лат алфавита, букв, цифр.

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

2 формы представления синтаксиса:

1. Нотации Бэкуса-Наура

2. синтаксические диаграммы Вирта

Хрень 1

<слагаемое>::=< слагаемое >{+< слагаемое >|-< слагаемое >}

<множитель>::=< множитель >{*< множитель >|/< множитель >}

<множитель>::=число|ИП|(<выражение>)

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

::= - равно по определению

<> - описывают(обрамляют) название грамматической конструкции

{} - обозначают повторение сколько угодно раз(в том числе и 0)

| - или

Описание простейшего входного языка

ДЗ НАПИСАТЬ СТРУКТУРУ ПРОСТЕЙШЕГО ВХОДНОГО ЯЗЫКА, ЯВЛЯЮЩЕГОСЯ ПОДМНОЖЕСТВОМ ЯЗЫКА С

Наложим ограничения на язык:

1. из всех типов данных оставим только целочисленный тип

2. для обработки целочисленных операндов будем использовать +, -, *, div

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

4. ввод и вывод будет осуществляться с помощью простейших форм операторов read и write

program test;

var x,s:integer

i:integer;

begin

s:=0;

for i:=1 to 100 do

begin

read(x);

s:=s+x

end;

s:=s div 100;

write(s);

end.

Лексемы:

1. зарезервированные слова

2. идентификаторы пользователя

3. целые числа

4. служебные символы

Синтаксис:

Правила вывода Бэкуса-Наура:

<программа>::=program ИП ;

VAR <список_объявлений> ;

Begin <список_операторов> end .

< список_объявлений >::=<объявление(я)> {;< объявление >}

< объявление >::=<список ИП>():integer

< список ИП >::= ИП{; ИП}

<список_операторов>::=<оператор>{;<оператор>}

<оператор>::=<присваивание>|<цикл>|<ввод>|<вывод>

<присваивание>::=ИП::=<выражение>

<выражение>::=< слагаемое >{+< слагаемое >|-< слагаемое >}

<слагаемое>::=< множитель >{*< множитель >|/< множитель >}

<множитель>::=число|ИП|(<выражение>)

<цикл>::=for <индексное_выражение> do

<тело_цикла>

<индексное_выражение>::= <присваивание> to <выражение>

< тело_цикла>::=<оператор>| begin <список_операторов> end

<ввод>::=read <список ИП>

<вывод>::=write<список ИП>

2. диаграммы вирта

Рис1

7.05.09

Лекция №

Рис1

ДЗ РАССМОТРЕТЬ ВСЕ ОСТАВШИЕСЯ ГРАММАТИЧЕСКИЕ КОНСТРУКЦИИ И НАРИСОВАТЬ ДЛЯ НИХ ДИАГРАММЫ ВИРТА

Рис2

Лексический анализ

Цель:

1. помогает уменьшить объем данных

2. помогает избавиться от паразитных конструкций языка

<comment>::=(*<строка>*)

Группы лексем:

1. Зарезервированные слова(ключевые) – имеют свой уникальный код.

2. идентификаторы пользователя – все лексемы этого типа имеют только 1 целочисленный код

3. целые числа – также имеют один целочисленный код

4. специальные символы

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

Алгоритм работы сканера

If “символ = буква” then

Begin

‘выделяем слово’

If ‘поиск в таблице зарезервированных слов’ then lex:=’зарезервированное слово’

Else lex:=’ИП’;

End

Else

If ‘символ = цифра’ then

Begin

‘формируем число’;

Lex:=’число’;

End;

Else

Case ‘символ’ of

‘;’:lex:=

...

‘:’:lex:=

...

Else lex:=”неизвестна”

End;

14.05.09

Лекция №

Основы синтаксического анализа

1. методы восходящего синтаксического анализа

2. методы нисходящего синтаксического анализа

дерево грамматического разбора

read(X, y)

<ввод>

Рис1

Восходящий синтаксический анализ(метод операторного предшествования)

Program test;

Var x,y:integer;

Begin

X:=1;

Y:=X+2;

End.

Program ИП(test) ; var ИП (x) , ИП(Y) : integer ; begin ИП(x) := число ; ИП:=ИП+число ; end .

Рис2

Отношение предшествования будем обозначать символом >.

Если лексема1>лексема2, то это ознчает что лексема 1 должна встретиться в программе раньше чем лексема 2.

Если лексема1~лексема2 – лексемы эквивалентны и принадлежат одной грамматической конструкции.

Идея метода операторного предшествования:

1. в процессе выделения лексем между соседними лексемами устанавливаем отношение предшествования и эквивалентности согласно таблице предшествования

2. в потоке лексем синтаксический анализатор пытается найти 1ю комбинацию вида ...лексема i<лексема i+1~...~ лексема i+j>лексема i+j+1...Найденную последовательность называем грамматической конструкцией Nk и между ней и соседними лексемами выстраиваем отношение предшествование и эквивалентности.

3. о5 просматриваем поток лексем для обнаружения следующей грамматической конструкции

…

+

-

*

/

(

)

…

…

…

…

…

…

…

…

…

…

+

…

>

>

<

?

<

>

…

-

…

>

>

<

?

<

>

…

*

…

>

>

>

?

<

>

…

/

…

?

?

?

?

?

?

…

(

…

<

<

<

?

<

~

…

)

…

>

>

>

?

--

>

…

…

…

…

…

…

…

…

…

…

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

...;x:=x+y*z;...

;<x~:=<x>+<y>*<z>;...

Рис3

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

21.05.09

Лекция №