Use of Transition Matrices in Compiling

An algorithms is described which constructs
from a suitable BNF grammar an efficient left-right 
recognizer for sentences of the corresponding language.
 The type of recognizer, used in a number of 
compilers, operates with a pushdown stack and with
a transition matrix.  Two examples illustrate how 
such recognizers may be used effectively for other
purposes besides the usual syntax checking.

CACM January, 1968

Gries, D.

transition matrices, compilation, translation,
grammar, context-free language, formal language, 
parsing

4.12 5.23

CA680107 JB February 23, 1978  2:35 PM

249	4	1787
254	4	1787
267	4	1787
272	4	1787
1102	4	1787
1109	4	1787
1139	4	1787
1140	4	1787
1141	4	1787
1188	4	1787
1215	4	1787
1215	4	1787
1223	4	1787
1306	4	1787
1323	4	1787
1358	4	1787
1380	4	1787
1396	4	1787
1464	4	1787
1491	4	1787
1496	4	1787
1498	4	1787
1542	4	1787
1647	4	1787
1665	4	1787
1665	4	1787
1683	4	1787
1683	4	1787
1693	4	1787
1767	4	1787
1767	4	1787
1768	4	1787
1768	4	1787
1781	4	1787
1781	4	1787
1781	4	1787
1781	4	1787
1781	4	1787
1781	4	1787
1781	4	1787
1787	4	1787
1787	4	1787
1787	4	1787
1787	4	1787
1787	4	1787
1787	4	1787
1787	4	1787
1787	4	1787
1787	4	1787
1792	4	1787
1824	4	1787
1825	4	1787
1836	4	1787
1836	4	1787
1860	4	1787
1861	4	1787
1945	4	1787
1945	4	1787
1945	4	1787
1945	4	1787
1949	4	1787
1988	4	1787
1989	4	1787
321	4	1787
364	4	1787
2015	4	1787
2059	4	1787
2060	4	1787
2061	4	1787
2061	4	1787
2082	4	1787
2091	4	1787
2110	4	1787
2112	4	1787
2126	4	1787
2127	4	1787
2152	4	1787
2179	4	1787
2187	4	1787
2252	4	1787
2317	4	1787
2340	4	1787
2356	4	1787
2534	4	1787
405	4	1787
2541	4	1787
2545	4	1787
2546	4	1787
435	4	1787
437	4	1787
438	4	1787
463	4	1787
483	4	1787
491	4	1787
2603	4	1787
2603	4	1787
2698	4	1787
2698	4	1787
2698	4	1787
2708	4	1787
2732	4	1787
2733	4	1787
2733	4	1787
2820	4	1787
2824	4	1787
2982	4	1787
2986	4	1787
560	4	1787
583	4	1787
3045	4	1787
3073	4	1787
3073	4	1787
3093	4	1787
3155	4	1787
627	4	1787
631	4	1787
632	4	1787
642	4	1787
644	4	1787
653	4	1787
680	4	1787
761	4	1787
762	4	1787
763	4	1787
763	4	1787
123	4	1787
140	4	1787
919	4	1787
989	4	1787
196	5	1787
1141	5	1787
1215	5	1787
224	5	1787
1491	5	1787
1496	5	1787
1781	5	1787
1787	5	1787
1787	5	1787
1787	5	1787
2534	5	1787
2708	5	1787
763	5	1787
799	5	1787
830	6	1787
123	6	1787
196	6	1787
919	6	1787
990	6	1787
1007	6	1787
1046	6	1787
1131	6	1787
1139	6	1787
1140	6	1787
1149	6	1787
1198	6	1787
1215	6	1787
1223	6	1787
1265	6	1787
1303	6	1787
1323	6	1787
1358	6	1787
1366	6	1787
1421	6	1787
1460	6	1787
1462	6	1787
1463	6	1787
1467	6	1787
1468	6	1787
1477	6	1787
1477	6	1787
1491	6	1787
1491	6	1787
1496	6	1787
1531	6	1787
1535	6	1787
1565	6	1787
1601	6	1787
1602	6	1787
1613	6	1787
1614	6	1787
1626	6	1787
1641	6	1787
1787	6	1787
1787	6	1787
1787	6	1787
1788	6	1787
205	6	1787
224	6	1787
249	6	1787
288	6	1787
1959	6	1787
1973	6	1787
316	6	1787
381	6	1787
398	6	1787
2111	6	1787
2111	6	1787
11	6	1787
2182	6	1787
2534	6	1787
2556	6	1787
404	6	1787
410	6	1787
463	6	1787
464	6	1787
483	6	1787
3184	6	1787
3188	6	1787
584	6	1787
600	6	1787
680	6	1787
680	6	1787
691	6	1787
763	6	1787
799	6	1787
799	6	1787