Comparative analysis of error detection and recovery in syntax directed compilers

Abstract

A theoretical and practical analysis for error detection and recovery are presented in this dissertation. This comparative analysis covers LL(1) and SLR(1) recovery algorithms with and without backtracking. Error detection and recovery methods of simple precedence parser, PL/C, and PL/1 are also analyzed and compared. Local and global recovery methods have been associated with each parsing algorithm. Local algorithms replace, delete, or insert symbols in the input stream. Global recovery changes the stack, the input, or both in order to recover. A recovery methodology is also presented for LL(1) parsing algorithm. This method allows the recovery to take place only if the input symbol is guaranteed to be shifted by the parser. In practical comparison, 800 psuedo-programs are submitted to each algorithm with errors ranging from one to eighty. The output of each compilation process is collected. The evaluation of this output has been illustrated in both quantitative and ranking analysis. The performance of each algorithm has been presented using six criteria: The number of discarded symbols, the local recovery activities, the stack elements lost per recovery, the number of symbols discarded per recovery, the cost of recovery, and the number of messages issued to the programmer. Cost and number of discarded symbols are given special consideration because of their importance on comparing these algorithms.