我正在尝试解析一种类似 lisp 的语言,它有一些常见函数的语法糖。例如,加函数可以写为 (+ 1 2) 或 1 + 2。我认为在尝试解释语言之前消除语法糖将显着促进解释过程,因为这样,唯一的评估规则需要实现的是函数调用,并且所有中缀运算符都必须具有相应的内置函数。我想我可以创建一个解析器,它将迭代从词法分析器接收到的标记,并对它们重新排序以将表达式放入前缀表示法中。但这需要解析器的输出也是一个标记列表。在 Spirit.Qi 中可能吗?据我了解,Spirit.Qi 构建了一个层次结构,而不是线性的代币列表。
最佳答案
当然,一切皆有可能。
也就是说,为什么不在 AST 上进行操作,
- 解释时不必担心输入表示
- 不用担心词法分析/解析时的解释
考虑 AST representation like this (受到一种简化的 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
为了好玩,我投入了
- 使用 karma ( display.hpp/display.cpp ) 的 AST 转储程序来演示如何
(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
存在
关于boost-spirit - 使用 Spirit.Qi 消除语法糖,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11319223/