Линейный генератор времени

Question

Я уже давно читаю 1-е издание техники парсинга Дика Грюна, книга написана в середине 90-х годов, и автор утверждает, что такой метод анализа (общий анализ в линейном времени) не был обнаружен до даты .

"нам бы хотелось иметь метод общего анализа с линейным временем. К сожалению, до настоящего времени такой метод не был обнаружен. "Pg 76

Так мне было интересно, кто-нибудь разрабатывал такой метод?

Заранее спасибо за помощь.

(извините за способ, которым я пометил, у StackOverflow нет "linear-time" и "General" в качестве тегов)

Answer 1

Такой метод не был разработан. Насколько я могу судить, алгоритм CYK остается общим алгоритмом синтаксического анализа с наилучшей наихудшей производительностью ( O (n ³ ) ).

Answer 2

Я занимаюсь разработкой парсера (JoeSon), написанного на CoffeeScript, и я считаю, что для большинства интересных грамматик это O (n).

Я думаю, что это, по сути, парсер Packrat, но с возможностью обходакеш для некоторых правил, которые я считаю необходимыми для написания чувствительных к пробелам грамматик.

Packrat не разбирает все контекстно-свободные грамматики.У него проблемы со счетом, как в случае с грамматикой 'S = x S x |Икс '.Но эти виды грамматики людям также трудно анализировать.

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

Answer 3

A GLR-синтаксические анализаторы - это O (n ^ 3) в худшем случае, но предлагают линейную производительность, когда грамматика является детерминированной. Многие грамматики обладают этим свойством, поэтому на практике вы получаете линейный анализ времени.

Нам удалось создать парсеры для многих реальных, сложных языков с использованием синтаксического анализатора GLR, даже для сложного анализа C ++ .

Answer 4

Packrat с полным запоминанием является гарантированным O (n), но существует относительно большой линейный множитель.