LL1 Parsing

                                    @ supposed to represent nothing at all
<block>   ::=  "{" <st-seq> "}"

<st-seq>  ::=  <stmt> <rest-ss>
            |  @

<rest-ss> ::=  ";" <st-seq>
            |  @

<stmt>    ::=  <assign>
            |  <while>
            |  <print>
            |  <block>

<assign>  ::=  identifier ":=" <expr>

<while>   ::=  "while" <expr> "do" <stmt>

<print>   ::=  "print" <expr>

<value>   ::=  number
            |  identifier
            |  "(" <expr> ")"

<prio-1>  ::=  <value> <rest-p1>

<rest-p1> ::=  "*" <prio-1>
            |  "/" <prio-1>
            |  @

<prio-2>  ::=  <prio-1> <rest-p2>

<rest-p2> ::=  "+" <prio-2>
            |  "-" <prio-2>
            |  @

<prio-3>  ::=  <prio-2> <rest-p3>

<rest-p3> ::=  "=" <prio-3>
            |  "<" <prio-3>
            |  @

<expr>    ::=  <prio-3>


nullable(sequence A B C)  = nullable(A) /\ nullable(B) /\ nullable(C)
nullable(choice A B C)    = nullable(A) \/ nullable(B) \/ nullable(C)
nullable(terminal symbol) = false
nullable(non-terminal)    = nullable(its definition)
nullable(@)               = true

nullable(<block>)   = nullable("{")
                    = false
nullable(<st-seq>)  = nullable(something | @)
                    = true
nullable(<rest-ss>) = nullable(something | @)
                    = true
nummable(<assign>)  = nullable(identifier)
                    = false
nummable(<while>)   = nullable("while")
                    = false
nummable(<print>)   = nullable("print")
                    = false
nullable(<stmt>)    = nullable(<assign>) \/ nullable(<while>) \/ nullable(<print>) \/ nullable(<block>)
                    = false
nullable(<prio-3>   = nullable(<value>) /\ nullable(<rest-p3>)
                    = false
nullable(<rest-p3>) = nullable(something | @)
                    = true
nullable(<prio-2>   = nullable(<prio-2>) /\ nullable(<rest-p2>)
                    = false
nullable(<rest-p2>) = nullable(something | @)
                    = true
nullable(<prio-1>   = nullable(<prio-2>) /\ nullable(<rest-p1>)
                    = false
nullable(<rest-p1>) = nullable(something | @)
                    = true
nullable(<expr>)    = nullable(<prio-1>)
                    = false

                                 + represents union, * represents intersection

first(@)         = { }
first(terminal symbol a)
                 = { a }
first(non-terminal symbol)
                 = first(its definition)
first(A | B | C) = first(A) + first(B) + first(C)
first(A B C)     = first(A) if not nullable(A)
                   first(A) + first(B) if nullable(A) /\ not nullable(B)
                   first(A) + first(B) if nullable(A) /\ not nullable(B)
                   first(A) + first(B) + first(C) if nullable(A) /\ nullable(B)

first(<block>)   = { "{" }
first(<st-seq>)  = first(<stmt>)
                 = { identifier, "while", "print", "{" }
first(<rest-ss>) = { ";" }
first(<stmt>)    = first(<assign>) + first(<while>) + first(<print>) + first(<block>)
                 = { identifier, "while", "print", "{" }
first(<assign>)  = { identifier }
first(<while>)   = { "while" }
first(<print>)   = { "print" }
first(<value>)   = { number, identifer, "(" }
first(<prio-1>)  = first(value)
                 = { number, identifer, "(" }
first(<rest-p1>) = { "*", "/" }
first(<prio-2>)  = first(<prio-1>)
                 = { number, identifer, "(" }
first(<rest-p2>) = { "+", "-" }
first(<prio-3>)  = first(<prio-2>)
                 = { number, identifer, "(" }
first(<rest-p3>) = { "=", "<" }
first(<expr>)    = first(<prio-3>)
                 = { number, identifer, "(" }


in a rule
   A ::= B
       | C
       | D

   indicate(B) = if B not nullable
                    then first(B)
                    else first(B) + follow(A)

   indicate(C) = if B not nullable
                    then first(C)
                    else first(C) + follow(A)

   indicate(D) = if B not nullable
                    then first(D)
                    else first(D) + follow(A)

indicate() is not just for a particular piece of grammar, it is different depending
on where that piece of grammar appears, which rule it is an option for.


follow sets (only for non-terminal symbols) are accumulated over the entire grammar

   whenever <A> appears inside but not at the end of a sequence in a rule
      <N> ::= ...
            | P Q R <A> X Y Z
      follow(<A>) includes first(X Y Z)
      and if nullable(X Y Z) it also includes follow(<N>)

   whenever <A> appears at the end of a rule
      <N> ::= ...
            | P Q R <A> 
      follow(<A>) includes follow(<N>)


What we get is

follow(<block>)   = { ";", "}", eof }
follow(<st-seq>)  = { "}" }
follow(<rest-ss>) = { "}" }
follow(<stmt>)    = { ";", "}" }
follow(<assign>)  = { ";", "}" }
follow(<while>)   = { ";", "}" }
follow(<print>)   = { ";", "}" }
follow(<value>)   = { "*", "/", "+", "-", "=", "<", ")", ";", "}", "do" }
follow(<prio-1>)  = { "+", "-", "=", "<", ")", ";", "}", "do" }
follow(<rest-p1>) = { "+", "-", "=", "<", ")", ";", "}", "do" }
follow(<prio-2>)  = { "=", "<", ")", ";", "}", "do" }
follow(<rest-p2>) = { "=", "<", ")", ";", "}", "do" }
follow(<prio-3>)  = { ")", ";", "}", "do" }
follow(<rest-p3>) = { ")", ";", "}", "do" }
follow(<expr>)    = { ")", ";", "}", "do" }


The only non-trivial indicates are

<st-seq>  ::=  <stmt> <rest-ss>     { identifier, "while", "print", "{" }
            |  @                    { "}" }

<rest-ss> ::=  ";" <st-seq>         { ";" }
            |  @                    { "}" }

<rest-p1> ::=  "*" <prio-1>         { "*" }
            |  "/" <prio-1>         { "/" }
            |  @                    { "+", "-", "=", "<", ")", ";", "}", "do" }

<rest-p2> ::=  "+" <prio-2>         { "+" }
            |  "-" <prio-2>         { "-" }
            |  @                    { "=", "<", ")", ";", "}", "do" }

<rest-p3> ::=  "=" <prio-3>         { "=" }
            |  "<" <prio-3>         { "<" }
            |  @                    { ")", ";", "}", "do" }

which means that all of the grammar's indicate sets are disjoint so LL1 will work.


parse a sequence
                     A ::= B C D
   bt = parse(B)
   ct = parse(C)
   dt = parse(D)
   return new node ("A", bt, ct, dt)


parse a choice                  * represents intersection
                     A ::= B
                         | C
                         | D

   look at next symbol s
   if s in indicate(B)
      t = parse(B)
   else if s in indicate(C)
      t = parse(C)
   else if s in indicate(D)
      t = parse(D)
   else
      syntax error s seen when one of indicate(B) + indicate(C) + indicate(D) expected
   return new node ("A", t)

   obviously the choice can not be made unless indicate(B) * indicate(C) * indicate(D) = { }


parse a terminal symbol, A, for example "while" or identifier

   read next symbol s
   if s = A
     return new node("symbol", s)
   else
     syntax error s seen when A expected


parse a non-terminal symbol, <A>

   return parse(its definition)


This style of definition for arithmetic

    <expr>  ::=  <value> <rest-expr>
    <rest-expr> ::=  "-" <expr>
                  |  @

would look more natural as

    <expr>  ::=  <value> { "-" <expr> }

where curly brackets mean their content is optional

which makes it easier to see a big problem.
It builds the wrong tree.

    8 - 4 - 2  only fits if 8 is accepted as the <value> and 4 - 2 is the other <expr>
                  (4 - 2 fits <expr> if 4 is the value and 2 is the other <expr>
                   2 fits <expr> if 2 is the <value> and the optional part is absent)

That would prodcue a subtract note with 8 on the left and (4 - 2)'s tree on the right,
forcing right-to-left evaluation.

What we really want is

    <expr> ::= { <expr> "-" } <value>

which would be written in the simpler style as

    <expr> ::= <expr> "-" <value>
             | <value>

Which would be programmed like this:

    parse_expr():
      S = look ahead at next symbol
      if S in indicate set for first option
        L = parse_expr()
        S = consume next symbol
        if S != "-"
          sytax error
        R = parse_value()
        return new node("-", L, R)
      else if S in indicate set for second option
        return parse_value()
      else
        syntax error

Not only has that got an infinite recursion in the first case, but also the indicate
sets for the two options will be identical.

In this case, and many like it, the solution is not to say that the grammar isn't LL1
therefore we must give up on LL1 and go with something else, as many people insist.

There is a very simple solution. Replace the recursion with a loop.

    parse_expr()
      L = parse_value()
      S = look ahead at next symbol
      while S = "-"
        consume next symbol (the -)
        R = parse_value()
        L = new node("-", L, R)
      return L

That is, strictly speaking LALR1 (close to LR1, the real bottom up method) but it fits
perfectly in with the much better structured LL1 framework.