Богданов В. С.. Лексический анализатор
.pdfФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Государственное образовательное учреждение высшего профессионального образования
РЯЗАНСКАЯ ГОСУДАРСТВЕННАЯ РАДИОТЕХНИЧЕСКАЯ АКАДЕМИЯ
ЛЕКСИЧЕСКИЙ АНАЛИЗАТОР
Электронное пособие
Автор
_____________/Богданов В.С./
Рязань 2005 г.
Введение.
В соответствии с учебным планом специальности 220400 студенты выполняют курсовую работу по дисциплине «Теория языков программирования и методы трансляции».
Курсовая работа может заключаться в конструировании лексического анализатора, синтаксического анализатора и в целом компилятора.
Программирование синтаксического анализатора рассмотрено в [6].
Данное пособие посвящено конструированию лексического анализатора и содержит в качестве примера программу лексического анализатора для лексического разбора структур данных типа массивов, а также задания по курсовой работе.
Требования к курсовой работе
Предметом курсового проектирования может быть транслятор, компилятор, ассемблер или интерпретатор для целевого языка программирования или его подмножества, работающий по одной из следующих схем:
–резидентной,
–схеме кросс–трансляции;
–синтаксически управляемой схеме.
Резидентная схема базируется на использовании одной машины Х. Программа на реализуемом языке поступает на обработку транслятором для машины Х, в результате чего появляется эквивалент программы на языке сборки.
Программа на языке сборки обрабатывается ассемблером Х, в результате чего формируется исполнимый модуль, реализуемый на машине Х.
В схеме кросс–трансляции программа обрабатывается транслятором на машине Х, затем ее эквивалент на языке сборки обрабатывается ассемблером машины Z, в результате чего получается исполнимой модуля для Z.
По третьей схеме в процессе трансляции используется синтаксис и семантика отдельной конструкций реализуемого языка. Выходом транслятора машины Z является язык сборки. Полученный файл обрабатывается ассемблером машины X (или Z), в результате получается исполнимый модуль для машины Z(X).
Курсовая работа заключается в определении возможностей целевого языка, типа его грамматики, возможности упрощения или преобразования
грамматики (устранение рекурсии, λ–правил, «пустых» символов и т. п.) к той или иной удобной для реализации форме.
В ней должны быть разработан синтаксический анализатор и транслятор для заданных фрагментов языка или модули, реализующие те или иные функции транслятора.
Разработанная программная система должна в той или иной степени отвечать части основных вариантов реализации языков программирования (таблица 1).
2
Таблица 1
|
Основные варианты реализации языков |
|
|
|
|
||||||
|
|
|
|
|
|
||||||
|
Название характеристики |
|
Варианты реализации |
|
|
||||||
1. |
Спецификация |
реализуемых |
Весь язык в целом. Подмножество |
||||||||
возможностей языка |
|
языка. |
Часть |
|
возможностей |
языка. |
|||||
|
|
|
Расширение |
языка. |
|
Модификация |
|||||
|
|
|
языка. |
|
|
|
|
|
|
|
|
2. |
Способ реализации |
|
Резидентный |
|
транслятор. |
Кросс– |
|||||
|
|
|
транслятор. |
|
|
Синтаксически |
|||||
|
|
|
управляемый |
|
|
|
транслятор. |
||||
|
|
|
Интерпретатор. |
С |
использованием |
||||||
|
|
|
системы |
построения |
трансляторов |
||||||
|
|
|
(СПТ) |
|
|
|
|
|
|
|
|
3. |
Число проходов транслятора |
Однопроходный. |
Двухпроходный. |
||||||||
|
|
|
Трехпроходный. |
|
|
|
|
||||
4. |
Организация работы проходов. |
Последовательная. |
|
Параллельная. |
|||||||
|
|
|
Параллельно–последовательная. |
|
|||||||
5. |
Организация информационной |
С |
помощью |
информационных |
|||||||
связи между проходами. |
|
массивов |
оперативной |
памяти. |
С |
||||||
|
|
|
помощью файлов внешней памяти. С |
||||||||
|
|
|
помощью |
информационных |
квантов |
||||||
|
|
|
(лексем, тетрад, слов и т. п.). |
||||||||
|
|
|
Комбинированный. |
|
|
|
|
||||
6. |
Метод синтаксического разбора |
Нисходящий |
разбор. |
Рекурсивный |
|||||||
|
|
|
спуск. Восходящий разбор на основе |
||||||||
|
|
|
грамматик предшествования и т. п. |
|
|||||||
7. |
Организация таблиц |
символов и |
Упорядоченные |
таблицы. Списковые |
|||||||
методы поиска символов. |
|
структуры. |
|
|
Последовательный |
||||||
|
|
|
просмотр |
с |
использованием |
метода |
|||||
|
|
|
деления пополам. С |
использованием |
|||||||
|
|
|
схем–функций. |
|
|
|
|
|
|||
8. |
Способ распределения рабочей |
Динамический, |
статический, |
с |
|||||||
памяти. |
|
использованием виртуальной памяти. |
|||||||||
9. Характеристика аппаратных средств |
Структура команд машины. Язык типа |
||||||||||
и инструментальный язык. |
Pascal, типа C, типа C++, ассемблер. |
|
Процесс выполнения курсовой работы состоит из следующих этапов:
1.Разработка схемы и блоков лексического анализатора, либо по первой части задания, либо применительно к заданной грамматики языка по второй части задания.
2.Анализ грамматики, определение ее типа, проведение необходимых преобразований грамматики к виду, удобному для реализации выбранным методом.
3.Разработка структуры синтаксического анализатора, блока проведения синтеза, генератора кодов (тетрад или триад).
3
4.Разработка блока вывода сообщений об синтаксических ошибках и отладка модулей на тестовых примерах, охватывающих все возможные синтаксические ошибки.
5.Оформление пояснительной записки к курсовой работе. При оформлении должны быть использованы соответствующие ГОСТы и рекомендации ЕСПД. Описание алгоритмов может быть выполнено на метоязыке типа PSL [5 стр. 52–53].
Пример конструирования сканера для распознавания массивов
Конструирование лексического анализатора требует разработки ряда процедур и функций, использующихся для распознавания тех или иных лексем языка. Приведенные ниже фрагменты используются для распознавания регулярных типов (массивов). Ниже приводятся тексты этих основных процедур на языке Турбо-Паскаль.
{ распознавание и удаление пробелов }
Procedure Probel;
begin { Probel } repeal
r:=r+1
until ((st[i] < > (( ))) or (i>=k)) end { Probel }
{st – строка, содержащая символы алфавита и пробел, описывается как глобальная переменная типа string }
{ Процедура выхода в случае обнаружения ошибок } Procedure Quit;
begin { Quit } writeln;
goto XY (0,15);
writeln (“Код ошибки: ” CodE); writeln (“Ошибка:” , CE [CodE]);
{ здесь CE: array [1..2] of string = (“не число”, ‘Не идентификатор’); а CodE –
код ошибки. Эти данные описываются как глобальные } readln;
Halt
end; ( Quit)
{ Функция для распознавания идентификаторов }
Function Identificator: boolean; var
fidentificator := true;
if not (st [i] in [’a’ .. ’z’, ’A’..’Z’]) then fidentificator : = false;
4
if fidentificator then begin
repeat i:=i+1
until ((not (st[i] in [’a’..’z’, ’A’..’Z’, ’O’..’9’, ’-’]))
or (i> = k); end;
Identificator:=fidentificator; end; { Identificator }
{ функции для распознавания констант }
Function Constanta : boolean; var
fConstanta: boolean; function Chislo: boolean; var
fChislo: boolean;
begin { Chislo } fChislo:= true;
if not (st [i] in [”O”..’9’] then fChislo:=false;
if fChislo then begin repeat i:= i+1
until ((not (st [i] in [”O”..’9’])) or (i>=k);
if ((i<=k) and (not (st [i] in [ “ “, ”, ’, ’; ’, ’: ’, ’. ’, ’] ’]))) then fChislo:= false
end;
Chislo:= fChislo end; { Chislo }
begin { Constanta }
fConstanta:= true;
if not (st [i] in [”O”..’9’, ’-’, ’+’, ’’’’]) then fConstanta:= false;
if fConstanta then
case st [i] of
”O”..’9’: if not Chislo then fConstanta:= false;
”+”, ’-’: begin
i:= i+1;
if st [i] = ” ” then Probel;
case st [i] of
”a”..’Z’, ’A’..’Z’: if not identificator then fConstanta:= false;
5
” ”..’9’ : if not Chislo then fConstanta:= false;
else fConstanta:= false end
end; ‘‘’’’’: begin
i:= i+1;
if st [i] = ‘‘’’’’ then begin
if st [i+1] = ‘‘’’’’ then i:= i+1
else fConstanta:= false end,
if fConstanta then begin
i:= i+1;
if st [i] < > ‘‘’’’’ then fConstanta:= false;
if fConstanta then i:= i+1
end end
end;
Constanta:= fConstanta
end; { Constanta }
Приведенная ниже процедура распознавания ключевых слов использует строку StWork, описанную глобально и иллюстрирует распознавание ключевых слов PACKED, ARRAY, TYPE, OF. Другие ключевые слова могут быть обработаны по той же схеме.
Procedure KeyWords (var cod: byte);
begin { KeyWords }
cod:= 0
stWork:= copy (st, i, 6); forj:= 1 to 6 do
stWork [j] := Up Case (StWork [j]);
if ((stWork = ”PACKED”) and (st [i+6] = ’ “ )) then begin
cod:= 4; i:= i+6; end;
stWork:= copy (stWork, 1, 5);
if ((stWork = ”ARRAY”) and (st [i+5]= (( ))) or (st [i+5]= “[“ ))) then
6
begin cod:=5; i:= i+5;
end;
stWork:= copy (stWork, 1, 4);
if ((stWork= “TYPE”) and (st [i+4]= “ “)) then begin
cod:= 1 i:= i+4; end;
stWork:= copy (stWork, 1, 2);
if ((stWork = “OF”) and (st [i+2]= “ “)) then begin
cod:= 8; i:= i+2; end
end; { KeyWords }
Заметим, что для ключевых слов назначены следующие дескриптеры кодов:
type – 1; array – 5; of – 8; packet – 4.
Вариант лексического анализатора для этих лексем языка приведен ниже. Он спроектирован как процедура с одним входным параметром ES:
stArray; где StArray это описатель типа: type
stArray = array [1..256] of bute Procedure Scanner (Var ES: StArray);
/ лексический анализатор /
/ лексемы языка имеют следующие коды: идентификаторы – 10, константы – 4, разделители = -2; -3; [-6;] - 7; , -9; .. -11, (-12;) -13 }
/ маркер конца строки – 15 }
var
CodKW, ilA: byte
begin { Scanner } i:= 1;
k:=length (st); vi = 0;
repcat
if s[i] = “ ” then Probel; case st [i] of
“+”, ‘-‘, ” ”, ‘ ’..’9’: begin if Constanta then
7
begin v:= v+1;
ES [v]: = 14 end
else begin
CodE:= 2; Quit;
end;
end;
“a”..’Z’, ‘A’..’Z’: begin
KeyWord (CodKW);
if CodKW < > 0 then begin
v:= v+1;
ES [v]:= CodKW; end
else
if not identificator then begin
CodE:= 1 Quit; end
else begin v:= v+1;
ES [v]:= 10; end;
end; “;” : begin
v:= v+1; ES [v]: = 3; i:= i+1; end;
“=” : begin
v:= v+1; ES [v]:= 2; i:= i+1; end;
“[” : begin
v:= v+1; ES [v]:= 6; i:= i+1; end;
“]” : begin
v:= v+1; ES [v]:= 7; i:= i+1; end;
“.” : begin
if st [i+1]= “.” Then begin
8
v:= v+1; ES [v]:= 11; i:= i+2 end
end; “,” : begin
v:= v+1; ES [v]:= 9; i:= i+1; end;
“(“ : begin
v:= v+1; ES [v]= 12; i:= i+1; end;
“)” : begin
v:= v+1; ES [v]:= 13; i:= i+1; end;
end;
until i>k; {* k – длина анализируемой строки *} ES [v+1]:= 15; v:= v+1
End; {*** SCANNER ***}
Во всех заданиях к курсовой работе первым этапом является конструирование сканера (лексического анализатора).
Задания к курсовой работе
1. Задана грамматика G ({“.”,+,–,0,1}, {áчислоñ, áчастьñ, áцифраñ, áосн. ñ}, P, áчислоñ) P:
áчислоñ ® + áосн. ñ – áосн. ñ êáосн. ñ áосн. ñ ® áчастьñ, áчастьñ êáчастьñ êáчастьñ
áцифраñ ® Ø ê1 Построить для этой грамматики обычный и расширенный МПавтоматы
[1] строк 391–397, 418–423.
Построить для этой грамматики нисходящий распознаватель с возвратом.
2. Дана грамматика G ({“”, “(“, “)”, o, r, a, n, a, t, b} {S, T, E, F}, P, S) P:
S ® SorT êT
T ® Tand E êE E ® not E ê F
F ® (S) êb
Написать программу для приведения грамматики к виду без ценных правил, и исключения левой рекурсии и используя ее преобразовать данную грамматику [1] стр. 426–433.
Построить для данной грамматики нисходящий распознаватель с возвратом. На печать ввести разбор цепочки “BorB and not B and (Bor not not B).
3. Дана грамматика:
G ({a, b, c}, {A, B, C, D, E, F, G, S} P, S) P:
9
S ® aAbB êE A ® BCa ê a êl B ® ACb ê b êl
C ® A êB êbA êaB êcC êaE êbE E ® Ea ® êEb êEc êED êFG êDG D ® c êFb êFa êl
F ® BC êAC êDC êEC
G ® Ga êGb êGc êGD
Преобразовать эту грамматику в нормальную форму Хомского и построить распознаватель на базе алгоритма Кока-Янгора-Касами [1] стр. 433.
4. Построить распознаватель, основанный на методе рекурсивного спуска для грамматики
G({a, b, c}, {S, A, B, C}, P, S) P:
S ® aABb êbBAa êcCc A ® aA êbB êcC
B ® bêaAC
C ® aA êbA êcC
Привести примеры и вывод на печать разборов некоторых цепочек,
принадлежащих языку a (G). 5. Дана грамматика
G ({(, ), Ù, &, ~, a}, {S, T, E, F}, P, S) P:
S ® ST êT
T ® T&E êE
E ® –E êF
F ® (S) êa
Построить для нее распознаватель на основе грамматики операторского предшествования. В качестве тестового примера привести разбор цепочки:
S = aÙa&~a&(aÙ~~a).
6. Задана грамматика операторного предшествования: G(“if”, “then”, “else”, a, b} {S, T, E, F}, P, S)
P:
S ® ifb then T else S êifb then S êa
T ® ifb then T else S êa
Построить для этой грамматики распознаватель операторного предшествования.
В качестве вывода распознавателя – разбор цепочки языка a (G) и вывод сообщений о синтаксических ошибках.
7. Разработать программу построения матрицы предшествования для произвольной грамматики предшествования. В качестве примера грамматики использовать грамматику из [2] стр. 235–239.
10