Разработка алгоритма преобразования арифметического выражения «Вычисление арифметических выражений, состоящих из констант» и реализация программно

Язык программирования является подмножеством естественного языка и предназначен для поддержки процесса общения человека с компьютером. В общем случае язык это множество предложений, которые можно записать на нем. Отличие языка программирования от естественного в его законченности или замкнутости. Под этим понимается, что теоретически можно перечислить все предложения, которые можно на нем составить. Для естественного языка это невозможно. В контексте нашего изложения под языком программирования будем понимать не только языки высокого уровня, но и языки командных процессоров и вообще любые наборы предложений, с помощью которых производится управление работой некоторой программы.

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

Основа любого естественного языка его алфавит, то есть множество символов букв.

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

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

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

Постановка задачи

Разработать алгоритм преобразования арифметического выражения «Вычисление арифметических выражений, состоящих из констант «и реализовать программно.

Средства разработки программы: язык программирования С для операционной системы DOS.

Алгоритм решения задачи

Синтаксический анализ методом рекурсивного спуска. Рекурсивный спуск является самым «естественным» алгоритм нисходящего разбора построения дерева «сверху вниз». При нисходящем разборе этот каждый нетерминальный символ необходимо заменить на правую часть одного из правил из соответствующей группы, в котором он присутствует в левой части. Единственным основанием для такого выбора является начало той части терминальной строки (предложения), которое «покрывается» этим нетерминальным символом (синтаксической единицей).

Используется название «нисходящий» из-за способа построения синтаксического дерева. При разборе отправляются от начального символа и нисходят к предложению (рис. 1).

Рис. 1.

Отсюда следует самый простой неформальный алгоритм синтаксического анализа. Для каждой группы правил с общим нетерминальным символом в левой части пишется функция распознавания, которая по начальным символам терминальной цепочки в состоянии определить, правую часть какого правила следует применить. Затем она параллельно просматривает терминальную цепочку и правую часть правила. Если очередные терминальные символы в цепочке и в правиле совпадают, то они оба пропускаются, если нет, то это признак синтаксической ошибки. Если в правиле встречается нетерминальный символ, то необходимо вызвать аналогичную функцию для обработки группы правил, в которой этот нетерминал встречается в левой части. Посмотрим, как эта идея воплотится для распознавания терма F.

Запишем процедуры для нетерминальных символов такой грамматики:

: := :=

| IF THEN

| IF THEN ELSE

: := i | i ()

: := | +

: := | *

: := | ()

Чтобы удобнее было работать, перепишем грамматику так:

: :=: =

| IF THEN [ELSE ]

: := i [()]

: := {+}

: := {*}

: := | ()

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

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

2. Подобно этому, перед тем как выйти из процедуры с сообщением об успехе, символ, следующий за уже разработанной под цепочкой, помещается в NXTSYMB.

3. Процедура SCAN готовит очередной символ исходной программы и помещает его в NXTSYMB.

4. Программа ERROR вызывается в тех случаях, когда обнаружена ошибка. Она печатает сообщение и передает управление обратно. После возврата мы продолжим работу так, как будто бы ни какой ошибки не было (см. соображения, следующие за описанием процедур).

5. Для того чтобы начать синтаксический анализ инструкции, мы обращаемся к программе SCAN, которая поместит первый символ в NXTSYMB, а затем вызываем процедуру STATE.

Описание программы

Программа выполняет следующие функции:

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

разбор арифметического выражения;

вычисление значения арифметического выражения.

Основные функции программы:

PrintTablVar () вывод таблицы переменных

void AssignOp (void) разбор и расчет выражения

void ExpressAdd (void) вычисления выражения для сложения и вычитания

void ExpressMult (void) — вычисление выражения для умножения и деления

void ExpressFunc (void) — вычисление первичного выражения

double getfloat (char *num, int max) — взять число во входной строке и преобразовать к double

int GetName (char *name, int max) — взять имя во входной строке

int FindNameVar (char *var, int *num) — найти имя в таблице символов

int AddNameVar (char *var) — добавить новое имя в таблицу символов

void SkipBlanks () — пропуск служебных символов

int match (char *str) — проверка вхождения строки во входной строке