Лексический блок

Лексический блок

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

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

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

у ** 34 + аbс

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

Алгоритм действия ЛА:

- чтение литеры;

- определение класса;

- выбор состояния из таблицы переходов ;

- возврат в конечном состоянии фиксированного количества символов [0] или [1];

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

Наиболее удобной формой представления КА для человека является графическая - диаграмма состояний-переходов, а для программирования и формальных преобразований – табличная.

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

Диаграмма состояний-переходов.

В данной диаграмме заключительные состояния нумеруются отрицательными числами, начиная с (–1).

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

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

- цифры 0 – 9;

- буквы;

- A – F;

- символ «(» ;

- символ «)» ;

- символ «=» ;

- символ «<» ;

- символ «>» ;

- символ «;» ;

- символ «+» ;

- символ «-» ;

- символ «*» ;

- символ «/» ;

- символ «#» ;

- символ «.» ;

- символ «,» ;

- остальные символы ;

Таблица содержит:

- 7 состояний;

- 17 классов литер.

Таблица состояний КА.

0	1	2	2	-11	-12	-16	3	4	-10	-13	-14	5	-4	-15	0	-1
-2	1	-2	1	-2	-2	-2	-2	-2	-2	-2	-2	-2	-2	-2	6	-2
-1	2	2	2	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1
-5	-5	-5	-5	-5	-5	-7	-5	-17	-5	-5	-5	-5	-5	-5	-5	-5
-6	-6	-6	-6	-6	-6	-8	-6	-6	-6	-6	-6	-6	-6	-6	-6	-6
-9	-9	-9	-9	-9	-9	-9	-9	-9	-9	-9	-9	-18	-9	-9	-9	-9
-2	6	-2	6	-2	-2	-2	-2	-2	-2	-2	-2	-2	-2	-2	-2	-2
ост	ц	б	A-F	(	)	=	<	>	;	+	-	*	/	#	.	,

Синтаксический блок

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

Результат классификации лексем (классы лексем) является входной информацией для синтаксического анализатора (класс лексемы называется на входе синтаксического анализатора символом).

Формальные грамматики (ФГ) как математический аппарат появились именно по «производственной необходимости» представления синтаксиса в трансляторах и автоматизации синтаксического анализа (СА). В отличие от лексики, которую можно в принципе реализовать, синтаксический анализатор почти невозможно сделать, руководствуясь «здравым смыслом» и очевидностью. Необходим некоторый промежуточный уровень между синтаксисом языка и программной системой, его распознающей. Таковым уровнем и является ФГ (на ее основе создается инструментарий СА).

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

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

- каждому нетерминалу соответствует отдельная процедура (функция), распознающая одну из правых частей правила, имеющего в левой части этот нетерминал;

- во входной строке имеется указатель (индекс) на текущий «закрываемый символ». Этот символ и является основанием для выбора необходимой правой части правила;

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

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

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

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

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

S::= пусто | OS // задание последовательности операторов.

O::= sa=E | ra | wE | xc | tC // перечень операторов программы.

L::= A | L|A // логическая операция ИЛИ.

A::= B | A&B // логическая операция И.

B::= C | !C // логическая операция НЕ.

C::= (L) | E<E | EnE | E=E | E>E | EgE | ElE // операции сравнения и приоритетные скобки логических операций.

E::= T | E+T | E-T // цепочка сложений/вычитаний.

T::= F | T*G | T/G // цепочка умножений/делений.

G::= F | F**F // возведение в степень.

F::= a | c | (E) | m(E) | i(E) | f(E, E,...,E) // приоритетные скобки, константы и вызовы функций.

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

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

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

2.  Объединяет эти блоки кода.

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

Интерпретатор кода

1.  Стековая машина имеет систему команд, которая берет два входных операнда из стека, производит над ними операции(все арифметические,

2.  логические операции и операции сравнения) и результат возвращают в стек.

LOADM 0

LOADC 34

LOADM 1

POW

ADD

2. Семантика стековой машины, операции:

LOADM – загрузка в стек переменной с номером.

LOADC – загрузка в стек константы.

SAVE – загрузка из стека

IN – ввод-номер переменной

OUT

OUTL

ADD

SUB

MUL

DIV арифметические операции

POW

MIN

INT

AND

OR

NOT

LE

LT логические операции.

GE

GT

EQ

NE

RADIX – задание системы счисления.

Операция сравнения. Сначала вычисление, потом сравнение знаков.

a>b

LOADM 0 (a)

LOADM 1 (b)

sub (a-b)

GT ( >0)

Арифметические и логические операции, операции сравнения. Вызывается команда Test - > OUTL

test a+b>5

LOADM 0 (a)

LOADM 1 (b)

ADD (a+b)

LOADC 5 (5)

SUB (a+b-5)

GT ( >0)

OUTL занесение в стек

Система счисления.

Функция atof переводит вещественное число из заданной системы счисления во внутреннюю форму. Вызывается при выполнении команд IN и LOADC.

Функция ftoa переводит число из внутренней формы в заданную систему счисления. Вызывается при выполнении команды OUT.