[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: glr2.cc: add an example
From: |
Valentin Tolmer |
Subject: |
Re: glr2.cc: add an example |
Date: |
Wed, 11 Nov 2020 19:03:22 +0100 |
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
- Re: glr2.cc: add an example,
Valentin Tolmer <=