Re: LALR parsing

"A. Soare" <alinsoar@voila.fr> writes:


> I want to implement a LALR parser for an arbitrary grammar (many
> common point to yacc, however different).
>
> However, I did read that these methods are not the most fast. The
> fastest methods use matrix multiplications, etc. In the book of Grune
> is it explained something about the equalence between parsing and
> matrix multiplication, but I see nothing useful apart of some vagues
> ideas.
>
> My question for you is: what are the most efficient methods of lalr parsing?


LALR(1) defined a class of grammars that can be parsed with a
deterministic LALR(1) parser. These can be parsed in something
approaching linear time. But LALR(1) can not deterministically parse
arbitrary grammars. You can add backtracking to allow parsing of
arbitrary grammars, but that can in the worst case give exponential
runtimes. GLR parsers (see http://en.wikipedia.org/wiki/GLR_parser)
handle the multiple parses in a breath-first manner instead of a
depth-first backtracking, so they can merge identical states. This
reduces the worst case to O(n^3).


While the matrix-multiplication methods you refer to have better
worst-case performance, GLR will outperform them in most cases. Matrix
multiplication can be done in O(n^2.376), but the algorithm for this has
a huge constant factor overhead that makes the traditional O(n^3) method
faster except for extremely large matrices. So I doubt the O(n^2.376)
algorithm is of any practical use for parsing.


Note, however, that while it has been proven that the complexity of
parsing is bounded by the complexity of matrix multiplication, the
converse is not true: There may well be general parsers that are faster
than matrix multiplication. IIRC, the lower bound for CF parsing is
still O(n).


Torben

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