| dc.description.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 | |
