如何获取正则表达式字符串的AST？
如何获得正则表达式的抽象语法树(AST)(在C++中)？
例如,
(XYZ)|(123)
应该产生一棵树:
|
/ \
. .
/ \ / \
. Z . 3
/ \ / \
X Y 1 2
是否有boost::spirit语法来解析正则表达式模式？该boost::regex库应该有它,但我没有找到它.是否还有其他开源工具可以为我提供正则表达式的抽象表示？
seh*_*ehe 27
我再次偶然发现了这个问题.我决定看一下使用Boost Spirit为正则表达式语法的重要子集编写解析器实际上有多难.
所以,像往常一样,我从笔和纸开始,过了一段时间就考虑了一些规则草案.是时候画出类似的AST了:
namespace ast
{
struct multiplicity
{
unsigned minoccurs;
boost::optional<unsigned> maxoccurs;
bool greedy;
multiplicity(unsigned minoccurs = 1, boost::optional<unsigned> maxoccurs = 1)
: minoccurs(minoccurs), maxoccurs(maxoccurs), greedy(true)
{ }
bool unbounded() const { return !maxoccurs; }
bool repeating() const { return !maxoccurs || *maxoccurs > 1; }
};
struct charset
{
bool negated;
using range = boost::tuple<char, char>; // from, till
using element = boost::variant<char, range>;
std::set<element> elements;
// TODO: single set for loose elements, simplify() method
};
struct start_of_match {};
struct end_of_match {};
struct any_char {};
struct group;
typedef boost::variant< // unquantified expression
start_of_match,
end_of_match,
any_char,
charset,
std::string, // literal
boost::recursive_wrapper<group> // sub expression
> simple;
struct atom // quantified simple expression
{
simple expr;
multiplicity mult;
};
using sequence = std::vector<atom>;
using alternative = std::vector<sequence>;
using regex = boost::variant<atom, sequence, alternative>;
struct group {
alternative root;
group() = default;
group(alternative root) : root(std::move(root)) { }
};
}
这是典型的AST(58 LOC)与灵效果很好(因为通过与升压整合variant和optional,以及具有战略性的选择构造函数).
语法结果只是稍微长一点:
template <typename It>
struct parser : qi::grammar<It, ast::alternative()>
{
parser() : parser::base_type(alternative)
{
using namespace qi;
using phx::construct;
using ast::multiplicity;
alternative = sequence % '|';
sequence = *atom;
simple =
(group)
| (charset)
| ('.' >> qi::attr(ast::any_char()))
| ('^' >> qi::attr(ast::start_of_match()))
| ('$' >> qi::attr(ast::end_of_match()))
// optimize literal tree nodes by grouping unquantified literal chars
| (as_string [ +(literal >> !char_("{?+*")) ])
| (as_string [ literal ]) // lone char/escape + explicit_quantifier
;
atom = (simple >> quantifier); // quantifier may be implicit
explicit_quantifier =
// bounded ranges:
lit('?') [ _val = construct<multiplicity>( 0, 1) ]
| ('{' >> uint_ >> '}' ) [ _val = construct<multiplicity>(_1, _1) ]
// repeating ranges can be marked non-greedy:
| (
lit('+') [ _val = construct<multiplicity>( 1, boost::none) ]
| lit('*') [ _val = construct<multiplicity>( 0, boost::none) ]
| ('{' >> uint_ >> ",}") [ _val = construct<multiplicity>(_1, boost::none) ]
| ('{' >> uint_ >> "," >> uint_ >> '}') [ _val = construct<multiplicity>(_1, _2) ]
| ("{," >> uint_ >> '}' ) [ _val = construct<multiplicity>( 0, _1) ]
) >> -lit('?') [ phx::bind(&multiplicity::greedy, _val) = false ]
;
quantifier = explicit_quantifier | attr(ast::multiplicity());
charset = '['
>> (lit('^') >> attr(true) | attr(false)) // negated
>> *(range | charset_el)
> ']'
;
range = charset_el >> '-' >> charset_el;
group = '(' >> alternative >> ')';
literal = unescape | ~char_("\\+*?.^$|{()") ;
unescape = ('\\' > char_);
// helper to optionally unescape waiting for raw ']'
charset_el = !lit(']') >> (unescape|char_);
}
private:
qi::rule<It, ast::alternative()> alternative;
qi::rule<It, ast::sequence()> sequence;
qi::rule<It, ast::atom()> atom;
qi::rule<It, ast::simple()> simple;
qi::rule<It, ast::multiplicity()> explicit_quantifier, quantifier;
qi::rule<It, ast::charset()> charset;
qi::rule<It, ast::charset::range()> range;
qi::rule<It, ast::group()> group;
qi::rule<It, char()> literal, unescape, charset_el;
};
现在,真正的乐趣是用AST做点什么.由于您想要可视化树,我想到了从AST生成DOT图.所以我做了:
int main()
{
std::cout << "digraph common {\n";
for (std::string pattern: {
"abc?",
"ab+c",
"(ab)+c",
"[^-a\\-f-z\"\\]aaaa-]?",
"abc|d",
"a?",
".*?(a|b){,9}?",
"(XYZ)|(123)",
})
{
std::cout << "// ================= " << pattern << " ========\n";
ast::regex tree;
if (doParse(pattern, tree))
{
check_roundtrip(tree, pattern);
regex_todigraph printer(std::cout, pattern);
boost::apply_visitor(printer, tree);
}
}
std::cout << "}\n";
}
该程序产生以下图表:
自我边缘描绘重复,颜色指示匹配是贪婪(红色)还是非贪婪(蓝色).正如您所看到的,为了清晰起见,我对AST进行了一些优化,但(联合国)对相关行进行评论会产生差异:
我认为调整起来并不难.希望它能成为某人的灵感.
这个要点的完整代码:https://gist.github.com/sehe/8678988
- 成为受虐狂的+1.我甚至没有使用正则表达式的直觉,更不用说为他们写一个解析器*了... (13认同)
我认为Boost Xpressive必须能够"几乎"开箱即用.
我会看看是否可以确认(使用小样本).
其他想法包括使用Boost Spirit和通用的utree工具来"存储"AST.你必须重现一个语法(这对于Regex语法的常见子集来说相对简单),所以它可能意味着更多的工作.
进展报告1
看看Xpressive,我取得了一些进展.我使用DDD的图形数据显示得到了漂亮的图片.但还不够.
然后我更多地探讨了"代码"方面:Xpressive是建立在Boost Proto之上的.它使用Proto 定义直接在C++代码中对正则表达式建模的DSEL.Proto 完全从C++代码生成表达式树(通用AST,如果你愿意)(通过重载所有可能的运算符).然后,库(Xpressive,在这种情况下)需要通过遍历树来定义语义,例如
- 构建特定于域的表达式树
- 用语义信息注释/装饰它
- 可能直接采取语义动作(例如Boost Spirit如何在Qi和Karma 1中进行语义动作)
正如你所看到的,天空真的是极限,而且看起来令人不安地类似于Boo,Nemerle,Lisp等编译器宏.
可视化表达Trres
现在,Boost Proto表达式树可以通常可视化:
使用Expressive C++中的示例:使用语法播放我稍微扩展了Xpressive的"Hello World"示例以显示表达式树:
#include <iostream>
#include <boost/xpressive/xpressive.hpp>
#include <boost/proto/proto.hpp>
using namespace boost::xpressive;
int main()
{
std::string hello( "hello world!" );
sregex rex = sregex::compile( "(\\w+) (\\w+)!" );
// equivalent proto based expression
rex = (s1= +_w) >> ' ' >> (s2= +_w) >> '!';
boost::proto::display_expr( (s1= +_w) >> ' ' >> (s2= +_w) >> '!');
smatch what;
if( regex_match( hello, what, rex ) )
{
std::cout << what[0] << '\n'; // whole match
std::cout << what[1] << '\n'; // first capture
std::cout << what[2] << '\n'; // second capture
}
return 0;
}
其输出接近(注意编译器ABI特定typeid名称):
shift_right(
shift_right(
shift_right(
assign(
terminal(N5boost9xpressive6detail16mark_placeholderE)
, unary_plus(
terminal(N5boost9xpressive6detail25posix_charset_placeholderE)
)
)
, terminal( )
)
, assign(
terminal(N5boost9xpressive6detail16mark_placeholderE)
, unary_plus(
terminal(N5boost9xpressive6detail25posix_charset_placeholderE)
)
)
)
, terminal(!)
)
hello world!
hello
world
免责声明您应该意识到这实际上并没有显示Regex AST,而是来自Proto 的通用表达式树,因此它没有特定于域的(Regex)信息.我提到它是因为差异可能会导致更多的工作(？除非我找到Xpressive编译结构的钩子),因为它对原始问题真正有用.
这就是现在
我会留下那张纸条,因为它是午餐时间,我正在接收孩子们,但这肯定引起了我的兴趣,所以我打算稍后发帖!
结论/进展报告1.0000001
坏消息:它不会起作用.
这就是原因.这个免责声明是对的钱.当周末到来时,我已经考虑了一些事情并且"预测"整个事情会在我离开的地方崩溃:AST基于原型表达树(不是正则表达式matchable_ex).
在一些代码检查后很快就确认了这个事实:在编译之后,原型表达式树不再可用于显示.更不用说当basic_regex首先被指定为动态模式时(从来没有一个proto表达式).
我一直一半希望匹配已经(使用原evalutation /评估环境)直接实现对原表达式树,但很快就证实了这是情况并非如此.
所以,主要的内容是:
- 这对显示任何正则表达式AST都不起作用
- 您可以使用上述内容实现最佳可视化原型表达式,您必须直接在代码中创建.这是一种在同一代码中手动编写AST的奇特方式......
稍微不那么严格的观察包括
- Boost Proto和Boost Expressive是非常有趣的图书馆(我不介意去那里钓鱼).我显然已经学到了一些关于模板元编程库的重要课程,特别是这些库.
- 很难设计一个构建静态类型表达式树的正则表达式解析器.事实上,在一般情况下它是不可能的 - 它需要编译器将所有可能的表达式树组合实例化到某个深度.这显然不会扩大规模.您可以通过引入多态组合和使用多态调用来解决这个问题,但这会消除模板元编程的好处(静态实例化类型/特化的编译时优化).
- Boost Regex和Boost Expressive都可能在内部支持某种正则表达式AST(以支持匹配评估)但
- 它没有被曝光/记录
- 没有明显的显示设施
1就连Spirit Spirit Lex支持它们(但默认情况下不支持)
boost::regex 似乎在 basic_regex_parser.hpp 中有一个手写的递归下降解析器。尽管感觉就像重新发明轮子一样，但您自己在 boost::spirit 中编写语法时可能会更快，尤其是在存在大量正则表达式格式的情况下。
| 归档时间： |
|
| 查看次数： |
3168 次 |
| 最近记录： |