Operations on sparse relations

ABSTRACT

Various computations on relations, Boolean matrices, or directed graphs, such as the computation of precedence relations for a context-free grammar, can be done by a practical algorithm that is asymptotically faster than those in common use. For example, how to compute operator precedence or Wirth-Weber precedence relations in O(n2) steps is shown, as well as how to compute linear precedence functions in O(n) steps, where n is the size of a grammar. The heart of the algorithms is a general theorem giving sufficient conditions under which an expression whose operands are sparse relations and whose operators are composition, transitive closure, union, and inverse, can be computed efficiently.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Theory of Parsing, Translation and Compiling, Prentice Hall Professional Technical Reference, 1973
• 2: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 3: James R. Bell, A new method for determining linear precedence functions for precedence grammars, Communications of the ACM, v.12 n.10, p.567-569, Oct. 1969 [doi>10.1145/363235.363255]
• 4: Franklin L. DeRemer, Simple LR(k) grammars, Communications of the ACM, v.14 n.7, p.453-460, July 1971 [doi>10.1145/362619.362625]
• 5: Robert W. Floyd, Syntactic Analysis and Operator Precedence, Journal of the ACM (JACM), v.10 n.3, p.316-333, July 1963 [doi>10.1145/321172.321179]
• 6: Gray, J.N., and Harrison, M.A. Single pass precedence analysis. IEEE Conf. Rec. 10th Ann. Symp. Switching and Automata Theory, 1969, pp. 106-117.
• 7: David Gries, Compiler Construction for Digital Computers, John Wiley & Sons, Inc., New York, NY, 1971
• 8: Hunt III, H.B,, Szymanski, T.G., and Ullman, J.D. Operations on sparse relations and efficient algcrithms for grammar problems. Proc. 15th Ann. Symp. Switching and Automata Theory, 1974, pp. 127-132.
• 9: David F. Martin, Programming Languages: Boolean matrix methods for the detection of simple precedence grammars, Communications of the ACM, v.11 n.10, p.685-687, Oct. 1968 [doi>10.1145/364096.364114]
• 10: David F. Martin, A Boolean matrix method for the computation of linear precedence functions, Communications of the ACM, v.15 n.6, p.448-454, June 1972 [doi>10.1145/361405.361413]
• 11: Szymanski, T.G., and Ullman, J.D. Evaluating relational expressions with dense and sparse arguments. Proc. 16th Ann. IEEE Symp. Foundations of Comptr. Sci., 1975, pp. 90-97. To appear in Siam. J. Comput.
• 12: Tarjan, R.E. Depth first search and linear graph algorithms. SIAMJ. Comptng. 1, 2 (1972), 146-160.
• 13: Niklaus Wirth , Helmut Weber, EULER: a generalization of ALGOL and it formal definition: Part 1, Communications of the ACM, v.9 n.1, p.13-25, Jan. 1966 [doi>10.1145/365153.365162]

INDEX TERMS

Keywords:
Boolean matrix, SLR grammar, T-canomical precedence relation, Wirth-Weber precedence relation, computational complexity, directed graph, linear precedence function, sparse relation