Re: Chomsky Normal Form and parsing (Hans de Vreught)
Tue, 23 Feb 1993 23:05:51 GMT

          From comp.compilers

Related articles
Chomsky Normal Form and parsing (1993-02-23)
Re: Chomsky Normal Form and parsing (1993-02-23)
Re: Chomsky Normal Form and parsing (1993-02-24)
Re: Chomsky Normal Form and parsing (1993-02-24)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Hans de Vreught)
Keywords: parse, question
Organization: Delft University of Technology
References: 93-02-127
Date: Tue, 23 Feb 1993 23:05:51 GMT (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)
The Netherlands

Post a followup to this message

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