Re: [HACKERS] Updated TODO item

On Tue, 8 Jan 2002, Christopher Kings-Lynne wrote:

> > Does this have the multiple "WITH xxx" clauses which were discussed
> > earlier? That is a nonstarter for syntax. There are other places in the
> > grammar having "with clauses" and multiple arguments or subclauses, and
> > having the shift/reduce issues resolved...
>
> I might be thicker than a whale sandwich (10 points if you can pick the
> quote :) ), but can someone please tell me what a shift/reduce issue is,
> exactly...
>

A Yacc parser does two things in order to parse input:

1) Reduce: attempt to reduce the stack by simplifying it to a rule
2) Shift: obtain the next token from input so that a reduction may be able
to take.

Shift/reduce conflicts are pretty ugly. Basically, what happens is that
the parser finds itself in a state where it is valid to reduce OR shift at
some point in the grammar. What I believe Thomas was refering to was this
condition:

Take a rule:

rule a: CREATE DATABASE <name> WITH LOCATION = <name>
rule b: CREATE DATABASE <name> WITH LOCATION = <name> WITH OWNER = <name>

now if the input is:

CREATE DATABASE test WITH LOCATION = '/var/test' WITH OWNER = swm
^

Then the parser can reach the point under-marked by the circumflex and
find it valid to reduce the stack (CREATE DATABASE test WITH LOCATION =
'/var/test') to rule a OR shift and put the WITH (after the circumflex) on
the stack given that this should match rule b.

Naturally, if this conflict is ignored for the grammar above, you could
end up with wild results in your parsed node tree. Realistically, Bison
and other yacc compilers will generate parsers unaffected for this
situation because they always opt to shift when there is a shift/reduce
conflict -- a pretty safe bet. But if it should have been valid to reduce
the input to a once it reached the circumflex, you'd be in trouble.

Gavin