Error recovering extended weak precedence parser

Abstract

The paper presents a simple but powerful table driven scheme for handling syntatical errors in a weak precedence parser which may be implemented by the use of1 Floyd-Evans productions. The recovery is established on the basis of the well defined concept of synchronizing triples, which are algorithmically obtainable from a WPG. Consequently this scheme may be easily incorporated into any constructor of Floyd-Evans parsers [4], It also meets typical software engineering requirements: primarily it does not degrade the performance of the parser on a correct program text and it gives the possibility of a very compact representation of recovery control tables. The quality of error handling by the scheme is rather high; it never fails and even enables satisfactory recovery from such diverse programming errors as declarations or statements out of order and, for example, the use of the Algol-type statement in a Pascal program text. There are many possibilities for additional improvements of the quality of error handling by the scheme. The use of a fixed sequence of choosing admissible corrections and recoveries, making the scheme so efficient, is difficult to remove without the ùse of much more space and time for the organization of trial parses. The trial parses (backtracking) give the possibility of using: a. the established and more precise methods for organizing parser forward moves [5]; b. the set PWST of proper and safe WST instead of the more restrictive set PDWST of deteiministic WST; c. cost functions for selecting the best correcting symbol [5].

Praca przedstawia prostą metodę neutralizacji i korekcji błędów składniowych w parserze słabego pierwszeństwa, w którym cel redukcji uchwytu identyfikowany jest przy pomocy ograniczonego lewego kontekstu. Podstawowym celem metody nie jest naprawienie całego programu lecz umożliwienie kontynuacji jego analizy i wyprodukowanie maksymalnej ilości użytecznych diagnoz przy minimum szumu (diagnoz błędów wtórnych), Metoda ta jest zorientowana frazowo i pozwala na korygowanie niektórych błędów w oparciu o ich kontekst lokalny lub na neutralizowanie ich skutków w oparciu o kontekst globalny. Procedura neutralizacji błędów jest sterowana tablicowo, a informacja sterująca może być uzyskana algorytmicznie z gramatyki. Formalną bazą dla metody jest dobrze zdefiniowana koncepcja triad synchronizujących. Podano teoretyczną charakteryzację triad oraz algorytmy dla konstrukcji tablic sterujących neutralizacją. Jako istotną część metody neutralizacji podano koncepcję symboli startowych, umożliwiającą proste zorganizowanie pracy parsera w trybie ekspansji (dla kondensacji prawego kontekstu błędu). W końcowej części pracy zilustrowano, na konkretnym przykładzie, jakość przedstawionej metody neutralizacji. Na podkreślenie zasługuje fakt, że metoda ta może być łatwo włączona do dowolnego konstruktora parserów słabego pierwszeństwa, w tym opartego o język produkcji Floyda-Evansa. Spełnia ona też typowe wymagania inżynierii programowania, a w szczególności nie obniża efektywności parsera przy analizie poprawnego programu, i daje możliwość użycia bardzo zwartej reprezentacji tablic sterujących.