|Chomsky Normal Form and parsing email@example.com (1993-02-23)|
|Re: Chomsky Normal Form and parsing firstname.lastname@example.org (1993-02-23)|
|Re: Chomsky Normal Form and parsing email@example.com (1993-02-24)|
|Re: Chomsky Normal Form and parsing firstname.lastname@example.org (1993-02-24)|
|From:||email@example.com (Hans de Vreught)|
|Organization:||Delft University of Technology|
|Date:||Tue, 23 Feb 1993 23:05:51 GMT|
firstname.lastname@example.org (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
Hans de Vreught
Delft University of Technology (TWI-ThI)
Return to the
Search the comp.compilers archives again.