1. Forum
  2. Usenet
  3. COMP.COMPILERS

  • Why no shift-shift conflicts?

    From Roger L Costello@21:1/5 to All on Tue Jan 25 21:58:21 2022
    Hello Compiler Experts!

    I have read that there are shift-reduce conflicts and reduce-reduce
    conflicts.

    It is my understanding that a "conflict" means the parser doesn't know which path to take.

    Consider this example rule from the Bison manual:

    compound: '{' declarations statements '}'
    | '{' statements '}'
    ;

    I look at that and think, "There is ambiguity. There are two possible paths to take. The parser doesn't know which path to take." That is, it looks to me
    like a shift-shift conflict.

    Why are there no shift-shift conflicts?

    /Roger
    [Sheesh, it's because that's how LR parsing works. The parser has a state machine and a stack.
    When it shifts, it puts the token on the stack and moves to the next state, and it's OK if that
    state might be part of more than one rule. It's only when it gets to the end of a rule and needs
    to reduce, i.e., pop the tokens for that rule off the stack, give them to the semantic routine,
    and push its result token on the stack, that the action has to correspond to a single rule. For more
    info I shamelessly recommend chapter 7 of flex&bison. -John]

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Kaz Kylheku@21:1/5 to Roger L Costello on Fri Jan 28 01:20:52 2022
    On 2022-01-25, Roger L Costello <[email protected]> wrote:
    Hello Compiler Experts!

    I have read that there are shift-reduce conflicts and reduce-reduce conflicts.

    It is my understanding that a "conflict" means the parser doesn't know which path to take.

    Consider this example rule from the Bison manual:

    compound: '{' declarations statements '}'
    | '{' statements '}'
    ;

    I look at that and think, "There is ambiguity. There are two possible paths to
    take. The parser doesn't know which path to take." That is, it looks to me like a shift-shift conflict.

    "shift" is the name of an action applied to the *input*. The input can
    be regarded as a stack: to shift is to pop the next symbol from the
    input stack and deal with it in the algorithm by moving it into the
    algorithm's stack, and changing state.

    Since there is only one input stream, there cannot be a shift-shift
    conflict. There is never any choice regarding which symbol is available
    from the input.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Andy Walker@21:1/5 to Kaz Kylheku on Fri Jan 28 10:13:17 2022
    On 28/01/2022 01:20, Kaz Kylheku wrote:
    [...]
    Since there is only one input stream, there cannot be a shift-shift
    conflict.

    I suppose there is no conceivable use for a parsing process
    that operates on several collateral input streams? Such an animal
    would not be a conventional compiler implementing a conventional
    programming language, but people often invent "little languages"
    for specialist purposes, and these often need "little compilers"
    to process them. It might help such people if tools similar to
    Flex and Bison were available to process multiple streams instead
    of having to roll your own [or somehow stitching the inputs into
    one stream].

    --
    Andy Walker, Nottingham.
    Andy's music pages: www.cuboid.me.uk/andy/Music
    Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Simpson
    [It seems pretty exotic. The obvious first question is whether you can
    combine the multiple input streams in a prepass and parse them as one. -John]

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Ev. Drikos@21:1/5 to Roger L Costello on Fri Jan 28 15:22:46 2022
    On 25/01/2022 23:58, Roger L Costello wrote:
    ...

    In example, you would care if you wanted to execute some
    actions on-shift, assuming you had a supporting tool. In
    example, given this grammar fragment, what the parser is
    supposed to do, increase or decrease variable 'a' after
    reading '1' on input?


    X: '1' { a = a + 1; } '2' 'x'
    ;

    Y: '1' { a = a - 1; } '2' 'y'
    ;

    Z: '1' '2' 'z' { a = 0 }
    ;

    Without the mid-rule actions above, any LR based parser is
    capable, after reading '1', to shift it onto a stack without
    reject any of the above three rules (imagine ie that an LR
    parser moves some dot on the above rules after '1', and the
    parser state is combination of the alive dotted items). So,
    the parser wouldn't see any conflict in such a transition.


    Regards,
    Ev. Drikos
    [The mid-rule action is a cheat, a shorthand for this:

    X: '1' x1 '2' 'x' ;
    x1: { a = a + 1; } ;


    Y: '1' y1 '2' 'y' ;
    y1: { a = a - 1; } ;

    That's why those actions create conflicts where there were none before.

    -John]

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Andy Walker@21:1/5 to All on Fri Jan 28 19:42:54 2022
    On 28/01/2022 10:13, I wrote:
        I suppose there is no conceivable use for a parsing process
    that operates on several collateral input streams? [...]
    [It seems pretty exotic.  The obvious first question is whether you can combine the multiple input streams in a prepass and parse them as one. -John]

    You can; /unless/ there are unresolved shift/shift conflicts!
    I suppose a more useful obvious question would be whether there are any real-life applications for collateral multiple input streams. There are certainly uses for multiple inputs; but these are usually resolved by
    some mechanism such as interrupts or polling, rather than by parsing,
    and the streams are handled separately rather than stitched together.
    It's possible that there is a chicken-egg situation; no-one thinks of "compiling" multiple streams because there are no tools to do it, as
    there are no applications that anyone has thought of for it.

    --
    Andy Walker, Nottingham.
    Andy's music pages: www.cuboid.me.uk/andy/Music
    Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Simpson

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Thomas Koenig@21:1/5 to Andy Walker on Fri Jan 28 19:19:49 2022
    Andy Walker <[email protected]> schrieb:
    On 28/01/2022 01:20, Kaz Kylheku wrote:
    [...]
    Since there is only one input stream, there cannot be a shift-shift
    conflict.

    I suppose there is no conceivable use for a parsing process
    that operates on several collateral input streams?

    The information about which stream the input comes from has to
    be around. Why not simply put an identifier for the input
    stream before the data, and build a conventional parser?

    Even a state machine with several inputs can be viewed as
    processing several input streams.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)