Syntactic Analysis
******************

Most of the grammars we are interested in are context free (and not regular).  This chapter presents the most classical techniques to parse (some) context free grammars.

Predictive Analysis
===================

Intuition
---------

     S ::= if E then S
         | begin S L
         | print string

     L ::= end
         | ; S L

     E ::= bool

What striking property has this grammar ?  Think about parsing the following input (notice that ; is a separator (like in Pascal), not end of instruction (C).  Experience shows us that less programming errors are made when using c-like syntax, than separator. All those psychological aspects should be well considered before making the syntax of a language.):

     if true then
     begin
       print "Success";
       print "Succès"
     end

We always know in which case (rule) just by looking at the next word, because every rule begins with a unique token.

     enum token_e token;

     void
     S (void)
     {
       switch (token)
       {
        case IF:
          accept (IF);  E ();  accept (THEN);  S ();
          break;
        case BEGIN:
          accept (BEGIN);  S ();  L ();
          break;
        case PRINT:
          accept (PRINT);  accept (STRING);
          break;
        default:
          error (token);
       }
     }

C++ provides even more flexibility:

     template <int k> class LL_k
     {
        private:
          vector<token>   tokens(k);
          exp             absyn;

             exp accept();
        public:
             exp parse();
     }

where accept() can accept the vector of token and give an exp emptying the vector, and parse() chooses the rule corresponding to the list of token, if no rule matches or if there is an ambiguity the next token is added to tokens and then retry other rules...

This method is called LL(1): Left to right, Leftmost Derivation, 1 look ahead token (we can use k tokens, in wich case it is called LL(k))

Complications
-------------

Does it always work when using

     S ::= I
         | begin S L
         | print string

     I ::= if E then S

     L ::= end
         | ; S L

     E ::= bool

and for

     S ::= I
         | begin S L
         | print string

     I ::= I1 I2

     I1 ::=

     I2 ::= if E then S

     L ::= end
         | ; S L

     E ::= bool

What happens if we try with our non-ambiguous arithmetics expression grammar

     E ::= E + T      T ::= T * F       F ::= num
        |  E - T          | T / F           | ( E )
        |  T              | F

     void
     E (void)
     {
       switch (token)
       {
        case ???:
          E () ; accept (PLUS) ; F () ;
          break;

        etc.
       }
     }

Formalization
-------------

Calculating FIRST, we need to know the NULLABLE tokens and the FOLLOWING ones (we will use the word CANCALABLE and FOLLOW to simplify reading).

     Algorithm upon prodution rules as A ::= A1 A2 .. An

     All is initialized to empty
     For every terminal A
       FIRST (A) := {A}
     Repeat
       For every rule A ::= A1 A2 .. An
         If every Ai are NULLABLE or i = 0
         Then A is NULLABLE
         For every i between 1 and n
           If A1 .. Ai-1 are NULLABLE
           Then add Ai in FIRST(A)
           If Ai+1 .. An are NULLABLE
           Then add FOLLOW(A) to FOLLOW(Ai)
           For every j between i+1 and n
             If Ai+1 .. Aj-1 are NULLABLE
             Then add FOLLOW(Aj) to FOLLOW(Ai)
           For end j;
         For end i;
       For end rule;
     Until FIRST FOLLOW and NULLABLE don't change

Try with the following grammar

     A ::= B
         | a

     B ::= b
         |

     C ::= A B C
         | c

we find

            |Ann.    |First   |Follow
     -------+--------+--------+-----
     A      |oui     |ab      |abc
     -------+--------+--------+-----
     B      |oui     |b       |abc
     -------+--------+--------+-----
     C      |non     |abc     |(vide)

Writing functions (which are switch on current token), needs, for every function, knowing what to do for every token.  More clearly (some people needs more explaination I feel it) we need an array (non terminal/terminal) wich contain rule to execute.("If it look like an automaton, if it tastes like an automaton, if it sounds like an automaton, it surely can be used as an automaton" B. Franklin the mad with the thunder bolt, no it's not a citation but it is just to "open your eyes, open your mind[...]  nescafee" sorry someone possessed my poor brain.)

For instance, it is clear that the rule A ::= a has to be written in the cell (A, a).  C ::= ABC obviously has to be put in (C, a), but intuition also reveals that since A is nullable, it has to be put in (C, b) too because b is member of FIRST(B).  It is easy to define FIRST(ABC) and understand that C ::= ABC is to be written in {C} x FIRST(ABC).

What's to be done with B ::=?  Just think of parsing ac with C being the axiom: you want to use C -> ABC, and have B disappear before the C which will become c.  And in fact, since FIRST(C) is {a, b, c}, any B before a C should be ready to disappear: put it in (B, a), (B, b), (B, c).

What's to be done of A ::= B?  Imagine we analyse this text: c, c as an axiom. According to (C, c), let's apply C ::= ABC. We treat A with cas look-ahead.  We feel that Amust become B, it's the only way for him to erase himself. We choose the rule B, with c as look-ahead.  As for A, B must erase:B ::= , i.e we now are at A.BC with c as look-ahead. B erases: AB.C with c as look-ahead, we have exactly what we want!!We are the champions...  Hence, A ::= B dans FOLLOW(A), i.e., (A, a), (A, b) et (A, c).

The algorithm is:

     A ::= A1 .. An

 1. If a is member of FIRST(A1 .. An), put the rule in (A, a).

 2. IF A1..An is nullable,put the rule in every (A, b) with b in FOLLOW(A)

Dans notre exemple, on obtient :

             a               b               c
     -------------------------------------------------
     A       A ::= a         A ::= B
             A ::= B         A ::= B         A ::= B
     -------------------------------------------------
     B                       B ::= b
             B ::=           B ::=           B ::=
     -------------------------------------------------
     C       C ::= ABC       C ::= ABC       C ::= ABC & C ::= c

Where rules selected by rule (1) are on first line, and the other selected by (2) on the second line.

We notice that this grammar gives many choice for a rule: we can not analyse it with this method. Analysable grammar with this method are called LL(1) (like the parsing method of the same name, it means an LL(1) grammar can be parsed by an LL(1) parser).Generalysing for LL(k), only need to construct FIRST with k-uples of terminals...

Actually it's even worse than this: this grammar is ambiguous.  Prove it, and exhibit a short word which can be parsed in an infinite number of ways.

Grammar Massage
---------------

When trying to build a recursive descent parser for arithmetics, we find several problems.

     E ::= E + T      T ::= T * F       F ::= num
        |  E - T          | T / F           | ( E )
        |  T              | F

First of all, this grammar is left-recursive:

     E ::= E - T
        |  T

which means that the routine which parses E's will look like:

     void
     E ()
     {
       swith (lookahead)
       {
         case ???:
            E (); accept (tok_minus); T (); break;
         case ???:
            T (); break;
       }
     }

Obviously we enter an infinite loop (E calls itself) as soon as the first case is selected.

A grammar which includes a left recursive rule cannot be LL.  So we have to make it right recursive :

     E ::= T - E
        |  T

Of course this implies that our ``reading'' is incorrect (here we read - as if it were right associative), and we will have to adjust our semantic actions so that the proper order is respected.

We then face a second problem: how can we decide between E ::= T - E, and E ::= T?  They all start the same way, i.e., we have:

     void
     E ()
     {
       swith (lookahead)
       {
         case FIRST (T):
            E (); accept (tok_minus); T (); break;
         case FIRST (T):
            T (); break;
       }
     }

the two case's are equal!

This issue is similar to the famous if-then-else:

     I ::= if E then I
         | if E then I else I

We obviously can't make any switch that make us able to have this rule done correctly.  Answer is simple: left factoring.

     I ::= if E then I ELSE-OPT

     ELSE-OPT ::= else I
               |

In the case of our arithmetical expressions, we'd use:

     E ::= T E'

     E' ::= - T E'
          |

Application to Arithmetical Expressions
---------------------------------------

First, the grammar must not be left recursive:

     E ::= T - E
        |  T

     T ::= F / T
         | F

     F ::= num
         | ( E )

then we left factor it:

     1. E  ::= T E'

     2. E' ::= - E
     3.      |

     4. T  ::= F T'

     5. T' ::= / T
     6.      |

     7. F  ::= num
     8.      | ( E )

E and E' are mutually recursive.  E' can be rewritten to be independent from E, and similarly for T':

     0. S  ::= E $

     1. E  ::= T E'

     2. E' ::= - T E'
     3.      |

     4. T  ::= F T'

     5. T' ::= / F T'
     6.      |

     7. F  ::= num
     8.      | ( E )

last, we need a means to know we reached the end of a file.  We will use $ to denote the end of file, and add one rule:

     0. S  ::= E $

Then you get:

        |  Null.   First    Follow
     ---+---------------------------
     S  |   n      ( N
     E  |   n      ( N      ) $
     E' |   o      -        ) $
     T  |   n      ( N      ) $ -
     T' |   o      /        ) $ -
     F  |   n      ( N      ) $ - /

hence

        |   (   )   -   /   N   $
     ---+-------------------------
     S  |   0               0
     E  |   1               1
     E' |       3   2           3
     T  |   4               4
     T' |       6   6   5       6
     F  |   8               7

that can be make trivially by:

     exp_t *
     p_E (FILE *s)
     {
       exp_t *t1, *t2;

       switch (token)
         {
         case tok_num:
           t1 = p_T (s);
           t2 = p_Ep (s);
           if (t2)
             return exp_bin_new (op_minus, t1, t2);
           else
             return t1;
           break;

         default:
           assert (0);
         }
     }

     exp_t *
     p_Ep (FILE *s)
     {
       exp_t *t1, *t2;

       switch (token)
         {
         case tok_minus:
           eat (s, tok_minus);
           t1 = p_T (s);
           t2 = p_Ep (s);
           if (t2)
             return exp_bin_new (op_minus, t1, t2);
           else
             return t1;
           break;

         case tok_eof:
           break;

         default:
           assert (0);
         }
     }

Easy, isn't it?  But completly false: operators are considered right associative...  Trying to reorder things in the parsing is tricky:

     exp_t *
     p_E (FILE *s)
     {
       exp_t *t1;

       switch (token)
         {
         case tok_num:
           t1 = p_T (s);
           return p_Ep (s, t1);
           break;

         default:
           assert (0);
         }
     }

     exp_t *
     p_Ep (FILE *s, exp_t *pred)
     {
       exp_t *t1, *t2;

       switch (token)
         {
         case tok_minus:
           eat (s, tok_minus);
           t1 = p_T (s);
           t2 = exp_bin_new (op_minus, pred, t1);
           return p_Ep (s, t2);
           break;

         case tok_eof:
           return pred;
           break;

         default:
           assert (0);
         }
     }

Unrecursiving that, allows us to obtain something simpler and more efficient:

     exp_t *
     p_exp (void)
     {
       exp_t *res = p_term ();

       while (token == tok_plus || token == tok_minus)
         {
           if (token == tok_plus)
             {
               eat (tok_plus);
               res = exp_bin_new (op_plus, res, p_term ());
             }
           else /* token == tok_minus */
             {
               eat (tok_minus);
               res = exp_bin_new (op_minus, res, p_term ());
             }
         }

       return res;
     }

LR Analysis
===========

LR(0)
-----

     0. S ::= E $
     1. E ::= ( L )
     2.     | x
     3. L ::= L , E
     4.     | E

Try to parse (x, (x, x, x)) by hand.

Build the automaton.

SLR
---

Try to build the LR(0) automaton for

     1. E ::= x + E
     2.     | x

        |  x    +    $   |  E
     ---+----------------+----
      1 | s3             |  2
      2 |            acc |
      3 | r2  s4/r2  r2  |
      4 | s3             |  5
      5 | r1   r1    r1  |

there is a conflict: this grammar is not LR(0).

What is the meaning of (x, 3) = r2?  It says ``when I want to reduce to an E and the next token is x, reduce to E''.  But it is impossible to have an x after an E. Why?

Simply because x does not belong to FOLLOW(E).

To improve our table, we will put the reduction only when the token belongs to FOLLOW of the nonterminal being reduced.  Since FOLLOW(E) = {$} one gets:

        |  x    +    $   |  E
     ---+----------------+----
      1 | s3             |  2
      2 |            acc |
      3 |       s4   r2  |
      4 | s3             |  5
      5 |            r1  |

LR(1)
-----

LR(k)
-----

The book by Robin Hunter, "Compilers", 5.2, says that any LR(k) language, k > 1, is also a LR(1) language, and even a LR(0) language if each sentence is followed by an end marker.

However, there are for example LR(2) grammars which are not LR(1), say

     %token a, t
     %%
     S:  F ',' S
       | F

     F:  a L

     L:  t
       | t ',' L

which in Bison produces the error contains 1 shift/reduce conflict.

The above grammar can be transformed into a LR(1):

     S: a t F

     F: /* empty */
       | ',' I F

     I:  a t
       | t

(Or so loc.cit. says.)

So Bison is just LR(1) or LALR(1) then, with no grammar transformation capabilities. -- Loc.cit. suggests to first try say the simpler LALR(1) algorithm, and in the cases it fails, to use the LR(1) algorithm; but it does not cite an example of a LR(1) grammar which isn't LALR(1), so I cannot check if Bison does that, or is simply LALR(1).

Tunning a Yacc Grammar
======================

First thing first, always use Bison, drop Yacc dead.  Secondly, when Bison complains because of conflicts, use bison -v so that it dumps a file with a verbose description of the grammar and its possible problems.

If this is not enough, reduce the grammar to the core of the problem. Also, forget about all the problems of typing, i.e., keep only tokens. It is a pity that there are no option --check that does this, hence you will probably need to strip the actions from the grammar.

Binary expressions
------------------

Of course, you should use precedence to help Yacc.  It is tempting to write

     %token INT PLUS TIMES
     %left PLUS
     %left TIMES
     %%
     exp: INT
        | exp op exp;
     op: PLUS | TIMES;

but you get 2 shift/reduce conflicts.  In fact, you don't even need two operators to get conflicts:

     %token INT PLUS
     %left PLUS
     %%
     exp: INT
        | exp op exp;
     op: PLUS ;

gives 1 shift/reduce conflict:

     exp  ->  exp . op exp   (rule 2)
     exp  ->  exp op exp .   (rule 2)

     PLUS      shift, and go to state 3
     PLUS      [reduce using rule 2 (exp)]
     $default  reduce using rule 2 (exp)

     op        go to state 4

if you recall the way the associativity and the precedence are used to build the automaton, you should recall that we were are actually comparing a rule against a token, not just two tokens.  Here, the associativity directive helps to compare the rule op: PLUS; against the token PLUS, which never happens!  The problem is exp: exp op exp against itself, you have to express the associativity of the rule itself:

     %token INT PLUS
     %left PLUS
     %%
     exp: INT
        | exp op exp %prec PLUS;
     op: PLUS ;

here you transfered the associativity and precedence of PLUS to the binary operator rule.  Actually, the proper writing is:

     %token INT PLUS
     %left PLUS
     %%
     exp: INT
        | exp PLUS exp;

Now you should understand why, although it might look stupidly verbose, you must not factor the binary operators to a rule exp: exp op exp.  You need:

     %token INT PLUS TIMES
     %left PLUS
     %left TIMES
     %%
     exp: INT
        | exp PLUS exp;
        | exp TIMES exp;

the problem is that there is not enough context.

You might think the solution provided above to still use a nonterminal can be extended to bigger problems?  Why not using several nonterminals to classify the operators per precedence, such as in

     %token INT PLUS TIMES
     %left ADDOP
     %left MULOP
     %%
     exp: INT
        | exp mulop exp %prec MULOP;
        | exp addop exp %prec ADDOP;

     mulop: TIMES;
     addop: PLUS;

alas!  It does not work.  Can you explain why?

     $ bison -dv arith.y
     arith.y contains 4 shift/reduce conflicts.
     $ cat arith.output
     [...]
     state 7

         exp  ->  exp . mulop exp   (rule 2)
         exp  ->  exp mulop exp .   (rule 2)
         exp  ->  exp . addop exp   (rule 3)

         PLUS	shift, and go to state 3
         TIMES	shift, and go to state 4

         PLUS	[reduce using rule 2 (exp)]
         TIMES	[reduce using rule 2 (exp)]
         $default	reduce using rule 2 (exp)

         mulop	go to state 5
         addop	go to state 6
     [...]

If you can explain why, then you will easily find the right way to do it: it is possible.

Handling the Dangling else
--------------------------

One way is simply to tolerate the shift/reduce it produces.  In this case, declare it to Bison:

     %token INT IF THEN ELSE
     /* Expected shift/reduce conflicts:
        - dangling else. */
     %expect 1
     %%
     exp: IF exp THEN exp
        | IF exp THEN exp ELSE exp
        | INT;

Another way is to use precedence:

     %token INT IF THEN ELSE
     /* ELSE has higher precedence than THEN. */
     %left THEN
     %left ELSE
     %%
     exp: IF exp THEN exp
        | IF exp THEN exp ELSE exp
        | INT;

In case of doubt, always check the output file.

     state 5
         exp  ->  IF exp THEN exp .            (rule 1)
         exp  ->  IF exp THEN exp . ELSE exp   (rule 2)
         ELSE        shift, and go to state 6
         $default    reduce using rule 1 (exp)

here, when it sees an ELSE, it shifts, which is exactly what we need.

Unrolling rules
---------------

There is a problem with the following portion of the Tiger grammar:

     %token ID LBRACK RBRACK OF
     %%
     exp: typeid LBRACK exp RBRACK OF exp
        | lvalue;
     lvalue: ID
           | lvalue LBRACK exp RBRACK;
     typeid: ID;

The Tiger grammar is making the difference between the identifier of a type, ID, and that of a value (variable or function), typeid.  This creates an ambiguity reported by Bison:

     % bison minitiger.y -v
     minitiger.y contains 1 reduce/reduce conflict.

Then, read the content of minitiger.output:

     State 1 contains 1 reduce/reduce conflict.

     Grammar
     rule 1    exp -> typeid LBRACK exp RBRACK OF exp
     rule 2    exp -> lvalue
     rule 3    lvalue -> ID
     rule 4    lvalue -> lvalue LBRACK exp RBRACK
     rule 5    typeid -> ID

     state 1
         lvalue  ->  ID .   (rule 3)
         typeid  ->  ID .   (rule 5)

         LBRACK      reduce using rule 3 (lvalue)
         LBRACK      [reduce using rule 5 (typeid)]
         $default    reduce using rule 3 (lvalue)

Bison says in state 1 with LBRACK as look ahead, it can either reduce rule 3 or 5.  I.e., the situation it describes is:

     my_id . [

At this point, it does not know where my_id is a type id, or a value id.  And indeed, it is impossible to know!  It can be my_id [1] := 1, my_id is a variable holding an array or my_id [1] of int, my_id is a type.

On the other hand, it is very easy to know: because of rule 1, we perfectly know that my_id is a type id if there is an of after the bracket.  But we can't see it, it is one level higher.

To help Bison, we will unroll the rule that bugs us:

     %token ID LBRACK RBRACK OF
     %%
     exp: ID     LBRACK exp RBRACK OF exp
        | lvalue;
     lvalue: ID
           | lvalue LBRACK exp RBRACK;

This time we have a shift/reduce conflict, let's check it:

     exp     ->  ID . LBRACK exp RBRACK OF exp   (rule 1)
     lvalue  ->  ID .                            (rule 3)

     LBRACK    shift, and go to state 3
     LBRACK    [reduce using rule 3 (lvalue)]
     $default  reduce using rule 3 (lvalue)

the parser will privilege shifting, i.e. it will prefer rule 1, which is not fine...  It means it will misunderstand id [1] := 1.  We also need to unroll the other part!

     %token ID LBRACK RBRACK OF
     %%
     exp: ID     LBRACK exp RBRACK OF exp
        | lvalue;

     lvalue: ID
           | ID LBRACK exp RBRACK;

but of course this is dead wrong: since we killed the recursion, we no longer can handle a[1][2].  We must reintroduce the recursion, but only for long enough values:

     %token ID LBRACK RBRACK OF
     %%
     exp: ID     LBRACK exp RBRACK OF exp
        | lvalue;
     lvalue: ID
           | lvalue.big
     lvalue.big: ID LBRACK exp RBRACK
               | lvalue.big LBRACK exp RBRACK;

This time, Bison accepts the grammar without any conflict.

Error Recovery
--------------

By default, if the grammar is not prepared to support syntax errors, the parser will stop on the first error.

There is a special token error which can be used to specify how to ``eat'' syntax errors:

     exp: LPAREN RPAREN
        | LPAREN exps RPAREN
        | LPAREN error RPAREN;

If there is an error ``inside'' exps, the parser will essentially pop everything which was on the state after the LPAREN, then discard all the input until it sees the RPAREN, then reduce this rule.

As you can see, the localization of the error handler is crucial.  As a thumb rule, you should place your error token before a token which closes a construct.  Another frequent use is in lists:

     /* One or more `exp; ...'. */
     exps.1:
       exp
     | exps.1 SEMI exp
     | error  SEMI exp
     ;

Comparison between LR and LL analyses
=====================================

Comparing LL and LR
-------------------

http://compilers.iecc.com/comparch/article/92-05-059.

          Newsgroups:   comp.compilers
          From:         parrt@ecn.purdue.edu (Terence J Parr)
          Keywords:     LL(1), LR(1), parse
          Organization: Compilers Central
          Date:         Mon, 11 May 1992 02:44:23 GMT

     tiller@solace.me.uiuc.edu (Mike Tiller) writes:

          Is there anything to be cautious of when using LL? I looked in Principles of Compiler Design, but I couldn't decipher exactly what the pros and cons were.

     There is no strict ordering between LL(k) and LALR(1); that is, I know of one grammar that is LL(k), but not LALR(1). However, LALR(1) has stronger recognition strength in practice. yacc's advantage in this area has narrowed due to PCCTS's full LL(k>1) parsing (only k=1 was commonly available before). Strength is not the end of the story because one rarely wants to merely recognize --> we translate. Here, LL parsers are the clear winner. A few highlights:

     Mid-rule actions
          Actions cannot introduce ambiguities into your LL grammar. All Yacc programmers say "arrgggghhh!" here.

     Inherited attributes
          LL rules may inherit attributes; i.e. you can pass stuff to them just like in a programming language.  For example, you can pass a scope to your rule that recognizes declarations.  Future versions of PCCTS will even let you pass productions to rules-->context-sensitive parsing.

     Local variables
          If recursive-descent compilers are generated, then local, stack-based variables are trivial to implement.  Bottom-up folks have no convenient way.  Local variables are useful because you get a new one at each rule invocation; e.g. a new 'scope' variable appears every time you enter rule function.

     The disadvantage really only lies in the fact that you have more constraints when writing LL(k) grammars--no left-recursion and no common prefixes of tokens >= k tokens in length.

          Basically, I just use Yacc (Bison whatever) to parse some input specification files.

     If you can do what you need to do with Yacc and/or already have grammars that do what you want, then there is no reason to change.

     Moral of story: Most languages can be described easily with LL(k); the semantic flexibility of LL(k) makes any fancy footwork regarding the grammar worth the effort for me.

     One other point: the tool's programming interface is also a consideration.  Does the system allow EBNF?  Can it build trees for you automagically?  Can you debug the resulting parsers (tables vs recursive-descent) easily?

     Terence Parr, parrt@ecn.purdue.edu Purdue University Electrical Engineering

Intellectual bigotry
--------------------

http://www.google.com/url?sa=U&start=4&q=http://compilers.iecc.com/comparch/article/95-11-138&e=42

          Re: LL(1) vs LALR(1) parsers
          Newsgroups:    comp.compilers
          From:         "steve (s.s.) simmons" <simmons@bnr.ca>
          Keywords:     parse, LALR, LL(1)
          Organization: Bell-Northern Research Ltd.
          References:   95-11-051
          Date:         Wed, 15 Nov 1995 13:39:07 GMT

          Why do compiler design text book authors only describe recursive parsers as a step stone on their way to bottom up parsers? I know that LALR allows for more complex grammars, but many languages can be described by LL(1) grammars. If LL(1) can yield faster, smaller and more understandable parsers with better error handling for many languages, why isn't this method more elaborated? (Holub, as an example, presents full grammar and compiler listings for a bottom-up C-compiler, not for top-down).

     Intellectual bigotry!!!!!

     That is, the automated parsers use a great deal of automata theory which helps build on the computer science foundation. Recursive descent parsers are a small matter of programming (SMOP). I do notice among peers in industry that people are no longer snubbing the idea of writing a recursive parser when it is appropiate.

     Remember you don't take a compiler course to learn how to build a compiler, surprise... Most people never write a compiler. You take it for the following reasons:

       - Improving your comp. sci. background to understand automata theory with a very good application.

       - Understanding what a compiler may do (or not do) for your code.

       - Learning about big system software, data structures, etc.

     Thank you.

     Steve Simmons

     [I agree that few CS students will write a conventional compiler, but we all end up having to decode some sort of input language in an application. -John]