  The problem of parsing has been studied extensively for various formal
grammars. Given an input string and a grammar, the parsing problem is to check
if the input string belongs to the language generated by the grammar. A closely
related problem of great importance is one where the input are a string ${\cal
I}$ and a grammar $G$ and the task is to produce a string ${\cal I}'$ that
belongs to the language generated by $G$ and the `distance' between ${\cal I}$
and ${\cal I}'$ is the smallest (from among all the strings in the language).
Specifically, if ${\cal I}$ is in the language generated by $G$, then the
output should be ${\cal I}$. Any parser that solves this version of the problem
is called an {\em error correcting parser}. In 1972 Aho and Peterson presented
a cubic time error correcting parser for context free grammars. Since then this
asymptotic time bound has not been improved under the (standard) assumption
that the grammar size is a constant. In this paper we present an error
correcting parser for context free grammars that runs in $O(T(n))$ time, where
$n$ is the length of the input string and $T(n)$ is the time needed to compute
the tropical product of two $n\times n$ matrices.
  In this paper we also present an $\frac{n}{M}$-approximation algorithm for
the {\em language edit distance problem} that has a run time of $O(Mn^\omega)$,
where $O(n^\omega)$ is the time taken to multiply two $n\times n$ matrices. To
the best of our knowledge, no approximation algorithms have been proposed for
error correcting parsing for general context free grammars.
