Парсер математических выражений

strbb

Как написать парсер математических выражений? Надо реализовать не только операторы (+, -, /, *), но и функции, например log, sin, cos, tan и т.д.

7 ответов

strbb

У математических выражений довольно простая структура - только бинарные операции ("+", "*" - два аргумента), унарные операции ("-", "sin" - один аргумент), и числа.

Один из наиболее простых способов написания парсера - это "рекурсивный спуск", т.е. написание парсера руками, без какого либо генератора парсеров (Bison, Boost.Spirit).

Хотя парсер может вычислять сразу выражение, обычно от парсера ожидается дерево операций, которое уже потом можно вычислить, или например напечатать. В простейшем виде элемент дерева выглядит так:

struct Expression {
    Expression(std::string token) : token(token) {} // Конструктор для чисел
    Expression(std::string token, Expression a) : token(token), args{a} {} // Конструктор унарных операций
    Expression(std::string token, Expression a, Expression b) : token(token), args{a, b} {} // Конструктор бинарных операций

    std::string token; // Операция или число
    std::vector<expression> args; // Выражения - аргументы операции
};
</expression>

Парсер математических выражений можно описать с помощью трех основных функций:

  • парсер "токенов" - низкоуровневых элементов выражения - операций и чисел. Например 2, *, -, 1 для выражения 2 * -1.
  • парсер простых выражений - числа, унарные операции, выражения в скобках. Например выражения 1, -1, (1+2).
  • парсер бинарных выражений - два простых выражения, и бинарный оператор между ними. Например выражения 1 + 2, или 3 * (1+2).

Соответственно можно написать такой класс парсера:

class Parser {
public:
    explicit Parser(const char* input) : input(input) {} // Конструктор, принимает строку с выражением
    Expression parse(); // Основная функция парсинга
private:
    std::string parse_token(); // Парсит один токен
    Expression parse_simple_expression(); // Парсит простое выражение
    Expression parse_binary_expression(int min_priority); // Парсит бинарное выражение

    const char* input; // Кусок строки, который еще не распарсили
};

Функция-парсер токенов извлекает из строки один токен, и продвигает input вперед.

std::string Parser::parse_token() {
    // Пропускаем пробелы перед токеном.        
    while (std::isspace(*input)) ++input;

    // Если input начинается с цифры, то парсим число.
    if (std::isdigit(*input)) {
        std::string number;
        while (std::isdigit(*input) || *input == '.') number.push_back(*input++);
        return number;
    }

    // Список всех известных токенов - операции и скобки.
    static const std::string tokens[] =
        { "+", "-", "**", "*", "/", "mod", "abs", "sin", "cos", "(", ")" };
    for (auto& t : tokens) {
        if (std::strncmp(input, t.c_str(), t.size()) == 0) {
            input += t.size();
            return t;
        }
    }

    return ""; // Какой-то неизвестный токен, или символ '\0' - конец строки.
}

Имея парсер токенов, можно написать парсер простых выражений:

Expression Parser::parse_simple_expression() {
    // Парсим первый токен.
    auto token = parse_token();
    if (token.empty()) // Неожиданный конец строки, или неизвестный токен
        throw std::runtime_error("Invalid input");

    if (std::isdigit(token[0])) // Если это цифра, возвращаем выражение без аргументов
        return Expression(token);

    if (token == "(") {
        auto result = parse();
        if (parse_token() != ")") throw std::runtime_error("Expected ')'");
        return result; // Если это скобки, парсим и возвращаем выражение в скобках
    }

    // Иначе, это унарная операция ("-", "sin", и т.п.)
    auto arg = parse_simple_expression(); // Парсим ее аргумент.
    return Expression(token, arg);
}

И наконец, последняя и самая сложная часть - бинарные выражения. У бинарных операций есть приоритеты, например у + и - приоритет меньше чем у * и /, у ** (возведение в степень) приоритет больше чем у умножения. Напишем функцию, возвращающую приоритет бинарной операции:

int get_priority(const std::string& token) {
    if (token == "+") return 1;
    if (token == "-") return 1;
    if (token == "*") return 2;
    if (token == "/") return 2;
    if (token == "mod") return 2; // остаток от деления
    if (token == "**") return 3; // степень
    return 0; // Возвращаем 0 если токен - это не бинарная операция (например ")")
}

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

Expression Parser::parse_binary_expression(int min_priority) {
    auto left_expr = parse_simple_expression(); // Парсим простое выражение.

    for (;;) {
        auto op = parse_token(); // Пробуем парсить бинарную операцию.
        auto priority = get_priority(op);
        // Выходим из цикла если ее приоритет слишком низок (или это не бинарная операция).
        if (priority <= min_priority) {
            input -= op.size(); // Отдаем токен обратно,
            return left_expr; // возвращаем выражение слева.
        }

        // Парсим выражение справа. Текущая операция задает минимальный приоритет.
        auto right_expr = parse_binary_expression(priority);
        left_expr = Expression(op, left_expr, right_expr); // Обновляем выражение слева.
    } // Повторяем цикл: парсинг операции, и проверка ее приоритета.
}

Функция parse() просто вызывает парсер бинарных выражений, передавая ему нулевой минимальный приоритет операций (любая бинарная операция):

Expression Parser::parse() {
    return parse_binary_expression(0);
}

Для строки"3*4/5" код работает так:

Сначала left_expr парсится как простое выражение "3",
затем парсится токен "*", его приоритет (2) больше минимального (0).
Парсится выражение справа: делается вызов parse_binary_expression(2).
    Здесь input="4/5", left_expr парсится как "4", за ним идет токен с операцией "/",
    но теперь его приоритет 2 не больше минимального (2), цикл сразу же заканчивается,
    токен "/" возвращается обратно (input="/5"), возвращается выражение "4".
Из правых и левых частей получается выражение ("*", "3", "4"), цикл повторяется.
Опять парсится токен "/", его приоритет (2) больше минимального (0).
Парсится выражение справа: вызов parse_binary_expression(2), при этом input = "5".
    left_expr парсится как "5", за ним идет пустой токен "" (конец строки).
    приоритет 0 меньше минимального (2), возвращается выражение "5".
Из правых и левых частей получается выражение ("/", ("*", "3", "4"), "5").
Цикл повторяется, опять парсится пустой токен "", функция завершается.

Если приоритеты повышаются, например 2+3*4/5, то во вложенных вызовах parse_binary_expression успевает отработать дольше:

Парсится выражение слева "2" и операция "+" (приоритет 1).
Для правой части делается вызов parse_binary_expression(1).
     Здесь всё как в предыдущем примере, input="3*4/5",
     только минимальный приоритет равен 1 а не 0.
     Цикл проходит несколько итераций, и мы получаем ("/", ("*", "3", "4"), "5")
     Дальше идут только пустые токены, т.к. input закончился. Выходим из цикла.
Объединяем правую и левую части, получаем ("+", "2", ("/", ("*", "3", "4"), "5")).

Итак, у нас есть парсер. Но надо еще как-то вычислять результаты парсинга. Это можно сделать одной функцией:

****** eval(const Expression& e) {
    switch (e.args.size()) {
        case 2: { // Два аргумента - бинарные операции.
            auto a = eval(e.args[0]);
            auto b = eval(e.args[1]);
            if (e.token == "+") return a + b;
            if (e.token == "-") return a - b;
            if (e.token == "*") return a * b;
            if (e.token == "/") return a / b;
            if (e.token == "**") return pow(a, b);
            if (e.token == "mod") return (int)a % (int)b;
            throw std::runtime_error("Unknown binary operator");
        }

        case 1: { // Один аргумент.
            auto a = eval(e.args[0]);
            if (e.token == "+") return +a;
            if (e.token == "-") return -a;
            if (e.token == "abs") return abs(a);
            if (e.token == "sin") return sin(a);
            if (e.token == "cos") return cos(a);
            throw std::runtime_error("Unknown unary operator");
        }

        case 0: { // Числа (ноль аргументов).
            return strtod(e.token.c_str(), nullptr);
        }
    }

    throw std::runtime_error("Unknown expression type");
}

>>> Здесь <<< можно найти весь код целиком.

Что делать если надо добавить функцию, которая принимает больше одного аргумента? - Функция, принимающая несколько аргументов - это функция принимающая один аргумент-кортеж (список). По этому самое простое решение - это ввести бинарную операцию "," (запятая), которая будет делать кортеж (список) чисел.


strbb

Допустим у нас уже есть простой интерпретатор (калькулятор) арифметического выражения в строке (scalc.c scalc.h) и мы хотим добавить к нему функции.

Калькулятор получает строку с выражением и интерпретирует ее, используя известный алгоритм с двумя стеками (операндов и операций) до первой встреченной ошибки. Несколько упрощенно (выброшен анализ ошибок структуры выражения и вспомогательные функции) его код может быть таким:

Контекст интерпретации выражения, в основном используется для уменьшения количества аргументов функций

    struct calc {
      const char *str; // expression source
      int  rc,         // return code (OK == 0 or some error)
        pos,           // position to scan next lexem
        histop;        // lexems type (operation/number) "history" 
      ****** result;   // current (and final) eval result or just read number
    #define STACK(T) struct { T *mem; int size, sp; } 
      STACK(******) nums; // stack for numbers (operands)
      STACK(char) ops;    // operations stack
    #undef DSTACK
    };

Лексер

    static int
    getlex (struct calc *ctx)
    {
      int i = ctx->pos, op;
      ctx->histop <<= 1; // shift operations history

      // skip spaces
      if (!(ctx->str[i += strspn(ctx->str + ctx->pos, " \t\r\n")])) {
        ctx->pos = i;
        return EOF;
      }
      ctx->pos = i + 1; // new starting position 

      char *p;
      static char *ops = "+-*/()";
      // take current character and  determine the type of the token
      if ((p = (char *)strchr(ops, op = ctx->str[i]))) {
        if (PREVOP(ctx->histop)) // clarify operation
          op = "PM*/()"[p - ops];
        ctx->histop |= op == ')' ? 0 : 1; 
      } else if (isdigit(op) || op == '.') { // number?
        ctx->result = strtod(ctx->str + i, &p);
        if (p != ctx->str + i) { // realy, next calls will detect possible error
          op = 'N';
          ctx->pos = p - ctx->str; // correct new starting position
        }
      } else
        op = '?';

      return op;
    }

Основные функции интерпретации выражения

"main"

    int
    calc (const char *str, ****** *pres)
    {
      if (!str)
        return EOF;
      *pres = NAN;
      // init context
      struct calc ctx = {str};
      ctx.result = NAN;
      // simulate that previous lexem was operation for simpler errors checking
      ctx.histop = 1; 

      int op; // lexem type
      while (ctx.rc == 0 && (op = getlex(&ctx)) != EOF) {
        switch (op) {
          // ignore unar `+`
        case 'P':
          break; 
          // push `(` and unar `-` to stack
        case '(': case 'M':
          PUSH(&ctx.ops, op);
          break;
          // push (and eval part of stack) `+` `-` `*` or `/` operations 
        case ')': case '*': case '/': case '+': case '-':
          eval(&ctx, op);
          break;
          // push new number to operands stack
        case 'N':
          PUSH(&ctx.nums, ctx.result);
          break;
          // invalid input char
        default: 
          ctx.rc = CALC_ERR_INPUT;
        }
      }

      if (!ctx.rc) // OK, eval stack
        eval(&ctx, EOF);
      *pres = ctx.result;
      // final stacks check 
      if (!ctx.rc) {
        if (ctx.nums.sp == 0 && ctx.ops.sp == 0)
          ctx.rc = CALC_NO_INPUT;
        else if (ctx.nums.sp > 1)
          ctx.rc = CALC_NUMS_ERR;
        else if (ctx.ops.sp)
          ctx.rc = CALC_OPRS_ERR;
      }
      free(ctx.nums.mem);
      free(ctx.ops.mem);

      return ctx.rc;
    }

Вычисление арифметической операции

/*
  Performs one elementary operation with operands in the stack
  Returns 0 -- error or 1 -- OK
 */
static int
expr (struct calc *ctx, int op)
{
  int n = op == 'M' ? 1 : 2; // number of operands

  if (ctx->nums.sp < n) 
    return !(ctx->rc = CALC_NO_NUMS);

  switch (op) {
  case '+':
    ctx->result = ctx->nums.mem[ctx->nums.sp - 1] + 
      ctx->nums.mem[ctx->nums.sp - 2];    break;
  аналогично case '-': case '*': case '/':
  ...

  case 'M':
    ctx->result = -(ctx->nums.mem[ctx->nums.sp - 1]);
    break;
    // internal error, unknown op
  default:
    return !(ctx->rc = CALC_ERR_OP);
  }

  ctx->nums.mem[ctx->nums.sp - n] = ctx->result;
  ctx->nums.sp -= (n - 1); // adjust the top of the stack

  return 1;
}

Вычисление очередной операции и манипуляции со стеком операций

/*
  Push the operation onto the stack, 
  popping and then perform the same or lower priority operations.
  Returns 0 -- error or 1 -- OK, last calculation result in ctx->result
 */
static int
eval (struct calc *ctx, int op)
{
  int p1 = priority(op);

  while (!EMPTY(&ctx->ops) && (p1  <= priority(TOP(&ctx->ops)))) {
    int top = POP(&ctx->ops);
    if (top == '(') 
      return op == EOF ? !(ctx->rc = CALC_NO_RP) : 1; // 1 -- `(` and ')'

    if (!expr(ctx, top))
      return 0;
  }
  if (op == ')') 
    return !(ctx->rc = CALC_NO_LP);

  if (op != EOF)
    PUSH(&ctx->ops, op);

  return 1;
}

Что же нужно сделать с таким кодом, если мы захотим всяких синусов, логарифмов и т.п.?

Понятно, что функция это операция, похожая на унарный минус (который наш лексер выдает как 'M'), которая в отличии от него применяется к нескольким операндам и заменяет их все своим результатом. Пусть это будет операция 'F'. А вот синтаксически имя функции похоже на число (цепочка символов), поэтому распознавать его придется не как символы остальных операций. Аргументы функция заключены в скобки и разделены запятыми. Появляется еще одна операция -- ','. Она напоминает закрывающую скобку с тем отличием, что дойдя до открывающей скобки в процессе вычисления операций из стека в eval() она не "аннигилирует" вместе с '(', а исчезает сама, оставив результат на вершине стека операндов.

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

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

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

Получаем вот такой интерфейс:

// калькулятор, вычисляет арифметическое выражение в str
  int calc (const char *str, ****** *pres, struct calc *ctx);
  // возвращает текст по коду возврата calc()
  const char *calc_strerr (int code);

Для доступа к переменным и функциям калькулятора реализуем:

// создает переменную или меняет значение существующей
  ****** *calc_set_var (Symtab **p, const char *name, int len, ****** v);
  // доступ к значению существующей переменной
  ****** *calc_get_var (Symtab **p, const char *name, int len);
  // добавляет функцию или меняет указатель на нее
  function *calc_set_func (Symtab **p, const char *name, function f);
  // доступ к указателю на функцию
  function *calc_get_func (Symtab **p, const char *name, int len);
  // удаляет из таблицы переменную или функцию
  int calc_delsymb (Symtab **p, const char *name);
  // для отладки (или любопытным) печатает таблицу переменных/функций
  // pri_content = 0 -- только статистика, 1 -- печать имен, 2 -- и значений
  int calc_pristat (Symtab *t, int pri_content);
  // удаляет всю таблицу переменных/функций
  void calc_destroy_symtab (Symtab **p);

Теперь можно вернуться к коду. Структуры данных:

#ifdef __cplusplus
typedef ****** (*function)(...);
#else
typedef ****** (*function)();
#endif

// лексема, заполняется calc_getlex()
struct calc_lexem {
  ****** v; // прочитанное число для type == 'N'
  int type, /* тип лексемы (операция): + - * / ( ) 
               M унарный минус
               P унарный плюс
               N число
               S имя переменной, присваивание
               V имя переменной, число
               F имя переменной, вызов функции
               , разделитель аргументов функции
            */
    pos, // индекс начала лексемы в строке
    len; // количество символов в лексеме (имени переменной, числе)
};

// указатели на таблицы переменных и функций пользователя
typedef struct u_item *Symtab;

// inout структура для вычисляемого выражения
struct calc {
  ****** result; // результат 
  struct calc_lexem curlex; /* последняя прочитанная лексема
                               может использоваться для печати ошибки */
  Symtab *varlist, /* переменные, которые могут использоваться в выражении
                      новые переменные, определяемые оператором присваивания
                      данного выражения, создаются в этой таблице */
    *funlist;      /* функции, определяемые пользователем
                      sin, asin, cos, acos, tan, atan, fabs, round, cell,
                      floor, trunc, sqrt, cbrt, pow, exp, log, log2 и
                      log10 уже определены в калькуляторе */
  int  rc;         // код возврата (OK == 0 иначе, код ошибки)
};

// список предопределенных функций
struct dfunc { 
  function f;
  const char *name;
};


struct fact { // функция ("параметры" операции F) в стеке оперций
  function f;
  int fsp;    // индекс в стеке операндов (начало аргументов вызова функции)
};

// контекст вычисляемого выражения
struct ucalc {
  const char *str; // "исходник" выражения
  int  rc,         // return code (OK == 0 иначе код ошибки)
    pos,           // позиция в str для поиска следующей лексемы
    prevop,        // тип предыдущей лексемы (.curlex.type)
    histop;        /* "история" видов лексем (operation == 1 / number == 0) 
                      при каждом вызове calc_getlex() сдвигается влево, 
                      младший бит устанавливается в вид текущей лексемы */
  struct calc_lexem curlex;
  ****** result;   /* конечный или любой промежуточный результат 
                      в т.ч. прочитанное calc_getlex() число */
#define STACK(T) struct { T *mem; int size, sp; }
  STACK(******)      nums;  // стек опрерандов (чисел)
  STACK(char)        ops;   // стек операций
  STACK(struct fact) funcs; // "расширение" стека операций для функций
#undef STACK
};

// элемент в hashtable (ключ .name[.len])
struct u_item {
  struct u_item *next;
  union {
    function f;
    ****** v;
  };
  int len;      // реальное количество байт в name[]
  char name[1]; // ключ элемента hashtable
};

Изменения и дополнения кода (непосредственно относящиеся к нашему вопросу).

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

int
calc_getlex (struct ucalc *ctx)
{
  int i = ctx->pos, // с этой точки начинаем поиск лексемы
    op; // а это будет ее код
  // организуем историю видов (операнд/операция) лексем
  ctx->histop <<= 1; 
  ctx->prevop = ctx->curlex.type;

  char *p;
  static char *ops = (char *)"+-*/(),";
  // по текущему символу (`op`) определим тип лексемы
  if ((p = (char *)strchr("+-*/(),", op = ctx->str[i]))) {
    if (PREVOP(ctx->histop))     // это операция, уточним какая именно
      op = "PM*/(),"[p - ops];
    // а вот `)`  должна выглядеть как операнд для проверки на ошибки
    ctx->histop |= (!(op == ')')); // занесем в историю вид лексемы
  } else if (isdigit(op) || op == '.') { // число?
    ctx->result = ctx->curlex.v = strtod(ctx->str + i, &p);
    if (p != ctx->str + i) {
      op = 'N';
      ctx->pos = p - ctx->str; // обновим начальную позицию
      ctx->curlex.len = ctx->pos - ctx->curlex.pos; // и длину лексемы
    }
  } else if (isalpha(op) || op == '_') { // идентификатор?
    int l, c, j;
    // пропустим допустимые для имени символы
    for (l = ctx->pos; (c = ctx->str[l]) && (isalnum(c) || c == '_'); l++);
    ctx->curlex.len = l - ctx->curlex.pos; // и обновим длину лексемы 
    op = 'V';
    if ((c = PEEKCHR(ctx->str + l, &j)) == '=')
      op = 'S'; // это оказывается присваивание переменной
    else if (c == '(')
      op = 'F'; // а если так, то обнаружили вызов функции

    ctx->histop |= (op != 'V'); // переменная это операнд, а остальное операция
    ctx->pos = l + ((op == 'V') ? 0 : j + 1); // новая начальная позиция
  } else
    op = '?';

  ctx->curlex.type = op;
  return op;
}

Поскольку теперь в стеках хранятся не только элементарные ****** и char, но и структуры в стеке фунцкций, придется модифицировать макросы TOP/POP так, чтобы они возвращали указатель на данные.

В код expr() (выполнение элементарных операций) вставим вызов функции. Это явно системозависимя часть и тестировалась только на x86 (32 и 64 bit). Реализация основывается на том, что у нас все функции получают аргументы типа ****** и функция возвращает результат ******. Если бы это было не так (если бы мы решили реализовать в калькуляторе еще и целые (и строки?)), то для 32-bit x86 понадобилось бы на ассемблере формировать стек вызова перед call, а на 64-bit заполнять аргументы разных типов (откровенно говоря, для linux/gcc только long и ******) данными из нашего стека операндов.

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

static int
expr (struct ucalc *ctx, int op)
{
  int n = op == 'M' ? 1 : 2; // число операндов для данной операции

  if (op != 'F' && ctx->nums.sp < n) // это не справедливо для вызова функции 
    return !(ctx->rc = CALC_NO_NUMS);

  switch (op) {
  case '+':
    ctx->result = ctx->nums.mem[ctx->nums.sp - 1] + 
 ..... case '-': ... case '/': ...
  case 'M':
    ctx->result = -(ctx->nums.mem[ctx->nums.sp - 1]);
    break;
  case 'F':
    { // вызов функции
      // возможные аргументы, обнулим для -Wall
      struct { ****** d0, d1, d2, d3, d4, d5, d6, d7, d8, d9; } a = {0};
      int isp = ctx->funcs.sp - 1, // индекс функции в стеке функций
        nsp = ctx->nums.sp;

      // перевычислим `n` -- число аргументов функции
      if ((n = nsp - ctx->funcs.mem[isp].fsp) == 0 && !ctx->nums.mem) {
        // и инициализируем стек операндов для вызова функции без аргументов
        PUSH(&ctx->nums, 0);
        POP(&ctx->nums);
      }
      if (n > 10)
        return !(ctx->rc = CALC_ARGS_ERR);
      switch (n - 1) { // скопируем аргументы из стека операндов
      case 9:   a.d9 = ctx->nums.mem[--nsp];
      case 8:   a.d8 = ctx->nums.mem[--nsp];
      case 7:   a.d7 = ctx->nums.mem[--nsp];
      case 6:   a.d6 = ctx->nums.mem[--nsp];
      case 5:   a.d5 = ctx->nums.mem[--nsp];
      case 4:   a.d4 = ctx->nums.mem[--nsp];
      case 3:   a.d3 = ctx->nums.mem[--nsp];
      case 2:   a.d2 = ctx->nums.mem[--nsp];
      case 1:   a.d1 = ctx->nums.mem[--nsp];
      case 0:   a.d0 = ctx->nums.mem[--nsp];
      }
      // выполним функцию
      ctx->result = ctx->funcs.mem[isp].f(a.d0, a.d1, a.d2, a.d3, 
                                          a.d4, a.d5, a.d6, a.d7, a.d8, a.d9);
      // уберем функцию из стека функций
      POP(&ctx->funcs); 
    }
    break;
    // internal error, unknown op
  default:
    return !(ctx->rc = CALC_ERR_OP);
  }

  // поместим результат в новую вершину стека операндов
  ctx->nums.mem[ctx->nums.sp - n] = ctx->result;
  ctx->nums.sp -= (n - 1); // и скорректируем индекс вершины

  return 1;
}

Приоритеты операций стали такими

static int
prty (int op)
{
  static char 
    oprs[] = "+-M*/(),F",
    prio[] = "335441121";

  return op == EOF ? 0 : prio[strchr(oprs, op) - oprs] - '0';
}

А вот в eval() добавилось довольно много кода

/*
  Выбираем и выполняем все операции из стека с приоритетом меньшим или
  равным приоритету новой операции (ctx->curlex.type), затем помещаем ее в стек.
  Закрывающая скобка, операция "запятая" (`,`) и EOF в стек не помещаются,
  `)` и `,` вычисляют и удаляют из стека все операции до `(` или `F` на
  вершине, `)` "аннигилирует" вместе с '(` или `F`, 
  EOF же, выполняя операции и обнаружив '(` или `F`, возвращает ошибку.

  Returns 0 -- error or 1 -- OK, last calculation result in ctx->result
 */
static int
eval (struct ucalc *ctx)
{
  int op = ctx->curlex.type, p1 = prty(op);

  while (!EMPTY(&ctx->ops) && (p1  <= prty(*TOP(&ctx->ops)))) {
    int top = *POP(&ctx->ops);
    if (top == 'F' || top == '(') {
      switch (op) {
      case EOF:
        return !(ctx->rc = (top == '(' ? CALC_NO_RP : CALC_NO_FRP)); // 0 - err
      case ')':
        return top == '(' ? 1 : expr(ctx, top);
      default:
        return !(ctx->rc = CALC_ERR_PRTY);
      }
    }

    if (!expr(ctx, top))
      return 0;
  }

  if (op == ')') 
    return !(ctx->rc = CALC_NO_LP);
  if (op == ',')
    return CMPTOP(&ctx->ops, 'F') ? 1 : !(ctx->rc = CALC_COMMA_ERR);
  // поместим новую операцию в стек
  if (op != EOF && !PUSH(&ctx->ops, op))
    return !(ctx->rc = CALC_OUT_OF_MEM);

  return 1;
}

С учетом анализа возможных ошибок в записи выражения код основной функции приобрел вот такой вид

/**
 * calc --  Калькулятор арифметических выражений с переменными и функциями.
 * @str:    IN    -- строка с выражением
 * @pres:   OUT   -- указатель для результата вычисления
 * @user:   INOUT -- указатель структуры (контекста выражения) с полями
 *   .varlist IN  -- таблица переменных
 *   .funlist IN  -- таблица функций
 *   .reuslt  OUT -- результат вычисления
 *   .rc      OUT -- код ошибки
 *   .curlex  OUT -- последняя прочитанная лексема выражения
 *                   (можно использовать при печати сообщения об ошибке)
 * Returns: 0 -- успешное вычисление, иначе код ошибки @.rc или EOF (@str == 0)
 */
int
calc (const char *str, ****** *pres, struct calc *user)
{
  if (!str)
    return EOF;
  ini_func(); // инициализация таблицы предопределенных функций
  if (*str == '?') { // печать в stdout таблиц переменных и функций
    fputs("variable ", stdout);
    if (!calc_pristat(user ? user->varlist : 0, 2))
      puts("");
    fputs("user functions ", stdout);
    if (!calc_pristat(user ? user->funlist : 0, 1))
      puts("");

    return fputs("calc functions ", stdout), calc_pristat(calc_fun, 1), 0;
  }

  struct ucalc ctx = {0}; // контекст вычисления выражения
  ctx.str = str;
  ctx.result = NAN;
  if (pres)
    *pres = NAN;
  if (user)
    user->result = NAN;
  ctx.histop = 1; // моделируем, что предыдущая лексема была операцией

  int loop = 0,   // номер цикла, присваивание допустимо только для loop == 1
    op; // тип лексемы
  struct calc_lexem setlex = {0}; // лексема переменной оператора присваивания

  /*
    Основной цикл вычисления.
    Вычисляем до первой ошибки (ctx.rc != 0) или до конца выражения (op == EOF).
    Алгоритм: 
      Берем очередную лексему.

      Операции `(`, M (унарный минус) и F (вызов функции) сразу помещаем
      в стек операций, для остальных операций вызываем eval(), 
      которая выполняет операции с меньшим или равным приоритету текущей 
      операции из стека над операндами из стека операндов, а затем помещает 
      текущую операцию в стек.

      Операнды (числа и значения переменных) заносим в стек операндов.
   */
  while (ctx.rc == 0 && (op = calc_getlex(&ctx)) != EOF) {
    loop++;
    switch (op) {
      // игнорируем унарный плюс
    case 'P': 
      break; 
      // обрабатываем присваивание
    case 'S':
      if (loop == 1) // допустимо только в начале выражения
        setlex = ctx.curlex;
      else
        ctx.rc = CALC_ASSG_ERR;
      break;
      // эти операции сразу в стек 
    case '(':
    case 'F':
      if (!PREVOP(ctx.histop)) {
        ctx.rc = CALC_NO_OP;
        break;
      }
      if (op == 'F') {
        function *pf = calc_get_function(user ? user->funlist : 0, 
                                         str + ctx.curlex.pos, ctx.curlex.len);
        if (!pf) {
          ctx.rc = CALC_NO_FUNC;
          break;
        }
        // запомним атрибуты вызова функции (ее адрес и SP стека операндов)
        struct fact fs = {*pf, ctx.nums.sp};
        if(!PUSH(&ctx.funcs, fs))
          ctx.rc = CALC_OUT_OF_MEM;     
      }
    case 'M':
      if(!PUSH(&ctx.ops, op))
        ctx.rc = CALC_OUT_OF_MEM;
      break;
      // выполним операцию, eval() положит ее в стек
    case ')':
    case ',':
    case '*':
    case '/':
      if (PREVOP(ctx.histop) && !(op == ')' && ctx.prevop == 'F')) {
        ctx.rc = CALC_NO_VAL; 
        break;
      }
    case '+':
    case '-':
      eval(&ctx);
      break;
      // запомним операнд в стеке операндов
    case 'V':
      { // для переменной найдем ее значение
        ****** *p = calc_get_var(user ? &user->varlist : 0, 
                                 str + ctx.curlex.pos, ctx.curlex.len);
        if (!p) {
          ctx.rc = CALC_NO_VAR;
          break;
        }
        ctx.result = *p;
      }
    case 'N':
      if (!PREVOP(ctx.histop))
        ctx.rc = CALC_NO_OP;
      else if (!PUSH(&ctx.nums, ctx.result))
          ctx.rc = CALC_OUT_OF_MEM;
      break;
      // прочли какой-то неизвестный символ
    default: 
      ctx.rc = CALC_ERR_INPUT;
    }
  }

  if (!ctx.rc)  
    eval(&ctx); // OK, вычислим все из стека

  // финальные проверки вроде бы безошибочного вычисления
  if (!ctx.rc) {
    if (ctx.nums.sp == 0 && ctx.ops.sp == 0)
      ctx.rc = CALC_NO_INPUT; // на самом деле просто ничего не было
    else if (ctx.nums.sp > 1)
      ctx.rc = CALC_NUMS_ERR;
    else if (ctx.ops.sp)
      ctx.rc = CALC_OPRS_ERR;
    else if (setlex.len && user && // и наконец, присваивание переменной
             !calc_set_var(&user->varlist, str + setlex.pos, setlex.len,
                        ctx.result))
      ctx.rc = CALC_OUT_OF_MEM;
  }
  free(ctx.nums.mem);
  free(ctx.ops.mem);
  free(ctx.funcs.mem);

  if (pres)
    *pres = ctx.result;
  if (user) {
    user->curlex = ctx.curlex;
    user->result = ctx.result;
  }

  return ctx.rc;
}

Полностью исходник находится здесь

Можете оттранслировать его

g++ fcalc.c -DCALC_TEST

запустить и что-нибудь вычислить

avp@avp-xub11:hashcode$ ./a.out
test calc1(), enter expressions, stop by ^D
> x=rad(rand() * 90)
1.319763779924807
> a=(sin(x))
0.9686564490678459
> b=cos(x)
0.2484042746799493
> 1 - (a*a + b*b)
0
>


strbb

Если интересны практические инструменты/решения на эту тему, то вот конкретный пример и теория для разработки парсера на ANTLR

На мой взгляд, это самый гибкий на сегодняшний день инструмент. Поддержка большинства ЯП, можно легко расширять функционал.

Последняя на данный момент - это 4-я версия. Для 3-й версии есть поддержка C, C++, C#, Delphi, Java, JS, Objective C, Perl, Python, Ruby, Scala, ActionScript, SML. Причем, поддержку любого языка можно ввести самому, т.к. ANTLR базируется на шаблонизаторе ST (для 3-й версии - это ST4), тут можно добавлять свои stg-шаблоны. А сам ANTLR, можно сказать, написан на ANTLR'е, у него есть свои грамматики, которые так же можно расширять при необходимости.

Как они пишут сами:

The latest version of ANTLR is 4.5.1, released July 15, 2015. As of 4.5.1, we have a Java, C#, JavaScript, Python2, Python3 targets (and alternate C# target). C++ is next on deck [no completion estimate].

и тут же дают инструкцию: "How to build ANTLR itself."

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


strbb

Парсер можно написать при помощи библиотеки Boost.Spirit. Это генератор парсеров, который использует EDSL (перегруженные операторы С++) для описания грамматики языка.

Для начала надо писать структуры синтаксического дерева (AST). Boost.Spirit активно использует Boost.Fusion и Boost.Variant. По этому для "базового типа" выражений надо (*) использовать boost::variant, а каждая структура должна быть адаптирована для использования в Boost.Fusion.

#include <boost fusion="" adapted.hpp="">
#include <boost variant.hpp="">

using Expression = boost::variant<
      ******
    , boost::recursive_wrapper<struct unaryexpression="">
    , boost::recursive_wrapper<struct binaryexpression="">
    , boost::recursive_wrapper<struct functioncall="">
    >;

struct UnaryExpression {
    enum op_t { Plus, Minus, };

    op_t op;
    Expression arg;
};

BOOST_FUSION_ADAPT_STRUCT(UnaryExpression, op, arg)

struct BinaryExpression {
    enum op_t { Plus, Minus, Mul, Div, Mod, Pow, };

    Expression first;
    std::vector<std::pair<op_t, expression="">> ops;
};

BOOST_FUSION_ADAPT_STRUCT(BinaryExpression, first, ops)

struct FunctionCall {
    std::string function;
    std::vector<expression> args;
};

BOOST_FUSION_ADAPT_STRUCT(FunctionCall, function, args)
</expression></std::pair<op_t,></struct></struct></struct></boost></boost>

*) Можно использовать обычное наследование, например сделать Expression обычным классом, и наследовать от него BinaryExpression и т.п., но тогда надо будет руками создавать и заполнять объекты AST в каждом правиле грамматики. Это заметно увеличит объем кода, по этому в этом примере используются Variant и Fusion.

Следующий шаг - это описание правил грамматики. Boost.Spirit использует синтаксис, близкий к ****, однако т.к. синтаксис реализован через перегрузку операторов С++, то вместо пробелов используется >> и символы * и + находятся перед выражением, а не после него.

#include <boost spirit="" home="" x3.hpp="">

namespace x3 = boost::spirit::x3;

// Список правил грамматики.
x3::rule<class identifier,="" std::string="">      const identifier;
x3::rule<class simple_expr,="" expression="">       const simple_expr;
x3::rule<class unary_expr,="" unaryexpression="">  const unary_expr;
x3::rule<class function_call,="" functioncall="">     const function_call;
x3::rule<class binary_expr_1,="" binaryexpression=""> const binary_expr_1;
x3::rule<class binary_expr_2,="" binaryexpression=""> const binary_expr_2;
x3::rule<class binary_expr_3,="" binaryexpression=""> const binary_expr_3;
x3::rule<class expr,="" expression="">       const expr;
//       ^                    ^                       ^
//       |                    |                       имя правила
//       |                    тип AST, который возвращает это правило
//       уникальный тип для каждого правила (нужно только объявление)

// Унарные операции
struct unary_op_t : x3::symbols<unaryexpression::op_t> {
    unary_op_t() {
        add("+",   UnaryExpression::Plus);
        add("-",   UnaryExpression::Minus);
    }
} const unary_op;

// Бинарные операции, для различных приоритетов
struct binary_op : x3::symbols<binaryexpression::op_t> {
    explicit binary_op(int precedence) {
        switch (precedence) {
        case 1:
            add("+", BinaryExpression::Plus);
            add("-", BinaryExpression::Minus);
            return;
        case 2:
            add("*",   BinaryExpression::Mul);
            add("/",   BinaryExpression::Div);
            add("mod", BinaryExpression::Mod);
            return;
        case 3:
            add("**", BinaryExpression::Pow);
            return;
        }
        throw std::runtime_error("Unknown precedence " + std::to_string(precedence));
    }
};

// Идентификаторы
auto const identifier_def = x3::raw[+(x3::alpha | '_')];

// Простые (не бинарные) выражения
auto const simple_expr_def
    = x3::******_
    | '(' >> expr >> ')'
    | unary_expr
    | function_call
    ;

// Унарные выражения
auto const unary_expr_def = unary_op >> simple_expr;

// Вызовы функций
auto const function_call_def = identifier >> '(' >> (expr % ',') >> ')';

// Бинарные выражения.
// Каждый приоритет должен иметь свое отдельное правило.
auto const binary_expr_1_def = binary_expr_2 >> *(binary_op(1) >> binary_expr_2);
auto const binary_expr_2_def = binary_expr_3 >> *(binary_op(2) >> binary_expr_3);
auto const binary_expr_3_def = simple_expr >> *(binary_op(3) >> simple_expr);

// Корневое правило для любых выражений.
auto const expr_def = binary_expr_1;

// В Boost.Spirit все описания правил должны иметь суффикс "_def".
// BOOST_SPIRIT_DEFINE связывает имена правил и их описания.
BOOST_SPIRIT_DEFINE(
    identifier,
    simple_expr,
    unary_expr,
    function_call,
    binary_expr_1, binary_expr_2, binary_expr_3,
    expr)
</binaryexpression::op_t></unaryexpression::op_t></class></class></class></class></class></class></class></class></boost>

Парсинг запускается функцией phrase_parse, которая принимает пару итераторов от входной последовательности, парсер, парсер для пропуска пробельных символов (и например комментариев), и ссылку на результат парсинга.

Expression parse(const char* input) {
    auto end = input + std::strlen(input);
    Expression result;
    bool ok = phrase_parse(input, end, expr, x3::space, result);
    if (ok && input == end) return result;
    throw std::runtime_error(std::string("Failed at: `") + input + "`");
}

Если phrase_parse вернула true, и итератор input передвинулся на конец входной строки, то парсинг прошел успешно.

Последнее что осталось - это вычислить выражение. Boost.Variant использует паттерн "Посетитель", по этому нам понадобится библиотека Boost.Functional чтобы собрать посетителя для каждого типа выражения:

#include <boost functional="" overloaded_function.hpp="">

****** eval_binary(BinaryExpression::op_t op, ****** a, ****** b) { 
    switch (op) {
    case BinaryExpression::Plus: return a + b;
    case BinaryExpression::Minus: return a - b;
    case BinaryExpression::Mul: return a * b;
    case BinaryExpression::Div: return a / b;
    case BinaryExpression::Mod: return (int)a % (int)b;
    case BinaryExpression::Pow: return pow(a, b);
    default: throw std::runtime_error("Unknown operator");
    }
}

****** eval(Expression e) {
    auto visitor = boost::make_overloaded_function(
        [](****** x) { return x; },
        [](const UnaryExpression& e) -> ****** {
            auto a = eval(e.arg);
            switch (e.op) {
            case UnaryExpression::Plus: return +a;
            case UnaryExpression::Minus: return -a;
            }
            throw std::runtime_error("Unknown operator");
        },
        [](const FunctionCall& e) -> ****** {
            auto arg = [&e](int i) { return eval(e.args.at(i)); };
            if (e.function == "abs") return abs(arg(0));
            if (e.function == "sin") return sin(arg(0));
            if (e.function == "cos") return cos(arg(0));
            if (e.function == "pow") return pow(arg(0), arg(1));
            throw std::runtime_error("Unknown function");
        },
        [](const BinaryExpression& e) -> ****** {   
            auto a = eval(e.first);
            for (auto&& o : e.ops) {
                auto b = eval(o.second);
                a = eval_binary(o.first, a, b);
            }
            return a;
        });
    return boost::apply_visitor(visitor, e);
}
</boost>

Весь код полностью можно посмотреть >>>здесь<<<.


strbb

Добавлю свои пять копеек

На хабре есть отличный цикл статей про написание игргушечного языка программирования (и настоящего компилятора к нему), освещена как теория (БНФ, грамматики, сравнение LR/LL), так и практика (распределение регистров, некоторые простые оптимизации), используется Flex/Bison. Требуется только знания С++, необходимая теория излагается по ходу дела.


strbb

Что-то в ответах наверчено... 8-!

Парсинг -- практически давно решенная задача (хотя ученые-информатики так и колупают тему, в основном на предмет многопоточной оптимизации), получить AST элементарно типовыми утилитами flex/bison (или ANTLR для жабофилов). Для узлов AST могу порекомендовать использовать вот такой набор типов:

struct Sym {
    string tag;    // тэг типа, указывает тип значения
    string val;    // значение объекта в текстовом представлении
    Sym(string T,string V); Sym(string V); // конструкторы: полный и sym-
    vector<sym*> nest; void push(Sym*);    // упорядоченные вложенные данные
    map<string,sym*> lookup;               // именованные поля
    virtual string head(); string pad(int);// \ вывод дампа объекта в виде дерева
    virtual strign dump(int depth);        // /
    virtual Sym* eval();                   // вычисление объекта,
                                           // реализацию надо расписывать подробно
    virtual Sym* add(Sym*);
    virtual Sym* sub(Sym*);
    virtual Sym* mul(Sym*);
    virtual Sym* div(Sym*);
    virtual Sym* pow(Sym*);
    virtual Sym* str();
    ...
};

struct Integer:Sym { Integer(string); long long val; string head(); };
struct Number:Sym { Number(string); ****** val; string head(); };

map<string,sym*> glob; // глобальная таблица символов, со ссылками на встроенные функции

typedef Sym* (FN*)(Sym*)
struct Function:Sym { Function(string,FN); FN fn; Sym* eval(); }; // встроенные функции
</string,sym*></string,sym*></sym*>

Вычисление выражений с функциями в исходном вопросе не было, но при необходимости делается на виртуальных функциях, для символов бОльшая часть возвращает struct Error:Sym, для чисел переопределяется с помощью сишных числовых операторов, анализируется тэг операнда (или тип операнда определяется через RTTI), при необходимости проводится конвертация типов int/float/string, возвращается новый объект Sym* с результатом (и имеем некоторый гемор с управлением памятью -- надо аккуратно подчищать операнды из памяти, иначе получим утечку, или наоборот обращение к deleted object в следующем вычисляемом выражении, например к переменной). Встроенные функции типа Sym* sin(Sym*) заворачиваются в объект Function:Sym, eval() переопределяется вызовом этой функции по указателю FN fn. Если подробнее -- надо код показывать, с пояснениями.

Функции определяемые пользователем и управление памятью со сборкой мусора (то есть фактически реализация DLR: Dynamic Language Runtime) -- вот тут реальная заcада, на русском языке нет ничего! Во всяких таториалах по реализации языка на flex/bison или с ручным парсером на этапе определения функций таториал аккуратно заканчиватся, чтобы автор не потерял лицо Великого Специалиста 8-). В приложениях библиотеки LLVM чуть получше -- есть обрезанная реализация ущербных Си-подобных функций (декларация, определение и вызов), и таториал ограничивается созданием соответствующих LLVM::-объектов (и опционально вызовом JIT-компилятора). Если хотите вкусностей типа континюаций и yield -- например для реализации движка логического вывода а-ля Пролог -- йок!

Сейчас неспешно делаю подстрочный перевод PLAI -- там реализации функций посвящено больше половины книги.

Я сейчас сам только в эту тему вгрызаюсь (хочу сделать SmallTalk-подобную интерактивную среду с метатранслятором и экспертной системой для transformational programming и MDA), если интересует подробное описание реализации парсера и вычислителя выражений -- заглядывайте в плейлист и пищите, поделюсь чему научился. В ближайшее время сделаю скринкаст разбора ASCII формата САПР Neutral с помощью flex/bison. Потом -- как раз вычислитель мат.выражений, но без пользовательских функций (надо PLAI разгрызть сначала).


strbb

Только парсинг, без вычисления, на выходе синтаксическое дерево, используются стандартные утилиты:

исходный код (максимально упрощено, синтаксис расширяется по необходимости)

# comment

-02 + +03.400 * 5e-06

mult = {x,y: x*y} # определение пользовательской именованной функция через лямбда-функцию

sin(pi)*mult(
    cos(x),
    {x:x^2}@z # оператор применения [лябда-]функции
)

что на выходе - текстовый дамп дерева, включает {лямбды} и кор,тежи

+
    -2
    *
        3.4
        5e-006

=
    mult
    {}
        ,
            x
            y
        *
            x
            y

*
    @
        sin
        pi
    @
        mult
        ,
            @
                cos
                x
            @
                {}
                    x
                    ^
                        x
                        2
                z

лексер на регулярных выражениях, компилируемый С-код получается командой flex lexer.lpp:

%{
#include "hpp.hpp"
%}
%option noyywrap yylineno
                                   // необязательный префикс: знак числа
S [\+\-]?
                                   // десятичное число
N [0-9]+
%%
#[^\n]*             {}             // комментарий
[ \t\r\n]+          {}             // пробельные символы выбрасываем

{S}{N}[eE]{S}{N}    TOC(Num,NUM)   // запись числа в exponential форме 12e34
{S}{N}\.{N}         TOC(Num,NUM)   // число с точной
{S}{N}              TOC(Num,NUM)   // целое число

\(                  TOC(Op,LP)     // скобки
\)                  TOC(Op,RP)
\[                  TOC(Op,LQ)
\]                  TOC(Op,RQ)
\{                  TOC(Op,LC)
\}                  TOC(Op,RC)

\=                  TOC(Op,EQ)     // операторы
\@                  TOC(Op,AT)
\,                  TOC(Op,COMMA)
\:                  TOC(Op,COLON)

\+                  TOC(Op,ADD)
\*                  TOC(Op,MUL)
\^                  TOC(Op,POW)

[a-zA-Z0-9_]+       TOC(Sym,SYM)   // символ (имя переменной или функции)

.                   {yyerror("lexer");} // на нераспознанный символ авостим

парсер синтаксиса (очень упрощенно, все пара операторов и скаляры) bison syntax.ypp генерирует файлы syntax.tab.cpp и syntax.tab.hpp:

%{
#include "hpp.hpp"
%}
%defines %union { Sym*o; }
%token <o> SYM NUM              // symbol number
%token <o> LP RP LQ RQ LC RC    // (exp) [vector] {lambda}
%token <o> ADD MUL POW          // + * ^
%token <o> EQ AT                // = @
%token <o> COMMA COLON          // , :

%type <o> ex scalar vector lambda tuple    

                  // приоритет операторов
%right EQ
%left ADD
%left MUL
%left POW

%%
REPL : | REPL ex { cout << $2->dump() << endl; } ;
scalar : SYM | NUM ;
ex : scalar | tuple
    | LP ex RP      { $$=$2; }
    | LQ vector RQ  { $$=$2; }
    | LC lambda RC  { $$=$2; }
    | SYM LP ex RP  { $$=new Op("@"); $$->push($1); $$->push($3); }
    | ex AT ex      { $$=$2; $2->push($1); $2->push($3); }
    | ex EQ  ex     { $$=$2; $2->push($1); $2->push($3); }
    | ex ADD ex     { $$=$2; $2->push($1); $2->push($3); }
    | ex MUL ex     { $$=$2; $2->push($1); $2->push($3); }
    | ex POW ex     { $$=$2; $2->push($1); $2->push($3); }
;
vector :            { $$=new Vector(); }
    | vector ex     { $$=$1; $$->push($2); }
;
lambda :                    { $$=new Lambda(); }
    | lambda SYM COLON      { $$=$1; $$->push($2); }
    | lambda tuple COLON    { $$=$1; $$->push($2); }
    | lambda ex             { $$=$1; $$->push($2); }
;
tuple : ex COMMA ex         { $$=new Tuple($1,$3); }
    | tuple COMMA ex        { $$=$1; $$->push($3); }
;
</o></o></o></o></o></o>

общие для всех модулей (.cpp файлов) хедеры:

#ifndef _H_HPP
#define _H_HPP
                              // заголовочные файлы
#include <iostream>           // поточный вывод
#include <sstream>            // поточный вывод в строку ostringstream
#include <cstdlib>            // нужен для exit()
#include <vector>             // шаблон вектор для хранения вложенных данных
using namespace std;

struct Sym {                                 // \\ универсальный тип данных
    string val;                              // значение (текстовое)
    Sym(string);                             // конструктор токена
    vector<sym*> nest; void push(Sym*);      // может иметь вложенные данные
    virtual string head(); string pad(int);  // \ текстовый дамп в виде дерева
    virtual string dump(int=0);              // /
};                                           // //

struct Num:Sym { Num(string); string head(); // \ числа,
                 ****** val; };              // значения хранятся в даблах
                                             // / (для последующего вычисления выражений)

struct Op:Sym { Op(string); };               // оператор

struct Vector:Sym { Vector(); };             // [вектор]
struct Lambda:Sym { Lambda(); };             // {лямбда:функция}
struct Tuple:Sym { Tuple(Sym*,Sym*); };      // кор,теж

extern int yylex();                          // \ интерфейс лексера на регулярках
extern int yylineno;
extern char* yytext;
#define TOC(C,X) { yylval.o = new C(yytext); return X; }
extern int yyparse();                        // \ интерфейс синтаксического парсера
extern int yyerror(string);
#include "ypp.tab.hpp"                       // /

#endif // _H_HPP
</sym*></vector></cstdlib></sstream></iostream>

сишный код (конструкторы и генерация дампа):

#include "hpp.hpp"

// callback функция вызывается из парсера при синтаксической ошибке
#define YYERR "\n\n"<<yylineno<<":"<<msg<<"["<<yytext<<"]\n\n" int="" yyerror(string="" msg)="" {="" cout<<yyerr;="" cerr<<yyerr;="" exit(-1);="" }="" при="" запуске="" программы="" выполнить="" парсер="" main()="" return="" yyparse();="" sym::sym(string="" v)="" val="V;" конструктор="" void="" sym::push(sym*o)="" nest.push_back(o);="" добавление="" вложенного="" элемента="" string="" sym::head()="" val;="" sym::pad(int="" n)="" s;="" for="" (int="" i="0;i<n;i++)" s+="\t" ;="" sym::dump(int="" depth)="" дамп="" дерева="" s="\n" +pad(depth)+head();="" заголовок="" (val)="" (auto="" it="nest.begin(),e=nest.end();it!=e;it++)" вложенные="" элементы="" +="(*it)-">dump(depth+1);                     // добавить c отступом
    return S; }

Num::Num(string V):Sym(V){ val=atof(yytext); }        // числа с преобразованием
string Num::head() {
    ostringstream os; os<</yylineno<<":"<<msg<<"["<<yytext<<"]\n\n">

Весь салат заправляем Makefile-ом:

log.log: src.src ./exe.exe
    ./exe.exe < $< > $@ && tail $(TAIL) $@
C = cpp.cpp ypp.tab.cpp lex.yy.c
H = hpp.hpp ypp.tab.hpp
CXXFLAGS += -std=gnu++11
./exe.exe: $(C) $(H)
    $(CXX) $(CXXFLAGS) -o $@ $(C)
lex.yy.c: lpp.lpp
    flex $<
ypp.tab.cpp: ypp.ypp
    bison $<

licensed under cc by-sa 3.0 with attribution.