A General Algorithm for Solving a Set of Recursive Equations: Exemplified by LR-theory

Resumé

A general algorithm for computing the solutions to a set of recursive equations of a general form is given. The form of the recursive equations is closely related to results on LR-theory. The algorithm appears as intuitively understandable in an abstract form. The correctness of the algorithm is proved. An analysis of the complexity shows that the algorithm compares well to existing algorithms. Examples of application of the general algorithm to elements of LR-theory, such as LALR(1)-lookahead computation and LR(1)-testing, are included.