4

I've been reading Dick Grune's Parsing techniques 1st edition for quite a while now, the book is from the mid-90's and the author argues that no such parsing method (Linear-time general parsing) has been discovered until the date.

"we should like to have a linear-time general parsing method. Unfortunately no such method has been discovered to date." pg 76

Has anyone developed such method?

double-beep
  • 5,031
  • 17
  • 33
  • 41
k3oy
  • 531
  • 2
  • 6
  • 19

4 Answers4

3

No such method has been devised. As far as I can tell, the CYK algorithm remains the general parsing algorithm with the best worst case performance (O(n3)).

opqdonut
  • 5,119
  • 22
  • 25
1

A GLR parsers are O(n^3) in worst case, but offer linear performance where the grammar is deterministic. Many grammars have this property, so in effect you get linear time parsing in practice.

We've managed to build parsers for many real, complicated languages using a GLR parser, even the famously hard to parse C++.

Community
  • 1
  • 1
Ira Baxter
  • 93,541
  • 22
  • 172
  • 341
0

Packrat with a full memoisation is a guaranteed O(n), but there is a relatively big linear multiplier.

SK-logic
  • 9,605
  • 1
  • 23
  • 35
0

I am developing a parser (JoeSon) written in CoffeeScript, and I believe it is O(n) for most interesting grammars.

I think it is essentially a Packrat parser, but with the ability to bypass the cache for some rules, which I think is necessary to write whitespace-sensitive grammars.

Packrat does not parse all context free grammars. It has difficulty with counting problems, like with the grammar ' S = x S x | x '. But these kinds of grammars are also difficult for humans to parse.

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

Jag the Reducer
  • 51
  • 4