Tue, 23 Feb 1993 23:05:51 GMT

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

Newsgroups: | comp.compilers |

From: | hdev@dutiag.twi.tudelft.nl (Hans de Vreught) |

Keywords: | parse, question |

Organization: | Delft University of Technology |

References: | 93-02-127 |

Date: | Tue, 23 Feb 1993 23:05:51 GMT |

ebcrmb@ebc.ericsson.se (BO/EBC/KX/ZG Michael Bergman 682 4958) writes:

*>Hi everyone, >I have some more entangled(?) questions on CFG's.*

*>This time it's Chomsky [...] normal forms I'm interested in.*

*>The question is: what's the practical use of this?*

If we would leave the linguistic stuff aside (Noam Chomsky is a linguist), it

gives you a very simple form of a grammar caple to generate any CFL. That is

very practical in formal language proofs: you may assume the grammar for a CFL

is in CNF.

*>Can we parse this Chomsky Normal Form for sure using some parsing method?*

Furthermore, because any CFG can be put into CNF it is sufficient to have

a parser for grammars in CNF. Such a parser does exist. The

Cocke-Younger-Kasami algorithm is exactly such an algorithm. The CYK

algorithm is very simple and run in O(n^3) time. Since it can handle

ambigous grammars the mainstream applications for this algorithm can be

found in NLP.

One step further, Rytter has parallelize this algorithm to obtain a fast

parallel algorithm running in O(log n) time with O(n^6) processors on a

CRCW-PRAM. O.K. O(n^6) sounds bad, but it gives the best time complexity

known.

--

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.