Error detection in precedence parsers

We consider methods by which a precedence matrix may be modified without severely degrading the error-detecting capability of a parser utilizing the matrix. Two different definitions of the same error detection capability are considered. The first, called exact equivalence, permits only useless parts of the precedence matrix to be modified. The second, called simply equivalence, allows the modified matrix to perform some reductions, but never to shift an input symbol, after the original has detected an error.We give necessary and sufficient conditions for a modified precedence parser to be equivalent or exactly equivalent to the canonical parser. We then consider the interesting case where the modification is caused by replacing the precedence matrix by linear precedence functions. A simple algorithm to find (if they exist) exactly equivalent linear precedence functions for a given precedence matrix is presented.The work by this author was partially supported by NSF grant GJ-465.