Re: Chomsky Normal Form and parsing

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

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