A Study of Error Correction and Recovery for SLR(k) Parsers

概要

論文の詳細を見る
We have proposed the practical error correcting and recovering algorithms for the SLR(k) parsers. First, we define the i-order valid pair for a LR(0) table T and a k-termlnal string w. Let (T_0...T_n, a_j...a_m) be an error configuration. If (T_n,a_h-.a_<h+k-1>,) is the i-order valid pair for someβεΣ^i, we correct the above configuration to (T_0 . . ..T_n,βa_h...a_m). If we extend β in the definition above to βε(N∪Σ)^i, then we can make error recovery in the same way. Most useful is the case i=0 or 1. In these cases , the i-order valid pairs can be stored in the SLR(k) parsing table. The SLR(k) parser with these algorithms can parse and correct an input with 1ength n within O(n) time.We have shown by simulation that the algorithm corrects60-800% of the programs with errors.
一般社団法人情報処理学会の論文