Содержание
- 2. Содержание: Транслятор Интегрированная среда Общий алгоритм работы транслятора Сканер Грамматика языка Метод рекурсивного спуска Оператор ветвления
- 3. Транслятор – это специальная программа, которая переводит исходную программу в эквивалентную ей объектную программу. Если транслятор
- 4. Интегрированная среда содержит: Текстовый редактор – в нем пользователь будет набирать исходный текст программы, которая управляет
- 5. Интегрированная среда Исполнитель Предмет сбора Меню Текстовый редактор Препятствие Меню загрузки Количество предметов Игровое поле
- 6. Генератор кода Общий алгоритм работы транслятора СКАНЕР … ВПРАВО; ВЗЯТЬ; ВНИЗ; … Интерпретатор Матрица поля cmRight
- 7. Сканер – лексический анализатор, который выделяет лексемы из исходного текста программы. Лексема – это последовательность символов,
- 8. ПРОГРАММА ТЕСТ; ПЕРЕМЕННЫЕ И:ЦЕЛЫЙ; НАЧАЛО НАЧАТЬ_С 0 0 2; ДЛЯ И=1 ДО 4 НАЧАЛО ВЗЯТЬ; ВПРАВО;
- 9. Сканер Как уже говорилось ранее, сканер – это лексический анализатор, предназначенный для просмотра исходного текста программы
- 10. Type Str_15=string[15]; tVarName=array[1..50] of Str_15; {Тип временного буфера имен переменных} tVar=record {Тип элемента таблицы имен переменных}
- 11. Function GetLex:Ident;{Ident –перечислимый тип, содержит} var i,Code:integer; {все лексемы языка} ii:Ident; begin While St='' do {Считываем
- 12. ':',';',',','=': {Здесь выделяются однознаковые лексемы} begin Lex:=Copy(st,1,1); Delete(st,1,1); end; '0'..'9':begin {Здесь выделяется число} while st[i] in
- 13. ii:=cmProg; {Начинаем с первого идентификатора} while (MainLex[ii] Lex)and(byte(ii) inc(ii); {пока имена не совпали, двигаемся дальше} GetLex:=ii
- 14. Грамматика языка Прежде, чем создавать генератор кода, необходимо разработать язык исходной программы. От того, как вы
- 15. Существует два способа разбора языков: восходящий и нисходящий. Мы только что рассмотрели восходящий. Сначала описываются некоторые
- 16. Метод рекурсивного спуска Пусть имеется грамматика, описывающая некоторый язык: ::=ПРОГРАММА | ::= | | {повтор «раздел
- 17. ПРОГРАММА МОЕ_ТВОРЕНИЕ; У, И, Х: ЦЕЛОЕ; НАЧАЛО ВЛЕВО; ВПРАВО; ДЛЯ И=1 ДО 10 {цикл с известным
- 18. Procedure progr; {считаем, что лексема уже считана в Ch} begin if Ch cmProg {Если первая лексема
- 19. procedure RazdelVar; var i:integer; begin Repeat {первый цикл нужен, так как возможно несколько групп переменных, каждая
- 20. Ch:=GetLex; if not (Ch in[cmInt]){если не указан тип, то ошибка} then Error('Требуется указать тип переменной') else
- 21. Repeat Repeat if ch=cmIdent then begin inc (NumbV);VarName[NumbV]:=Lex; end; Ch:=GetLex; if not(Ch in [cmTT,cmZP]) then Error(‘Требуется
- 22. Сложнее разобрать тело программы. ::= ::= | | | | | | Оно начинается ключевым словом
- 23. Для каждого оператора есть своя начальная и завершающая лексема:
- 24. Рассмотрим подпрограмму, которая разбирает тело программы. В цикле пока не встретится лексема=КОНЕЦ; Считать очередную лексему в
- 25. Procedure Operator(var Last:pNode); {Переменная Last используется как указатель на последнее звено цепочки объектного кода, но об
- 26. Генератор кода Генератор кода – это часть транслятора, которая отвечает за создание объектного кода – программы,
- 27. Type pObject=^tObject; tPoint=record Case Target:boolean of True: (tp:pObject); False: (Tx,Ty: integer); End; Данная структура называется запись
- 28. Линейные команды, которые выполняются последовательно – одна за другой, хранятся в линейном списке через указатель Next.
- 29. repeat Ch:=GetLex; case Ch of cmIf: OperIf(Last); cmFor: OperFor(Last); cmLeft:begin AddElem(Last,NewElem(cmLeft)); Ch:=GetLex; end; cmRight:begin AddElem(Last,NewElem(cmRight)); Ch:=GetLex;
- 30. Оператор ветвления Procedure OperIf(var Last:pNode); {Анализ оператора ветвления} Var pp:pNode; begin AddElem(Last,NewElem(cmIf)); {создать новое звено} {Процедура
- 31. Каждое звено будет хранить одинаковые поля, часть из них вообще не будет использоваться. Чтобы это избежать,
- 32. Поля op1,op2 имеют тип pZnach. Это тоже указатель на особую запись. Дело в том, что в
- 33. Procedure OperIf(var Last:pNode); Var pp:pNode; begin AddElem(Last,NewElem(cmIf)); Uslovie(Last); Ch:=GetLex; if Ch cmThen then Error('Требуется «ТОГДА»'); Ch:=GetLex;
- 34. Интерпретатор объектного кода После того, как трансляция прошла успешно, и объектный код построен, можно приступать к
- 35. procedure Interpetator(p:pNode); begin While p nil do {пока не конец списка} begin case p^.Typ of {в
- 36. Конечные автоматы Конечный автомат представляет собой особый способ описания алгоритма, который характеризуется набором из 5 элементов:
- 37. Описать конечный автомат, распознающий запись целого числа в десятичном виде. В чем проблема данного автомата? Есть
- 38. Описать конечный автомат, распознающий запись дробного числа в десятичном виде. Описать конечный автомат, распознающий запись дробного
- 39. Дана работоспособная программа на Паскале. Необходимо удалить из нее комментарии так, чтобы сохранить ее функции: А)
- 40. Описание языков с использованием графов Опишем наш уже созданный язык, но в терминах графа. Каждой дуге
- 41. Проанализируем данную схему. Это конечный автомат с несколькими состояниями (0-20). В начале работы автомат находится в
- 42. Procedure Automat (sost : integer); Var Ch: Ident; …; Begin Ch:=GetLex; {Получить первую лексему} repeat Case
- 43. 2: begin if Ch=cmIdent {если имя переменной, то } then sost:=3 else if Ch=cmBegin {если слово
- 44. 6:begin заполнить таблицу имен переменных, указать их тип и начальное значение; Ch:=GetLex; If Ch=cmBegin Then begin
- 45. 19:begin {оператор закончился} if Ch cmTZ {“;”} then Error (‘Требуется “;”’) else Sost:=7 end 20: Sost:=pop;
- 46. {блок кода для состояния 9, рассматривается отдельно, чтобы не загромождать основную процедуру} Case Ch of CmLeft,
- 47. Представленная процедура позволяет реализовать анализ конкретного языка, но можно пойти дальше, разработать структуру данных, позволяющую представлять
- 48. Пошаговая трассировка. Определение точки возникновения синтаксической ошибки. В предыдущей части мы рассмотрели процесс анализа исходного текста
- 49. Противники Игра становится гораздо интереснее, если выполнению миссии нашего героя (черепашки, кота, зайца) мешают противники. Например,
- 50. Многозадачный транслятор В отличие от однозадачного транслятора, многозадачный имеет не один динамический список с объектным кодом,
- 51. Список программ – Массив Task Игрок 0 Вход в объектный код Текущая команда Переменные 0 1
- 52. Представление сложных условий в операторе ветвления. Оператор присваивания При исполнении объектного кода возникает проблема хранения сложных
- 53. Разбор арифметических выражений, содержащих скобки В некоторых задачах необходимо вычислить значение арифметического выражения, возможно содержащего скобки.
- 54. Разделим эту задачу на две части: разбор и строительство дерева по арифметическому выражению без скобок, работа
- 55. Затем, когда все высокоприоритетные операции закончатся, проводим ту же операцию над сложением и вычитанием. Если один
- 56. procedure Arif(m:SetC); {Ищет только операции из множества m} var i:integer; tz:ref; f:boolean; begin f:=false; Repeat i:=1;
- 57. a+b*c-d/h procedure Arif(m:SetC); var i:integer; tz:ref; f:boolean; begin f:=false; Repeat i:=1; {Ищем только операции из множества
- 58. Function Calc(St:string):Ref; {Строит дерево по арифметическому выражению без скобок} begin{Calc} Arif(['*','/']);{обработать умнож. и деление} Arif(['+','-']); {теперь
- 59. Function CalcScob(st:string):ref; var f:boolean; i,j:integer; tz:ref; begin f:=false;CalcScob:=nil; Repeat i:=Pos( ')', st); {Ищем самую левую скобку
- 60. Дальнейшее развитие этой программы очевидно – переменные a, b, c, … можно заменить числами или создать
- 62. Звено, которое представляет оператор ветвления в объектном коде, имеет указатель на древовидную структуру. Именно она хранит
- 63. Разбор арифметических выражений методом рекурсивного спуска Для арифметического выражения дерево разбора можно описать так. В корне
- 64. var s:string;{исходное выражение} i:integer;{номер текущего символа} function Mul:longint; Forward; function Factor:longint; Forward; function Add:longint; {суммирует слагаемые}
- 65. function Mul:longint; {перемножает множители} var q,res:longint; c:char; Begin res:=Factor;{первый множитель} While s[i] in ['*','/'] do Begin
- 66. function Number:longint;{выделяет число} var res:longint; Begin res:=0; While (i res:=res*10+(ord(s[i])-ord('0')); i:=i+1 End; {While} Number:=res End; function
- 67. Арифметическое выражение представляет собой сумму нескольких слагаемых (возможно одно). Каждое слагаемое это произведение множителей (возможно одно).
- 68. function Add:longint; {суммирует слагаемые} Begin res:=Mul;{первое слагаемое} While s[i] in ['+','-'] do Begin c:=s[i]; i:=i+1; q:=Mul;{очередное
- 73. Динамический линейный однонаправленный список Основными проблемами классического статического списка на основе массива являются: неэффективное распределение памяти
- 74. Формирование списка Рассмотрим структуру данных. Для примера в списке будем хранить литеры (буквы), причем признаком конца
- 75. Procedure CreateList(var inz:ref); Var tz:ref; a:char; Begin New(inz); tz:=Inz; Read(a);tz^.Lit:=a; {дополнительный указатель tz потребовался, так как
- 76. Вывод списка. Встаем на начало списка (inz), двигаемся по нему, переходя к следующему элементу (поле Next)
- 77. Поиск элемента в списке. Одна из важнейших операций в программировании. Встаем на начало списка (inz), двигаемся
- 78. Вставка элемента в список. В отличие от статического списка, в котором для вставки элемента необходимо сместить
- 79. б) вставка перед текущим. Пусть tz указывает на некоторый элемент списка, перед которым необходимо разместить новое
- 80. ‘.’ nil Inz a Дан линейный динамический список, вставить в нем букву ‘a’ после буквы ‘b’.
- 81. Удаление элемента из списка. В отличие от статического списка, в котором для удаление элемента необходимо сместить
- 82. б) удаление текущего. Пусть tz указывает на некоторый элемент списка, который нам необходимо удалить. Опять кажется,
- 83. Дан линейный динамический список, удалить в нем все буквы ‘a’. ‘.’ nil b Procedure DelCur(tz:ref); Var
- 84. Динамический линейный однонаправленный кольцевой список с заглавным элементом Основные проблемы классического динамического линейного списка: наличие нескольких
- 85. Procedure CreateRing(var inz:ref); Var tz:ref; a:char; Begin {создадим заглавное звено} New(inz); tz:=Inz; repeat New(tz^.next);{создадим новое звено}
- 86. Вывод списка Встаем на начало списка (inz), двигаемся по нему, переходя к следующему элементу (поле Next)
- 88. Скачать презентацию
Содержание:
Транслятор
Интегрированная среда
Общий алгоритм работы транслятора
Сканер
Грамматика языка
Метод рекурсивного спуска
Оператор ветвления
Генератор кода
Интерпретатор объектного
Содержание:
Транслятор
Интегрированная среда
Общий алгоритм работы транслятора
Сканер
Грамматика языка
Метод рекурсивного спуска
Оператор ветвления
Генератор кода
Интерпретатор объектного
Конечные автоматы
Описание языков с использованием графов
Пошаговая трассировка
Противники
Многозадачный транслятор
Представление сложных условий в операторе ветвления
Разбор арифметических выражений, содержащих скобки
Динамический линейный однонаправленный список
Транслятор – это специальная программа, которая переводит исходную программу в эквивалентную
Транслятор – это специальная программа, которая переводит исходную программу в эквивалентную
Если транслятор переводит программу на машинный язык, то он называется компилятор. Интерпретатор же, переводит программу на некоторый промежуточный язык, удобный для специально созданной виртуальной машины. Виртуальная машина – это специальная программа, созданная для выполнения особого набора команд. Каждая команда сначала считывается, затем определяется ее тип, после этого она выполняется.
Более просто реализовать интерпретатор, так как не придется опускаться до низкоуровневого кодирования на машинном языке. Рассмотрим основные части Интегрированной среды, созданной для реализации нашего языка программирования.
Интегрированная среда содержит:
Текстовый редактор – в нем пользователь будет набирать исходный
Интегрированная среда содержит:
Текстовый редактор – в нем пользователь будет набирать исходный
Игровое поле – на нем располагаются предметы сбора, препятствия, противники и т.д.
Меню – система управления средой (запуск программы, выход и т.д.)
Транслятор – переводит программу из текстового вида (набрал пользователь) в объектный вид (особый список), удобный для исполнения.
Интегрированная среда
Исполнитель
Предмет сбора
Меню
Текстовый редактор
Препятствие
Меню загрузки
Количество предметов
Игровое поле
Интегрированная среда
Исполнитель
Предмет сбора
Меню
Текстовый редактор
Препятствие
Меню загрузки
Количество предметов
Игровое поле
Генератор кода
Общий алгоритм работы транслятора
СКАНЕР
…
ВПРАВО;
ВЗЯТЬ;
ВНИЗ;
…
Интерпретатор
Матрица поля
cmRight
cmTake
cmLeft
Исходный текст программы
Сканер – разбивает текст
Генератор кода
Общий алгоритм работы транслятора
СКАНЕР
…
ВПРАВО;
ВЗЯТЬ;
ВНИЗ;
…
Интерпретатор
Матрица поля
cmRight
cmTake
cmLeft
Исходный текст программы
Сканер – разбивает текст
Генератор кода – преобразует лексемы в список
Интерпретатор – исполняет объектный код
ВПРАВО
ВЗЯТЬ
ВНИЗ
Сканер – лексический анализатор, который выделяет лексемы из исходного текста программы.
Сканер – лексический анализатор, который выделяет лексемы из исходного текста программы.
Таблица переменных и их типов;
Таблица констант;
Возможно формирование таблицы типов.
ПРОГРАММА ТЕСТ;
ПЕРЕМЕННЫЕ И:ЦЕЛЫЙ;
НАЧАЛО
НАЧАТЬ_С 0 0 2;
ДЛЯ И=1 ДО
ПРОГРАММА ТЕСТ;
ПЕРЕМЕННЫЕ И:ЦЕЛЫЙ;
НАЧАЛО
НАЧАТЬ_С 0 0 2;
ДЛЯ И=1 ДО
НАЧАЛО
ВЗЯТЬ;
ВПРАВО;
КОНЕЦ;
КОН_ДЛЯ;
ЕСЛИ КОЛ_БРЕВЕН>=3
ТОГДА СОЗДАТЬ МОСТ;
ВНИЗ;
ПОСТАВИТЬ МОСТ;
ВНИЗ; ВПРАВО;
ВЗЯТЬ;
ВНИЗ; ВНИЗ;
ПОЛОЖИТЬ РЫБУ;
КОНЕЦ;
Рассмотрим процесс исполнения программы в Интегрированной среде и отображения процесса исполнения на игровом поле.
Как можно заметить, некоторым командам исходной программы соответствуют свои действия исполнителя: переместиться, взять предмет, построить мост и т.д.
Сканер
Как уже говорилось ранее, сканер – это лексический анализатор, предназначенный
Сканер
Как уже говорилось ранее, сканер – это лексический анализатор, предназначенный
Например, пусть имеется некоторая программа:
ПРОГРАММА ИМЯ;
ПЕРЕМЕННЫЕ
А, В: ЦЕЛЫЙ;
НАЧАЛО
А:=5;
…
После начала работы сканер будет выделять лексемы в следующем порядке: «ПРОГРАММА». Получив ее, генератор кода проверит лексему по специальной таблице команд. Генератор кода знает, что за этой лексемой должен следовать идентификатор. Если его нет, то, значит, возникла ошибка. Получив лексему «ПЕРЕМЕННЫЕ», генератор кода будет считывать идентификаторы переменных и помещать их в специальный временный буфер. Процесс будет продолжаться до тех пор, пока не появится лексема ”:”. Ее появление означает начало объявления типа. Все имена переменных переписываются из временного буфера в специальную таблицу имен переменных, где хранится: имя переменной, ее тип, текущее значение. Для простоты можно рассмотреть только целые переменные.
Type
Str_15=string[15];
tVarName=array[1..50] of Str_15;
{Тип временного буфера имен переменных}
tVar=record {Тип элемента таблицы
Type
Str_15=string[15];
tVarName=array[1..50] of Str_15;
{Тип временного буфера имен переменных}
tVar=record {Тип элемента таблицы
Name:Str_15; {Имя переменной}
Znach:integer;{Ее текущее значение}
Type_:Ident; {Тип переменной}
end;
tVarM=array[1..50] of tVar; {Тип таблицы имен переменных}
Var
VarN:tVarM;{Таблица имен переменных}
Рассмотрим подпрограмму GetLex, которая непосредственно выделяет лексемы из входного файла, и помещает лексему в глобальную переменную Ch.
Function GetLex:Ident;{Ident –перечислимый тип, содержит}
var i,Code:integer; {все лексемы языка}
ii:Ident;
begin
While
Function GetLex:Ident;{Ident –перечислимый тип, содержит}
var i,Code:integer; {все лексемы языка}
ii:Ident;
begin
While
ReadLn(f,st);{строчки файла}
i:=1;
while st[i]=' ' do {удаляем лишние пробелы}
inc(i);
delete(st,1,i-1);
i:=1;
case st[1] of {анализируем первый символ}
'<','>': begin
if st[2] in ['>','=']
then i:=2
else i:=1;
Lex:=Copy(st,1,i);
Delete(st,1,i);
end;
Сканер определяет, что обнаружен символ ”<”, но пока это ничего не значит, так как еще не известно, что следует за ним. Может далее идет символ “=”, а он существенно меняет смысл знака “<”. Поэтому, программа проверяет второй символ. Вырезанная лексема, помещается в переменную Lex. Далее в специальном цикле, будет просматриваться таблица идентификаторов и в ней выбираться соответствующий лексеме идентификатор.
':',';',',','=': {Здесь выделяются однознаковые лексемы}
begin
Lex:=Copy(st,1,1);
Delete(st,1,1);
end;
'0'..'9':begin {Здесь
':',';',',','=': {Здесь выделяются однознаковые лексемы}
begin
Lex:=Copy(st,1,1);
Delete(st,1,1);
end;
'0'..'9':begin {Здесь
while st[i] in ['0'..'9','.'] do
inc(i);
Lex:=Copy(st,1,i-1);
Val(Lex,LexNum,code);
Delete(st,1,i-1);
GetLex:=cmNumber;
exit;
end;
else {Если ничего из выше перечисленного нет, то это}
if st[1] in ID {идентификатор. ID – множество литер,}
then begin {из которого может строиться имя}
while st[i] in Id do
inc(i);
Lex:=Copy(st,1,i-1);
Delete(st,1,i-1);
End
Else Error(‘Недопустимый символ ’+Lex);
end;{case}
Теперь в переменной Lex хранится лексема в строковом виде. Однако работать с ней в таком виде очень неудобно. Поэтому, мы введем специальный перечислимый тип Ident. В нем будут перечислены все возможные типы идентификаторов. Порядок следования имен в типе Ident должен полностью соответствовать порядку следования имен в массиве MainLex
ii:=cmProg; {Начинаем с первого идентификатора}
while (MainLex[ii]<>Lex)and(byte(ii) inc(ii); {пока
ii:=cmProg; {Начинаем с первого идентификатора}
while (MainLex[ii]<>Lex)and(byte(ii)
GetLex:=ii {возвращаем код идентификатора}
end;
Рассмотрим объявление типов
Type Ident = (cmProg, cmIf, cmThen, cmElse, cmEndIf,
cmBegin, cmEnd, cmFor, cmTo, cmInt, cmTZ, cmTT,
cmZP,cmLeft, cmRight, cmEqu, cmNumber,cmLess,
cmMore,cmNotEqu,cmLessEQU, cmMoreEqu, cmIdent);
const MaxLex=22;
MainLex:array[ident] of Str_15= ('ПРОГРАММА','ЕСЛИ','ТОГДА','ИНАЧЕ', 'КОН_ЕСЛИ', 'НАЧАЛО', 'КОНЕЦ', 'ДЛЯ', 'ДО', 'ЦЕЛЫЙ', ';', ':', ',', 'ВЛЕВО', 'ВПРАВО','=','','<','>', '<>','<=','>=', '');
Коду CmProg соответствует слово ‘ПРОГРАММА’, и если, найденное и выделенное слово “ПРОГРАММА”, совпадет с элементом списка массива MainLex, то цикл прервется:
while (MainLex[ii]<>Lex)and(byte(ii)
а переменная ii будет равна коду cmProg.
Самым последним значением в перечислимом типе Ident должно быть значение cmIdent – идентификатор. Это значение не имеет эквивалента в строковом массиве MainLex.
Грамматика языка
Прежде, чем создавать генератор кода, необходимо разработать язык исходной
Грамматика языка
Прежде, чем создавать генератор кода, необходимо разработать язык исходной
Входной язык принято описывать специальным образом. Существует несколько способов описания:
Описание с помощью БНФ (нормальные формы Бекуса Наура)
<идентификатор>::=<буква>|<идентификатор><цифра>|<идентификатор><буква>
<константа>::=<знак>|<цифра>|<точка>|<константа>
знак “|” означает ИЛИ, “::=” означает “ПО ОПРЕДЕЛЕНИЮ ЕСТЬ”
Существует два способа разбора языков: восходящий и нисходящий. Мы только что
Существует два способа разбора языков: восходящий и нисходящий. Мы только что
Метод рекурсивного спуска
Пусть имеется грамматика, описывающая некоторый язык:
<программа>::=ПРОГРАММА <имя;>|<раздел переменных><тело
Метод рекурсивного спуска
Пусть имеется грамматика, описывающая некоторый язык:
<программа>::=ПРОГРАММА <имя;>|<раздел переменных><тело
<раздел переменных>::= <имя>|<, имя> <:> <тип переменной;>|<раздел переменных>
{повтор «раздел переменных» в правой части говорит о том, что описание переменных может повторяться}
<тип переменной>::=<ЦЕЛЫЕ>|<ДРОБНЫЕ>|<СИМВОЛ>
<имя>::=<буква>|<имя> <цифра>|<имя> <буква>
<тело программы>::=<НАЧАЛО> <оператор> <КОНЕЦ> <.>
<оператор>::=<ВЛЕВО><;>|<ВПАРВО><;>|<ВВЕРХ><;>| <ВНИЗ><;>|<оператор ветвления><;>| <оператор цикла><;>|<оператор>
Не буду описывать весь язык, предлагаю самостоятельно описать в БНФ оператор ветвления (предусмотреть одну и две ветки, простой и составной оператор на них), а также два вида циклов: аналоги паскалевских For и While.
В описании языка участвовали два типа символов:
те, которые написаны большими буквами, называются терминальными и непосредственно используются в программе как операторы или ключевые слова;
те, которые написаны маленькими буквами, называются нетерминальными и непосредственно в программе не используются, однако, за каждый из них будет отвечать своя подпрограмма. Вспомните, мы говорим «в программе есть оператор ветвления», причем можем не уточнять какой именно, полный или сокращенный. Термин «оператор ветвления» - это и есть нетерминальный символ, он состоит из терминальных: «ЕСЛИ», «ТОГДА», «ИНАЧЕ».
ПРОГРАММА МОЕ_ТВОРЕНИЕ;
У, И, Х: ЦЕЛОЕ;
НАЧАЛО
ВЛЕВО;
ВПРАВО;
ДЛЯ И=1 ДО
ПРОГРАММА МОЕ_ТВОРЕНИЕ;
У, И, Х: ЦЕЛОЕ;
НАЧАЛО
ВЛЕВО;
ВПРАВО;
ДЛЯ И=1 ДО
НАЧАЛО
ВЛЕВО;
ВПРАВО;
КОНЕЦ;
ЕСЛИ Х<5 {оператор ветвления}
ТОГДА НАЧАЛО {ветка «Да», составной оператор}
ВЛЕВО;
ВПРАВО;
КОНЕЦ
ИНАЧЕ ВЛЕВО; {ветка «Нет», простой оператор}
КОН_ЕСЛИ; {конец оператора ветвления}
КОНЕЦ. {конец программы}
Сравните описание языка и программу на этом языке. Очень важно понять, как из описания языка появляется программа. Наш интерпретатор будет делать наоборот, по имеющейся программе будет определять соответствует она грамматике языка или нет.
Итак, начнем… Первым ключевым словом в программе должно быть слово «ПРОГРАММА», Затем возможен раздел описания переменных или тело программы. Нашей первой строке грамматике в БНФ будет соответствовать отдельная процедура.
Procedure progr; {считаем, что лексема уже считана в Ch}
begin
if Ch<>cmProg
Procedure progr; {считаем, что лексема уже считана в Ch}
begin
if Ch<>cmProg
then Error('Требуется слово ПРОГРАММА')
else begin
Ch:=GetLex; {Считать очередную лексему}
if Ch<>cmIdent {Если не «имя»,то ошибка}
then Error('Требуется имя программы')
else begin
Ch:=GetLex;
if Ch<>cmTZ then Error('Требуется «;»');
Ch:=GetLex;
end
end
end;
В самой программе данная процедура вызывается так:
Ch:=GetLex;{считать первую лексему}
Progr; {проанализировать раздел имени программы}
if Ch=cmIdent {если лексема=идентификатор, то это}
Then RazdelVar;{раздел описания переменных}
if ch=cmBegin {Если лексема=НАЧАЛО, то разобрать}
then Operator(Last); {тело программы}
За каждый раздел (описания переменных и тело программы) отвечает своя процедура, только она знает, как должен выглядеть этот раздел.
procedure RazdelVar;
var i:integer;
begin
Repeat {первый цикл нужен, так как возможно несколько
групп
procedure RazdelVar;
var i:integer;
begin
Repeat {первый цикл нужен, так как возможно несколько
групп
Repeat {второй цикл идет до “:”, выделяет имена переменных}
if ch=cmIdent {Если это имя, то запомнить его}
then begin
inc (NumbV); VarName[NumbV]:=Lex;
end;
Ch:=GetLex;
if not(Ch in [cmTT,cmZP]){cmTT=’:’, cmZP=’,’}
then Error(‘Требуется :’)
else if Ch=cmZP then Ch:=GetLex;
until Ch=cmTT;{закончить, когда дойдем до “:”}
Ch:=GetLex;
if not (Ch in[cmInt]){если не указан тип, то ошибка}
Ch:=GetLex;
if not (Ch in[cmInt]){если не указан тип, то ошибка}
else begin
{переписываем найденные имена в таблицу имен переменных}
for i:=1 to NumbV do
begin
inc(NumbVar);
VarN[NumbVar].Name:=VarName[i];
VarN[NumbVar].Type_:=Ch; {cmInt}
VarN[NumbVar].Znach:=0;
end;
NumbV:=0;
end;
Ch:=GetLex;
if (Ch <>cmTZ)then Error(‘Требуется ;’)
else Ch:=GetLex;
until Ch=cmBegin {Раздел описания переменных закончится словом «НАЧАЛО», а это уже не «наша» компетенция}
end;
Repeat
Repeat
if ch=cmIdent
then begin
inc (NumbV);VarName[NumbV]:=Lex;
end;
Ch:=GetLex;
Repeat
Repeat
if ch=cmIdent
then begin
inc (NumbV);VarName[NumbV]:=Lex;
end;
Ch:=GetLex;
then Error(‘Требуется :’)
else if Ch=cmZP then Ch:=GetLex;
until Ch=cmTT;{закончить, когда дойдем до “:”}
Ch:=GetLex;
if not (Ch in[cmInt])
then Error('Требуется указать тип переменной')
else begin
for i:=1 to NumbV do
begin
inc(NumbVar);
VarN[NumbVar].Name:=VarName[i];
VarN[NumbVar].Type_:=Ch; {cmInt}
VarN[NumbVar].Znach:=0;
end;
NumbV:=0;
end;
Ch:=GetLex;
if (Ch <>cmTZ)then Error(‘Требуется ;’)
else Ch:=GetLex;
until Ch=cmBegin
А, В, С: ЦЕЛЫЕ;
Х: ДРОБНЫЕ;
НАЧАЛО
VarName
1 2 3 4 5 6
VarN
1 2 3 4 5 6
Lex
А
Ch
cmIdent
Repeat
Repeat
if ch=cmIdent
then begin
inc (NumbV);VarName[NumbV]:=Lex;
end;
Ch:=GetLex;
if not(Ch in [cmTT,cmZP])
then Error(‘Требуется :’)
else if Ch=cmZP then Ch:=GetLex;
until Ch=cmTT;{закончить, когда дойдем до “:”}
Ch:=GetLex;
if not (Ch in[cmInt])
then Error('Требуется указать тип переменной')
else begin
for i:=1 to NumbV do
begin
inc(NumbVar);
VarN[NumbVar].Name:=VarName[i];
VarN[NumbVar].Type_:=Ch; {cmInt}
VarN[NumbVar].Znach:=0;
end;
NumbV:=0;
end;
Ch:=GetLex;
if (Ch <>cmTZ)then Error(‘Требуется ;’)
else Ch:=GetLex;
until Ch=cmBegin
Мы обнаружили очередной идентификатор (имя переменной), занесем его в массив VarName
Repeat
Repeat
if ch=cmIdent
then begin
inc (NumbV);VarName[NumbV]:=Lex;
end;
Ch:=GetLex;
if not(Ch in [cmTT,cmZP])
then Error(‘Требуется :’)
else if Ch=cmZP then Ch:=GetLex;
until Ch=cmTT;{закончить, когда дойдем до “:”}
Ch:=GetLex;
if not (Ch in[cmInt])
then Error('Требуется указать тип переменной')
else begin
for i:=1 to NumbV do
begin
inc(NumbVar);
VarN[NumbVar].Name:=VarName[i];
VarN[NumbVar].Type_:=Ch; {cmInt}
VarN[NumbVar].Znach:=0;
end;
NumbV:=0;
end;
Ch:=GetLex;
if (Ch <>cmTZ)then Error(‘Требуется ;’)
else Ch:=GetLex;
until Ch=cmBegin
Читаем следующий идентификатор. Если это не запятая или двоеточие, то выведем сообщение об ошибке.
,
cmZP
А, В, С: ЦЕЛЫЕ;
Х: ДРОБНЫЕ;
НАЧАЛО
Repeat
Repeat
if ch=cmIdent
then begin
inc (NumbV);VarName[NumbV]:=Lex;
end;
Ch:=GetLex;
if not(Ch in [cmTT,cmZP])
then Error(‘Требуется :’)
else if Ch=cmZP then Ch:=GetLex;
until Ch=cmTT;{закончить, когда дойдем до “:”}
Ch:=GetLex;
if not (Ch in[cmInt])
then Error('Требуется указать тип переменной')
else begin
for i:=1 to NumbV do
begin
inc(NumbVar);
VarN[NumbVar].Name:=VarName[i];
VarN[NumbVar].Type_:=Ch; {cmInt}
VarN[NumbVar].Znach:=0;
end;
NumbV:=0;
end;
Ch:=GetLex;
if (Ch <>cmTZ)then Error(‘Требуется ;’)
else Ch:=GetLex;
until Ch=cmBegin
Читаем следующий идентификатор. Это должно быть имя переменной. Занесем его в массив
В
cmIdent
А, В, С: ЦЕЛЫЕ;
Х: ДРОБНЫЕ;
НАЧАЛО
Repeat
Repeat
if ch=cmIdent
then begin
inc (NumbV);VarName[NumbV]:=Lex;
end;
Ch:=GetLex;
if not(Ch in [cmTT,cmZP])
then Error(‘Требуется :’)
else if Ch=cmZP then Ch:=GetLex;
until Ch=cmTT;{закончить, когда дойдем до “:”}
Ch:=GetLex;
if not (Ch in[cmInt])
then Error('Требуется указать тип переменной')
else begin
for i:=1 to NumbV do
begin
inc(NumbVar);
VarN[NumbVar].Name:=VarName[i];
VarN[NumbVar].Type_:=Ch; {cmInt}
VarN[NumbVar].Znach:=0;
end;
NumbV:=0;
end;
Ch:=GetLex;
if (Ch <>cmTZ)then Error(‘Требуется ;’)
else Ch:=GetLex;
until Ch=cmBegin
Дальше процесс идет аналогично: читаются имена переменных и запятые и так до появления лексемы ‘:’. Внутренний цикл прерывается
,
cmZP
А, В, С: ЦЕЛЫЕ;
Х: ДРОБНЫЕ;
НАЧАЛО
С
cmIdent
А, В, С: ЦЕЛЫЕ;
Х: ДРОБНЫЕ;
НАЧАЛО
:
cmITT
А, В, С: ЦЕЛЫЕ;
Х: ДРОБНЫЕ;
НАЧАЛО
Repeat
Repeat
if ch=cmIdent
then begin
inc (NumbV);VarName[NumbV]:=Lex;
end;
Ch:=GetLex;
if not(Ch in [cmTT,cmZP])
then Error(‘Требуется :’)
else if Ch=cmZP then Ch:=GetLex;
until Ch=cmTT;{закончить, когда дойдем до “:”}
Ch:=GetLex;
if not (Ch in[cmInt])
then Error('Требуется указать тип переменной')
else begin
for i:=1 to NumbV do
begin
inc(NumbVar);
VarN[NumbVar].Name:=VarName[i];
VarN[NumbVar].Type_:=Ch; {cmInt}
VarN[NumbVar].Znach:=0;
end;
NumbV:=0;
end;
Ch:=GetLex;
if (Ch <>cmTZ)then Error(‘Требуется ;’)
else Ch:=GetLex;
until Ch=cmBegin
Считываем очередную лексему – это описание целого типа, если нет, то – ошибка. Переносим имена переменных из массива VarName в VarN
ЦЕЛЫЕ
cmInt
А, В, С: ЦЕЛЫЕ;
Х: ДРОБНЫЕ;
НАЧАЛО
Repeat
Repeat
if ch=cmIdent
then begin
inc (NumbV);VarName[NumbV]:=Lex;
end;
Ch:=GetLex;
if not(Ch in [cmTT,cmZP])
then Error(‘Требуется :’)
else if Ch=cmZP then Ch:=GetLex;
until Ch=cmTT;{закончить, когда дойдем до “:”}
Ch:=GetLex;
if not (Ch in[cmInt])
then Error('Требуется указать тип переменной')
else begin
for i:=1 to NumbV do
begin
inc(NumbVar);
VarN[NumbVar].Name:=VarName[i];
VarN[NumbVar].Type_:=Ch; {cmInt}
VarN[NumbVar].Znach:=0;
end;
NumbV:=0;
end;
Ch:=GetLex;
if (Ch <>cmTZ)then Error(‘Требуется ;’)
else Ch:=GetLex;
until Ch=cmBegin
Считываем очередную лексему – это ‘;’, если нет, то- ошибка. Следующая лексема должна быть НАЧАЛО, если нет, то продолжим разбор раздела переменных
А, В, С: ЦЕЛЫЕ;
Х: ДРОБНЫЕ;
НАЧАЛО
;
cmTZ
А, В, С: ЦЕЛЫЕ;
Х: ДРОБНЫЕ;
НАЧАЛО
X
cmIdent
А, В, С: ЦЕЛЫЕ;
Х: ДРОБНЫЕ;
НАЧАЛО
:
cmTT
А, В, С: ЦЕЛЫЕ;
Х: ДРОБНЫЕ;
НАЧАЛО
ДРОБНЫЕ
cmReal
Repeat
Repeat
if ch=cmIdent
then begin
inc (NumbV);VarName[NumbV]:=Lex;
end;
Ch:=GetLex;
if not(Ch in [cmTT,cmZP])
then Error(‘Требуется :’)
else if Ch=cmZP then Ch:=GetLex;
until Ch=cmTT;{закончить, когда дойдем до “:”}
Ch:=GetLex;
if not (Ch in[cmInt])
then Error('Требуется указать тип переменной')
else begin
for i:=1 to NumbV do
begin
inc(NumbVar);
VarN[NumbVar].Name:=VarName[i];
VarN[NumbVar].Type_:=Ch; {cmInt}
VarN[NumbVar].Znach:=0;
end;
NumbV:=0;
end;
Ch:=GetLex;
if (Ch <>cmTZ)then Error(‘Требуется ;’)
else Ch:=GetLex;
until Ch=cmBegin
Встретив лексему НАЧАЛО, цикл разбора раздела описания переменных заканчивается. Дальше будет работать другая подпрограмма – разбор операторов.
А, В, С: ЦЕЛЫЕ;
Х: ДРОБНЫЕ;
НАЧАЛО
НАЧАЛО
cmBegin
Сложнее разобрать тело программы.
<тело программы>::=<НАЧАЛО> <оператор> <КОНЕЦ> <.>
<оператор>::=<ВЛЕВО><;>|<ВПАРВО><;>|<ВВЕРХ><;>|
<ВНИЗ><;>|
<оператор ветвления><;>| <оператор цикла><;>|<оператор>
Оно
Сложнее разобрать тело программы.
<тело программы>::=<НАЧАЛО> <оператор> <КОНЕЦ> <.>
<оператор>::=<ВЛЕВО><;>|<ВПАРВО><;>|<ВВЕРХ><;>|
<ВНИЗ><;>|
<оператор ветвления><;>| <оператор цикла><;>|<оператор>
Оно
Для каждого оператора есть своя начальная и завершающая лексема:
Для каждого оператора есть своя начальная и завершающая лексема:
Рассмотрим подпрограмму, которая разбирает тело программы.
В цикле пока не встретится
Рассмотрим подпрограмму, которая разбирает тело программы.
В цикле пока не встретится
Считать очередную лексему в переменную Ch;
Case Ch of
cmLeft: обработать команду влево; cmRight: обработать команду вправо; cmIf: обработать оператор ветвления;
end;
За обработку каждого оператора отвечает своя подпрограмма, она создает новое звено, вставляет его в цепочку объектного кода, настраивает его параметры (например, начальное и конечное значение счетчика цикла).
Procedure Operator(var Last:pNode);forward; {это описание позволит вам ссылаться на подпрограмму, которая будет описана позже}
…{здесь необходимо описать подпрограммы разбора различных операторов, некоторые из них (например, оператор ветвления) потребуют вызова еще неописанной процедуры Operator. А она, в свою очередь, потребует вызова процедуры разбора оператора ветвления.}
Procedure Operator(var Last:pNode); {Переменная Last используется как указатель на последнее звено
Procedure Operator(var Last:pNode); {Переменная Last используется как указатель на последнее звено
begin
repeat {цикл пока не дошли до лексемы КОНЕЦ}
Ch:=GetLex; {считать очередную лексему}
case Ch of
cmIf: OperIf(Last);{Если это оператор ветвления, то разобрать его}
cmFor: OperFor(Last);{Если это цикл, то разобрать его}
cmLeft:begin {Если это команда ВЛЕВО, то создать звено }
AddElem(Last,NewElem(cmLeft));{и разместить его в}
Ch:=GetLex;{цепочке объектного кода}
end;
cmRight:begin
AddElem(Last,NewElem(cmRight));
Ch:=GetLex;
end;
end;{case}
if Ch<>cmTZ {Если очередная лексема не “;”, то ошибка}
then Error('Требуется «;»');
until Ch=cmEnd; {Закончить, если «КОНЕЦ»}
end;
Из примера видно, что довольно нелогичная структура составного оператора паскаля begin… end становится более логичной. Эту подпрограмму Operator можно использовать не только для разбора основного тела программы, но и для разбора операторов веток «Да» и «Нет» оператора ветвления, тела цикла… Ведь составной оператор (тело цикла) можно рассматривать как новое маленькое тело программы. Поэтому подпрограмма «оператор ветвления» может вызывать подпрограмму «оператор», а она – его, то есть на лицо косвенная рекурсия.
Генератор кода
Генератор кода – это часть транслятора, которая отвечает за
Генератор кода
Генератор кода – это часть транслятора, которая отвечает за
В виде цепочки объектов (для 3 года обучения);
В виде цепочки динамических звеньев. Этот способ менее удобен, но, как говорится, «На безрыбье и рак - рыба» (см. Динамические списки).
Каждый оператор исходного языка будет однозначно представлен записью с несколькими полями. Рассмотрим самый простой случай, когда все поля записи хранятся вне зависимости от типа звена (например, команде «ВЛЕВО» указатель на ветку «Да» не нужен).
pNode=^tNode; {pNode – указатель на объект-звено}
tNode=record {Само звено}
Typ:Ident; { Тип звена, говорит интерпретатору что делать}
Then_,Else:pNode;{Указатели на цепочки операторов веток «Да» и «Нет»}
Next: pNode; {Указатель на следующее звено}
op1,op2:pZnach; {два операнда из условия оператора ветвления}
Operation:Ident;{операция, использованная в условии опер. ветв.}
ForI:integer; {Указатель на счетчик цикла For}
end;
Как видно из примера, многие поля не будут использоваться в каждом звене, как этого избежать, мы узнаем позже. Обратите внимание на то, что в паскале есть особый тип – запись с вариантами, он более эффективен в данном случае.
Type pObject=^tObject;
tPoint=record
Case Target:boolean of
True: (tp:pObject);
Type pObject=^tObject;
tPoint=record
Case Target:boolean of
True: (tp:pObject);
End;
Данная структура называется запись с вариантами, она позволяет использовать несколько групп полей, которые не нужны одновременно (что позволяет уменьшить размер переменной и сэкономить память). У данной записи есть обязательное поле Target (существует всегда). В зависимости от его значения появляются другие поля:
Если Target=true, то существует поле tp – указатель на объект, который мы атакуем.
Если Target=false, то существуют два поля tx и ty – координаты цели (например, куда ехать)
Одновременно tp и tx, ty не могут существовать!
Линейные команды, которые выполняются последовательно – одна за другой, хранятся в
Линейные команды, которые выполняются последовательно – одна за другой, хранятся в
У оператора ветвления есть заглавное звено, которое хранит условие и два указателя: на ветку «да» и ветку «нет». Каждая ветка – это аналогичный список, который может состоять из одного или нескольких звеньев. Если оператор сокращенный, то указатель Else_=nil. Для удобства работы списки чаще всего делают с заглавным элементом (на рисунке не показано)
У оператора цикла есть управляющее звено, которое хранит: индекс переменной-счетчика, начальное и конечное значение счетчика, указатель на список операторов, являющихся телом цика. Этот список может содержать любые операторы, в том числе и другой цикл.
repeat
Ch:=GetLex;
case Ch of
cmIf: OperIf(Last);
cmFor: OperFor(Last);
repeat
Ch:=GetLex;
case Ch of
cmIf: OperIf(Last);
cmFor: OperFor(Last);
AddElem(Last,NewElem(cmLeft));
Ch:=GetLex;
end;
cmRight:begin
AddElem(Last,NewElem(cmRight));
Ch:=GetLex;
end;
cmTake:begin
AddElem(Last,NewElem(cmTake));
Ch:=GetLex;
end;
end;{case}
if Ch<>cmTZ
then Error('Требуется «;»');
until Ch=cmEnd;
ВЛЕВО;
ВЗЯТЬ;
ЕСЛИ Х=0
ТОГДА ВПРАВО;
ИНАЧЕ НАЧАЛО
ВЛЕВО;
ВЗЯТЬ;
КОН_ЕСЛИ
Lex
ВЛЕВО
Ch
cmLeft
Мы обнаружили очередной идентификатор (ВЛЕВО), создадим звено, соответствующее команде, и разместим его в списке
Code
repeat
Ch:=GetLex;
case Ch of
cmIf: OperIf(Last);
cmFor: OperFor(Last); cmLeft:begin
AddElem(Last,NewElem(cmLeft));
Ch:=GetLex;
end;
cmRight:begin
AddElem(Last,NewElem(cmRight));
Ch:=GetLex;
end;
cmTake:begin
AddElem(Last,NewElem(cmTake));
Ch:=GetLex;
end;
end;{case}
if Ch<>cmTZ
then Error('Требуется «;»');
until Ch=cmEnd;
ВЛЕВО;
ВЗЯТЬ;
ЕСЛИ Х=0
ТОГДА ВПРАВО;
ИНАЧЕ НАЧАЛО
ВЛЕВО;
ВЗЯТЬ;
КОН_ЕСЛИ
;
cmTZ
Читаем очередной идентификатор (‘;’), если его не обнаружили – сообщаем об ошибке.
repeat
Ch:=GetLex;
case Ch of
cmIf: OperIf(Last);
cmFor: OperFor(Last); cmLeft:begin
AddElem(Last,NewElem(cmLeft));
Ch:=GetLex;
end;
cmRight:begin
AddElem(Last,NewElem(cmRight));
Ch:=GetLex;
end;
cmTake:begin
AddElem(Last,NewElem(cmTake));
Ch:=GetLex;
end;
end;{case}
if Ch<>cmTZ
then Error('Требуется «;»');
until Ch=cmEnd;
ВЛЕВО;
ВЗЯТЬ;
ЕСЛИ Х=0
ТОГДА ВПРАВО;
ИНАЧЕ НАЧАЛО
ВЛЕВО;
ВЗЯТЬ;
КОН_ЕСЛИ
ВЗЯТЬ
cmTake
Читаем очередной идентификатор (ВЗЯТЬ), создаем новое звено, размещаем его в списке, аналогично разбираем лексему ‘;’
repeat
Ch:=GetLex;
case Ch of
cmIf: OperIf(Last);
cmFor: OperFor(Last); cmLeft:begin
AddElem(Last,NewElem(cmLeft));
Ch:=GetLex;
end;
cmRight:begin
AddElem(Last,NewElem(cmRight));
Ch:=GetLex;
end;
cmTake:begin
AddElem(Last,NewElem(cmTake));
Ch:=GetLex;
end;
end;{case}
if Ch<>cmTZ
then Error('Требуется «;»');
until Ch=cmEnd;
ВЛЕВО;
ВЗЯТЬ;
ЕСЛИ Х=0
ТОГДА ВПРАВО;
ИНАЧЕ НАЧАЛО
ВЛЕВО;
ВЗЯТЬ;
КОН_ЕСЛИ
ЕСЛИ
cmIf
Читаем очередной идентификатор (ЕСЛИ), за его разбор отвечает своя отдельная процедура OperIf. Она разбирает условие и сохраняет его в звене, затем разбирает ветку ТОГДА и прицепляет ее к указателю Then_, если есть ветка ИНАЧЕ, то разбирает и ее
Then_
Else_
ВЛЕВО;
ВЗЯТЬ;
ЕСЛИ Х=0
ТОГДА ВПРАВО;
ИНАЧЕ НАЧАЛО
ВЛЕВО;
ВЗЯТЬ;
КОН_ЕСЛИ
ВЛЕВО;
ВЗЯТЬ;
ЕСЛИ Х=0
ТОГДА ВПРАВО;
ИНАЧЕ НАЧАЛО
ВЛЕВО;
ВЗЯТЬ;
КОН_ЕСЛИ
ВЛЕВО;
ВЗЯТЬ;
ЕСЛИ Х=0
ТОГДА ВПРАВО;
ИНАЧЕ НАЧАЛО
ВЛЕВО;
ВЗЯТЬ;
КОН_ЕСЛИ
ВПРАВО
cmRight
ВЛЕВО
cmLeft
ВЗЯТЬ
cmTake
Оператор ветвления
Procedure OperIf(var Last:pNode); {Анализ оператора ветвления}
Var pp:pNode;
begin
AddElem(Last,NewElem(cmIf)); {создать
Оператор ветвления
Procedure OperIf(var Last:pNode); {Анализ оператора ветвления}
Var pp:pNode;
begin
AddElem(Last,NewElem(cmIf)); {создать
{Процедура NewElem создает новое звено указанного типа, AddElem – вставляет созданное звено в цепочку объектного кода, смещает указатель Last так, чтобы он всегда указывал на последнее звено}
Uslovie(Last); {выделить условие, разместить его в созданном звене}
Ch:=GetLex;
if Ch<>cmThen {Если после условия нет ветки ТОГДА, то ошибка}
then Error('Требуется «ТОГДА»');
Ch:=GetLex; New(Last^.Then_); {Создать заглавный элемент ветки «Да»}
pp:=Last^.Then_;
if Ch=cmBegin {Если после лексемы «ТОГДА» идет слово НАЧАЛО, то}
then Operator(pp) {обработать составной оператор}
else SimpOper(pp); {иначе простой (без цикла repeat … until Ch=cmEnd)}
Ch:=GetLex;
if Ch=cmElse {анализ возможной ветки ИНАЧЕ}
then begin
Ch:=GetLex; New(Last^.Else_); pp:=Last^.Else_;
if Ch=cmBegin then Operator(pp) else SimpOper(pp);
Ch:=GetLex;
end;
if Ch<>cmEndIf then Error('Требуется Кон_если');
Ch:=GetLex;
end;
Каждое звено будет хранить одинаковые поля, часть из них вообще не
Каждое звено будет хранить одинаковые поля, часть из них вообще не
pNode=^tNode; {pNode – указатель на объект-звено}
tNode=record {Само звено}
Next: pNode; {Указатель на следующее звено}
Case Typ:Ident of {Тип звена, говорит интерпретатору что делать}
CmIf:( Then_, Else_: pNode; {Указатели на цепочки операторов веток «Да» и «Нет»}
op1,op2:pZnach;{два операнда из условия оператора ветвления}
Operation:Ident;{операция, использованная в условии опер. ветв.}
);
CmFor:(ForI: integer; {Указатель на счетчик цикла For}
Body: pNode; {Указатели на тело цикла}
nz,kz: pZnach;{начальное и конечное значение счетчика}
);
cmWhile: …
end;
Обращаю внимание на то, что некоторые поля не могут использоваться одновременно, их существование определяется значением поля Typ. Например, если Typ=cmIf, то есть поле Then_, но нет поля Body. Хотя пользователь может обратиться к этому полю, компилятор этой ошибки обнаружить не может. Оператор Case в записи может использоваться только в конце, после описания общих полей. Слово End ставится только одно для записи и оператора Case.
Поля op1,op2 имеют тип pZnach. Это тоже указатель на особую запись.
Поля op1,op2 имеют тип pZnach. Это тоже указатель на особую запись.
ЕСЛИ Х<У …
ЕСЛИ Х<0 …
ЕСЛИ 0<У …
Поэтому введен новый тип:
pZnach=^tZnach;
tZnach=record
p:integer;
f:boolean;{true - число, false номер в массиве переменных}
end;
Если флаг f=true, то поле р – это переменная, которая хранит значение числа, если f=false, то р является индексом массива имен переменных,.
Procedure OperIf(var Last:pNode);
Var pp:pNode;
begin
AddElem(Last,NewElem(cmIf));
Uslovie(Last);
Ch:=GetLex;
if Ch<>cmThen
then
Procedure OperIf(var Last:pNode);
Var pp:pNode;
begin
AddElem(Last,NewElem(cmIf));
Uslovie(Last);
Ch:=GetLex;
if Ch<>cmThen
then
Ch:=GetLex;
New(Last^.Then_);
pp:=Last^.Then_;
if Ch=cmBegin
then Operator(pp)
else SimpOper(pp)
Ch:=GetLex;
if Ch=cmElse
then begin
Ch:=GetLex; New(Last^.Else_);
pp:=Last^.Else_;
if Ch=cmBegin then Operator(pp)
else SimpOper(pp);
Ch:=GetLex;
end;
if Ch<>cmEndIf
then Error('Требуется Кон_если');
Ch:=GetLex;
end;
ЕСЛИ Х=0
ТОГДА ВПРАВО;
ИНАЧЕ НАЧАЛО
ВЛЕВО;
ВЗЯТЬ;
КОНЕЦ
КОН_ЕСЛИ
Lex
ЕСЛИ
Ch
cmIf
Last
Читаем очередную лексему ЕСЛИ, в результате вызываем процедуру разбора оператора ветвления OperIf
Then_
Else_
Procedure OperIf(var Last:pNode);
Var pp:pNode;
begin
AddElem(Last,NewElem(cmIf));
Uslovie(Last);
Ch:=GetLex;
if Ch<>cmThen
then Error('Требуется «ТОГДА»');
Ch:=GetLex;
New(Last^.Then_);
pp:=Last^.Then_;
if Ch=cmBegin
then Operator(pp)
else SimpOper(pp)
Ch:=GetLex;
if Ch=cmElse
then begin
Ch:=GetLex; New(Last^.Else_);
pp:=Last^.Else_;
if Ch=cmBegin then Operator(pp)
else SimpOper(pp);
Ch:=GetLex;
end;
if Ch<>cmEndIf
then Error('Требуется Кон_если');
Ch:=GetLex;
end;
Создаем основное звено оператора ЕСЛИ и вставляем его в динамический список, Last – указывает на последнее звено списка
Procedure OperIf(var Last:pNode);
Var pp:pNode;
begin
AddElem(Last,NewElem(cmIf));
Uslovie(Last);
Ch:=GetLex;
if Ch<>cmThen
then Error('Требуется «ТОГДА»');
Ch:=GetLex;
New(Last^.Then_);
pp:=Last^.Then_;
if Ch=cmBegin
then Operator(pp)
else SimpOper(pp)
Ch:=GetLex;
if Ch=cmElse
then begin
Ch:=GetLex; New(Last^.Else_);
pp:=Last^.Else_;
if Ch=cmBegin then Operator(pp)
else SimpOper(pp);
Ch:=GetLex;
end;
if Ch<>cmEndIf
then Error('Требуется Кон_если');
Ch:=GetLex;
end;
Далее разбираем условие и сохраняем его в звено оператора ЕСЛИ. Лучше всего в виде дерева ,в нашем случае в виде записи с тремя элементами: двумя операторами и кодом операции
X
cmIdent
ЕСЛИ Х=0
ТОГДА ВПРАВО;
ИНАЧЕ НАЧАЛО
ВЛЕВО;
ВЗЯТЬ;
КОНЕЦ
КОН_ЕСЛИ
Procedure OperIf(var Last:pNode);
Var pp:pNode;
begin
AddElem(Last,NewElem(cmIf));
Uslovie(Last);
Ch:=GetLex;
if Ch<>cmThen
then Error('Требуется «ТОГДА»');
Ch:=GetLex;
New(Last^.Then_);
pp:=Last^.Then_;
if Ch=cmBegin
then Operator(pp)
else SimpOper(pp)
Ch:=GetLex;
if Ch=cmElse
then begin
Ch:=GetLex; New(Last^.Else_);
pp:=Last^.Else_;
if Ch=cmBegin then Operator(pp)
else SimpOper(pp);
Ch:=GetLex;
end;
if Ch<>cmEndIf
then Error('Требуется Кон_если');
Ch:=GetLex;
end;
Читаем очередную лексему, если это не ТОГДА, то – ошибка, иначе – создаем заглавный элемент ветки «ДА» и, в зависимости от наличия или отсутствия НАЧАЛО, разбираем один оператор или много операторов.
ТОГДА
cmThen
ЕСЛИ Х=0
ТОГДА ВПРАВО;
ИНАЧЕ НАЧАЛО
ВЛЕВО;
ВЗЯТЬ;
КОНЕЦ
КОН_ЕСЛИ
Procedure OperIf(var Last:pNode);
Var pp:pNode;
begin
AddElem(Last,NewElem(cmIf));
Uslovie(Last);
Ch:=GetLex;
if Ch<>cmThen
then Error('Требуется «ТОГДА»');
Ch:=GetLex;
New(Last^.Then_);
pp:=Last^.Then_;
if Ch=cmBegin
then Operator(pp)
else SimpOper(pp)
Ch:=GetLex;
if Ch=cmElse
then begin
Ch:=GetLex; New(Last^.Else_);
pp:=Last^.Else_;
if Ch=cmBegin then Operator(pp)
else SimpOper(pp);
Ch:=GetLex;
end;
if Ch<>cmEndIf
then Error('Требуется Кон_если');
Ch:=GetLex;
end;
ВПРАВО
cmRight
Procedure OperIf(var Last:pNode);
Var pp:pNode;
begin
AddElem(Last,NewElem(cmIf));
Uslovie(Last);
Ch:=GetLex;
if Ch<>cmThen
then Error('Требуется «ТОГДА»');
Ch:=GetLex;
New(Last^.Then_);
pp:=Last^.Then_;
if Ch=cmBegin
then Operator(pp)
else SimpOper(pp)
Ch:=GetLex;
if Ch=cmElse
then begin
Ch:=GetLex; New(Last^.Else_);
pp:=Last^.Else_;
if Ch=cmBegin then Operator(pp)
else SimpOper(pp);
Ch:=GetLex;
end;
if Ch<>cmEndIf
then Error('Требуется Кон_если');
Ch:=GetLex;
end;
Определяем, простой или составной оператор идет по ветке «ДА», так как лексема не НАЧАЛО, то – простой, вызываем SimpOper, который создаст новое звено.
ЕСЛИ Х=0
ТОГДА ВПРАВО;
ИНАЧЕ НАЧАЛО
ВЛЕВО;
ВЗЯТЬ;
КОНЕЦ
КОН_ЕСЛИ
ИНАЧЕ
cmElse
Procedure OperIf(var Last:pNode);
Var pp:pNode;
begin
AddElem(Last,NewElem(cmIf));
Uslovie(Last);
Ch:=GetLex;
if Ch<>cmThen
then Error('Требуется «ТОГДА»');
Ch:=GetLex;
New(Last^.Then_);
pp:=Last^.Then_;
if Ch=cmBegin
then Operator(pp)
else SimpOper(pp)
Ch:=GetLex;
if Ch=cmElse
then begin
Ch:=GetLex; New(Last^.Else_);
pp:=Last^.Else_;
if Ch=cmBegin then Operator(pp)
else SimpOper(pp);
Ch:=GetLex;
end;
if Ch<>cmEndIf
then Error('Требуется Кон_если');
Ch:=GetLex;
end;
Читаем очередную лексему, если она не ИНАЧЕ, то оператор ветвления имеет не полную форму (без else), в противном случае разберем ветку.
ЕСЛИ Х=0
ТОГДА ВПРАВО;
ИНАЧЕ НАЧАЛО
ВЛЕВО;
ВЗЯТЬ;
КОНЕЦ
КОН_ЕСЛИ
НАЧАЛО
cmBegin
Procedure OperIf(var Last:pNode);
Var pp:pNode;
begin
AddElem(Last,NewElem(cmIf));
Uslovie(Last);
Ch:=GetLex;
if Ch<>cmThen
then Error('Требуется «ТОГДА»');
Ch:=GetLex;
New(Last^.Then_);
pp:=Last^.Then_;
if Ch=cmBegin
then Operator(pp)
else SimpOper(pp)
Ch:=GetLex;
if Ch=cmElse
then begin
Ch:=GetLex; New(Last^.Else_);
pp:=Last^.Else_;
if Ch=cmBegin then Operator(pp)
else SimpOper(pp);
Ch:=GetLex;
end;
if Ch<>cmEndIf
then Error('Требуется Кон_если');
Ch:=GetLex;
end;
Читаем очередную лексему, это НАЧАЛО – оператор составной. Создаем заглавный элемент списка ветки «НЕТ».
Интерпретатор объектного кода
После того, как трансляция прошла успешно, и объектный
Интерпретатор объектного кода
После того, как трансляция прошла успешно, и объектный
procedure Interpetator(p:pNode);
begin
While p<> nil do {пока не конец списка}
begin
procedure Interpetator(p:pNode);
begin
While p<> nil do {пока не конец списка}
begin
cmLeft,cmRight:write(MainLex[p^.Typ],' ');
cmIf: begin
writeln(MainLex[p^.Typ]); {вывести оператор ветвления}
Write('Then:');
Interpetator(p^.Then_); {разобрать ветку «Да»}
Write('Else:');
Interpetator(p^.Else_); {разобрать ветку «Нет»}
end;
cmFor: begin
writeln(MainLex[p^.Typ]);
Write('Тело Цикла');
Interpetator(p^.Body);
Writeln;
end;
end; {case}
p:=p^.next {Перейти к следующему звену}
end; {while}
end;
В реальной программе в интерпретаторе не будет команд write, а при выполнении команд взаимодействия с полем (влево, вправо, взять, положить) будет вызываться специальная подпрограмма, которая анимационно будет изображать процесс перемещения (взаимодействия) на игровом поле. Другие команды (цикл, ветвление и т.д.) не будут отображаться на экране, но будут менять состояние переменных и списков
Конечные автоматы
Конечный автомат представляет собой особый способ описания алгоритма, который
Конечные автоматы
Конечный автомат представляет собой особый способ описания алгоритма, который
Говорят, что конечный автомат допускает цепочку, если при ее анализе, начиная с начального состояния, функция D определена на каждом шаге и последнее состояние является заключительным.
Конечный автомат не допускает входную цепочку, если:
1) на каком-то шаге не определена функция D;
2) последнее состояние не является заключительным.
Пример. Конечный автомат, распознающий идентификатор.
K={0,1} множество состояний
A={' ', 'A'..'Z','a'..'z','0'..'9'} алфавит
S=0 начальное состояние
F={1} конечное состояние
Конечный автомат можно задавать не только таблицей, но и диаграммой переходов.
Описать конечный автомат, распознающий запись целого числа в десятичном виде.
В чем
Описать конечный автомат, распознающий запись целого числа в десятичном виде.
В чем
Есть контр примеры:
-1, +15.
Исправьте автомат!
Function IntA(s:string):boolean;
Var i, q :integer; f:boolean;
Begin
q:=0; i:=0; f:=true;
repeat
inc(i);
case q of
0: if s[i] in [‘0’..’9’]
then q:=1
else if s[i] in [‘+’,’-’]
then q:=2 else f:=false;
2: if s[i] in [‘0’..’9’]
then q:=1 else f:=false;
1: if not (s[i] in [‘0’..’9’])
then f:=false
end
until (not f)or(i>=length(s));
IntA:=f
End;
Есть ошибка!
Найдите ее!
Function IntA(s:string):boolean;
Var i, q :integer; f:boolean;
Begin
q:=0; i:=0; f:=true;
repeat
inc(i);
case q of
0: if s[i] in [‘0’..’9’]
then q:=1
else if s[i] in [‘+’,’-’]
then q:=2 else f:=false;
2: if s[i] in [‘0’..’9’]
then q:=1 else f:=false;
1: if not (s[i] in [‘0’..’9’])
then f:=false
end
until (not f)or(i>=length(s));
IntA:=f and (q=1)
End;
Посмотрим, как работает автомат для числа
s=‘-15’
q
0
S
-15
0
-15
2
-15
1
-15
2
1
Описать конечный автомат, распознающий запись дробного числа в десятичном виде.
Описать конечный
Описать конечный автомат, распознающий запись дробного числа в десятичном виде.
Описать конечный
Дана работоспособная программа на Паскале. Необходимо удалить из нее комментарии так,
Дана работоспособная программа на Паскале. Необходимо удалить из нее комментарии так,
А) разрешается использовать комментарии только одного типа. Все, что заключено в фигурные скобки ‘{‘, ‘}’ считается комментарием. Комментарии не могут быть вложены друг в друга.
Б) разрешается использовать комментарии только двух типов. Все, что заключено в фигурные скобки ‘{‘, ‘}’ или (*. *) считается комментарием. Комментарии разного типа могут быть вложены друг в друга.
Когда этот автомат не работает?
Write(‘{это не комментарий}’);
If x=‘{‘ then …
Case x of
‘{‘:…
Что делать, если комментариев два типа?
Что опять неправильно?
Write((*комментарий*))
(*комментарий**)
Есть ли еще проблемы? За каждую найденную - +5 к краме ☺
Описание языков с использованием графов
Опишем наш уже созданный язык, но
Описание языков с использованием графов
Опишем наш уже созданный язык, но
Проанализируем данную схему. Это конечный автомат с несколькими состояниями (0-20). В
Проанализируем данную схему. Это конечный автомат с несколькими состояниями (0-20). В
описание переменных и их типов;
начало программы.
Неопределенность разрешается через анализ лексем. Если пришла лексема cmBegin, то это означает анализ тела программы, автомат переходит в состояние 7 и помещает в специальный стек особое состояние, обозначенной константой Stop. Перейдя в нее автомат, завершает работу. Если вместо лексемы “НАЧАЛО” пришла лексема идентификатор, то это означает начало описания переменных.
Получив имя переменной, дальше возможно два типа лексем:
переменная “:”
переменная “,”
Имена закончились, далее описывается тип.
Получив “:”, автомат будет ожидать тип переменной, “,” – следующее имя переменной.
Если после описания типа встретилась лексема «НАЧАЛО», то переходим в состояние 7 (анализ тела программы), если нет, то это описание следующей группы переменных. Например,
Х, У: ЦЕЛЫЕ;
А, В: ДРОБНЫЕ;
Самая сложная для понимания часть – анализ операторов. Дело в том, что операторы начинаются после слова «НАЧАЛО» (после начала программы). Однако, некоторые операторы, например оператор ветвления, могут в свою очередь содержать другие операторы, в том числе и оператор ветвления и т.д. Чтобы не увеличивать число состояний автомата, усложнять его вид, было принято решение об организации специального стека состояний. Перед началом анализа оператора, автомат заносит в этот стек номер состояния, в которое нужно вернуться после завершения анализа данного оператора. Когда анализ оператора завершен, автомат выполняет команду Sost:=Pop - извлечь из стека состояние, в которое необходимо вернуться.
Procedure Automat (sost : integer);
Var Ch: Ident;
…;
Begin
Ch:=GetLex; {Получить первую лексему}
Procedure Automat (sost : integer);
Var Ch: Ident;
…;
Begin
Ch:=GetLex; {Получить первую лексему}
Case Sost of
0:if Ch<>cmProgram
then Error (‘Требуется слово «Программа»’)
else begin
Sost:=1;Ch:=GetLex
End;
1:if Ch<>cmIdent
then Error (‘Требуется имя программы’)
else begin
Ch:=GetLex
If Ch<>cmTZ {“;”}
Then Error(‘Требуется “;” ’);
Sost:=2;Ch:=GetLex
End;
Находясь в состоянии 0, автомат ждет слово ПРОГРАММА, если его нет, то выводим сообщение об ошибке, иначе переходим с состояние 1.
Находясь в состоянии 1, автомат ждет идентификатор имени программы, если его нет, то выводим сообщение об ошибке, иначе ищем «;» и переходим с состояние 2.
2: begin
if Ch=cmIdent {если имя переменной, то }
then sost:=3
else if Ch=cmBegin {если
2: begin
if Ch=cmIdent {если имя переменной, то }
then sost:=3
else if Ch=cmBegin {если
then begin
Sost:=7;Push(Stop) {занести в стек номер конечного состояния}
end
else Error (‘Требуется «НАЧАЛО»’)
end;
3:begin запомнить имя переменной; Ch:=GetLex;
If Ch=cmTT {“:”} Then Sost:=5
Else if Ch=cmZP {“,”} Then Sost:=4
Else Error(‘Требуется “,” или ”:”’)
end;
4: begin Ch:=GetLex;
if Ch=cmIdent {если имя переменной, то} then sost:=3
else Error (‘Требуется имя переменной’)
end;
5: begin {если “:”}
Ch:=GetLex; If not (Ch in [cmInt, cmReal, cmChar])
Then Error (‘Требуется тип переменной’)
Else Sost:=6;
end;
Находясь в состоянии 2, автомат может встретить идентификатор, тогда это описание переменных (состояние 3) или начало программы (состояние 7)
Находясь в состоянии 3, автомат может встретить «:», тогда перечисление имен переменных закончилось, надо ждать имя типа (состояние 5) или «,» - ждем имя переменной (состояние 4)
Находясь в состоянии 5, автомат ждет имя типа , если его нет, то выводим «ошибка», иначе переходим в состояние 6
6:begin
заполнить таблицу имен переменных, указать их тип и начальное значение;
6:begin
заполнить таблицу имен переменных, указать их тип и начальное значение;
If Ch=cmBegin
Then begin
Sost:=7;
Push(Stop)
end
Else if Sost=cmIdent Then Sost:=3
Else Error (‘Требуется «НАЧАЛО»’)
End;
7: begin
Ch:=GetLex;
If Ch=cmEnd Then Sost:=20
Else if cm in [cmLeft, cmRight, …]
Then begin
Sost:=9; Push (19)
end
Else Error(‘Требуется оператор’)
end;
В состоянии 6 закончилось описание списка переменных, заносим их в таблицу имен и читаем следующую лексему. Если это НАЧАЛО, то переходим в состояние 7 и разбираем операторы, если – идентификатор, то разбираем новый блок описания переменных (состояние 3)
В состоянии 7 мы можем встретить лексему КОНЕЦ, что означает завершение логического блока – переходим в состояние 20, или можем встретить любой оператор: ВЛЕВО, ЕСЛИ, цикл и т.д. В этом случае переходим в состояние 20 для их разбора. Не забываем запомнить состояние, куда надо вернуться (Push (19)).
19:begin {оператор закончился}
if Ch<>cmTZ {“;”}
then Error (‘Требуется “;”’)
else Sost:=7
end
20:
19:begin {оператор закончился}
if Ch<>cmTZ {“;”}
then Error (‘Требуется “;”’)
else Sost:=7
end
20:
9:begin
{сюда необходимо вставить блок кода для анализа операторов}
end;
End; {case}
Until Sost=Stop {завершить анализ при достижении конечного состояния}
End;
{блок кода для состояния 9, рассматривается отдельно, чтобы не загромождать основную
{блок кода для состояния 9, рассматривается отдельно, чтобы не загромождать основную
Case Ch of
CmLeft, cmRight, cmUp, cmDown: Begin
Создать объектный код данных операторов;
Sost:=POP; {извлечь состояние, в которое нужно вернуться}
Ch:=GetLex
End;
CmIf:begin
Анализ оператора ветвления:
Case Sost of
…
End;
Sost:=POP; Ch:=GetLex
End;
…
End; {case}
End;
Представленная процедура позволяет реализовать анализ конкретного языка, но можно пойти дальше,
Представленная процедура позволяет реализовать анализ конкретного языка, но можно пойти дальше,
Пошаговая трассировка. Определение точки возникновения синтаксической ошибки.
В предыдущей части мы
Пошаговая трассировка. Определение точки возникновения синтаксической ошибки.
В предыдущей части мы
If Ch<> чему-то
Then Error(‘Требуется то-то’);
Понятно, что процедура Error выводит сообщение «Требуется то-то», но пользователю очень сложно понять, в какой части программы требуется «ТО-ТО». Хочется, чтобы синтаксический анализатор не только сообщал об ошибке, но и показывал точку в тексте программы, где эта ошибка была обнаружена. Чтобы решить эту проблему, достаточно в каждом звене объектного кода хранить ссылку на строку текстового редактора с ее текстовым эквивалентом. Ссылка может быть представлена в виде пары чисел: номер строки, номер слова в строке. Такой подход позволит не только указать место возникновения синтаксической ошибки на этапе компиляции, но и реализовать пошаговую трассировку программы (подсвечивая строку с исполняемой командой), устанавливать точки останова.
Противники
Игра становится гораздо интереснее, если выполнению миссии нашего героя (черепашки,
Противники
Игра становится гораздо интереснее, если выполнению миссии нашего героя (черепашки,
Многозадачный транслятор
В отличие от однозадачного транслятора, многозадачный имеет не один
Многозадачный транслятор
В отличие от однозадачного транслятора, многозадачный имеет не один
Когда надо прекратить исполнение текущей программы и перейти к следующей?
Куда возвращаться? (на какое звено объектного кода)
Как обеспечить взаимную независимость программ и их переменных?
Список программ –
Массив Task
Игрок 0
Вход в объектный код
Текущая команда
Переменные
0
1
…
Игрок 1
Вход
Список программ –
Массив Task
Игрок 0
Вход в объектный код
Текущая команда
Переменные
0
1
…
Игрок 1
Вход
Текущая команда
В массиве Task (задачи) хранится вся информация об игроках: вход в список объектного кода, указатель на текущую команду, список переменных и их значений, вход в список строк текста программы, характеристики исполнителя (координаты и т.д.)
Параллельное исполнение нескольких программ будет осуществляться путем последовательного исполнения каждой программы до команды, которая изменяет состояние поля (перемещение исполнителя, выстрел, взятие предмета с поля)
Repeat
for i:=0 to NumbGamer-1
Interpretation(Task[i]);
нарисовать изменения на поле
Until игра завершена
Как только интерпретатор встретил команду перемещения исполнителя, он помещает в очередь произошедшие события и прерывает исполнение текущей программы, начинает следующую. Когда все программы отработали необходимо анимационно изобразить все события на поле.
Представление сложных условий в операторе ветвления. Оператор присваивания
При исполнении объектного
Представление сложных условий в операторе ветвления. Оператор присваивания
При исполнении объектного
Если Х<8 тогда … {простое условие}
Если (Х<8)И(X>20)ИЛИ(Z=0) тогда … {сложное логическое выражение}
Представление простых условий мы уже рассмотрели раньше. Теперь рассмотрим идею представления сложных, но прежде вернемся к оператору присваивания. Слева от оператора присваивания может стоять только переменная, а вот справа любое арифметическое выражения, причем в нем могут встречаться не только четыре арифметических действия, но и скобки, меняющие порядок действий.
Например, x:=(2+y)*34-(y+z)/4. Порядок действий в таких выражениях вовсе не очевиден. Существует классический алгоритм, позволяющий перевести выражение в особый вид – обратную польскую запись. Но работать с таким представлением не всегда удобно. Воспользуемся древовидным представлением.
Разбор арифметических выражений, содержащих скобки
В некоторых задачах необходимо вычислить значение
Разбор арифметических выражений, содержащих скобки
В некоторых задачах необходимо вычислить значение
Разделим эту задачу на две части: разбор и строительство дерева по
Разделим эту задачу на две части: разбор и строительство дерева по
Разбор выражения без скобок. Просматривается арифметическое выражение слева направо, ищутся высокоприоритетные операции ‘*’, ‘/’. У найденной операции выделяются левый и правый операнд. Строится дерево из трех узлов. Данная структура помещается в особый массив, а операция и операнды заменяются особой переменной, к которой прикрепляется построенная структура.
Затем, когда все высокоприоритетные операции закончатся, проводим ту же операцию над
Затем, когда все высокоприоритетные операции закончатся, проводим ту же операцию над
Type Ref=^Node;
Node=record
Lit:char;
L,R:Ref;{Массив переменных}
end;
alf='А'..'Я';
var
Num:Alf;{количество переменных}
Mass:array[Alf] of ref;
Root:ref; {корень дерева}
Function NewEl(c:char):Ref;
{Создает новое звено, со значением С}
var tz:ref;
begin
New(tz); tz^.L:=nil;tz^.R:=nil; tz^.Lit:=c; NewEl:=tz;
end;
procedure Arif(m:SetC); {Ищет только операции из множества m}
var i:integer; tz:ref; f:boolean;
begin
procedure Arif(m:SetC); {Ищет только операции из множества m}
var i:integer; tz:ref; f:boolean;
begin
Repeat
i:=1; {Ищем только операции из множества m}
While (not (st[i] in m)and(i
if st[i] in m {если операция найдена, то}
then begin
tz:=NewEl(st[i]); {создать новое звено}
if st[i-1] in ['a'..'z'] {если найден операнд, то}
then tz^.L:=NewEl(st[i-1]) {создать новое звено, прицепить его слева}
else tz^.L:=mass[st[i-1]];{если это замененная переменная, то прицепить ее}
if st[i+1] in ['a'..'z'] {аналогично справа…}
then tz^.R:=NewEl(st[i+1])
else tz^.R:=mass[st[i+1]];
Delete(st,i-1,2); {удалить операцию и один операнд}
inc(Num); Mass[Num]:=tz; {создать новую переменную в массиве}
st[i-1]:=Num
end
else f:=true{если операций уже не осталось, то закончить цикл}
until f; end;
a+b*c-d/h
procedure Arif(m:SetC);
var i:integer; tz:ref; f:boolean;
begin
f:=false;
Repeat
i:=1; {Ищем только
a+b*c-d/h
procedure Arif(m:SetC);
var i:integer; tz:ref; f:boolean;
begin
f:=false;
Repeat
i:=1; {Ищем только
While (not(st[i] in m)and(i
if st[i] in m {если операция найдена, то}
then begin
tz:=NewEl(st[i]);
if st[i-1] in ['a'..'z']
then tz^.L:=NewEl(st[i-1])
else tz^.L:=mass[st[i-1]]
if st[i+1] in ['a'..'z']
then tz^.R:=NewEl(st[i+1])
else tz^.R:=mass[st[i+1]];
Delete(st,i-1,2);
inc(Num); Mass[Num]:=tz;
st[i-1]:=Num
end
else f:=true
until f;
end;
St
Ищем самую левую операцию * или /.
‘@’ ‘#’ ‘$’ ‘%’ ‘&’
procedure Arif(m:SetC); Нашли умножение, создаем звено операции * procedure Arif(m:SetC); Прикрепляем к нему слева операнд b b procedure Arif(m:SetC); Прикрепляем к нему справа операнд с с procedure Arif(m:SetC); Помещаем «заготовку» в массив, а переменную в строку st a+@-d/h * b с procedure Arif(m:SetC); Аналогично ищем /, создаем звено и помещаем его в массив a+@-# Повторяем процесс для низкоприоритетных операций сложения и вычитания, создаем звено и помещаем его в массив + a $-# Повторяем для вычитания, создаем звено и помещаем его в массив. Теперь mass[%] хранит вход в дерево арифметического выражения - %
var i:integer; tz:ref; f:boolean;
begin
f:=false;
Repeat
i:=1; {Ищем только операции из множества m}
While (not(st[i] in m)and(i
if st[i] in m {если операция найдена, то}
then begin
tz:=NewEl(st[i]);
if st[i-1] in ['a'..'z']
then tz^.L:=NewEl(st[i-1])
else tz^.L:=mass[st[i-1]]
if st[i+1] in ['a'..'z']
then tz^.R:=NewEl(st[i+1])
else tz^.R:=mass[st[i+1]];
Delete(st,i-1,2);
inc(Num); Mass[Num]:=tz;
st[i-1]:=Num
end
else f:=true
until f;
end;
var i:integer; tz:ref; f:boolean;
begin
f:=false;
Repeat
i:=1; {Ищем только операции из множества m}
While (not(st[i] in m)and(i
if st[i] in m {если операция найдена, то}
then begin
tz:=NewEl(st[i]);
if st[i-1] in ['a'..'z']
then tz^.L:=NewEl(st[i-1])
else tz^.L:=mass[st[i-1]]
if st[i+1] in ['a'..'z']
then tz^.R:=NewEl(st[i+1])
else tz^.R:=mass[st[i+1]];
Delete(st,i-1,2);
inc(Num); Mass[Num]:=tz;
st[i-1]:=Num
end
else f:=true
until f;
end;
var i:integer; tz:ref; f:boolean;
begin
f:=false;
Repeat
i:=1; {Ищем только операции из множества m}
While (not(st[i] in m)and(i
if st[i] in m {если операция найдена, то}
then begin
tz:=NewEl(st[i]);
if st[i-1] in ['a'..'z']
then tz^.L:=NewEl(st[i-1])
else tz^.L:=mass[st[i-1]]
if st[i+1] in ['a'..'z']
then tz^.R:=NewEl(st[i+1])
else tz^.R:=mass[st[i+1]];
Delete(st,i-1,2);
inc(Num); Mass[Num]:=tz;
st[i-1]:=Num
end
else f:=true
until f;
end;
var i:integer; tz:ref; f:boolean;
begin
f:=false;
Repeat
i:=1; {Ищем только операции из множества m}
While (not(st[i] in m)and(i
if st[i] in m {если операция найдена, то}
then begin
tz:=NewEl(st[i]);
if st[i-1] in ['a'..'z']
then tz^.L:=NewEl(st[i-1])
else tz^.L:=mass[st[i-1]]
if st[i+1] in ['a'..'z']
then tz^.R:=NewEl(st[i+1])
else tz^.R:=mass[st[i+1]];
Delete(st,i-1,2);
inc(Num); Mass[Num]:=tz;
st[i-1]:=Num
end
else f:=true
until f;
end;
var i:integer; tz:ref; f:boolean;
begin
f:=false;
Repeat
i:=1; {Ищем только операции из множества m}
While (not(st[i] in m)and(i
if st[i] in m {если операция найдена, то}
then begin
tz:=NewEl(st[i]);
if st[i-1] in ['a'..'z']
then tz^.L:=NewEl(st[i-1])
else tz^.L:=mass[st[i-1]]
if st[i+1] in ['a'..'z']
then tz^.R:=NewEl(st[i+1])
else tz^.R:=mass[st[i+1]];
Delete(st,i-1,2);
inc(Num); Mass[Num]:=tz;
st[i-1]:=Num
end
else f:=true
until f;
end;
Function Calc(St:string):Ref; {Строит дерево по арифметическому выражению без скобок}
begin{Calc}
Arif(['*','/']);{обработать умнож.
Function Calc(St:string):Ref; {Строит дерево по арифметическому выражению без скобок}
begin{Calc}
Arif(['*','/']);{обработать умнож.
Arif(['+','-']); {теперь сложение и вычитание}
Calc:=mass[st[1]]
end;
Скобочные выражения анализируются так: ищется самая левая закрывающая скобка ‘)’, затем ее открывающая пара. Выражение между этих скобок вырезается из строки и разбирается функцией Calc.
Function CalcScob(st:string):ref;
var f:boolean; i,j:integer; tz:ref;
begin
f:=false;CalcScob:=nil;
Repeat
i:=Pos( ')', st); {Ищем
Function CalcScob(st:string):ref;
var f:boolean; i,j:integer; tz:ref;
begin
f:=false;CalcScob:=nil;
Repeat
i:=Pos( ')', st); {Ищем
if i<>0 then begin{если нашли, то}
j:=i;
While (st[j]<>'(')and(j>0) do dec(j); {ищем ее пару}
if j=0 then exit; {если пары нет, то ошибка}
tz:=Calc(copy(st,j+1,i-j-1));{разбираем выражение между скобок}
delete(st,j,i-j); {удаляем из строки разобранное выражение}
inc(num); mass[Num]:=tz; st[j]:=Num; {создаем переменную}
end
else f:=true
until f;
if length(st)<>1 then CalcScob:=Calc(st)
else CalcScob:=mass[st[1]];
end;
Дальнейшее развитие этой программы очевидно – переменные a, b, c, …
Дальнейшее развитие этой программы очевидно – переменные a, b, c, …
Var Value:array[‘a’..’z’] of real;
Каждый элемент массива Value имеет литерный номер и вещественное значение. Чтобы получить значение некоторой переменной нужно: Пусть tz^.lit=’a’, тогда Value[tz^.lit]=значение переменной. Рассмотрим функцию нахождения результата арифметического выражения представленного в дереве, построенном предыдущей программой.
Function Arifmet(Root:ref):real;
Begin
If Root^.L=Root^.R {Если это лист, то Root^.L=Root^.R = nil}
Then Arifmet:=Value[Root^.Lit]
Else case Root^.Lit of
‘+’: Arifmet:= Arifmet (Root^.L)+ Arifmet(Root^.R);
‘-’: Arifmet:= Arifmet (Root^.L) - Arifmet(Root^.R);
‘*’: Arifmet:= Arifmet (Root^.L) * Arifmet(Root^.R);
‘/’: Arifmet:= Arifmet (Root^.L) / Arifmet(Root^.R);
end;{case}
End;
Для простоты мы не анализировали случай пустого дерева, когда Root=nil.
Вернемся к логическим выражениям. Любое логическое условие преобразуем в древовидное представление.
Звено, которое представляет оператор ветвления в объектном коде, имеет указатель на
Звено, которое представляет оператор ветвления в объектном коде, имеет указатель на
Type pRef=^tNode;
tNode=record
left, right:pRef;
case TypeNode:byte of
cmNumber: Num:real; {хранится число}
cmVariable: Index: integer; {хранится индекс переменной}
cmOperation: Oper:string[3];{или char, операция}
End;
В момент компиляции происходит перевод арифметических и логических выражений в древовидное представление. В момент исполнения объектного кода, интерпретатор вычисляет значение выражения и использует его по назначению.
Разбор арифметических выражений методом рекурсивного спуска
Для арифметического выражения дерево разбора можно
Разбор арифметических выражений методом рекурсивного спуска
Для арифметического выражения дерево разбора можно
Подсчет значения арифметического выражения, основанный на таком способе представления рекурсивен и фактически совпадает с рекурсивным определением самого выражения.
<выражение>::=<терм>|<терм>+<выражение>|<терм>-<выражение>
<терм>::=<множитель>|<множитель>*<терм>|<множитель>/<терм>
<множитель>::=(<выражение>)|<имя>|<натуральное число>
<имя>::=<буква>|<имя><буква>|<имя><цифра>
<натуральное число>::=<цифра>|<натуральное число><цифра>
<цифра>::=0|1|2|3|4|5|6|7|8|9
<буква>::=_|A|B|…|Z|a|b|…|z|
Так, выражение представляет собой сумму слагаемых (здесь под суммой подразумевается выполнение операций, как сложения, так и вычитания). Каждое слагаемое представляет собой произведение множителей (сюда же отнесена операция деления). А множитель представляет собой либо число, либо переменную, либо выражение в скобках (при наличии унарного минуса множителем является также выражение со стоящим перед ним знаком минус).
var s:string;{исходное выражение}
i:integer;{номер текущего символа}
function Mul:longint; Forward;
function Factor:longint; Forward;
function
var s:string;{исходное выражение}
i:integer;{номер текущего символа}
function Mul:longint; Forward;
function Factor:longint; Forward;
function
var q,res:longint; c:char;
Begin
res:=Mul;{первое слагаемое}
While s[i] in ['+','-'] do
Begin
c:=s[i]; i:=i+1; q:=Mul;{очередное слагаемое}
case c of
'+':res:=res+q;
'-':res:=res-q;
End
End;{While}
Add:=res
End;
function Mul:longint; {перемножает множители}
var q,res:longint; c:char;
Begin
res:=Factor;{первый множитель}
While s[i] in
function Mul:longint; {перемножает множители}
var q,res:longint; c:char;
Begin
res:=Factor;{первый множитель}
While s[i] in
Begin
c:=s[i]; i:=i+1;q:=Factor;{очередной множитель}
case c of
'*':res:=res*q;
'/':If q=0
then Begin writeln('деление на 0');
halt
End
else res:=res div q
End {case}
End; {While}
Mul:=res
End;
function Number:longint;{выделяет число}
var res:longint;
Begin res:=0;
While (i<=length(s)) and (s[i] in ['0'..'9'])
function Number:longint;{выделяет число}
var res:longint;
Begin res:=0;
While (i<=length(s)) and (s[i] in ['0'..'9'])
res:=res*10+(ord(s[i])-ord('0')); i:=i+1
End; {While}
Number:=res
End;
function Factor:longint; {выделяет множитель}
var q:longint; c:char;
Begin
case s[i] of
'0'..'9':Factor:=Number;
'(':Begin i:=i+1;Factor:=Add; i:=i+1;{пропустили ')'}End;
'-':Begin i:=i+1; Factor:=-Factor; End
else Begin writeln('ошибка'); halt End
End {case}
End;
Begin {основная программа}
readln(s); i:=1; writeln(Add)
End.
Арифметическое выражение представляет собой сумму нескольких слагаемых (возможно одно). Каждое слагаемое
Арифметическое выражение представляет собой сумму нескольких слагаемых (возможно одно). Каждое слагаемое
function Add:longint; {суммирует слагаемые}
Begin
res:=Mul;{первое слагаемое}
While s[i] in ['+','-']
function Add:longint; {суммирует слагаемые}
Begin
res:=Mul;{первое слагаемое}
While s[i] in ['+','-']
c:=s[i]; i:=i+1; q:=Mul;{очередное слагаемое}
case c of
'+':res:=res+q;
'-':res:=res-q;
End
End;{While}
Add:=res
End;
function Mul:longint; {перемножает множители}
Begin
res:=Factor;{первый множитель}
While s[i] in ['*','/'] do Begin
c:=s[i]; i:=i+1;q:=Factor;{очередной множитель}
case c of
'*': res:=res*q;
'/': res:=res div q
End {case}
End; {While}
Mul:=res
End;
function Number:longint;{выделяет число}
Begin
End;
function Factor:longint; {выделяет множитель}
Begin
case s[i] of
'0'..'9':Factor:=Number;
'(':Begin i:=i+1;Factor:=Add; i:=i+1; End;
'-':Begin i:=i+1; Factor:=-Factor; End
else Begin writeln('ошибка'); halt End
End {case}
End;
5*2+7*3-11
S
Результат
function Add:longint; {суммирует слагаемые}
Begin
res:=Mul;{первое слагаемое}
While s[i] in ['+','-'] do Begin
c:=s[i]; i:=i+1; q:=Mul;{очередное слагаемое}
case c of
'+':res:=res+q;
'-':res:=res-q;
End
End;{While}
Add:=res
End;
function Mul:longint; {перемножает множители}
Begin
res:=Factor;{первый множитель}
While s[i] in ['*','/'] do Begin
c:=s[i]; i:=i+1;q:=Factor;{очередной множитель}
case c of
'*': res:=res*q;
'/': res:=res div q
End {case}
End; {While}
Mul:=res
End;
function Number:longint;{выделяет число}
Begin
End;
function Factor:longint; {выделяет множитель}
Begin
case s[i] of
'0'..'9':Factor:=Number;
'(':Begin i:=i+1;Factor:=Add; i:=i+1; End;
'-':Begin i:=i+1; Factor:=-Factor; End
else Begin writeln('ошибка'); halt End
End {case}
End;
S:=‘5*2+7*3-11’;
i:=1; writeln(Add)
Запускается программа, что приводит к вызову процедуры Add, которая выделяет первое слагаемое.
function Add:longint; {суммирует слагаемые}
Begin
res:=Mul;{первое слагаемое}
While s[i] in ['+','-'] do Begin
c:=s[i]; i:=i+1; q:=Mul;{очередное слагаемое}
case c of
'+':res:=res+q;
'-':res:=res-q;
End
End;{While}
Add:=res
End;
function Mul:longint; {перемножает множители}
Begin
res:=Factor;{первый множитель}
While s[i] in ['*','/'] do Begin
c:=s[i]; i:=i+1;q:=Factor;{очередной множитель}
case c of
'*': res:=res*q;
'/': res:=res div q
End {case}
End; {While}
Mul:=res
End;
function Number:longint;{выделяет число}
Begin
End;
function Factor:longint; {выделяет множитель}
Begin
case s[i] of
'0'..'9':Factor:=Number;
'(':Begin i:=i+1;Factor:=Add; i:=i+1; End;
'-':Begin i:=i+1; Factor:=-Factor; End
else Begin writeln('ошибка'); halt End
End {case}
End;
Это приводит к вызову процедуры Mul, которая будет считать произведение в каждом слагаемом (если оно, конечно, есть).
function Add:longint; {суммирует слагаемые}
Begin
res:=Mul;{первое слагаемое}
While s[i] in ['+','-'] do Begin
c:=s[i]; i:=i+1; q:=Mul;{очередное слагаемое}
case c of
'+':res:=res+q;
'-':res:=res-q;
End
End;{While}
Add:=res
End;
function Mul:longint; {перемножает множители}
Begin
res:=Factor;{первый множитель}
While s[i] in ['*','/'] do Begin
c:=s[i]; i:=i+1;q:=Factor;{очередной множитель}
case c of
'*': res:=res*q;
'/': res:=res div q
End {case}
End; {While}
Mul:=res
End;
function Number:longint;{выделяет число}
Begin
End;
function Factor:longint; {выделяет множитель}
Begin
case s[i] of
'0'..'9':Factor:=Number;
'(':Begin i:=i+1;Factor:=Add; i:=i+1; End;
'-':Begin i:=i+1; Factor:=-Factor; End
else Begin writeln('ошибка'); halt End
End {case}
End;
Это приводит к вызову процедуры Factor, которая определяет, что является множителем: число или выражение в скобках? В нашем случае это число!
5*2+7*3-11
5
function Add:longint; {суммирует слагаемые}
Begin
res:=Mul;{первое слагаемое}
While s[i] in ['+','-'] do Begin
c:=s[i]; i:=i+1; q:=Mul;{очередное слагаемое}
case c of
'+':res:=res+q;
'-':res:=res-q;
End
End;{While}
Add:=res
End;
function Mul:longint; {перемножает множители}
Begin
res:=Factor;{первый множитель}
While s[i] in ['*','/'] do Begin
c:=s[i]; i:=i+1;q:=Factor;{очередной множитель}
case c of
'*': res:=res*q;
'/': res:=res div q
End {case}
End; {While}
Mul:=res
End;
function Number:longint;{выделяет число}
Begin
End;
function Factor:longint; {выделяет множитель}
Begin
case s[i] of
'0'..'9':Factor:=Number;
'(':Begin i:=i+1;Factor:=Add; i:=i+1; End;
'-':Begin i:=i+1; Factor:=-Factor; End
else Begin writeln('ошибка'); halt End
End {case}
End;
Возвращаемся в процедуру Mul, обнаруживаем знак умножения, выделяем аналогичным образом второй множитель 2.
5*2+7*3-11
function Add:longint; {суммирует слагаемые}
Begin
res:=Mul;{первое слагаемое}
While s[i] in ['+','-'] do Begin
c:=s[i]; i:=i+1; q:=Mul;{очередное слагаемое}
case c of
'+':res:=res+q;
'-':res:=res-q;
End
End;{While}
Add:=res
End;
function Mul:longint; {перемножает множители}
Begin
res:=Factor;{первый множитель}
While s[i] in ['*','/'] do Begin
c:=s[i]; i:=i+1;q:=Factor;{очередной множитель}
case c of
'*': res:=res*q;
'/': res:=res div q
End {case}
End; {While}
Mul:=res
End;
function Number:longint;{выделяет число}
Begin
End;
function Factor:longint; {выделяет множитель}
Begin
case s[i] of
'0'..'9':Factor:=Number;
'(':Begin i:=i+1;Factor:=Add; i:=i+1; End;
'-':Begin i:=i+1; Factor:=-Factor; End
else Begin writeln('ошибка'); halt End
End {case}
End;
Найдем результат 5*2 и вернем его в качестве первого слагаемого
5*2+7*3-11
10
function Add:longint; {суммирует слагаемые}
Begin
res:=Mul;{первое слагаемое}
While s[i] in ['+','-'] do Begin
c:=s[i]; i:=i+1; q:=Mul;{очередное слагаемое}
case c of
'+':res:=res+q;
'-':res:=res-q;
End
End;{While}
Add:=res
End;
function Mul:longint; {перемножает множители}
Begin
res:=Factor;{первый множитель}
While s[i] in ['*','/'] do Begin
c:=s[i]; i:=i+1;q:=Factor;{очередной множитель}
case c of
'*': res:=res*q;
'/': res:=res div q
End {case}
End; {While}
Mul:=res
End;
function Number:longint;{выделяет число}
Begin
End;
function Factor:longint; {выделяет множитель}
Begin
case s[i] of
'0'..'9':Factor:=Number;
'(':Begin i:=i+1;Factor:=Add; i:=i+1; End;
'-':Begin i:=i+1; Factor:=-Factor; End
else Begin writeln('ошибка'); halt End
End {case}
End;
Вернулись в процедуру Add, первое слагаемое равно 10, текущий символ ‘+’, выделяем второе слагаемое (опять процедурой Mul)
5*2+7*3-11
10+
function Add:longint; {суммирует слагаемые}
Begin
res:=Mul;{первое слагаемое}
While s[i] in ['+','-'] do Begin
c:=s[i]; i:=i+1; q:=Mul;{очередное слагаемое}
case c of
'+':res:=res+q;
'-':res:=res-q;
End
End;{While}
Add:=res
End;
function Mul:longint; {перемножает множители}
Begin
res:=Factor;{первый множитель}
While s[i] in ['*','/'] do Begin
c:=s[i]; i:=i+1;q:=Factor;{очередной множитель}
case c of
'*': res:=res*q;
'/': res:=res div q
End {case}
End; {While}
Mul:=res
End;
function Number:longint;{выделяет число}
Begin
End;
function Factor:longint; {выделяет множитель}
Begin
case s[i] of
'0'..'9':Factor:=Number;
'(':Begin i:=i+1;Factor:=Add; i:=i+1; End;
'-':Begin i:=i+1; Factor:=-Factor; End
else Begin writeln('ошибка'); halt End
End {case}
End;
Выделяем первый множитель при помощи factor, убеждаемся, что есть знак умножения ‘*’, выделяем второй множитель и считаем результат. Его возвращаем в качестве очередного слагаемого в Add
5*2+7*3-11
10+21
function Add:longint; {суммирует слагаемые}
Begin
res:=Mul;{первое слагаемое}
While s[i] in ['+','-'] do Begin
c:=s[i]; i:=i+1; q:=Mul;{очередное слагаемое}
case c of
'+':res:=res+q;
'-':res:=res-q;
End
End;{While}
Add:=res
End;
function Mul:longint; {перемножает множители}
Begin
res:=Factor;{первый множитель}
While s[i] in ['*','/'] do Begin
c:=s[i]; i:=i+1;q:=Factor;{очередной множитель}
case c of
'*': res:=res*q;
'/': res:=res div q
End {case}
End; {While}
Mul:=res
End;
function Number:longint;{выделяет число}
Begin
End;
function Factor:longint; {выделяет множитель}
Begin
case s[i] of
'0'..'9':Factor:=Number;
'(':Begin i:=i+1;Factor:=Add; i:=i+1; End;
'-':Begin i:=i+1; Factor:=-Factor; End
else Begin writeln('ошибка'); halt End
End {case}
End;
Прибавляем слагаемое 21, сдвигаемся по строке, обнаруживаем операцию ‘-’, вызываем Mul, которая при помощи factor обнаружит число 11 и вернет его нам, остается найти результат.
5*2+7*3-11
31-11
20
5*2+7*3-11
Динамический линейный однонаправленный список
Основными проблемами классического статического списка на основе
Динамический линейный однонаправленный список
Основными проблемами классического статического списка на основе
неэффективное распределение памяти (резервирование лишней);
невозможность увеличить размер списка в ходе программы;
медленные операции вставки и удаления элементов без нарушения порядка их следования (сдвиг элементов в среднем О(n/2) штук).
От этих проблем избавлен динамический список. Он формируется по мере необходимости путем добавления (вставки) нового звена. Рассмотрим основные операции над динамическим списком:
Формирование списка
Рассмотрим структуру данных. Для примера в списке будем хранить литеры
Формирование списка
Рассмотрим структуру данных. Для примера в списке будем хранить литеры
Type ref=^Node;{указатель на звено}
Node=record{звено}
Next:Ref; {указатель на следующее звено}
Lit:char {информация звена (символ)}
End;
Каждое звено хранит один информационный символ и указатель на следующее звено.
Сам список будет выглядеть так:
Procedure CreateList(var inz:ref);
Var tz:ref; a:char;
Begin
New(inz); tz:=Inz;
Read(a);tz^.Lit:=a;
{дополнительный указатель tz
Procedure CreateList(var inz:ref);
Var tz:ref; a:char;
Begin
New(inz); tz:=Inz;
Read(a);tz^.Lit:=a;
{дополнительный указатель tz
While a<>’.’ Do
Begin
New(tz^.next);{создадим новое звено}
Tz:=tz^.Next;{перейдем к следующему звену}
Read(a); tz^.lit:=a
End;
Tz^.Next:=nil; ;{ пометим конец списка}
Readln ;{ удалим enter из буфера клавиатуры}
End;
Inz
tz
‘m’
‘a’
‘m’
‘a’
‘.’
nil
Вывод списка.
Встаем на начало списка (inz), двигаемся по нему, переходя к
Вывод списка.
Встаем на начало списка (inz), двигаемся по нему, переходя к
Procedure WriteList(inz:ref);
Var tz:ref;
Begin
tz:=Inz;
While tz<>nil Do
Begin
write(tz^.Lit);{выведем информацию из текущего звена}
Tz:=tz^.Next;{перейдем к следующему звену}
End;
End;
Признаком конца списка мы используем не символ ‘.’, а пустую ссылку nil. Это позволяет оторваться от конкретного списка и создать универсальную процедуру вывода списка, которая не зависит от того, что в нем содержится.
tz
Поиск элемента в списке.
Одна из важнейших операций в программировании. Встаем на
Поиск элемента в списке.
Одна из важнейших операций в программировании. Встаем на
function Seek(inz:ref;key:lit):ref;
Var tz:ref;
Begin
tz:=Inz;
While (tz<>nil)and(tz^.Lit<>key) Do
Tz:=tz^.Next;{перейдем к следующему звену}
Seek:=tz
End;
Мы имеем два сравнения на каждый элемент, поэтому худшая скорость будет О(2n), а средняя – О(2n/2)=O(n). Обратите внимание, что в цикле while используется логическая операции and, а не or! Это условие продолжения, а не окончания!
tz
Вставка элемента в список.
В отличие от статического списка, в котором для
Вставка элемента в список.
В отличие от статического списка, в котором для
а) вставка после текущего.
Пусть tz указывает на некоторый элемент списка, необходимо за ним разместить новое звено с заданным символом.
Procedure InsAfter(tz:ref;a:char);
Var p:ref;
Begin
New(p);{создадим новое звено}
P^.lit:=a; {запомним заданный символ}
P^.Next:=tz^.next;
Tz^.Next:=p; {перекинем указатели}
End;
р
л
tz
б) вставка перед текущим.
Пусть tz указывает на некоторый элемент списка, перед
б) вставка перед текущим.
Пусть tz указывает на некоторый элемент списка, перед
Procedure InsBefore(tz:ref;a:char);
Var p:ref;
Begin
New(p);{создадим новое звено}
P^.lit:=tz^.lit;{запомним текущий символ}
P^.Next:=tz^.next;
Tz^.Next:=p; {перекинем указатели}
Tz^.Lit:=a
End;
р
с
tz
л
‘.’
nil
Inz
a
Дан линейный динамический список, вставить в нем букву ‘a’ после буквы
‘.’
nil
Inz
a
Дан линейный динамический список, вставить в нем букву ‘a’ после буквы
Procedure InsAfter(tz:ref;a:char);
Var p:ref;
Begin
New(p);
P^.lit:=a;
P^.Next:=tz^.next;
Tz^.Next:=p;
End;
Procedure InsA(var inz:Ref;
a,b:char);
Vat tz:Ref;
Begin
tz:=Inz;
While tz<>nil do begin
if tz^.Lit=b
then InsAfter(tz,a)
tz:=tz^.Next
end
End;
Procedure InsAfter(tz:ref;a:char);
Var p:ref;
Begin
New(p);
P^.lit:=a;
P^.Next:=tz^.next;
Tz^.Next:=p;
End;
Procedure InsA(var inz:Ref;
a,b:char);
Vat tz:Ref;
Begin
tz:=Inz;
While tz<>nil do begin
if tz^.Lit=b
then InsAfter(tz,a)
tz:=tz^.Next
end
End;
Procedure InsAfter(tz:ref;a:char);
Var p:ref;
Begin
New(p);
P^.lit:=a;
P^.Next:=tz^.next;
Tz^.Next:=p;
End;
Procedure InsA(var inz:Ref;
a,b:char);
Vat tz:Ref;
Begin
tz:=Inz;
While tz<>nil do begin
if tz^.Lit=b
then InsAfter(tz,a)
tz:=tz^.Next
end
End;
Procedure InsAfter(tz:ref;a:char);
Var p:ref;
Begin
New(p);
P^.lit:=a;
P^.Next:=tz^.next;
Tz^.Next:=p;
End;
Procedure InsA(var inz:Ref;
a,b:char);
Vat tz:Ref;
Begin
tz:=Inz;
While tz<>nil do begin
if tz^.Lit=b
then InsAfter(tz,a)
tz:=tz^.Next
end
End;
Procedure InsAfter(tz:ref;a:char);
Var p:ref;
Begin
New(p);
P^.lit:=a;
P^.Next:=tz^.next;
Tz^.Next:=p;
End;
Procedure InsA(var inz:Ref;
a,b:char);
Vat tz:Ref;
Begin
tz:=Inz;
While tz<>nil do begin
if tz^.Lit=b
then InsAfter(tz,a)
tz:=tz^.Next
end;
End
Procedure InsAfter(tz:ref;a:char);
Var p:ref;
Begin
New(p);
P^.lit:=a;
P^.Next:=tz^.next;
Tz^.Next:=p;
End;
Procedure InsA(var inz:Ref;
a,b:char);
Vat tz:Ref;
Begin
tz:=Inz;
While tz<>nil do begin
if tz^.Lit=b
then InsAfter(tz,a);
tz:=tz^.Next
end
End;
Procedure InsAfter(tz:ref;a:char);
Var p:ref;
Begin
New(p);
P^.lit:=a;
P^.Next:=tz^.next;
Tz^.Next:=p;
End;
Procedure InsA(var inz:Ref;
a,b:char);
Vat tz:Ref;
Begin
tz:=Inz;
While tz<>nil do begin
if tz^.Lit=b
then InsAfter(tz,a);
tz:=tz^.Next
end
End;
Procedure InsAfter(tz:ref;a:char);
Var p:ref;
Begin
New(p);
P^.lit:=a;
P^.Next:=tz^.next;
Tz^.Next:=p;
End;
Procedure InsA(var inz:Ref;
a,b:char);
Vat tz:Ref;
Begin
tz:=Inz;
While tz<>nil do begin
if tz^.Lit=b
then InsAfter(tz,a);
tz:=tz^.Next
end
End;
Procedure InsAfter(tz:ref;a:char);
Var p:ref;
Begin
New(p);
P^.lit:=a;
P^.Next:=tz^.next;
Tz^.Next:=p;
End;
Procedure InsA(var inz:Ref;
a,b:char);
Vat tz:Ref;
Begin
tz:=Inz;
While tz<>nil do begin
if tz^.Lit=b
then InsAfter(tz,a);
tz:=tz^.Next
end
End;
Procedure InsAfter(tz:ref;a:char);
Var p:ref;
Begin
New(p);
P^.lit:=a;
P^.Next:=tz^.next;
Tz^.Next:=p;
End;
Procedure InsA(var inz:Ref;
a,b:char);
Vat tz:Ref;
Begin
tz:=Inz;
While tz<>nil do begin
if tz^.Lit=b
then InsAfter(tz,a);
tz:=tz^.Next
end
End;
Procedure InsAfter(tz:ref;a:char);
Var p:ref;
Begin
New(p);
P^.lit:=a;
P^.Next:=tz^.next;
Tz^.Next:=p;
End;
Procedure InsA(var inz:Ref;
a,b:char);
Vat tz:Ref;
Begin
tz:=Inz;
While tz<>nil do begin
if tz^.Lit=b
then InsAfter(tz,a);
tz:=tz^.Next
end
End;
Procedure InsAfter(tz:ref;a:char);
Var p:ref;
Begin
New(p);
P^.lit:=a;
P^.Next:=tz^.next;
Tz^.Next:=p;
End;
Procedure InsA(var inz:Ref;
a,b:char);
Vat tz:Ref;
Begin
tz:=Inz;
While tz<>nil do begin
if tz^.Lit=b
then InsAfter(tz,a);
tz:=tz^.Next
end
End;
a
Удаление элемента из списка.
В отличие от статического списка, в котором для
Удаление элемента из списка.
В отличие от статического списка, в котором для
а) удаление после текущего.
Пусть tz указывает на некоторый элемент списка, необходимо удалить следующий за ним элемент. Воспользуемся дополнительным указателем р. Установим его на следующее звено, перекинем связь Next минуя удаляемый элемент.‘с’‘л’‘о’‘н’‘.’
Procedure DelAfter(tz:ref);
Var p:ref;
Begin
P:=tz^.Next;{p:= след.звено}
If p<> nil;{если след. есть, то}
Then begin
tz^.Next:=p^.Next;
Dispose(p){перекинем связи и удалим объект}
end
End;
Недостаток метода: нельзя удалить первое звено.
р
tz
б) удаление текущего.
Пусть tz указывает на некоторый элемент списка, который нам
б) удаление текущего.
Пусть tz указывает на некоторый элемент списка, который нам
Procedure DelCur(tz:ref);
Var p:ref;
Begin
P:=tz^.Next;{p:= след.звено}
If p<> nil;{если след. есть, то}
Then begin
tz^.Next:=p^.Next;
tz^.Lit:=p^.lit;
Dispose(p){перекинем связи и удалим объект}
end
End;
р
tz
o
Дан линейный динамический список, удалить в нем все буквы ‘a’.
‘.’
nil
b
Procedure
Дан линейный динамический список, удалить в нем все буквы ‘a’.
‘.’
nil
b
Procedure
Var p:ref;
Begin
P:=tz^.Next;
If p<> nil;
Then begin
tz^.Next:=p^.Next;
tz^.Lit:=p^.lit;
Dispose(p)
end
End;
Procedure DelA(var inz:Ref; a:char);
Vat tz:Ref;
Begin
tz:=Inz;
While tz<>nil do
if tz^.Lit=a
then DelCur(tz)
else tz:=tz^.Next
End;
Procedure DelCur(tz:ref);
Var p:ref;
Begin
P:=tz^.Next;
If p<> nil;
Then begin
tz^.Next:=p^.Next;
tz^.Lit:=p^.lit;
Dispose(p)
end
End;
Procedure DelA(var inz:Ref;
a:char);
Vat tz:Ref;
Begin
tz:=Inz;
While tz<>nil do
if tz^.Lit=a
then DelCur(tz)
else tz:=tz^.Next
End;
Procedure DelCur(tz:ref);
Var p:ref;
Begin
P:=tz^.Next;
If p<> nil;
Then begin
tz^.Next:=p^.Next;
tz^.Lit:=p^.lit;
Dispose(p)
end
End;
Procedure DelA(var inz:Ref;
a:char);
Vat tz:Ref;
Begin
tz:=Inz;
While tz<>nil do
if tz^.Lit=a
then DelCur(tz)
else tz:=tz^.Next
End;
Procedure DelCur(tz:ref);
Var p:ref;
Begin
P:=tz^.Next;
If p<> nil;
Then begin
tz^.Next:=p^.Next;
tz^.Lit:=p^.lit;
Dispose(p)
end
End;
Procedure DelA(var inz:Ref;
a:char);
Vat tz:Ref;
Begin
tz:=Inz;
While tz<>nil do
if tz^.Lit=a
then DelCur(tz)
else tz:=tz^.Next
End;
Procedure DelCur(tz:ref);
Var p:ref;
Begin
P:=tz^.Next;
If p<> nil;
Then begin
tz^.Next:=p^.Next;
tz^.Lit:=p^.lit;
Dispose(p)
end
End;
Procedure DelA(var inz:Ref;
a:char);
Vat tz:Ref;
Begin
tz:=Inz;
While tz<>nil do
if tz^.Lit=a
then DelCur(tz)
else tz:=tz^.Next
End;
Procedure DelCur(tz:ref);
Var p:ref;
Begin
P:=tz^.Next;
If p<> nil;
Then begin
tz^.Next:=p^.Next;
tz^.Lit:=p^.lit;
Dispose(p)
end
End;
Procedure DelA(var inz:Ref;
a:char);
Vat tz:Ref;
Begin
tz:=Inz;
While tz<>nil do
if tz^.Lit=a
then DelCur(tz)
else tz:=tz^.Next
End;
Procedure DelCur(tz:ref);
Var p:ref;
Begin
P:=tz^.Next;
If p<> nil;
Then begin
tz^.Next:=p^.Next;
tz^.Lit:=p^.lit;
Dispose(p)
end
End;
Procedure DelA(var inz:Ref;
a:char);
Vat tz:Ref;
Begin
tz:=Inz;
While tz<>nil do
if tz^.Lit=a
then DelCur(tz)
else tz:=tz^.Next
End;
Procedure DelCur(tz:ref);
Var p:ref;
Begin
P:=tz^.Next;
If p<> nil;
Then begin
tz^.Next:=p^.Next;
tz^.Lit:=p^.lit;
Dispose(p)
end
End;
Procedure DelA(var inz:Ref;
a:char);
Vat tz:Ref;
Begin
tz:=Inz;
While tz<>nil do
if tz^.Lit=a
then DelCur(tz)
else tz:=tz^.Next
End;
Procedure DelCur(tz:ref);
Var p:ref;
Begin
P:=tz^.Next;
If p<> nil;
Then begin
tz^.Next:=p^.Next;
tz^.Lit:=p^.lit;
Dispose(p)
end
End;
Procedure DelA(var inz:Ref;
a:char);
Vat tz:Ref;
Begin
tz:=Inz;
While tz<>nil do
if tz^.Lit=a
then DelCur(tz)
else tz:=tz^.Next
End;
Procedure DelCur(tz:ref);
Var p:ref;
Begin
P:=tz^.Next;
If p<> nil;
Then begin
tz^.Next:=p^.Next;
tz^.Lit:=p^.lit;
Dispose(p)
end
End;
Procedure DelA(var inz:Ref;
a:char);
Vat tz:Ref;
Begin
tz:=Inz;
While tz<>nil do
if tz^.Lit=a
then DelCur(tz)
else tz:=tz^.Next
End;
Procedure DelCur(tz:ref);
Var p:ref;
Begin
P:=tz^.Next;
If p<> nil;
Then begin
tz^.Next:=p^.Next;
tz^.Lit:=p^.lit;
Dispose(p)
end
End;
Procedure DelA(var inz:Ref;
a:char);
Vat tz:Ref;
Begin
tz:=Inz;
While tz<>nil do
if tz^.Lit=a
then DelCur(tz)
else tz:=tz^.Next
End;
Procedure DelCur(tz:ref);
Var p:ref;
Begin
P:=tz^.Next;
If p<> nil;
Then begin
tz^.Next:=p^.Next;
tz^.Lit:=p^.lit;
Dispose(p)
end
End;
Procedure DelA(var inz:Ref;
a:char);
Vat tz:Ref;
Begin
tz:=Inz;
While tz<>nil do
if tz^.Lit=a
then DelCur(tz)
else tz:=tz^.Next
End;
c
Динамический линейный однонаправленный
кольцевой список с заглавным элементом
Основные проблемы классического
Динамический линейный однонаправленный
кольцевой список с заглавным элементом
Основные проблемы классического
наличие нескольких частных случаев списка: пустой, один элемент, несколько элементов. Каждый случай требует отдельного рассмотрения;
при удалении последнего оставшегося звена и получении пустого списка требуется изменение входного указателя inz, а это потребует усложнение процедур удаления элементов;
трудности с удалением крайних элементов списка;
гигантские проблемы с пустым списком, вставкой, удалением и так далее.
От большинства этих недостатков избавлен кольцевой список с заглавным элементом. Заглавный элемент не содержит информации, его задача избавиться от частного случая – пустой список, в котором inz=nil. Кольцо – позволяет замкнуть последнюю связь на заглавный элемент, что в принципе позволяет добраться до любого элемента.
Procedure CreateRing(var inz:ref);
Var tz:ref; a:char;
Begin
{создадим заглавное звено}
New(inz); tz:=Inz;
repeat
Procedure CreateRing(var inz:ref);
Var tz:ref; a:char;
Begin
{создадим заглавное звено}
New(inz); tz:=Inz;
repeat
Tz:=tz^.Next;{перейдем к следующему звену}
Read(a); tz^.lit:=a
Until a=’.’
Tz^.Next:=inz; ;{замкнем конец списка на его начало}
Readln ;{удалим enter из буфера клавиатуры}
End;
Inz
tz
‘с’
‘ы’
‘р’
‘.’
Вывод списка
Встаем на начало списка (inz), двигаемся по нему, переходя
Вывод списка
Встаем на начало списка (inz), двигаемся по нему, переходя
Procedure WriteList(inz:ref);
Var tz:ref;
Begin
tz:=Inz^.Next;{пропустим заглавный элемент}
While tz<>Inz Do
Begin
write(tz^.Lit);{выведем информацию из текущего звена}
Tz:=tz^.Next;{перейдем к следующему звену}
End;
End;
Признаком конца списка мы используем не символ ‘.’и пустую ссылку nil, а входной указатель inz.