Warshall算法之证明及若干应用

WARSHALL ALGORITHM:A NEW PROOF ON ITS CORRECTNESS AND SOME OF ITS APPLICATIONS

本文给出了 Warshall 算法的一个正确性证明,不仅简明,而且极有利于对 Warshall 算法本身的理解。对于自动编译程序构造中的基本问题之一,求非终极符所对应的终极符串的带头符(FIRST)和后继符(FOLLOW)集,本文还介绍了基于 Warshall 算法的计算办法。

A correctness proof on Warshall algorithm,not only simple and cleer,but alsovery helpful for understanding of the algorithm itself,is presented.In addition,acomputing method based on Warshall algorithm is suggested to find FIRST & FOLLOWfunctions of a terminal set corresponding to its nonterminals,one of the fundamentalproblems in automatic construction of compiler.