Re: Chomsky Normal Form and parsing

ebcrmb@ebc.ericsson.se (BO/EBC/KX/ZG
>Can we parse this Chomsky Normal Form for sure using some parsing method?


eifrig@beanworld.cs.jhu.edu (Jonathan Eifrig) writes:
> Of course, these are the wrong sorts of parsing questions to ask,
>in practice. As I argued above, there's very little use for a parser that
>just answers "Yes" or "No"; what one _really_ needs is a parser that
>generates a parse tree of the input.


Ah, but such a parser *does* exist. In the recognition phase an upper
triangular matrix is filled in such a way such that every partial parse
can be retrieved. So after that phase you only have to look why the answer
on the recognition question was yes. While establishing that justification
you are able to retrieve a parse tree. Since the parsing stage is simple
the total complexity for recognition and parsing is O(n^3).


Like I said before (in a previous posting), algorithms for CFGs in CNF are
used frequently. However, not in compiler design but in natural language
processing.
--
Hans de Vreught
hdev@dutiba.twi.tudelft.nl
Delft University of Technology (TWI-ThI)
The Netherlands
--

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