線性時間一般分析器

Question

我一直在閱讀Dick Grune的解析技術第1版已有相當長一段時間了，本書是從90年代中期開始的，作者認爲沒有這種解析方法（線性時間通用解析）直到日期才被發現。

「我們希望有一個線性時間的通用解析方法 不幸的是迄今爲止還沒有發現這樣的方法。第76頁

所以我想知道有沒有人開發過這樣的方法？

在此先感謝您的幫助。

（約我標記的方式對不起，StackOverflow上沒有「線性時間」和「一般」的標籤）

Answer 1

沒有這樣的方法已經被設計出來。據我所知道的，CYK algorithm仍然一般分析算法的最佳最壞的情況性能（爲O（n ））。

Answer 2

Packrat與完整的memoisation是一個有保證的O（n），但有一個相對較大的線性乘法器。

Answer 3

A GLR parsers在最壞的情況下是O（n^3），但是在語法是確定性的情況下提供線性性能。許多語法都有這個屬性，所以實際上你可以在實踐中獲得線性時間解析。

我們使用GLR解析器設計了parsers for many real, complicated languages，even the famously hard to parse C++。

Answer 4

我正在開發一個用CoffeeScript編寫的解析器（JoeSon），我相信對大多數有趣的語法來說它是O（n）。

我認爲它本質上是一個Packrat解析器，但能夠繞過某些規則的緩存，我認爲這對編寫空白敏感的語法是必要的。

Packrat不解析所有上下文無關語法。計算問題有困難，例如語法'S = x S x |' X '。但是這些語法對於人類來說也是很難解析的。

https://github.com/jaekwon/joeson/blob/master/joeson_grammar.coffee https://github.com/jaekwon/joeson/blob/master/joescript_grammar.coffee