| dc.description.abstract | Compiler Generators have become well-established tools in the production of a compiler. In general, a compiler generator uses a specification of a programming language at an abstract level as input and outputs the code for the compiler.
While LR, SLR, and LALR grammars are generally used for the specification of the syntax of a programming language, attribute grammars and affix grammars are commonly used to specify the semantics of the language.
The compilers generated by many compiler generators require scanning the input (or a parse tree generated from the input) more than once. Such multi-pass compilers based on attribute grammars generally require more space and time compared to their one-pass counterparts.
Producing one-pass compilers based on LR parsing of affix grammars was first introduced by Watt. A different approach suggested by Fohlmann has the advantage of both simplicity and the ability to parse a larger class of grammars than those covered by Watt’s technique.
In this thesis, Fohlmann’s method has been adapted for implementation. The basic idea is to augment the moves of the LR(K) automaton for the grammar to take into account affix computations. The problems addressed and the algorithms developed are summarized below. a. Testing an input affix grammar for well-formedness.
b. Implementing a test (the ALR(k) test) to check whether a given affix grammar is deterministically parsable using our technique.
The test, originally given by Fohlmann, has been implemented with adaptations to make it suitable for application on the LR(k) automaton for the grammar.
Efficient data structures (optimized for both time and space) have been designed.
c. Once the input affix grammar passes the test in (b), it can be used to generate a compiler.
A compiler generator has been designed, which includes the standard components—namely the lexer and the parsing table.
Additionally, facilities to generate semantic actions have been incorporated.
An existing skeleton facility (consisting of an SLR(1) parser generator) has been enhanced for this purpose.
The system designed has been successfully used to generate the front-end of a compiler for a Pascal subset, the grammar for which contains about sixty productions.
Based on experience with the system, the merits and disadvantages of the scheme are discussed.
Space considerations are seen to be critical during the testing phase (i.e., during the ALR(k) test).
d. A new algorithm, which is an alternative to Fohlmann’s ALR(k) test, is proposed.
This algorithm has a time complexity comparable to that of Fohlmann’s, while its space requirements are much less. | |
