Re: LALR parsing

Russ Cox <rsc@swtch.com> writes:
> We prove a dual result: any CFG parser with time complexity
> O(g*n^(3-epsilon)), where g is the size of the grammar and n is
> the length of the input string, can be efficiently converted into
> an algorithm to multiply m x m Boolean matrices in time
> O(m^(3-epsilon/3)).
>
> The more precise version of the statement above is therefore:
> Unless you can do matrix multiplication in O(m^(2 1/3)) time,
> you cannot do context free parsing in O(g*n) time.


http://en.wikipedia.org/wiki/Matrix_multiplication#Algorithms_for_efficient_matrix_multiplication
states that the asymptoticallty fastest known square matrix
multiplication algorithm is O(m^2.376), which isn't that far from
O(m^2.3333). Since O(m^2.376) is "only" the currently best known
result, it is quite plausible that faster methods exist. So I can't see
the statement itself being a serious impediment to linear-time general
CF parsing.


Personally, I would not look at matrix multiplication for fast general
parsing, but rather look at extensions to deterministic push-down
automata. Two-way deterministic pushdown automata (which are O(n) on a
RAM) can parse surprisingly complex grammars (including many non-CF
grammars), and AFAIK it has not been proven that they can not parse all
CF grammars. So they seem like a good point to start looking for fast
parsing.


Torben

Return to the comp.compilers page.
Search the comp.compilers archives again.