Mei*_*bur 23 language-agnostic parser-generator
序言:虽然解析器识别的语言集(无上下文语法)严格大于扫描程序(常规语法),但大多数解析器生成器都需要扫描程序.
(请不要试图解释其背后的原因,我非常了解它们).
我见过解析器,不需要扫描仪
使用无扫描仪有一些优点:
通常,使用"解决方法"就像在解析器的请求上切换扫描程序一样.
问题:你知道其他任何无扫描器解析器生成器(任何语言)吗？这些是实用的(或纯粹的学术性的)？除了Tomita/GLR之外还有其他方法吗？
回答:
Nor*_*sey 11
另外两个:
Bryan Ford的Parsing Expression Grammars(PEG)不需要扫描仪.高效,懒惰的"packrat解析器"是可选的.我对Lua LPEG版本只有很好的经验,它编译成一个高效的字节码机器.相当实用.
YAKKER看起来非常有趣,尽管它仍处于释放前的状态.他们正在使用他们声称的Earley解析算法的有效变体.
我实际上是无扫描解析器的忠实粉丝; 它们极大地简化了配置.温和地说,典型的扫描仪发生器使用起来并不是很有趣.从Lex的手册页:
最后,我对Elkhound没有个人经验,但我听到的二手报道令人印象深刻.我想说毫无疑问,但是一些无扫描器解析器生成器非常实用.
分析器生成器不需要扫描仪.但如果你不使用它,你就会非常疯狂.
解析器生成器构建的解析器不关心您为它们提供什么,只要您将它们称为令牌即可.
要构建使用不带扫描器的解析器生成器,只需将语法定义到字符级别,然后将单个字符作为标记提供给解析器.
这很疯狂的原因是解析是一个比lexing更复杂的活动.您可以将词法分析器构建为有限状态机,它将机器代码转换为"比较并跳转到下一个状态".对于速度,这真的很难被击败.解析器生成器构造解析器,执行递归下降预测解析(对于大多数LL生成器,如ANTLR)或通过散列,二进制或线性搜索等进行表查找.因此解析器在令牌上花费的能量比词法分析器花费的更多.字符.
如果您将字符作为标记提供给解析器,那么它将在字符上花费相应的能量,而不是相同的词法分析器.如果你处理大量的输入文本,这最终会很重要,无论你是为数以万计的小输入流还是为一些非常大的输入流而做.
相对于设计为使用令牌的GLR解析器,所谓的无扫描器GLR解析器遭受此性能问题.
我的公司构建了一个工具, 即DMS软件再造工具包,它使用了一个GLR解析器(并且成功地解析了你知道的所有常见语言,以及你没有的许多常见语言,因为它有一个GLR解析器).我们知道无扫描器解析器,并且由于速度差异而选择不实现它们; 我们有一个经典风格(但非常强大)的LEX类子系统,用于定义词法标记.在一个案例中,DMS对XT(一种具有无扫描器GLR解析器的工具)基于工具处理相同输入进行了鼻子对鼻子,DMS的速度似乎是XT包的10倍.公平地说,所做的实验是临时的,不会重复,但因为它符合我的怀疑,我认为没有理由重复它.因人而异.当然,如果我们想要无扫描,那么,正如我已经指出的那样,很容易用字符终端编写一个语法.
GLR Scannerless解析器确实有另一个非常好的属性,对大多数人来说无关紧要.您可以为无扫描器解析器提供两个单独的语法,并逐字地连接它们,并且仍然可以获得解析器(通常具有很多含糊之处).当你在另一个语言中嵌入一种语言时,这很重要.如果这不是你在做什么,这只是学术上的好奇心.
并且,AFAIK,Elkhound不是无扫描仪的.(我可能错了).(编辑:2/10:看起来我错了.不会是我生命中的第一次:)
| 归档时间： |
|
| 查看次数： |
3169 次 |
| 最近记录： |