Шаг 183.
Библиотека Qt.
Синтаксический анализ формул

    На этом шаге рассмотрим синтаксический анализ формул в приложении Электронная таблица.

    Функция evalExpression() возвращает значение выражения из ячейки электронной таблицы. Выражение состоит из одного или нескольких термов, разделенных знаками операций "+" или "-". Термы состоят из одного или нескольких факторов, разделенных знаками операций "*" или "/". Разбивая выражения на термы, а термы на факторы, мы обеспечиваем правильную последовательность выполнения операций.

    Например, "2*C5+D6" является выражением, первый терм которого будет "2*С5", а второй терм - "D6". "2*С5" является термом, первый фактор которого будет "2", а второй фактор - "С5"; "D6" состоит из одного фактора - "D6".

    Фактором может быть число ("2"), обозначение ячейки ("С5") или выражение в скобках, перед которым может стоять знак минуса. Блок-схема синтаксического анализа выражений электронной таблицы представлена на рис. 1.


Рис.1. Блок-схема синтаксического анализа выражений электронной таблицы

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

QVariant Cell::evalExpression(const QString &str, int &pos) const
{
    //вызываем функцию evalTerm() для получения значения первого терма
    QVariant result = evalTerm(str, pos);
    while (str[pos] != QChar::Null) {
        QChar op = str[pos];
        /*если за ним не идет символ "+" или "-",
        то выражение состоит из единственного терма, и мы возвращаем его значение
        в качестве значения всего выражения*/
        if (op != '+' && op != '-')
            return result;
        ++pos;
        //в противном случае, вызываем второй раз evalTerm()
        QVariant term = evalTerm(str, pos);
        /*после получения значений первых двух термов мы вычисляем
        результат операции в зависимости от оператора. Если при оценке обоих
        термов их значения будут иметь тип double, мы рассчитываем результат в
        виде числа типа double; в противном случае мы устанавливаем результат на
        значение Invalid*/
        if (result.type() == QVariant::Double
                && term.type() == QVariant::Double) {
            if (op == '+') {
                result = result.toDouble() + term.toDouble();
            } else {
                result = result.toDouble() - term.toDouble();
            }
        } else {
            result = Invalid;
        }
    }
    return result;
}

    Продолжаем эту процедуру, пока не закончатся термы. Это даст правильный результат, потому что операции сложения и вычитания обладают свойством "ассоциативности слева" (left-associative); то есть "1-2-3" означает "(1-2)-3", а не "1-(2-3)".

    Функция evalTerm() очень напоминает функцию evalExpression(), но в отличие от последней она имеет дело с операциями умножения и деления.

QVariant Cell::evalTerm(const QString &str, int &pos) const
{
    QVariant result = evalFactor(str, pos);
    while (str[pos] != QChar::Null) {
        QChar op = str[pos];
        if (op != '*' && op != '/')
            return result;
        ++pos;
        QVariant factor = evalFactor(str, pos);
        if (result.type() == QVariant::Double
                && factor.type() == QVariant::Double) {
            if (op == '*') {
                result = result.toDouble() * factor.toDouble();
            } else {
                if (factor.toDouble() == 0.0) {
                    result = Invalid;
                } else {
                    result = result.toDouble() / factor.toDouble();
                }
            }
        } else {
            result = Invalid;
        }
    }
    return result;
}

    В функции evalTerm() необходимо учитывать одну тонкость, а именно, нельзя допускать деление на нуль, так как это приводит к ошибке на некоторых процессорах. Хотя не рекомендуется проверять равенство чисел с плавающей точкой из-за ошибки округления, можно спокойно делать проверку на равенство значению 0.0 для предотвращения деления на нуль.

    Функция evalFactor():

QVariant Cell::evalFactor(const QString &str, int &pos) const
{
    QVariant result;
    bool negative = false;
    //начинаем с проверки, не является ли фактор отрицательным
    if (str[pos] == '-') {
        negative = true;
        ++pos;
    }
    //проверяем наличие открытой скобки
    if (str[pos] == '(') {
        ++pos;
        /*если она имеется, анализируем значение внутри скобок как выражение,
        вызывая evalExpression(). При анализе выражения в скобках evalExpression()
        вызывает функцию evalTerm(), которая вызывает функцию evalFactor(),
        которая вновь вызывает функцию evalExpression(). Именно в этом месте
        осуществляется рекурсия при синтаксическом анализе*/
        result = evalExpression(str, pos);
        if (str[pos] != ')')
            result = Invalid;
        ++pos;
    } else {
      /*если фактором не является вложенное выражение, мы выделяем
      следующую лексему (token), и она должна задавать обозначение ячейки или
      быть числом*/
        QRegExp regExp("[A-Za-z][1-9][0-9]{0,2}");
        QString token;
        while (str[pos].isLetterOrNumber() || str[pos] == '.') {
            token += str[pos];
            ++pos;
        }
        /*если эта лексема удовлетворяет регулярному выражению в переменной QRegExp,
        мы считаем, что она является ссылкой на ячейку, и вызываем функцию value()
        для этой ячейки. Ячейка может располагаться в любом месте в электронной
        таблице, и она может ссылаться на другие ячейки. Такая зависимость не
        вызывает проблемы и просто приводит к дополнительным вызовам функции
        value() и к дополнительному синтаксическому анализу ячеек с признаком
        "dirty" для перерасчета значений всех зависимых ячеек*/
        if (regExp.exactMatch(token)) {
            int column = token[0].toUpper().unicode() - 'A';
            int row = token.mid(1).toInt() - 1;
            Cell *c = static_cast<Cell *>(
                              tableWidget()->item(row, column));
            if (c) {
                result = c->value();
            } else {
                result = 0.0;
            }
        } else {
          //если лексема не является ссылкой на ячейку, рассматриваем ее как число 
            bool ok;
            result = token.toDouble(&ok);
            if (!ok)
                result = Invalid;
        }
    }
    if (negative) {
        if (result.type() == QVariant::Double) {
            result = -result.toDouble();
        } else {
            result = Invalid;
        }
    }
    return result;
}

    Что произойдет, если ячейка А1 содержит формулу "=А1"? Или если ячейка А1 содержит "=А2", а ячейка А2 содержит "=А1"? Хотя нами не написан специальный программный код для обнаружения бесконечных циклов в рекурсивных зависимостях, парсер прекрасно справится с этой ситуацией и возвратит недопустимое значение переменной типа QVariant. Это даст нужный результат, поскольку мы устанавливаем флажок cachelsDirty на значение false и переменную cachedValue на значение Invalid в функции value() перед вызовом evalExpression(). Если evalExpression() рекурсивно вызывает функцию value() для той же ячейки, она немедленно возвращает значение Invalid, и тогда все выражение принимает значение Invalid.

    Теперь мы завершили программу синтаксического анализа формул. Ее можно легко модифицировать для обработки стандартных функций электронной таблицы, например "sum()" и "avg()", расширяя грамматическое определение фактора. Можно также легко расширить эту реализацию, обеспечив возможность выполнения операции "+" над строковыми операндами (для их конкатенации); это не потребует внесения изменений в грамматику.

    Файлы приложения Электронная таблица можно взять здесь.

    На следующем шаге приступим к рассмотрению большого раздела, посвященного компьютерной графике, и начнем с классов геометрии.




Предыдущий шаг Содержание Следующий шаг