In this paper, we present a derivative-based, functional recognizer and parser generator for visibly pushdown grammars. The generated parser accepts ambiguous grammars and produces a parse forest containing all valid parse trees for an input string in linear time. Each parse tree in the forest can then be extracted also in linear time. Besides the parser generator, to allow more flexible forms of the visibly pushdown grammars, we also present a translator that converts a tagged CFG to a visibly pushdown grammar in a sound way, and the parse trees of the tagged CFG are further produced by running the semantic actions embedded in the parse trees of the translated visibly pushdown grammar. The performance of the parser is compared with a popular parsing tool ANTLR and other popular hand-crafted parsers. The correctness of the core parsing algorithm is formally verified in the proof assistant Coq.


翻译:在本文中, 我们为明显下推语法提供了一个基于衍生物的、 功能识别器和剖析器生成器。 生成的剖析器接受模糊的语法, 并生成一个包含所有有效剖析树的剖析林, 用于直线时间的输入线条。 然后, 森林中的每一棵剖析树也可以在线性时间中提取 。 除了剖析器生成器外, 允许更灵活的表推语法形式, 我们还提出一个翻译器, 将贴有标签的 CFG 转换成一个明显推下语法, 并且通过运行被翻译的明显下推语法树的剖析树进一步生成 。 剖析器的性能与流行的剖析工具 ANTRR 和其他流行手工艺的剖析器相比较。 校准助理 Coq 正式验证了核心剖析算法的正确性 。

0
下载
关闭预览

相关内容

最新【深度生成模型】Deep Generative Models,104页ppt
专知会员服务
69+阅读 · 2020年10月24日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
78+阅读 · 2020年7月26日
【经典书】贝叶斯编程,378页pdf,Bayesian Programming
专知会员服务
247+阅读 · 2020年5月18日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
无人机视觉挑战赛 | ICCV 2019 Workshop—VisDrone2019
PaperWeekly
7+阅读 · 2019年5月5日
Gartner:2019 年 MSP 魔力象限
云头条
15+阅读 · 2019年3月6日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
VIP会员
相关资讯
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
无人机视觉挑战赛 | ICCV 2019 Workshop—VisDrone2019
PaperWeekly
7+阅读 · 2019年5月5日
Gartner:2019 年 MSP 魔力象限
云头条
15+阅读 · 2019年3月6日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Top
微信扫码咨询专知VIP会员