Debugging the PostgreSQL grammar (Bison)

== Shift/reduce conflicts ==
Postgres development rules forbid shift/reduce conflicts in the main grammar (and the other conflicts bison produces - reduce/reduce conflicts - are even worse). Often if you're making a grammar change, you can introduce a shift/reduce conflict to the grammar that needs to be fixed. As Tom Lane explains here, shift/reduce conflicts can often be fixed by "unfactoring" the grammar a little. (For more context see the original discussion on the -hackers mailing list.)
Frequently, when debugging shift/reduce conflicts it's useful to review the gram.output file, which building the parser leaves behind by default. This report can indicate how the ambiguity arises, as discussed here.
For those interested in a bit more of the theory of parsers, most compiler construction books cover them to some degree, including the venerable if a bit dated Dragon Book.
> > bison -v doesn't show anything useful beyond saying that there is one
> > shift/reduce conflict. The gram.output is 10MB, which doesn't help me
> > much (I'm still trying to make sense of it).
Well, you need to learn a bit more about bison I think. The complaint
is
State 1135 conflicts: 1 shift/reduce
so we look at state 1135, which says:
state 1135
 241 alter_table_cmd: ADD_P . opt_column columnDef
 251 | ADD_P . TableConstraint
 CHECK shift, and go to state 1698
 COLUMN shift, and go to state 1742
 CONSTRAINT shift, and go to state 1699
 EXCLUSION shift, and go to state 1700
 FOREIGN shift, and go to state 1701
 PRIMARY shift, and go to state 1702
 UNIQUE shift, and go to state 1703
 EXCLUSION [reduce using rule 887 (opt_column)]
 $default reduce using rule 887 (opt_column)
 TableConstraint go to state 1743
 ConstraintElem go to state 1705
 opt_column go to state 1744
This is the state immediately after scanning "ADD" in an ALTER TABLE
command, and what it's unhappy about is that it has two different things
to do if the next token is EXCLUSION. (The dot in the productions
indicates "where we are", and the square brackets mark the unreachable
action.) If you check the other mentioned states it becomes clear that
the state-1700 path leads to deciding that EXCLUSION begins a
TableConstraint, while rule 887 is the "empty" alternative for
opt_column, and is what would have to be done next if EXCLUSION is a
column name beginning a ColumnDef. So the difficulty is that it can't
be sure whether EXCLUSION is a column name without looking one token
past EXCLUSION, but it has to decide whether to eliminate COLUMN before
it can look ahead past EXCLUSION.
This is a pretty common difficulty with empty-producing productions.
The usual way around it is to eliminate the empty production by making
the calling production a bit more redundant. In this case, we can fix
it by replacing
alter_table_cmd:
 ADD_P opt_column columnDef
with two productions
alter_table_cmd:
 ADD_P columnDef
 | ADD_P COLUMN columnDef
The reason this fixes it is that now the parser does not have to make
a shift-reduce decision while EXCLUSION is the next token: it's just
going to shift all the time, and it only has to reduce once EXCLUSION
is the current token and it can see the next one as lookahead. (In
which case, it will reduce EXCLUSION to ColId and proceed with the
its-a-ColumnDef path, only if the next token isn't "(" or "USING".)
Another way to think about it is that we are forcing bison to split
this one state into two, but I find it easier to understand how to
fix the problem by looking for ways to postpone the reduce decision.
== Debugging the PostgreSQL parser ==
More sophisticated analysis may be required where a grammar produces unexpected results (i.e. the parser is built, but parse analysis receives a raw query tree that does not meet expectations in some way). The Bison documentation describes how to enable traces:
https://www.gnu.org/software/bison/manual/html_node/Enabling-Traces.html
The best way to get this to work in PostgreSQL seems to be to declare an "extern int base_yydebug" variable within the top of parser.c. It is also necessary to use the %debug directive. The following patch accomplishes this (debug output will appear in stderr):
diff --git a/src/backend/parser/gram.y b/src/backend/parser/gram.y
index 0bc8815..fa21a5a 100644
--- a/src/backend/parser/gram.y
+++ b/src/backend/parser/gram.y
@@ -635,6 +635,7 @@ static Node *makeRecursiveViewSelect(char *relname, List *aliases, Node *query);
 
 
 /* Precedence: lowest to highest */
+%debug
 %nonassoc SET /* see relation_expr_opt_alias */
 %left UNION EXCEPT
 %left INTERSECT
diff --git a/src/backend/parser/parser.c b/src/backend/parser/parser.c
index 6632966..84d401c 100644
--- a/src/backend/parser/parser.c
+++ b/src/backend/parser/parser.c
@@ -24,6 +24,7 @@
 #include "parser/gramparse.h"
 #include "parser/parser.h"
 
+extern int base_yydebug;
 
 /*
 * raw_parser
@@ -48,6 +49,8 @@ raw_parser(const char *str)
 /* initialize the bison parser */
 parser_init(&yyextra);
 
+ base_yydebug = 1;
+
 /* Parse! */
 yyresult = base_yyparse(yyscanner);
 
This will allow you to see exactly what states the parser enters as your statement is parsed, which, combined with a Bison report, will greatly aid debugging.
== Other issues ==
It may also be useful to temporarily #define COPY_PARSE_PLAN_TREES within pg_config_manual.h when at a loss as to why the parser produces unexpected results.
Category:Development‎