代码之家 › 专栏 › 技术社区 › ljs TheVillageIdiot

GLR解析算法资源

glr parser-generator parsing compiler-construction

20

ljs TheVillageIdiot · 技术社区 · 15 年前

I am writing GLR parser generator 我想了解一些关于这个算法的参考资料,包括互联网上的和死树(为那些不熟悉极客语言的人准备的书)。

那么,有人知道我可以利用的好资源吗?谢谢

4 回复 | 直到 15 年前

1

15

Matthew Slattery 15 年前

我在网上遇到过一些好东西:

关于 Elkhound Elkhound: A Fast, Practical GLR Parser Generator . 在2004年4月的《编译器构造函数会议记录》(CC04)中。

这个 UCB/CSSD-2-1214 technical report
Bison documentation :伊丽莎白·斯科特、阿德里安·约翰斯通和沙姆萨·萨达夫·侯赛因。 Tomita-Style Generalised LR Parsers . TR—00—12,Royal Holloway,伦敦大学,计算机系,2000年12月。

我还知道第三个开源GLR解析器: DParser

2

5

Kenneth Cochran 10 年前

Adrian Johnstone发表了大量关于GLR算法高级版本的工作。伊斯 publications website

3

Steve Hanov 15 年前

这本书中包含了我所见过的最好的描述,以及演示算法每个步骤的图片:

http://books.google.ca/books?id=05xA_d5dSwAC&lpg=PA381&dq=generalized%20deterministic%20parsers&pg=PA381#v=onepage&q=generalized%20deterministic%20parsers&f=false

对于伪代码,请转到源代码:Tomita的广义LR解析,第70页左右。Farshi的论文包含了一个简洁的描述。

http://books.google.ca/books?id=PvZiZiVqwHcC&lpg=PP1&dq=generalized%20lr%20parsing&pg=PA70#v=onepage&q=&f=false

这是我为qb.js尝试的技术之一( qbasic in javascript ).

4

2

Anon. 15 年前

当解析失败时(由于遇到非法元素),它会被简单地删除,因为它一定是对早期歧义的错误猜测。

最后,除了一个解析之外,所有的解析都应该终止了——而幸存的解析就是对这些歧义点的“正确”解析。

5

0

Gunther Schadow 3 年前

几年前,我刚刚发现我重新发明了GLR解析,因为我正在解析英文文本以提取项目的复杂描述。我想,我从我看到的每个标记的初始状态开始,每个标记都有多个并行状态,在每个状态上,我保留合成的语义值堆栈。我以为我发明了一些很酷的新东西,结果发现它已经在1974年完成了,叫做GLR解析。我仍然很难手动编码我的状态和转换,还没有退下来考虑我如何定义我的语法使用一些类似于BNF的符号。