Я пытаюсь разобрать язык, похожий на шепелявость, в котором есть синтаксический сахар для общих функций. Например, функция plus может быть записана как (+ 1 2) или как 1 + 2. Я думаю, что устранение синтаксического сахара перед попыткой интерпретации языка значительно облегчило бы процесс интерпретации, потому что тогда единственное правило вычисления, которое должен быть реализован вызов функции, и все инфиксные операторы должны иметь соответствующие встроенные функции. Я подумал, что могу создать синтаксический анализатор, который будет перебирать токены, полученные от лексера, и переупорядочивать их, чтобы поместить выражение в префиксную нотацию. Но для этого потребуется, чтобы на выходе анализатора также был список токенов. Возможно ли это в Spirit.Qi? Насколько я понимаю, Spirit.Qi строит иерархическую структуру, а не линейный список токенов.
Устранение синтаксического сахара с помощью Spirit.Qi
Ответы (1)
Все, конечно, возможно.
Тем не менее, почему бы вам не оперировать AST, и
- не беспокойтесь о входном представлении при интерпретации
- не беспокойтесь об интерпретации во время лексирования/парсинга
Рассмотрим представление AST, подобное этому (вдохновленное своего рода упрощенным s-выражением):
typedef boost::make_recursive_variant<
std::string,
std::vector< boost::recursive_variant_ >
>::type expr_t;
Вы сможете определить правила для принятия s_expr
или binobj
и разбирать в один и тот же AST.
qi::rule<It, std::vector<expr_t>(), Skipper> binop;
qi::rule<It, expr_t(), Skipper> expr, s_expr, name;
expr = binop | s_expr;
binop = (s_expr >> (string("+") | string("-") | string("*") | string("/")) >> expr)
[
phx::push_back(_val, _2),
phx::push_back(_val, _1),
phx::push_back(_val, _3)
];
name = as_string [ lexeme [ +(graph - char_("()") ) ] ];
s_expr = ('(' > +expr > ')') | name;
Полная демонстрация
У меня есть полная демонстрация этой идеи здесь: https://gist.github.com/3047788
Ради интереса я вставил
- дампер AST, использующий карму (display.hpp/display.cpp), чтобы продемонстрировать, как
(1 + 3)
анализируется в том же синтаксическом дереве, что и(+ 1 3)
. - базовый механизм оценки (eval.hpp/eval.cpp) 1
Основная демонстрация test.cpp:
int main()
{
for (const auto input : std::list<std::string> {
"",
"(+ 1 3)",
"(1 + 3)",
"(1 + 4 / 2)",
"(1 + (* 4 5 6) / 2)",
"(avg 1 + (* 4 5 6) / 2)",
"(trace 1 + (* 4 5 6) / 2 1 1 1 1 999)",
"(avg 1 + (* 4 5 6) / 2 1 1 1 1 999)",
"(avg 1 + (* 4 (unknown-function 5) 6) / 2 a b c)",
})
{
std::cout << "----------------------\n";
expr_t ast = doParse(input, qi::space);
try
{
std::cout << "eval<double>: " << eval<double>(ast) << std::endl;
std::cout << "eval<int> : " << eval<int> (ast) << std::endl;
} catch(std::exception const& e)
{
std::cerr << e.what() << '\n';
}
}
}
Результаты в следующем выводе:
----------------------
parse failed: ''
warning: undefined '<no ast>'
eval<double>: 0
warning: undefined '<no ast>'
eval<int> : 0
----------------------
parse success
input : (+ 1 3)
ast parsed : (+ 1 3)
eval<double>: 4
eval<int> : 4
----------------------
parse success
input : (1 + 3)
ast parsed : ((+ 1 3))
eval<double>: 4
eval<int> : 4
----------------------
parse success
input : (1 + 4 / 2)
ast parsed : ((+ 1 (/ 4 2)))
eval<double>: 3
eval<int> : 3
----------------------
parse success
input : (1 + (* 4 5 6) / 2)
ast parsed : ((+ 1 (/ (* 4 5 6) 2)))
eval<double>: 61
eval<int> : 61
----------------------
parse success
input : (avg 1 + (* 4 5 6) / 2)
ast parsed : (avg (+ 1 (/ (* 4 5 6) 2)))
eval<double>: 0
eval<int> : 0
----------------------
parse success
input : (trace 1 + (* 4 5 6) / 2 1 1 1 1 999)
ast parsed : (trace (+ 1 (/ (* 4 5 6) 2)) 1 1 1 1 999)
trace( 61 1 1 1 1 999 )
eval<double>: 0
trace( 61 1 1 1 1 999 )
eval<int> : 0
----------------------
parse success
input : (avg 1 + (* 4 5 6) / 2 1 1 1 1 999)
ast parsed : (avg (+ 1 (/ (* 4 5 6) 2)) 1 1 1 1 999)
eval<double>: 167.167
eval<int> : 167
----------------------
parse success
input : (avg 1 + (* 4 (unknown-function 5) 6) / 2 a b c)
ast parsed : (avg (+ 1 (/ (* 4 (unknown-function 5) 6) 2)) a b c)
error: can't apply 'unknown-function' to 1 args (std::exception)
1 имейте в виду, что здесь нет системы типов, поэтому вы должны указать жестко запрограммированный тип данных для интерпретации всех значений как (например, double result = eval<double>(ast)
). Также нет таблицы символов, поэтому существуют только встроенные функции +-/*
trace
и avg
person
sehe
schedule
04.07.2012