LL(1) Grammars and Analysers
Since this course is not solely concerned with syntax analysis, a choice has had to be made amongst a large number of possible methods. We have chosen to present the two methods which seem to be the most fundamental in theoretical terms. The choice was, o
- PDF / 1,768,354 Bytes
- 28 Pages / 439.37 x 666.142 pts Page_size
- 100 Downloads / 241 Views
I - INTRODUCTIONSince this course is not solely concerned with syntax analysis, a choice has had to be made amongst a large number of possible methods. We have chosen to present the two methods which seem to be the most fundamental in theoretical terms. The choice was, of course, much easier amongst top-down methods, of which there are few. The LL(l) techniques described in this chapter were discovered by Foster [Foster 68J and received a theoretical treatment in [Knuth 71J. The method is topdown, deterministic with one character of look-ahead.
Before going into details of the method, we should consider the context in which it will apply. Why are compiler-writers so interested in syntax? It is certainly not true that, in a given compiler, the syntactic part is that which requires the most work. In fact, the pratical compiler writer should be able to produce his compiler without even bothering much about the mechanics of syntax analysis. He is more interested in using the syntax as a framework on which to hang semantics, since this gives the overall structure of the compiler. Essentially, for the compiler writer, Backus normal form is a programming language.
This discussion shows us that, to be useful, a syntax analysis method must be automated; the user merely has to type his grammar and some program prepares the appropriate analyser, which must also be efficient and allow easy interaction F. L. Bauer et al., Compiler Construction © Springer-Verlag Berlin Heidelberg 1974
58
with the semantics. This last point means that the method must be deterministic, but we will come back to that with the examples. We start with a non-deterministic method from long bygone days (a little over ten years ago), and then look at the problem of making it deterministic.
1.1 - Predictive Analysis Consider the following grammar, which describes an ALGOL block Block
7
begin DL
DL
7
D
D
DL
SL
7
S
S
SL
SL end
We will analyse the following program (considering declarations and instructions to be non-separable units for the time being) begin D ; D ; S ; S end
59
Analysis proceeds by comparing targets with the source text. The first target is the axiom of the grammar, and new targets are produced by replacing left-most terminal symbols by their possible expansions. Thoses targets which do not correspond to the text are rejected, leaving the others for further comparison, and so on. The successive states of the analysis of the given program are drawn up in the form of a table:
Text
Targets Block
1.
2.
begi n DL ; SL end
-
3.
DL
4.
D ; SL end DL ; SL end
D;
;
;
Send
D; D; S
;
D; D; S ;
Send Send -
; D ; S ; Send
D; S
;
;
SL end SL end
Send -
Send S ; SL -end D ; SL end DL ; SL end
D; S
;
Send
DL
-
-
-
-
-
8.
; ;
begin D ; D ; S
;
DL
6.
D;
Send
SL end SL end
;
7.
-
;
-
5. ;
SL end
begin D ; D ; S
DL
;
SL end SL end
-
;
S ; Send
-
and so on. State 8. is the same as state 5., except that some of the source text has been analysed between times. Resuming the rules of th
Data Loading...
