Why no shift-shift conflicts?

[Roger L Costello]

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]

[Kaz Kylheku]

On 2022-01-25, Roger L Costello <cost...@mitre.org> 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.

[Andy Walker]

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]

[Ev. Drikos]

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]

[Thomas Koenig]

Andy Walker <a...@cuboid.co.uk> 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.

[Andy Walker]

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.