Анализаторы Паскаль-программы для вычисления центральной разностной производной, арифметических выражений и языка право-линейной грамматики

Текст задания 3
Правила грамматики описания указанных конструкций с указанием типа грамматики по классификации Хомского 3
Диаграмма лексического анализатора 5
Тестовые примеры 11
Список использованных источников 15

То, какой узел в дерене является операцией, а какой — операндом, никак невозможно определить из грамматики, описывающей синтаксис входного языка. Также ниоткуда не следует, каким операциям должен соответствовать объектный код в результирующей программе, а каким — нет. Все это определяется только исходя из семантики — «смысла» — языка входной программы. Поэтому только разработчик компилятора может четко определить, как при построении дерева операции должны различаться операнды и сами операции, а также то, какие операции являются семантически незначащими для порождения объектного кода.Алгоритм преобразования дерева семантического разбора и дерево операции можно представить следующим образом.Шаг 1. Если в дереве больше не содержится узлов, помеченных нетерминальными символами, то выполнение алгоритма завершено; иначе — перейти к шагу 2Шаг. 2. Выбрать крайний левый узел дерена, помеченный нетерминальным символом грамматики и сделать его текущим. Перейти к шагу 3.Шаг 3. Если текущий узел имеет только один нижележащий узел, то текущий узел необходимо удалить из дерена, а связанный с ним узел присоединить к узлу вышележащего уровня (исключить из дерена цепочку) и вернуться к шагу 1; иначе – перейти к шагу 4.Шаг 4. Если текущий узел имеет нижележащий узел (лист дерева), помеченный терминальным символом, который не несет семантической нагрузки, тогда этот лист нужно удалить из дерева и вернуться к шагу 3; иначе — перейти к шагу 5.Шаг 5. Если текущий узел имеет один нижележащий узел (лист дерева), помеченный терминальным символом, обозначающим знак операции, а остальные узлы помечены как операнды, то лист, помеченный знаком операции, надо удалить из дерева, текущий узел пометить этим знаком операции и перейти к шагу 1; иначе — перейти к шагу 6.Шаг 6. Если среди нижележащих узлов для текущего узла есть узлы, помеченные нетерминальными символами грамматики, то необходимо выбрать крайний левый среди этих узлов, сделать его текущим умом и перейти к шагу 3: иначе — выполнение алгоритма завершено.Тестовые примеры/* prog - файл с транслируемой программой, lex - выходной файл лексем */ while(!feof (prog)) { ch = readsym(); /* чтение очередного символа ch с пропуском пробелов */ if(isAlpha(ch)) fprintf(lex, "%c %d", ch, 1); else if(isDigit(ch)) digit(); /* Процедура чтения числа и вывода его в файл */ else if(ch == '=') fprintf(lex, "%c %d", ch, 3); else if(ch == '*' || ch == '/') fprintf(lex, "%c %d", ch, 4); else if(ch == '+' || ch == '-') fprintf(lex, "%c %d", ch, 5); elseprintf("Недопустимый символ языка - %c \n", ch); }2. Алгоритм перевода в обратную польскую запись функции, имеющей не менее одного параметра, такой же, что для переменной с индексами, но различие состоит в том, что в момент прихода закрывающей круглой скобки в выходную строку записывается символ Ф. Чтобы отличить открывающую круглую скобку в начале списка фактических параметров от открывающей круглой скобки в начале выражения, используют специальную переменную состояния f (признак функции), которая обычно имеет значение 0. В момент появления идентификатора функции f принимает значение 1, а после занесения в стек круглой скобки и начального значения счетчика операндов, равного 2, вновь принимает значение 0. Закрывающая скобка, встретив в стеке открывающую круглую скобку, записанную вместе со значением счетчика операндов, заносит это значение в выходную строку, записывает туда знак Ф и уничтожает в стеке круглую скобку и значение счетчика операндов.Обратная польская нотация (RPN) заданного выражения – корень(4*a – 8/a^2) будет иметь вид 0 4 а-8*а корень2^/3. Обычно задача решается следующим образом:Каждому состоянию ставим в соответствие нетерминал. Если есть переход из состояния X в состояние Y по а, добавляем правило X → aY. Для конечных состояний добавляем правила X → ε. Для ε-переходов — X → Y.Пример.Продукция грамматики имеет вид:A → aB | cCB → bD | cEC → εD → aB | cCE → aB | cCСписок использованных источниковСеребряков – Языки программирования: http://infonet.cherepovets.ru/citforum/programming/theory/serebryakovСвободная энциклопедия – Википедия http://ru.wikipedia.org/wiki/%D0%A2%D1%80%D0%B0%D0%BD%D1%81%D0%BB%D1%8F%D1%82%D0%BE%D1%80