Python parser

andrew cooke andrew at acooke.org
Wed Mar 4 13:12:31 CET 2009


Kay Schluehr wrote:
> You'll most likely need a GLR parser.

i'm not sure why you think this.  as far as i can tell, the OP needs a
parser that is suitable for whatever grammar they find (and the grammar
will probably be written for a particular parser, which may not be GLR).

however, if you are saying that only a GLR parser can parse natural
languages then i think you are wrong.  not only can grammars be rewritten
in different ways, but a recursive descent parser with appropriate
memoisation is capable of parsing "any" grammar.

see, for example, the second example at
http://www.acooke.org/lepl/advanced.html#memoisation - that is a
left-recursive, highly ambiguous grammar, and is parsed successfully with
recursive descent (as far as i can tell).  for more info see
http://www.acooke.org/lepl/implementation.html#memoisation and
http://www.cs.uwindsor.ca/~hafiz/p46-frost.pdf

in theory (if not currently in practice for my code, at least) it is also
efficient (in a "big O" sense).

disclaimer - the lepl parser linked to is my own and that functionality is
very new (there's a beta version released, but it is buggy).  however,
that doesn't mean this is not possible....

andrew





More information about the Python-list mailing list