Operations on sparse relations and efficient algorithms for grammar problems
Harry B. Hunt, Thomas G. Szymanski, Jeffrey David Ullman · 1974
various operations on graphs, matrices, or relations can be executed more quickly when the arguments are "sparse" (i.e., if e ≪ ≪ v2where e is the number of edges and v the number of vertices) than when they are "dense" (i.e., e ≈ v2). Fast algorithms are presented for a large class of operations on sparse relations. These algorithms are used to produce the best known methods for solving a variety of grammar problems relevant to parsing. Letting the size n of a grammar be the sum of the lengths of all of its productions, we discuss the following - (1) finding linear precedence functions in 0(n) steps; (2) computing precedence relations in 0(n2) steps; (3) LR(0), SLR(1), and LL(1) testing in 0(n2) steps; and (4) polynomial algorithms for LL(k), SLR(k), and LR(k) testing, for fixed k.