GLL syntax analysers for EBNF grammars
GLL syntax analysers for EBNF grammars
复制标题
用于 EBNF 语法的 GLL 语法分析器
DOI：
10.1016/j.scico.2018.06.001
复制
发表时间：
2018
影响因子：
1.3
通讯作者：
Scott E
中科院分区：
文献类型：
--
作者：
Scott E
GLL 是一种最坏情况三次、基于递归下降的解析技术，可以应用于所有 BNF 语法，而不需要进行语法修改。然而，EBNF 语法因其紧凑性和相对表达的简单性而经常被使用。在本文中，我们给出了推导的解析树表示的正式规范，它反映了语法的 EBNF 结构，是最坏情况的立方大小，并在歧义的情况下捕获所有推导。对于具有可为 null 主体的闭包，需要特别小心。我们还描述了直接支持 EBNF 结构的 GLL 扩展。生成的解析器是最坏情况立方的，并遵循指定 EBNF 语法的结构，使得解析器行为易于推理。解析器利用因式分解的效率和迭代而不是递归的使用，在存在嵌入语义动作的情况下保留规范的结构。
GLL is a worst-case cubic, recursive descent based parsing technique which can be applied to all BNF grammars without the need for grammar modification. However, EBNF grammars are often used, both for their compactness and their relative expressive simplicity. In this paper we give a formal specification for a parse tree representation of derivations which reflects the EBNF structure of the grammar, is worst case cubic size, and captures all derivations in the case of ambiguity. Particular care is need in the case of closures with nullable bodies. We also describe an extension of GLL which directly supports the EBNF constructs. The resulting parsers are worst case cubic and follow the structure of the specifying EBNF grammar, making the parser behaviour easy to reason about. The parsers exploit the efficiency of factorisation and the use of iteration rather than recursion, retaining the structure of the specification in the presence of embedded semantic actions.
登录
查看更多内容
DOI：
10.1016/j.scico.2012.03.005
发表时间：
2013-10
期刊：
Sci. Comput. Program.
影响因子：
--
作者：
E. Scott;A. Johnstone
通讯作者：
E. Scott;A. Johnstone
增加LR解析的适用性
DOI：
10.1007/978-94-010-9733-8_3
发表时间：
1993
期刊：
J. Comput. Lang.
影响因子：
--
作者：
M. Nederhof;J. Sarbo
通讯作者：
J. Sarbo
更快的广义 LR 解析
影响因子：
0.6
作者：
John Aycock;N. Horspool;Jan Janousek;B. Melichar
通讯作者：
B. Melichar
对于句法定义中不必要的符号多样性，我们能做些什么呢？
影响因子：
22.7
作者：
N. Wirth
通讯作者：
N. Wirth
构建 GLL 解析算法以提高性能
影响因子：
1.3
作者：
Scott E
通讯作者：
Scott E