Left and Right recursion

Left and Right recursion

Our version of YACC has a tracing facility that we can use to see how it treats left-recursive and right-recursive grammars - e.g. when recognising a , b , c as a list of identifiers.

Example parse trace for list : id | list ',' id ;

                  .... look ahead at id 'a'
        id <-- 'a'
        |
        list
        |                 .... look ahead at ','
        |     ',' <-- ','
        |      |                 .... look ahead at id 'b'
        |      |      id <-- 'b'
        +------+------+
        list
        |                 .... look ahead at ','
        |     ',' <-- ','
        |      |                 .... look ahead at id 'c'
        |      |      id <-- 'c'
        +------+------+
        list
        |                 .... look ahead at END

Example parse trace for list : id | id ',' list ;

                  .... look ahead at id 'a'
        id <-- 'a'
        |                 .... look ahead at ','
        |     ',' <-- ','
        |      |                 .... look ahead at id 'b'
        |      |     id <-- 'b'
        |      |      |                 .... look ahead at ','
        |      |      |     ',' <-- ','
        |      |      |      |                 .... look ahead at id 'c'
        |      |      |      |     id <-- 'c'
        |      |      |      |      |                 .... look ahead at END
        |      |      |      |     list
        |      |      +------+------+
        |      |     list
        +------+------+
        list
        |