|Chomsky Normal Form and parsing firstname.lastname@example.org (1993-02-23)|
|Re: Chomsky Normal Form and parsing email@example.com (1993-02-23)|
|Re: Chomsky Normal Form and parsing firstname.lastname@example.org (1993-02-24)|
|Re: Chomsky Normal Form and parsing email@example.com (1993-02-24)|
|From:||firstname.lastname@example.org (Hans de Vreught)|
|Organization:||Delft University of Technology|
|Date:||Wed, 24 Feb 1993 11:40:04 GMT|
>Can we parse this Chomsky Normal Form for sure using some parsing method?
email@example.com (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
Hans de Vreught
Delft University of Technology (TWI-ThI)
Return to the
Search the comp.compilers archives again.