Evolutionary Parsing for a Probabilistic Context Free Grammar.
Lourdes Araujo.
Proc. International Conference on Rough Sets and Current Trends in Computing
(RSCTC-2000) , LNCS 2005, Springer-Verlag, (2000).

Classic parsing methods are based on complete search techniques to find
the different interpretations of a sentence. However, the size of the
search space increases exponentially with the length of the sentence or text
to be parsed, so that exhaustive search methods can fail to reach a solution
in a reasonable time. Nevertheless, large problems can be solved approximately
by some kind of stochastic techniques, which do not guarantee the optimum
value, but allow adjusting the probability of error by increasing the
number of points explored. Genetic Algorithms are among such techniques. This
paper describes a probabilistic natural language parser based on a genetic
algorithm. The algorithm works with a population of possible parsings
for a given sentence and grammar, which represent the chromosomes. The
algorithm produces successive generations of individuals, computing their
``fitness'' at each step and selecting the best of them when the termination
condition is reached. The paper deals with the main issues arising
in the algorithm:chromosome representation and evaluation, selection and
replacement strategies, and design of genetic operators for crossover
and mutation. The model has been implemented, and the results obtained
for a number of sentences are presented.