2
valeriimВ свое время, захотевши написать простой компилятор мат.выражений, но не будучи знакомым с теорией синтаксического анлиза, грамматического разбора и т.д., я "изобрел" простой парсер, специально для нужд разбора простых формул. Как потом оказалось, дизайн парсера оказался не таким уж и плохим. Фактически, это обычный рекурсивно-нисходящий парсер, но свернутый в одну функцию.
Выглядит он примерно так:
Код:
tree expr(int p)
{
string op; tree left;
if(p>maxp) return term();
left=expr(p+1);
if(!check(p, op)) return left;
if(right(op))
left=infix(p, op, left);
else
do left=infix(p+1, op, left) while(check(p, op));
return left;
}
}
Здесь
p обозначает приоритет оператора (начиная с нуля);
maxp -- соответсвенно максимално возможный приоритет; функция
check принимает приоритет и ссылку на буфер, проверяет является ли текущая лексема оператором и если является, то совпадает ли его приоритет с данным, потом копирует оператор в указанный буфер и считывает следующую лексему (в случае удачи) и возвращает результат проверки; фукция
infix, как нетрудно догадаться, обрабатывает бинарный оператор указанного приоритета, т.е. конструирует соответствующий узел дерева; функция
term обрабатывает скобки и унарные (префиксные/постфиксные операторы); ну и наконец, функция
right просто проверяет оператор на правую ассоциативность.
Как может выглядеть код для
infix(p, op, left)? Он должен создать новый узел с меткой
op, левой подветкой которого станет переданная ветка, а правая ветка будет получена вызовом
expr(p). Возможный вид
infix'а:
Код:
tree infix(int p, char *op, tree left)
{
return mknode(op, left, expr(p));
}
Функция
term очень проста, но места занимает очень много. Начать её писать можно так:
Код:
tree term()
{
if(match("("))
{
t=expr(0);
expect(")");
return t;
}
switch(token.kind)
{
case tk_number: t=mknode(token.value); next_token(); return t;
...
Функция
match проверяет, совпадает ли текст текущей лексемы с данным и если совпадает, то считывает следующую лексему и возвращает истину. Функция
expect проводит почти такую-же проверку, но при несовпадении генерирует ошибку (и если парсер допускает восстановление после ошибок, то
expect может считывать новую лексему в любом случае). Что означает
next_token() надеюсь понятно (да, ещё и лексический анализатор придется написать, например в виде конечного автомата).
В общем, как-то так. Это проверенная работающая схема. Осталось только правильно распечатать построенное синтаксическое дерево; собственно в этом задание-то и заключалось. Наверное код будет примерно таким:
Код:
display(tree AST)
{
switch(AST->node_kind)
{
nk_op:
display(AST->left);
display(AST->right);
display(AST->left)
print(AST->op);
display(ASR->right);
break;
nk_funccall:
for(i=0; i<AST->argc; i++) display(AST->argv[i]);
print(AST->id);
print("(");
for(i=0; i<AST->argc; i++)
{
if(i) print(", ");
display(AST->argv[i]);
}
print(")");
...
Точно не знаю, как он должен выглядет, но, думаю, достаточно немного поэкспериментировать, чтобы это понять.
Подход с построением синтаксического дерева оправдан за счет необходимости дублировать выводимые на печать операнды при печати объемлющего их выражения. Т.е. в выражении
(a+b)*(c+d) сначала печатаем
(a+b), потом
(c+d), а потом все выражение, т.е. содержимое скобок печатается по нескольку раз. Навреное уж лучше один раз построить дерево, чем хранить все промежуточные куски строк (хотя ведь достаточно хранить позиции и длины подстрок, но генерация дерева хороша в образовательном смысле :) ).
P.S.: Я считаю, что для таких заданий прекрасно подходит техника синтаксического разбора с использованием комбинаторов парсеров, вроде хаскелевского parsec'а, boost::spirit для C++, или даже reparse для js. Это наиболее красивый способ дословного перевода нфбн-грамматики в программный код парсера. Обычно к таким библиотекам неизменно прилагается пример реализации калькулятора, вот его то и нужно переделать для генерации синтаксического дерева, которое потом нужно будет правильно распечатать, см. выше.
P.P.S.: Насчет запятой и правоассоциативности ничего не понял. Чем запятая отличается от других операторов? И при чем тут правоассоциативность(с каких пор запятая правоассоциативна)? И что особого в правой ассоциативности? Обычно, при прямом построении рекурсивно-нисходящего парсера, могут возникать проблемы, но не для право-, а для левоассоциативных операций (функция сразу же вызывает саму себя рекурсивно, что приводит к зацикливанию); правда это никакая не проблема и все исправляется простыми циклами...
12.09.2011, 14:52 
Как это можно сделать?
Но если, конечно, много операторов, тут целиком согласен, что нужна грамматика. А вообще, если автору и понадобятся операторы (даже в нужности ему запятой [ну, можно ведь её сделать точкой с запятой, чтобы не спуталась с разделителем параметров функции] я сомневаюсь), то можно их представить в виде функций 
