Lourdes Araujo.

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.