Studies on parsing, syntax directed translation and conditional grammars

Abstract

The compilation process for programming langtiages in digital computers essentially consists of the following two steps; i. Translation of the source language, and ii. The generation of machine code-. The first step (translation) unravels the sentences of the source language into an intermediate representation containing the necessary information to proceed with the second step (code generation). In order to carry out this translation, syntax-directed compilers have been constructed using the theory of context-free languages. An account of syntax-directed compiling is available in Cheatham and Saatley [1964],“ for a survey on translator writing systems, see Feldman and (Jries [1968]; a more extensive treatment on the theory of translation is given in Aho and Ullman [l971, 1972a, 1973b], Some of thq important points in favour of syntaxdirected compiling are: Al, Since the method is directed by the syntax of the language, we are assured of the implementation of the language as specified* A2, Syntactic extension can be carried out rather easily A3, The translation to be performed by the compiler can be specified readily,- A4. Systematic procedures can be evolved for syntax error detection, recovery and correction. A5. After a >meta system’ is evolved, it is possible to implement other similar languages easily. In spite of all the above favourable points the following shortcomings do exist. Bl. The algorithms used are, in general slow, particularly for parallel-processing computers. B2. The algorithmic efficiency with respect to some criterion viz., memory required or time required can only be improved at the expense of certain other relevant features; for example, error detecting ability. B3. Invariably, there is a need for adding the semantics to the parser. B4. Syntax-directed error recovery schemes are not available for non-context-free grajmaars (e.g., extensible contextfree grammars). B5 . Ilie language o m lie outside the class of grammars of the ’meta» system. In this dissertation, our study Is motivated towards overcoming some of the above shortoomings. With this in mind, we attempt to solve the follomng closely related problems: i. Construction of efficient precedence parsers, ii. Determining whether a certain language belonging to a certain class of unambiguous context-free languages, such as the class of power languages, can be defined by an LR(k) grammarj this would enable us to obtain an efficient parser for that language. iii. Study of classes of unambiguous grammars larger than the class of LR grammars, which are linear time parsable. iv. Syntax-error detection, recovery, and corrections of extensible context-free languages and context-free languages. V, Studying the relationship between the 'syntaxdirected translation schema' of any two context-free grammars G-^ and having the property that ’covers’ G^. Intuitively speaking, we say that ‘covers* G^' when the ability to parse G^ allows one to parse G^ by a 'table look-up technique'- The type of relationship discussed will be useful when the parsing algorithm we use requires the grammar to be in some specified normal form, vi. A study of a class of grammars which have production rules of context-free typ^ but capable of generating all context-sensitive languagesj this would obviate the shortcoming B5 , where there is a need for r:jGffiantics to be added to the parser. vii. In addition, we also study the efficiency of languages using an information theoretic approach. All these aspects are organized in this dissertation in three parts