Construction of quasi-optimal Floyd-Evans parsers

Abstract

In the paper we have presented methods and algorithms for the generation of compact and effective Floyd-Evans parsers for a large class o f weak precedence grammars, not necessarily UI. These algorithms make it possible to implement, in an easy way, a constructor o f such parsers. A peculiarity of the Floyd-Evans parser is a homogeneous representation of parser controlling tables, having the form o f a program written in a particular language (we call it the FE-program). The algorithms have been given for the generation of FE-programs shifting the observed symbol, detecting the handle and a goal o f its reduction (using a bounded left context) as well as checking up if the reduction o f the handle has been done in a proper right context. In case o f a shift and a checking FE-program, the presented algorithms give for better results than a classical one, developed by Ichbiach and Morse [6]. (The generated FE-programs are 10—25% shorter. The latter figures are typical for large grammars of programming languages). An important result o f the paper is a method for the construction of an FE-program determining a goal of the handle reduction by the use o f a context, in particular the idea of minimal discriminating left contexts and the algorithm for their direct construction. This idea may be easily generalized to include a right context, it also allows the heuristic determination of a goal o f the handle reduction based on semantic attributes of symbols forming the handle [7, 9]. We should also emphasize that the obtained FE-programs can be improved by the use of methods elaborated for the optimization of a code in a compiler [2]. (There is a possibility for removing the inaccessible statements and shortening the chains of unconditional jumps).

Praca przedstawia metody i algorytmy umożliwiające mechaniczne generowanie zwartych i efektywnych parserów Floyda-Evansa dla obszernej klasy gramatyk słabego pierwszeństwa, niekoniecznie jednoznacznie odwracalnych. Cechą charakterystyczną parsera Floyda-Evansa jest jednolite reprezentowanie informacji sterującej w formie tzw. FE-programu. Podano algorytmy generacji FE-programów przesuwających symbol obserwowany na stos parsera, wyznaczających uchwyt i cel jego redukcji, a także sprawdzających, czy redukcja uchwytu wykonana została we właściwym prawym kontekście. Dla konstrukcji FE-programu przesuwającego podano metodę będącą ulepszoną wersją znanej metody Ichbiacha-Morse’a. Zaproponowana modyfikacja wykorzystuje taką heurystyczną transformację grafu częściowego dla relacji inkluzji zbiorów, która obniża jego koszt (to jest ilość generowanych FE-produkcji typu Z ) poprzez wprowadzenie nowych wierzchołków. Istotnym wynikiem pracy jest metoda konstrukcji FE-programu wyznaczającego cel redukcji uchwytu przy użyciu ograniczonego lewego kontekstu, a w szczególności koncepcja minimalnego kontekstu wyróżniającego i algorytm jego bezpośredniego wyznaczania.