Re: glr2.cc: add an example

[Valentin Tolmer]

Hi Akim,

Thanks for the example, and sorry for the late reply, got swamped with work
and the bug was less than easy to track... I had the pleasure of
discovering the joys of `rr` for a time-traveling GDB, but I would have
hoped it wouldn't come to that.

Anyway, I pushed a patch to the glr2_cc branch on my github if you want to
have a look (https://github.com/nitnelave/bison/tree/glr2_cc). It was a
combination of a memory corruption when accessing the wrong field of an
union, and a badly translated loop from glr.c.

Cheers,

On Sat, Sep 26, 2020 at 5:19 PM Akim Demaille <akim.demaille@gmail.com>
wrote:

> 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
>
>

-- 
Valentin Tolmer