A Boolean Matrix Method for the Computation
of Linear Precedence Functions

A modified version of Bell's Boolean matrix
method for the computation of linear precedence 
functions associated with a conflict-free matrix of
precedence relations is given.  This algorithm not 
only detects when the precedence functions do not  exist,
but also provides an indication of why they 
do not exist, so that corrective action can be taken
if possible.  Necessary and sufficient conditions 
for the existence of precedence functions are given.
 The use of Boolean matrices to prove the existence 
of precedence functions associated with classes of conflict-free
grammars is illustrated through an example.

CACM June, 1972

Martin, D. F.

precedence grammars, context-free parsing

4.12

CA720605 JB January 30, 1978  4:28 PM

1542	4	2340
1683	4	2340
1693	4	2340
1781	4	2340
1787	4	2340
1836	4	2340
1836	4	2340
1945	4	2340
2060	4	2340
2061	4	2340
2082	4	2340
2091	4	2340
2152	4	2340
2179	4	2340
2221	4	2340
2340	4	2340
2340	4	2340
2340	4	2340
2340	4	2340
2356	4	2340
2546	4	2340
2603	4	2340
2698	4	2340
2708	4	2340
2824	4	2340
2824	4	2340
2982	4	2340
2982	4	2340
2986	4	2340
2986	4	2340
2986	4	2340
3045	4	2340
3093	4	2340
1191	5	2340
1491	5	2340
1683	5	2340
1836	5	2340
2340	5	2340
2340	5	2340
2340	5	2340
2824	5	2340
2982	5	2340
2986	5	2340
1491	6	2340
1491	6	2340
1491	6	2340
1683	6	2340
1683	6	2340
1836	6	2340
1836	6	2340
2179	6	2340
2340	6	2340
2340	6	2340
2340	6	2340