The basic idea of a recursive descent parser is to use the current input symbol to decide which alternative to choose. Grammars which have the property that it is possible to do this are called LL(1) grammars.
First we introduce an end marker , for a given
we define the augmented grammar
where
Now for each nonterminal symbol
we define
![]() |
|
![]() |
For each production
we define the set
which are the set of symbols which indicate
that we are in this alternative.
![]() |
![]() |
|
![]() |
We now say a grammar is LL(1), iff for each pair
with
it is the case
that