Re: Chomsky Normal Form and parsing

hdev@dutiak.twi.tudelft.nl (Hans de Vreught)
Wed, 24 Feb 1993 11:40:04 GMT

          From comp.compilers

Related articles
Chomsky Normal Form and parsing ebcrmb@ebc.ericsson.se (1993-02-23)
Re: Chomsky Normal Form and parsing hdev@dutiag.twi.tudelft.nl (1993-02-23)
Re: Chomsky Normal Form and parsing eifrig@beanworld.cs.jhu.edu (1993-02-24)
Re: Chomsky Normal Form and parsing hdev@dutiak.twi.tudelft.nl (1993-02-24)
| List of all articles for this month |

Newsgroups: comp.compilers
From: hdev@dutiak.twi.tudelft.nl (Hans de Vreught)
Keywords: parse, theory
Organization: Delft University of Technology
References: 93-02-127 93-02-131
Date: Wed, 24 Feb 1993 11:40:04 GMT



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
--


Post a followup to this message

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