Parser generating systems are useful for fast compiler development of various high level programming languages. And the parser generating system with table driven or algorithmic error handling scheme is important not only for the language independent error repair parsers but for the automatic compiler generating system.
Locally least-cost error repair model proposed by Fischer et al. [D&F78, FDM79, FMQ80] is an algorithmic error repair scheme with insertion and deletion cost of terminal symbols given by compiler designer. Eryacc (Error Repair Yacc), error repair parser generating system under UNIX with an efficient algorithm for computing least-cost insertion string for LR-based parser proposed by Choe and Chang[C&C86], is useful for the generation of language-independent parsers. But due to the inefficient algorithm for the computation of prefix strings used in computation of the least-cost insertion string makes the execution time of Eryacc unreasonable in case of the large size programming languages such as Ada, CHILL.
In this thesis, efficient algorithm for the computation of prefix strings is proposed and experimental results are also presented.
