Лабораторна робота №6
(модуль 1)
Тема: Непряма рекурсія. Синтаксичний аналіз формули. (2 години)
Мета: Закріпити знання про рекурсивні методи, а саме про непряму рекурсію. Сформувати навички синтаксичного аналізу формул. Сформувати уміння застосовувати синтаксичні діаграми і синтаксичний аналіз для обчислення значення виразів.
Література:
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.– М.: Мир, 1979.– 536 с.
Венц А. Н. Профессия – программист.– Ростов: Изд-во «Феникс», 1999.– 384 с.
Гусева А.И. Учимся информатике: задачи и методы решения.– М.: «Диалог – МИФИ», 1998.– 320 с.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ.– М.: МЦНМО, 1999.– 960 с.
Культин Н.Б. Turbo Pascal в задачах и примерах
М.С.Львов, О.В. Співаковський. Основи алгоритмізації та програмування.
Марченко А.И., Марченко Л.А. Программирование в среде Turbo Pascal 7.0
Меженный О.А. Turbo Pascal
Н. Вирт. Алгортитмы + структуры данных = программы. – М.: Мир. - 1985.
Н.Вирт. Алгоритмы + структуры данных = программы. Москва, Мир, 1985 г. 406 с.
Н.Вирт. Алгоритмы и структуры данных. Москва, Мир, 1989 г. 420 с.
Немцова Т.И., Голова С.Ю., Абрамова И.В. Программирование на языке высокого уровня. программирование на языке Object Pascal
Окулов С.М. Основы программирования.– М.: ЮНИМЕДИАСТАЙЛ, 2002.– 424 с.
Павловская Т.А. Паскаль. Программирование на языке высокого уровня
Пильщиков В.Н. Сборник упражнений по языку Паскаль. Москва, Наука, 1989 г., 160 с.
Р. Хэзфилд, К. Лоуренс и др.Искусство программирования на С. – К.: «ДиаСофт». - 2001.
Фаронов В.В. Turbo Pascal 7.0. Начальный курс. – Учебное пособие. – М.: Издательство «ОМД Групп», 2003 г. -616 с.
Фаронов В.В. Turbo Pascal 7.0. Практика программирования
Фаронов В.В. Turbo Pascal 7.0. Учебный курс
План.
Основні етапи аналізу.
Лексичний аналіз.
Синтаксичний і контекстний аналіз формули.
Обчислення значень формули.
Короткі теоретичні відомості.
Рекурсивні описи алгоритмів містять тільки спосіб зведення задачі, що розв’язується, до такої ж задачі, тільки «меншого розміру». Хід розв’язування задачі у явному вигляді не описується, а застосування способа зведення для розв’язування задачі бере на себе система програмування.
Опис процедури (функції) P, у розділі операторів якої використовується оператор цієї процедури (виклик функції), називається рекурсивним.
Програма, яка використовує рекурсивно описану процедуру (функцію) має вигляд
На цій схемі тіла основної програми B і процедури P позначені прямокутниками, а виклики – стрілками. Звертання процедури Р до себе означає, що стрілка рекурсивного виклику вказує на заголовок Р.
Основні етапи аналізу
Лексичний аналізатор розбиває вхідний потік на неподільні частини-лексеми (число, ідентифікатор, знак операції і т.д.).
Синтаксичний аналізатор аналізує послідовність лексем і створює проміжний код, що потім інтерпретується.
Інтерпретатор.
Непряма рекурсія
Процедура (функція), що викликає безпосередньо саме себе, називається рекурсивною. У деяких ситуаціях рекурсія організується непрямим чином: за допомогою декількох процедур, виклики яких утворюють кільце!
. . .
На малюнку показана схема побічно рекурсивних викликів процедур A, B, .., Z. Для ілюстрації програмування непрямої рекурсії розглянемо задачу аналізу синтаксичної правильності арифметичного виразу.
Хід заняття.
Задача 1. Арифметичний вираз складений з однобуквених змінних, знаків операцій +, -, *, / і круглих дужок. Складіть програму, що перевіряє дотримання синтаксису в цьому виразі.
Розв’язок. В основі розв’язку цієї задачі, як і інших задач синтаксичного аналізу, лежить опис поняття правильно побудованого арифметичного виразу. Один з можливих способів синтаксичних описів - мова синтаксичних діаграм.
Розглянемо правила опису виразів, синтаксичні діаграми цих правил і процедури аналізу правильності, побудовані за цими правилами. Для простоти ми представляємо аналізований вираз як дане A типу String. Рядок А містить т.зв. вхідний потік - аналізований вираз, що закінчується крапкою (ознакою кінця).
Правило:
Арифметичний вираз складається з одного або декількох доданків, відділених один від одного знаками + (плюс) або - (мінус)

Діаграма Вираз
Procedure Expression;
begin
Summa;
While Sym in ['+', '-'] do
begin
NextSymbol; Summa
End
end;
Правило:
Доданок складається з одного співмножника або декількох співмножників відділених один від одного знаками * (множення) або / (ділення)

Діаграма Доданок
Procedure Summa;
begin
Factor;
While Sym in ['*', '/'] do begin
NextSymbol; Factor
end
end;
Правило
Співмножник - це змінна або арифметичний вираз, узятий в круглі дужки.
Діаграма Співмножник
Procedure Factor;
Begin
If Sym = '('
then begin
NextSymbol; Expression;
If Sym = ')' then NextSymbol else Error
end
else if Sym in Variables
then NextSymbol else Error
end;
Отже, синтаксичні діаграми відповідають правилам побудови виразів і відіграють роль формальних описів – технічних завдань для написання процедур аналізу правильності виразів. Програма аналізу правильності виразу викликає «по колу» Expression, Summ і Factor:
Expression ( Summ ( Factor ( Expression
Програма аналізу виразу виглядає у такий спосіб:
Program Synt;
Var A:String;
Ch, Sym: Char; i:Integer;
Variables: Set of Char;

Procedure Expression; Forward;
Procedure Error;
begin
Writeln('Terrible Error');
Ch:=ReadKey; Halt
end;

Procedure NextSymbol;
Begin
inc(i); Sym := A[i]; Write(Sym);
end;

{Procedure Factor;}
{Procedure Summa;}
{Procedure Expression;}
begin
Variables := ['a'..'z'];
Writeln('Input expression '); Readln(A);
i:=0; NextSymbol;
Expression;
If Sym = '.'
then Writeln('OK')
else Writeln('Uncorrect End of Expression');
end.
Задачі для самостійного розв’язування
Написати програму, що вилучає з тексту всі підслова виду 'abc'.
У мові програмування Pascal коментарі записують у фігурних дужках:
begin {початок циклу}
i:=i+1; {збільшуємо i на 1}
Написати програму, що вилучала б коментарі і вставляла б замість виключеного коментарію пробіл (щоб '1{один}2' перетворилося не в '12', а в '1 2').
Складіть програму для розпізнавання дійсного числа.
Складіть програму для розпізнавання дійсного числа, якщо перед числом може стояти знак "мінус" або знак "плюс" (а може нічого не стояти).
Складіть програму для розпізнавання дійсного числа, якщо до того ж після числа може стояти показник ступеня десяти, як у 254E-4 (=0.0254) або в 0.123E+9 (=123000000)
Що треба змінити в програмі задачі 5, щоб дозволити порожні цілу і дробову частини (як у '1.', '.1' або навіть '.' - останнє число вважаємо рівним нулеві)?
Складіть програму, що визначає правильність розміщення трьох видів дужок ( ), [ ], { }.
Складіть програму реалізації калькулятора, що виконує дії +, –, *, / в арифметичному виразі, що містить числа.
Напишіть програму синтаксичного аналізу правильності арифметичного виразу, що містить ще операцію піднесення в степінь і функції від однієї або декількох змінних. Ім'я функції містить три букви.
Напишіть програму обчислення значення арифметичного виразу, який містить операції +, –, *, / та піднесення в степінь і функції від однієї або декількох змінних. Ім'я функції містить три букви. Придумайте спосіб введення значень змінних, що входять у вираз.