抽象语法树的迭代更新与提升精神 [英] Iterative update of abstract syntax tree with boost spirit
问题描述
我有一个工作提升精神解析器和在想是否有可能做一个抽象语法树的迭代更新与提升精神？
我有一个结构类似：
结构AST; TYPEDEF提振::变体LT;提高:: recursive_wrapper＆LT; AST＆GT; ＆GT;节点; 结构AST
{
的std ::矢量＆lt;＆INT GT;值;
的std ::矢量＆lt;节点＆GT;儿童;
};
这是由使用的解析：
BOOL R = phrase_parse（开始，结束，语法，空间，AST）;
有可能做的抽象语法树的迭代更新与提升精神？我还没有发现任何这文件，但我想，如果解析器语义动作可以在一个已经存在的AST的push_back。有没有人试过这种？
这将允许解析如下：
BOOL R = phrase_parse（开始，结束，语法，空间，AST）; //初步分析//第二解析将给予一定的事件/定时器/ IO /东西后状态调用BOOL R = phrase_parse（开始，结束，语法，空间，AST）; //额外的解析，这将更新现有的AST
您如何知道哪些节点要合并？或者，你总是在根级别增加（移植）？在这种情况下，你为什么不只是另一种分析和合并的元素移动到现有的AST？
AST＆安培;运算符+ =（AST＆安培;＆安培;其他）{
的std ::移动（other.value.begin（），other.value.end（），back_inserter（值））;
的std ::移动（other.children.begin（），other.children.end（），back_inserter（儿童））;
返回*这一点;
}
演示时间
让我们来设计我可以为这个AST想到的最简单的语法：
开始='{'＆GT;＆GT; - （int_％'，'）GT;＆GT; ';' ＆GT;＆GT; - （起始％'，'）GT;＆GT; };
<子>的注意我甚至没有让; 可选。好吧。样品。练习的读者。 ☡你知道演练的
我们实现了平凡函数 AST解析（这楼它升），然后我们可以简单地合并的AST：
INT的main（）{
AST合并;
对于（标准::字符串常量和放大器;输入：{
{1，2，3; {4; {9,8;}}，{5,6;}}，
{10,20,30; {40 {90，80;}}，{50,60;}}，
}）
{
合并+ =解析（input.begin（），input.end（））;
性病::法院LT＆;＆LT; 合并+＆LT;＆LT;输入＆LT;＆LT; - ＆gt;中与所述;＆下;合并＆LT;＆LT; \\ n;
}
}
<大骨节病> 住在Coliru
//＃定义BOOST_SPIRIT_DEBUG
＃包括LT＆;升压/融合/调整/ struct.hpp＆GT;
＃包括LT＆;升压/精神/有/ qi.hpp＆GT;
＃包括LT＆;升压/精神/有/ karma.hpp＆GT;命名空间补气=的boost ::精神::补气;
命名空间因缘=的boost ::精神::人缘;结构AST;// typedef的提振:: make_recursive_variant＆LT;提高:: recursive_wrapper＆LT; AST＆GT; ＆GT; ::类型的节点;
TYPEDEF提振::变体LT;提高:: recursive_wrapper＆LT; AST＆GT; ＆GT;节点;结构AST {
的std ::矢量＆lt;＆INT GT;值;
的std ::矢量＆lt;节点＆GT;儿童; 邮票;运算符+ =（AST＆安培;＆安培;其他）{
的std ::移动（other.value.begin（），other.value.end（），back_inserter（值））;
的std ::移动（other.children.begin（），other.children.end（），back_inserter（儿童））;
返回*这一点;
}
};BOOST_FUSION_ADAPT_STRUCT（AST，
（性病::矢量＆lt;＆INT GT;，值）
（性病::矢量＆lt;节点＆GT;，子女）
）模板＆LT; TYPENAME它，类型名船长=补气::空间类型＆GT;
语法结构：补气::语法＆LT;它，AST（），船长＆GT;
{
语法（）：语法:: base_type（开始）{
使用命名空间补气;
启动='{'＆GT;＆GT; - （int_％'，'）GT;＆GT; ';' ＆GT;＆GT; - （起始％'，'）GT;＆GT; };
BOOST_SPIRIT_DEBUG_NODES（（开始））;
}
私人的：
齐::规则＆LT;它，AST（），船长＆GT;开始;
};//输出：
静态内联的std :: ostream的＆放大器;运营商所述;≤（性病:: ostream的＆放大器;操作系统，AST常量＆放大器; 5）{
使用命名空间因缘;
治＆LT;的boost ::精神:: ostream_iterator，AST（）＆GT; - [R;
R ='{'＆LT;＆LT; - （int_％'，'）所述;＆下; ';' ＆LT;＆LT; - （（R | EPS）％'，'）所述;＆下; };
返回OS＆LT;＆LT;格式（R，ⅴ）;
}模板＆LT; TYPENAME它＆GT; AST解析（这楼它升）
{
AST解析; 静态语法＆LT;它＆GT; G;
布尔OK =齐:: phrase_parse（F，L，G，补气::空间分析）; 如果（OK！||（F！= 1））{
性病::法院LT＆;＆LT; 解析失败\\ n;
性病::法院LT＆;＆LT; 剩余未解析：'＆LT;＆LT;标准::字符串（F，L）LT;＆LT; '\\ n;
出口（255）;
} 返回解析;
}诠释主（）{
AST合并;
对于（标准::字符串常量和放大器;输入：{
{1，2，3; {4; {9,8;}}，{5,6;}}，
{10,20,30; {40 {90，80;}}，{50,60;}}，
}）
{
合并+ =解析（input.begin（），input.end（））;
性病::法院LT＆;＆LT; 合并+＆LT;＆LT;输入＆LT;＆LT; - ＆gt;中与所述;＆下;合并＆LT;＆LT; \\ n;
}
}
当然，它打印：
合并+ {1，2，3; {4; {9,8;}}，{5,6;}} - GT; {1,2,3; {4; {9,8;}}，{5,6;}}
合并+ {10,20,30; {40 {90，80;}}，{50,60;}} - GT; {1,2,3,10,20,30; {4; {9,8;}}，{5,6;}，{40; {90,80;}}，{50,60;}}
更新
在此 - 微不足道的 - 例如，你可以只集合绑定到解析调用的属性。同样的事情会发生，而不移动元素所需运算符+ = 通话，因为规则将被写入自动追加的到绑定容器的属性。
警告：修改目标值就地是，如果解析失败，会出现什么明显的劣势。在版本
合并值则是未定义（已收到从故障解析部分信息）。
所以，如果你要分析输入原子，第一个，更明确的做法是更好的选择。
所以下面是写相同的略短的方式：
<大骨节病> 住在Coliru
//的#define BOOST_SPIRIT_DEBUG
＃包括LT＆;升压/融合/调整/ struct.hpp＆GT;
＃包括LT＆;升压/精神/有/ qi.hpp＆GT;
＃包括LT＆;升压/精神/有/ karma.hpp＆GT;命名空间补气=的boost ::精神::补气;
命名空间因缘=的boost ::精神::人缘;结构AST;// typedef的提振:: make_recursive_variant＆LT;提高:: recursive_wrapper＆LT; AST＆GT; ＆GT; ::类型的节点;
TYPEDEF提振::变体LT;提高:: recursive_wrapper＆LT; AST＆GT; ＆GT;节点;结构AST {
的std ::矢量＆lt;＆INT GT;值;
的std ::矢量＆lt;节点＆GT;儿童;
};BOOST_FUSION_ADAPT_STRUCT（AST，
（性病::矢量＆lt;＆INT GT;，值）
（性病::矢量＆lt;节点＆GT;，子女）
）模板＆LT; TYPENAME它，类型名船长=补气::空间类型＆GT;
语法结构：补气::语法＆LT;它，AST（），船长＆GT;
{
语法（）：语法:: base_type（开始）{
使用命名空间补气;
启动='{'＆GT;＆GT; - （int_％'，'）GT;＆GT; ';' ＆GT;＆GT; - （起始％'，'）GT;＆GT; };
BOOST_SPIRIT_DEBUG_NODES（（开始））;
}
私人的：
齐::规则＆LT;它，AST（），船长＆GT;开始;
};//输出：
静态内联的std :: ostream的＆放大器;运营商所述;≤（性病:: ostream的＆放大器;操作系统，AST常量＆放大器; 5）{
使用命名空间因缘;
治＆LT;的boost ::精神:: ostream_iterator，AST（）＆GT; - [R;
R ='{'＆LT;＆LT; - （int_％'，'）所述;＆下; ';' ＆LT;＆LT; - （（R | EPS）％'，'）所述;＆下; };
返回OS＆LT;＆LT;格式（R，ⅴ）;
}模板＆LT; TYPENAME它＆GT;无效解析（这楼它L，AST＆安培;进入）
{
静态语法＆LT;它＆GT; G;
布尔OK =齐:: phrase_parse（F，L，G，补气::空间，进入）; 如果（OK！||（F！= 1））{
性病::法院LT＆;＆LT; 解析失败\\ n;
性病::法院LT＆;＆LT; 剩余未解析：'＆LT;＆LT;标准::字符串（F，L）LT;＆LT; '\\ n;
出口（255）;
}
}诠释主（）{
AST合并;
对于（标准::字符串常量和放大器;输入：{
{1，2，3; {4; {9,8;}}，{5,6;}}，
{10,20,30; {40 {90，80;}}，{50,60;}}，
}）
{
解析（input.begin（），input.end（），合并）;
性病::法院LT＆;＆LT; 合并+＆LT;＆LT;输入＆LT;＆LT; - ＆gt;中与所述;＆下;合并＆LT;＆LT; \\ n;
}
}不过打印
I have a working boost spirit parser and was thinking if it is possible to do iterative update of an abstract syntax tree with boost spirit?
I have a struct similar to:
struct ast; typedef boost::variant< boost::recursive_wrapper<ast> > node; struct ast { std::vector<int> value; std::vector<node> children; };Which is being parsed by use of:
bool r = phrase_parse(begin, end, grammar, space, ast);Would it be possible to do iterative update of abstract syntax tree with boost spirit? I have not found any documentation on this, but I was thinking if the parsers semantic actions could push_back on an already existing AST. Has anyone tried this?
This would allow for parsing like this:
bool r = phrase_parse(begin, end, grammar, space, ast); //initial parsing //the second parse will be called at a later state given some event/timer/io/something bool r = phrase_parse(begin, end, grammar, space, ast); //additional parsing which will update the already existing AST
解决方案How would you know which nodes to merge? Or would you always add ("graft") at the root level? In that case, why don't you just parse another and merge moving the elements into the existing ast?
ast& operator+=(ast&& other) { std::move(other.value.begin(), other.value.end(), back_inserter(value)); std::move(other.children.begin(), other.children.end(), back_inserter(children)); return *this; }
Demo Time
Let's devise the simplest grammar I can think of for this AST:
start = '{' >> -(int_ % ',') >> ';' >> -(start % ',') >> '}';Note I didn't even make the
;optional. Oh well. Samples. Exercises for readers. ☡ You know the drill.We implement the trivial function
ast parse(It f, It l), and then we can simply merge the asts:int main() { ast merged; for(std::string const& input : { "{1 ,2 ,3 ;{4 ;{9 , 8 ;}},{5 ,6 ;}}", "{10,20,30;{40;{90, 80;}},{50,60;}}", }) { merged += parse(input.begin(), input.end()); std::cout << "merged + " << input << " --> " << merged << "\n"; } }//#define BOOST_SPIRIT_DEBUG #include <boost/fusion/adapted/struct.hpp> #include <boost/spirit/include/qi.hpp> #include <boost/spirit/include/karma.hpp> namespace qi = boost::spirit::qi; namespace karma = boost::spirit::karma; struct ast; //typedef boost::make_recursive_variant<boost::recursive_wrapper<ast> >::type node; typedef boost::variant<boost::recursive_wrapper<ast> > node; struct ast { std::vector<int> value; std::vector<node> children; ast& operator+=(ast&& other) { std::move(other.value.begin(), other.value.end(), back_inserter(value)); std::move(other.children.begin(), other.children.end(), back_inserter(children)); return *this; } }; BOOST_FUSION_ADAPT_STRUCT(ast, (std::vector<int>,value) (std::vector<node>,children) ) template <typename It, typename Skipper = qi::space_type> struct grammar : qi::grammar<It, ast(), Skipper> { grammar() : grammar::base_type(start) { using namespace qi; start = '{' >> -(int_ % ',') >> ';' >> -(start % ',') >> '}'; BOOST_SPIRIT_DEBUG_NODES((start)); } private: qi::rule<It, ast(), Skipper> start; }; // for output: static inline std::ostream& operator<<(std::ostream& os, ast const& v) { using namespace karma; rule<boost::spirit::ostream_iterator, ast()> r; r = '{' << -(int_ % ',') << ';' << -((r|eps) % ',') << '}'; return os << format(r, v); } template <typename It> ast parse(It f, It l) { ast parsed; static grammar<It> g; bool ok = qi::phrase_parse(f,l,g,qi::space,parsed); if (!ok || (f!=l)) { std::cout << "Parse failure\n"; std::cout << "Remaining unparsed: '" << std::string(f,l) << "'\n"; exit(255); } return parsed; } int main() { ast merged; for(std::string const& input : { "{1 ,2 ,3 ;{4 ;{9 , 8 ;}},{5 ,6 ;}}", "{10,20,30;{40;{90, 80;}},{50,60;}}", }) { merged += parse(input.begin(), input.end()); std::cout << "merged + " << input << " --> " << merged << "\n"; } }Of course, it prints:
merged + {1 ,2 ,3 ;{4 ;{9 , 8 ;}},{5 ,6 ;}} --> {1,2,3;{4;{9,8;}},{5,6;}} merged + {10,20,30;{40;{90, 80;}},{50,60;}} --> {1,2,3,10,20,30;{4;{9,8;}},{5,6;},{40;{90,80;}},{50,60;}}
UPDATE
In this - trivial - example, you can just bind the collections to the attributes in the parse call. The same thing will happen without the
operator+=call needed to move the elements, because the rules are written to automatically append to the bound container attribute.CAVEAT: A distinct disadvantage of modifying the target value in-place is what happens if parsing fails. In the version the
mergedvalue will then be "undefined" (has received partial information from the failed parse).So if you want to parse inputs "atomically", the first, more explicit approach is a better fit.
So the following is a slightly shorter way to write the same:
// #define BOOST_SPIRIT_DEBUG #include <boost/fusion/adapted/struct.hpp> #include <boost/spirit/include/qi.hpp> #include <boost/spirit/include/karma.hpp> namespace qi = boost::spirit::qi; namespace karma = boost::spirit::karma; struct ast; //typedef boost::make_recursive_variant<boost::recursive_wrapper<ast> >::type node; typedef boost::variant<boost::recursive_wrapper<ast> > node; struct ast { std::vector<int> value; std::vector<node> children; }; BOOST_FUSION_ADAPT_STRUCT(ast, (std::vector<int>,value) (std::vector<node>,children) ) template <typename It, typename Skipper = qi::space_type> struct grammar : qi::grammar<It, ast(), Skipper> { grammar() : grammar::base_type(start) { using namespace qi; start = '{' >> -(int_ % ',') >> ';' >> -(start % ',') >> '}'; BOOST_SPIRIT_DEBUG_NODES((start)); } private: qi::rule<It, ast(), Skipper> start; }; // for output: static inline std::ostream& operator<<(std::ostream& os, ast const& v) { using namespace karma; rule<boost::spirit::ostream_iterator, ast()> r; r = '{' << -(int_ % ',') << ';' << -((r|eps) % ',') << '}'; return os << format(r, v); } template <typename It> void parse(It f, It l, ast& into) { static grammar<It> g; bool ok = qi::phrase_parse(f,l,g,qi::space,into); if (!ok || (f!=l)) { std::cout << "Parse failure\n"; std::cout << "Remaining unparsed: '" << std::string(f,l) << "'\n"; exit(255); } } int main() { ast merged; for(std::string const& input : { "{1 ,2 ,3 ;{4 ;{9 , 8 ;}},{5 ,6 ;}}", "{10,20,30;{40;{90, 80;}},{50,60;}}", }) { parse(input.begin(), input.end(), merged); std::cout << "merged + " << input << " --> " << merged << "\n"; } }Still prints
这篇关于抽象语法树的迭代更新与提升精神的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
