shift/reduce conflicts in the YACC grammar of C99

Discussion in 'C Programming' started by eliben, Oct 30, 2010.

  1. eliben

    eliben Guest

    The "old standard" ANSI/ISO C (C89) had a known shift-reduce conflict
    in its YACC grammar, because of the uncertainty of where to hang an
    else in nested if statements. This conflict was resolved to "shift" by
    YACC, which is fine for C's semantics.

    It appears that C99 introduced two new shift/reduce conflicts with
    these new derivations for postfix-expression:

    ( type-name ) { initializer-list }
    ( type-name ) { initializer-list , }

    This is called compound literals and allows things like:

    struct POINT p;
    p = (struct POINT) {x, y};

    int *ap;
    ap = (int []) {1, 2, 3};

    Can someone confirm that this indeed creates 2 new shift/reduce
    conflicts in the grammar? Or am I defining it incorrectly?

    This is the conflict report I'm getting from PLY (A particular
    implementation of YACC, in Python):

    (206) unary_expression -> SIZEOF LPAREN type_name RPAREN .
    (221) postfix_expression -> LPAREN type_name RPAREN . LBRACE
    initializer_list LBRACE
    (222) postfix_expression -> LPAREN type_name RPAREN . LBRACE
    initializer_list COMMA LBRACE

    ! shift/reduce conflict for LBRACE resolved as shift

    Thanks in advance
     
    eliben, Oct 30, 2010
    #1
    1. Advertising

  2. eliben <> writes:

    > The "old standard" ANSI/ISO C (C89) had a known shift-reduce conflict
    > in its YACC grammar, because of the uncertainty of where to hang an
    > else in nested if statements. This conflict was resolved to "shift" by
    > YACC, which is fine for C's semantics.
    >
    > It appears that C99 introduced two new shift/reduce conflicts with
    > these new derivations for postfix-expression:
    >
    > ( type-name ) { initializer-list }
    > ( type-name ) { initializer-list , }
    >
    > This is called compound literals and allows things like:
    >
    > struct POINT p;
    > p = (struct POINT) {x, y};
    >
    > int *ap;
    > ap = (int []) {1, 2, 3};
    >
    > Can someone confirm that this indeed creates 2 new shift/reduce
    > conflicts in the grammar? Or am I defining it incorrectly?
    >
    > This is the conflict report I'm getting from PLY (A particular
    > implementation of YACC, in Python):
    >
    > (206) unary_expression -> SIZEOF LPAREN type_name RPAREN .
    > (221) postfix_expression -> LPAREN type_name RPAREN . LBRACE
    > initializer_list LBRACE
    > (222) postfix_expression -> LPAREN type_name RPAREN . LBRACE
    > initializer_list COMMA LBRACE
    >
    > ! shift/reduce conflict for LBRACE resolved as shift


    Yes, that looks right. '( type-name )' can appear in several places but
    when it denotes a cast, the grammar can tell because the next token
    can't be '{'. A sizeof expression can end after the ')' or the
    expression may continue with '{' ... '}'.

    --
    Ben.
     
    Ben Bacarisse, Oct 30, 2010
    #2
    1. Advertising

  3. eliben

    eliben Guest

    > > This is the conflict report I'm getting from PLY (A particular
    > > implementation of YACC, in Python):

    >
    > >     (206) unary_expression -> SIZEOF LPAREN type_name RPAREN .
    > >     (221) postfix_expression -> LPAREN type_name RPAREN . LBRACE
    > > initializer_list LBRACE
    > >     (222) postfix_expression -> LPAREN type_name RPAREN . LBRACE
    > > initializer_list COMMA LBRACE

    >
    > >   ! shift/reduce conflict for LBRACE resolved as shift

    >
    > Yes, that looks right.  '( type-name )' can appear in several places but
    > when it denotes a cast, the grammar can tell because the next token
    > can't be '{'.  A sizeof expression can end after the ')' or the
    > expression may continue with '{' ... '}'.
    >


    I thought about it, but what sense does a full sizeof expression
    followed by { make? Taking the longest derivation is supposed to be
    built-in for LALR parsers like YACC, otherwise a lot of things would
    not work, such as:

    x = y + z;

    Stop at 'y' or continue to '+ z'?

    Eli
     
    eliben, Oct 30, 2010
    #3
  4. eliben <> writes:

    >> > This is the conflict report I'm getting from PLY (A particular
    >> > implementation of YACC, in Python):

    >>
    >> >     (206) unary_expression -> SIZEOF LPAREN type_name RPAREN .
    >> >     (221) postfix_expression -> LPAREN type_name RPAREN . LBRACE
    >> > initializer_list LBRACE
    >> >     (222) postfix_expression -> LPAREN type_name RPAREN . LBRACE
    >> > initializer_list COMMA LBRACE

    >>
    >> >   ! shift/reduce conflict for LBRACE resolved as shift

    >>
    >> Yes, that looks right.  '( type-name )' can appear in several places but
    >> when it denotes a cast, the grammar can tell because the next token
    >> can't be '{'.  A sizeof expression can end after the ')' or the
    >> expression may continue with '{' ... '}'.

    >
    > I thought about it, but what sense does a full sizeof expression
    > followed by { make?


    What sense would ruling it out make? If you think that the result of

    sizeof ( type-name ) { initializer-list }

    is always the same as sizeof ( type-name ) then consider

    sizeof (char *[]){"abc", "def", "ghi"}

    Of course, the grammar could exclude compound literals from sizeof while
    permitting a work around by adding parentheses:

    sizeof ((char *[]){"abc", "def", "ghi"})

    but, again, what is the advantage of adding all the complexity?

    > Taking the longest derivation is supposed to be
    > built-in for LALR parsers like YACC, otherwise a lot of things would
    > not work, such as:
    >
    > x = y + z;
    >
    > Stop at 'y' or continue to '+ z'?


    Yes, but YACC switches to another mechanism for expressions and
    deliberately does not report the myriad shift/reduce conflicts that
    would otherwise be shown.

    --
    Ben.
     
    Ben Bacarisse, Oct 30, 2010
    #4
  5. eliben

    eliben Guest

    <snip>
    > What sense would ruling it out make?  If you think that the result of
    >
    >   sizeof ( type-name ) { initializer-list }
    >
    > is always the same as sizeof ( type-name ) then consider
    >
    >  sizeof (char *[]){"abc", "def", "ghi"}
    >
    > Of course, the grammar could exclude compound literals from sizeof while
    > permitting a work around by adding parentheses:
    >
    >   sizeof ((char *[]){"abc", "def", "ghi"})
    >
    > but, again, what is the advantage of adding all the complexity?
    >
    > > Taking the longest derivation is supposed to be
    > > built-in for LALR parsers like YACC, otherwise a lot of things would
    > > not work, such as:

    >
    > > x = y + z;

    >
    > > Stop at 'y' or continue to '+ z'?

    >
    > Yes, but YACC switches to another mechanism for expressions and
    > deliberately does not report the myriad shift/reduce conflicts that
    > would otherwise be shown.


    Eventually it turned out to be a typo in the grammar definition that
    was causing the trouble (*blush*). Fixed, it analyzes the full C99
    grammar with only the single if-else conflict.

    I apologize for the confusion, but at least there's now a fully
    functional C99 grammar for YACC (although a Python version thereof -
    PLY) available :)

    Eli
     
    eliben, Oct 31, 2010
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    3
    Views:
    3,758
    Chris Torek
    Feb 20, 2006
  2. Ray Mitchell

    C99 Grammar Definition

    Ray Mitchell, Dec 31, 2006, in forum: C Programming
    Replies:
    6
    Views:
    1,267
    Tarique
    Jan 6, 2007
  3. None

    cant reove the shift reduce conflict..

    None, Apr 5, 2007, in forum: C Programming
    Replies:
    5
    Views:
    537
    Ian Collins
    Apr 5, 2007
  4. saorjag1729
    Replies:
    0
    Views:
    769
    saorjag1729
    Dec 28, 2007
  5. Jim Freeze
    Replies:
    9
    Views:
    162
    YANAGAWA Kazuhisa
    Oct 21, 2003
Loading...

Share This Page