LL(1) is left-to-right with one look-ahead. We must write a grammar that
uses the first token to decide which rule to use and once it is committed,
there is no turning back.
Let us begin with a simple binary operation. The input is similar to the
following sentence.
table1 = 10 and (table2 = 20 or table3 = 30)
Its grammar will be:
clause := clause and clause
clause := clause or clause
clause := name = value
clause := ( clause )
To have the operator cascaded ( A and B and C ...)
, we
use right recursion (on the rule "clauses").
clause := expr clauses
clauses := logic expr clauses | empty
logic := and | or
(Note to the reader: is it left or right association?)
Let the precedence of "=" be higher than "and" "or". So, first, we "embed"
the operator "=" rule "inside" by creating a new rule for it (the rule
"expr").
expr := name = value
Finally to take care of the highest precedence "(...)" we embed it in the
innest rule.
expr := name = value | ( clause )
The next rule we will consider is the grammar for a list (containing
variable number of elements). This is the example of a list.
(10, 20, 30)
list := ( element )
element := number elements
elements := , number elements | empty
Please note that this grammar does not allow an empty list ()
.
It can be incorporated into the grammar easily.
list := ( member
member := ) | number members
members := , number members ) | empty
end