Жасмин Бланшет - QT 4: программирование GUI на С++

Например, «2*C5+D6» является выражением, первый терм которого будет «2*C5», а второй терм — «D6». «2*C5» является термом, первый фактор которого будет «2», а второй фактор — «C5»; «D6» состоит из одного фактора — «D6». Фактором могут быть число («2»), обозначение ячейки («C5») или выражение в скобках, перед которым может стоять знак минуса.

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

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

Давайте начнем с evalExpression(), то есть с функции, которая выполняет синтаксический разбор выражения:

01 QVariant Cell::evalExpression(const QString &str, int &pos) const

02 {

03 QVariant result = evalTerm(str, pos);

04 while (str[pos] != QChar::Null) {

05 QChar op = str[pos];

06 if (op != '+' && op != '-') return result;

07 ++pos;

08 QVariant term = evalTerm(str, pos);

09 if (result.type() == QVariant::Double

10 && term.type() == QVariant::Double) {

11 if (op == '+') {

12 result = result.toDouble() + term.toDouble();

13 } else {

14 result= result.toDouble() - term.toDouble();

15 }

16 } else {

17 result = Invalid;

18 }

19 }

20 return result;

21 }

Во-первых, мы вызываем функцию evalTerm() для получения значения первого терма. Если за ним идет символ «+» или «—», мы вызываем второй раз evalTerm(); в противном случае выражение состоит из единственного терма, и мы возвращаем его значение в качестве значения всего выражения. После получения значений первых двух термов мы вычисляем результат операции в зависимости от оператора. Если при оценке обоих термов их значения будут иметь тип double, мы рассчитываем результат в виде числа типа double; в противном случае мы устанавливаем результат на значение Invalid.

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

01 QVariant Cell::evalTerm(const QString &str, int &pos) const

02 {

03 QVariant result = evalFactor(str, pos);

04 while (str[pos] != QChar::Null) {

05 QChar op = str[pos];

06 if (op != '*' && op != '/')

07 return result;

08 ++pos;

09 QVariant factor = evalFactor(str, pos);

10 if (result.type() == QVariant::Double &&

11 factor.type() == QVariant::Double) {

12 if (op == '*') {

13 result = result.toDouble() * factor.toDouble();

14 } else {

15 if (factor.toDouble() == 0.0) {

16 result = Invalid;

17 } else {

18 result = result.toDouble() / factor.toDouble();

19 }

20 }

21 } else {

22 result = Invalid;

23 }

24 }

25 return result;

26 }

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

01 QVariant Cell::evalFactor(const QString &str, int &pos) const

02 {

03 QVariant result;

04 bool negative = false;

05 if (str[pos] == '-') {

06 negative = true;

07 ++pos;

08 }

09 if (str[pos] == '(') {

10 ++pos;

11 result = evalExpression(str, pos);

12 if (str[pos] != ')')

13 result = Invalid;

14 ++pos;

15 } else {

16 QRegExp regExp("[A-Za-z][1-9][0-9]{0,2}");

17 QString token;

18 while (str[pos].isLetterOrNumber() || str[pos] == '.') {

19 token += str[pos];

20 ++pos;

21 }

22 if (regExp.exactMatch(token)) {

23 int column = token[0].toUpper().unicode() - 'A';

24 int row = token.mid(1).toInt() - 1;

25 Cell *c = static_cast(tableWidget()->item(row, column));

26 if (c) {

27 result = c->value();

28 } else {

29 result = 0.0;

30 }

31 } else {

32 bool ok;

33 result = token.toDouble(&ok);

34 if (!ok)

35 result = Invalid;

36 }

37 }

38 if (negative) {

39 if (result.type() == QVariant::Double) {

40 result = -result.toDouble();

41 } else {

42 result = Invalid;

43 }

44 }

45 return result;

46 }

Функция evalFactor() немного сложнее, чем evalExpression() и evalTerm(). Мы начинаем с проверки, не является ли фактор отрицательным. Затем мы проверяем наличие открытой скобки. Если она имеется, мы анализируем значение внутри скобок как выражение, вызывая evalExpression(). При анализе выражения в скобках evalExpression() вызывает функцию evalTerm(), которая вызывает функцию evalFactor(), которая вновь вызывает функцию evalExpression(). Именно в этом месте осуществляется рекурсия при синтаксическом анализе.

Если фактором не является вложенное выражение, мы выделяем следующую лексему (token), и она должна задавать обозначение ячейки или быть числом. Если эта лексема удовлетворяет регулярному выражению в переменной QRegExp, мы считаем, что она является ссылкой на ячейку, и вызываем функцию value() для этой ячейки. Ячейка может располагаться в любом месте в электронной таблице, и она может ссылаться на другие ячейки. Такая зависимость не вызывает проблемы и просто приводит к дополнительным вызовам функции value() и к дополнительному синтаксическому анализу ячеек с признаком «dirty» («грязный») для перерасчета значений всех зависимых ячеек. Если лексема не является ссылкой на ячейку, мы рассматриваем ее как число.

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

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