glr2.cc: add an example

[Akim Demaille]

Hi Valentin,

As we discussed, here is an example for glr2.cc.  Eventually, we will make it 
use the variants, and in fact, one can still see it comes from C: there's still 
work to do to make this example a decent C++ citizen.

I did not though, because it's actually already failing...  If you compile the 
example and run on "T (x) + y;", it crashes.  I have not tried to address this 
crash, but it's clearly within the realm of glr2.cc, not the example itself.  
Well, I might be wrong, of course.

I hope this won't be too hard to spot and fix.  FWIW, you have the same example 
in C in examples/c/glr.  It might be helpful to compare.  In fact, if you move 
this glr2.cc example to using glr.cc, it works.  It might be another way to try 
to spot what happened.  Asan might be helpful too.

Cheers!

commit 3a24da124ae5c7578becda3ecd758b53bb086312
Author: Akim Demaille <akim.demaille@gmail.com>
Date:   Sat Sep 26 08:33:14 2020 +0200

    glr2.cc: add an example
    
    Currently this example crashes on input such as "T (x) + y;".
    The same example with glr.c works properly.
    
    * examples/c++/glr/Makefile, examples/c++/glr/README.md,
    * examples/c++/glr/c++-types.test, examples/c++/glr/c++-types.yy,
    * examples/c++/glr/local.mk, examples/c++/local.mk: New.
    Based on examples/c/glr/c++-types.y.

diff --git a/data/skeletons/glr2.cc b/data/skeletons/glr2.cc
index 4f7e89d2..1bbd623a 100644
--- a/data/skeletons/glr2.cc
+++ b/data/skeletons/glr2.cc
@@ -2092,7 +2092,7 @@ public:
               {
                 state_set_index yynewStack = yystateStack.yysplitStack (yyk);
                 YY_DEBUG_STREAM << "Splitting off stack " << yynewStack.get()
-                                << " from " << yyk.get();
+                                << " from " << yyk.get() << '\n';
                 YYRESULTTAG yyflag =
                   yyglrReduce (yynewStack, *yyconflicts,
                                yyimmediate[*yyconflicts]);
diff --git a/examples/c++/calc++/local.mk b/examples/c++/calc++/local.mk
index 00f47a48..5cc1ed30 100644
--- a/examples/c++/calc++/local.mk
+++ b/examples/c++/calc++/local.mk
@@ -18,7 +18,6 @@
 ## Parser generation.  ##
 ## ------------------- ##
 
-%D%/parser.stamp: $(dependencies)
 SUFFIXES += .yy .stamp
 .yy.stamp:
        $(AM_V_YACC)rm -f $@
@@ -26,6 +25,7 @@ SUFFIXES += .yy .stamp
        $(AM_V_at)$(YACCCOMPILE) -o $*.cc $<
        $(AM_V_at)mv -f $@.tmp $@
 
+%D%/parser.stamp: $(dependencies)
 $(calcxx_sources_generated): %D%/parser.stamp
        @test -f $@ || rm -f %D%/parser.stamp
        @test -f $@ || $(MAKE) $(AM_MAKEFLAGS) %D%/parser.stamp
diff --git a/examples/c++/glr/Makefile b/examples/c++/glr/Makefile
new file mode 100644
index 00000000..a56edb1f
--- /dev/null
+++ b/examples/c++/glr/Makefile
@@ -0,0 +1,28 @@
+# This Makefile is designed to be simple and readable.  It does not
+# aim at portability.  It requires GNU Make.
+
+BASE = c++-types
+BISON = bison
+XSLTPROC = xsltproc
+
+all: $(BASE)
+
+%.c %.h %.xml %.gv: %.y
+       $(BISON) $(BISONFLAGS) --defines --xml --graph=$*.gv -o $*.c $<
+
+$(BASE): $(BASE).o
+       $(CC) $(CFLAGS) -o $@ $^
+
+run: $(BASE)
+       @echo "Type C++ declarations or expressions.  Quit with ctrl-d."
+       ./$<
+
+html: $(BASE).html
+%.html: %.xml
+       $(XSLTPROC) $(XSLTPROCFLAGS) -o $@ $$($(BISON) 
--print-datadir)/xslt/xml2xhtml.xsl $<
+
+CLEANFILES =                                                                   
\
+  $(BASE) *.o $(BASE).[ch] $(BASE).output $(BASE).xml $(BASE).html $(BASE).gv
+
+clean:
+       rm -f $(CLEANFILES)
diff --git a/examples/c++/glr/README.md b/examples/c++/glr/README.md
new file mode 100644
index 00000000..60de8d65
--- /dev/null
+++ b/examples/c++/glr/README.md
@@ -0,0 +1,24 @@
+# glr
+
+This example demonstrates the use of GLR parsers to handle (local)
+ambiguities in the C++ language.  See the node "Merging GLR Parses" in
+Bison's documentation.
+
+<!---
+Local Variables:
+fill-column: 76
+ispell-dictionary: "american"
+End:
+
+Copyright (C) 2020 Free Software Foundation, Inc.
+
+This file is part of Bison, the GNU Compiler Compiler.
+
+Permission is granted to copy, distribute and/or modify this document
+under the terms of the GNU Free Documentation License, Version 1.3 or
+any later version published by the Free Software Foundation; with no
+Invariant Sections, with no Front-Cover Texts, and with no Back-Cover
+Texts.  A copy of the license is included in the "GNU Free
+Documentation License" file as part of this distribution.
+
+--->
diff --git a/examples/c++/glr/c++-types.test b/examples/c++/glr/c++-types.test
new file mode 100644
index 00000000..6f55c8ab
--- /dev/null
+++ b/examples/c++/glr/c++-types.test
@@ -0,0 +1,52 @@
+#! /bin/sh
+
+# Copyright (C) 2020 Free Software Foundation, Inc.
+#
+# This program is free software: you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation, either version 3 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+cat >input <<EOF
+z + q;
+
+T x;
+
+T x = y;
+
+x = y;
+EOF
+run 0 "\
+1.0-4: +(z, q)
+3.0-2: <declare>(T, x)
+5.0-6: <init-declare>(T, x, y)
+7.0-4: =(x, y)"
+
+exit 77
+
+cat >input <<EOF
+T (x) + y;
+
+T (x);
+
+T (y) = z + q;
+
+T (y y) = z + q;
+
+z + q;
+EOF
+run 0 "\
+1.0-8: +(<cast>(x, T), y)
+3.0-4: <OR>(<declare>(T, x), <cast>(x, T))
+5.0-12: <OR>(<init-declare>(T, y, +(z, q)), =(<cast>(y, T), +(z, q)))
+7.0-14: <error>
+9.0-4: +(z, q)
+err: 7.5: syntax error, unexpected identifier, expecting '=' or '+' or ')'"
diff --git a/examples/c++/glr/c++-types.yy b/examples/c++/glr/c++-types.yy
new file mode 100644
index 00000000..5c76c83c
--- /dev/null
+++ b/examples/c++/glr/c++-types.yy
@@ -0,0 +1,255 @@
+/* Simplified -*- C++ -*- Type and Expression Grammar.  */
+
+%glr-parser
+%skeleton "glr2.cc"
+%header
+%locations
+%debug
+
+/* Nice error messages with details. */
+%define parse.error detailed
+
+%code requires
+{
+  union Node {
+    struct {
+      int isNterm;
+      int parents;
+    } nodeInfo;
+    struct {
+      int isNterm; /* 1 */
+      int parents;
+      char const *form;
+      union Node *children[3];
+    } nterm;
+    struct {
+      int isNterm; /* 0 */
+      int parents;
+      char *text;
+    } term;
+  };
+  typedef union Node Node;
+}
+
+%define api.value.type {Node *}
+
+%code
+{
+
+#include <cassert>
+#include <cctype>
+#include <cstdio>
+#include <cstdlib>
+#include <cstring>
+
+  static Node *new_nterm (char const *form, Node *child0 = nullptr, Node 
*child1 = nullptr, Node *child2 = nullptr);
+  static Node *new_term (char *);
+  static void free_node (Node *);
+  static std::ostream& operator<< (std::ostream& o, const Node &node);
+  static YYSTYPE stmtMerge (YYSTYPE x0, YYSTYPE x1);
+
+  static int yylex (YYSTYPE *lvalp, YYLTYPE *llocp);
+}
+
+%expect-rr 1
+
+%token
+  TYPENAME "typename"
+  ID "identifier"
+
+%right '='
+%left '+'
+
+%destructor { free_node ($$); } stmt expr decl declarator TYPENAME ID
+
+%%
+
+prog : %empty
+     | prog stmt   { std::cout << @2 << ": " << *$2 << '\n'; free_node ($2); }
+     ;
+
+stmt : expr ';'  %merge <stmtMerge>     { $$ = $1; }
+     | decl      %merge <stmtMerge>
+     | error ';'        { $$ = new_nterm ("<error>"); }
+     | '@'              { $$ = $1; YYACCEPT; }
+     ;
+
+expr : ID
+     | TYPENAME '(' expr ')'
+                        { $$ = new_nterm ("<cast>", $3, $1); }
+     | expr '+' expr    { $$ = new_nterm ("+", $1, $3); }
+     | expr '=' expr    { $$ = new_nterm ("=", $1, $3); }
+     ;
+
+decl : TYPENAME declarator ';'
+                        { $$ = new_nterm ("<declare>", $1, $2); }
+     | TYPENAME declarator '=' expr ';'
+                        { $$ = new_nterm ("<init-declare>", $1,
+                                          $2, $4); }
+     ;
+
+declarator
+     : ID
+     | '(' declarator ')' { $$ = $2; }
+     ;
+
+%%
+
+int
+main (int argc, char **argv)
+{
+  // Enable parse traces on option -p.
+  if (1 < argc && strcmp (argv[1], "-p") == 0)
+    yydebug = 1;
+  yy::parser parser;
+  return !!parser.parse ();
+}
+
+
+/* A C error reporting function.  */
+void yy::parser::error (const location_type& l, const std::string& m)
+{
+  std::cerr << l << ": " << m << '\n';
+}
+
+int yylex (YYSTYPE *lvalp, YYLTYPE *llocp)
+{
+  static int lineNum = 1;
+  static int colNum = 0;
+
+  while (1)
+    {
+      int c;
+      assert (!feof (stdin));
+      c = getchar ();
+      switch (c)
+        {
+        case EOF:
+          return 0;
+        case '\t':
+          colNum = (colNum + 7) & ~7;
+          break;
+        case ' ': case '\f':
+          colNum += 1;
+          break;
+        case '\n':
+          lineNum += 1;
+          colNum = 0;
+          break;
+        default:
+          {
+            int tok;
+            llocp->begin.line = llocp->end.line = lineNum;
+            llocp->begin.column = colNum;
+            if (isalpha (c))
+              {
+                char buffer[256];
+                unsigned i = 0;
+
+                do
+                  {
+                    buffer[i++] = static_cast<char> (c);
+                    colNum += 1;
+                    assert (i != sizeof buffer - 1);
+                    c = getchar ();
+                  }
+                while (isalnum (c) || c == '_');
+
+                ungetc (c, stdin);
+                buffer[i++] = 0;
+                tok
+                  = isupper (static_cast <unsigned char> (buffer[0]))
+                  ? yy::parser::token::TYPENAME
+                  : yy::parser::token::ID;
+                *lvalp = new_term (strcpy (static_cast<char*> (malloc (i)), 
buffer));
+              }
+            else
+              {
+                colNum += 1;
+                tok = c;
+                *lvalp = NULL;
+              }
+            llocp->end.column = colNum-1;
+            return tok;
+          }
+        }
+    }
+}
+
+static Node *
+new_nterm (char const *form, Node *child0, Node *child1, Node *child2)
+{
+  Node *res = new Node;
+  res->nterm.isNterm = 1;
+  res->nterm.parents = 0;
+  res->nterm.form = form;
+  res->nterm.children[0] = child0;
+  if (child0)
+    child0->nodeInfo.parents += 1;
+  res->nterm.children[1] = child1;
+  if (child1)
+    child1->nodeInfo.parents += 1;
+  res->nterm.children[2] = child2;
+  if (child2)
+    child2->nodeInfo.parents += 1;
+  return res;
+}
+
+static Node *
+new_term (char *text)
+{
+  Node *res = new Node;
+  res->term.isNterm = 0;
+  res->term.parents = 0;
+  res->term.text = text;
+  return res;
+}
+
+static void
+free_node (Node *node)
+{
+  if (!node)
+    return;
+  node->nodeInfo.parents -= 1;
+  /* Free only if 0 (last parent) or -1 (no parents).  */
+  if (node->nodeInfo.parents > 0)
+    return;
+  if (node->nodeInfo.isNterm == 1)
+    {
+      free_node (node->nterm.children[0]);
+      free_node (node->nterm.children[1]);
+      free_node (node->nterm.children[2]);
+    }
+  else
+    free (node->term.text);
+  delete node;
+}
+
+static std::ostream&
+operator<< (std::ostream& o, const Node &node)
+{
+  if (node.nodeInfo.isNterm == 1)
+    {
+      o << node.nterm.form;
+      if (node.nterm.children[0])
+        {
+          o << '(' << *node.nterm.children[0];
+          if (node.nterm.children[1])
+            o << ", " << *node.nterm.children[1];
+          if (node.nterm.children[2])
+            o << ", " << *node.nterm.children[2];
+          o << ")";
+        }
+    }
+  else
+    o << node.term.text;
+  return o;
+}
+
+
+static YYSTYPE
+stmtMerge (YYSTYPE x0, YYSTYPE x1)
+{
+  return new_nterm ("<OR>", x0, x1);
+}
+
diff --git a/examples/c++/glr/local.mk b/examples/c++/glr/local.mk
new file mode 100644
index 00000000..8558651a
--- /dev/null
+++ b/examples/c++/glr/local.mk
@@ -0,0 +1,46 @@
+## Copyright (C) 2020 Free Software Foundation, Inc.
+##
+## This program is free software: you can redistribute it and/or modify
+## it under the terms of the GNU General Public License as published by
+## the Free Software Foundation, either version 3 of the License, or
+## (at your option) any later version.
+##
+## This program is distributed in the hope that it will be useful,
+## but WITHOUT ANY WARRANTY; without even the implied warranty of
+## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+## GNU General Public License for more details.
+##
+## You should have received a copy of the GNU General Public License
+## along with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+glrxxdir = $(docdir)/%D%
+
+## ----------- ##
+## c++-types.  ##
+## ----------- ##
+
+%D%/c++-types.stamp: $(dependencies)
+$(nodist_%C%_c___types_SOURCES): %D%/c++-types.stamp
+       @test -f $@ || rm -f %D%/c++-types.stamp
+       @test -f $@ || $(MAKE) $(AM_MAKEFLAGS) %D%/c++-types.stamp
+CLEANFILES += \
+  $(nodist_%C%_c___types_SOURCES) %D%/c++-types.stamp
+CLEANDIRS += %D%/*.dSYM
+
+## -------------------- ##
+## Building & testing.  ##
+## -------------------- ##
+
+# Avoid using BUILT_SOURCES which is too global.
+$(%C%_c___types_OBJECTS): $(cxx_types_sources_generated)
+
+if ENABLE_CXX
+  check_PROGRAMS += %D%/c++-types
+  nodist_%C%_c___types_SOURCES =               \
+    %D%/c++-types.cc                           \
+    %D%/c++-types.hh
+  # Don't use gnulib's system headers.
+  %C%_c___types_CPPFLAGS = -I$(top_srcdir)/%D% -I$(top_builddir)/%D%
+  TESTS += %D%/c++-types.test
+endif ENABLE_CXX
+EXTRA_DIST += %D%/c++-types.yy %D%/c++-types.test
diff --git a/examples/c++/local.mk b/examples/c++/local.mk
index a41613fd..6af9ac94 100644
--- a/examples/c++/local.mk
+++ b/examples/c++/local.mk
@@ -15,6 +15,7 @@
 
 cxxdir = $(docdir)/%D%
 include %D%/calc++/local.mk
+include %D%/glr/local.mk
 
 ## -------- ##
 ## Simple.  ##
diff --git a/examples/c/glr/Makefile b/examples/c/glr/Makefile
index 6221ca9e..a56edb1f 100644
--- a/examples/c/glr/Makefile
+++ b/examples/c/glr/Makefile
@@ -1,7 +1,7 @@
 # This Makefile is designed to be simple and readable.  It does not
 # aim at portability.  It requires GNU Make.
 
-BASE = calc
+BASE = c++-types
 BISON = bison
 XSLTPROC = xsltproc
 
@@ -14,7 +14,7 @@ $(BASE): $(BASE).o
        $(CC) $(CFLAGS) -o $@ $^
 
 run: $(BASE)
-       @echo "Type arithmetic expressions.  Quit with ctrl-d."
+       @echo "Type C++ declarations or expressions.  Quit with ctrl-d."
        ./$<
 
 html: $(BASE).html