Re: several messages

[Joel E. Denny]

Hi Akim.

On Wed, 16 Sep 2009, Akim Demaille wrote:

> > How many S/R and R/R conflicts?  I'm also interested in conflicts that are
> > resolved by prec/assoc declarations.
> 
> There are no remaining conflicts.  The updated log has the figures on solved
> conflicts:

What do you mean by the "updated log"?  Did I miss an attachment 
somewhere?

> - 1143 in lalr/ielr
> - 64650 in full lr

Thanks.  This data demonstrates another motivation not to use canonical 
LR: when you're debugging conflicts using the parser tables, you don't 
want to deal with an order of magnitude more states or an order of 
magnitude more conflicts.  This motivation is timeless in that computer 
hardware improvements won't alleviate it.

> > It's good to see that the IELR computation time is barely worse than LALR.
> > Because IELR didn't split any states, the output files are of course
> > exactly the same.  However, that also means there may not have been much
> > for IELR to do, and so the timings may not reveal much about IELR's
> > complexity.  The number of conflicts would provide some insight here...
> > but maybe I'm getting off topic a little.

Using the grammar you sent me, I ran a script of mine to analyze the 
canonical LR versus LALR tables, and it confirms that no parser actions 
have changed for any viable prefix.  I say this just to give more 
confidence that IELR is working correctly when it concludes that LALR is 
sufficient for your grammar.

Also, all those conflicts indicate that IELR likely had much work to do 
even though it ran nearly as quickly as just LALR.  I was able to actually 
see some of the work it did by using '-Dlr.type=ielr --trace=ielr'.  The 
summary at the end of the trace is the best indicator.  The rest of the 
trace is a bit cryptic, I'm afraid.

> > (By the way, I've been meaning to add a test case for Bison that makes
> > sure the LALR and IELR parser tables are exactly the same for
> > parse-gram.y.  If they ever become different, we'll need to fix
> > parse-gram.y or start using IELR.)
> 
> Good point :)

I pushed the patch below to master and branch-2.5.

> > Wow.  What a jump.  I can see why you don't want this.  I have to admit
> > that I haven't spent much time exploring the combination of canonical-lr
> > and different values of lr.default-reductions.  Maybe it's bad that I
> > defaulted it to "accepting"?  I just didn't want anyone to argue that they
> > specified canonical LR but didn't get it.
> 
> I have no strong opinion about this.  After all, someone reading the doc about
> lr.type should be ready to read the section about lr.default-reductions.  We
> have to warn them.

That makes sense.  I still need to reorganize that documentation though.

> My figures are public, if you mean to use them in some
> form in the documentation, that would be fine with me.

Thanks.  Your figures are definitely interesting as a very bad case for 
canonical LR.

> I changed my mind when I saw how current GCCs talk to me.
> 
> $ cat /tmp/foo.cc
> void foo (float*) {}
> void foo (int*){}
> 
> int
> main()
> {
>  foo(1);
> }
> $ g++ -Wall /tmp/foo.cc
> /tmp/foo.cc: In function 'int main()':
> /tmp/foo.cc:7: error: call of overloaded 'foo(int)' is ambiguous
> /tmp/foo.cc:1: note: candidates are: void foo(float*) <near match>
> /tmp/foo.cc:2: note:                 void foo(int*) <near match>
> 
> and Emacs correctly understands this as a single error.

Ah, C++.  Well, that's a strong precedent.  I had only checked the C 
compiler previously, so I missed it.

> > BTW, I've not yet done any homework to see if any of this has been done
> > before.  Now that I write it down, it seems like such a simple premise, so
> > maybe it has been done many times.  I should probably have researched it
> > before banging out an implementation.  Maybe there's a better way already
> > discovered.
> 
> It seems that indeed, many many results were obtained about LR parsers, but
> many of them are now somewhat forgotten.  Yet, there are so many papers out
> there that I don't know what's the right means to fetch only the relevant
> ones.

I did do a quick search and saw that this issue has been discussed in 
various forms for Bison.  I still would like to find some published papers 
or complete implementations.  It's like looking for a needle in a 
haystack.  Maybe I'll write comp.compilers for advice.

> > > I can send ugrammar.y privately, if you wish.
> > 
> > I'd like to see that.  Thanks!
> 
> Will do right afterwards.

Thanks for sending that!

> Please, no dirty jokes about my grammar :)  I wish
> it was nicer in many places...

I haven't spent much time reading the .y file itself yet.  I've just run 
automated traces and analyses.  I'll let you know if I come up with any 
jokes later.  :)

>From 43aabb70a95ecbd20c76797c53554641c3576db4 Mon Sep 17 00:00:00 2001
From: Joel E. Denny <address@hidden>
Date: Sat, 26 Sep 2009 14:49:20 -0400
Subject: [PATCH] tests: check that parse-gram.y's IELR and LALR are identical.

* tests/atlocal.in (abs_top_srcdir): New shell variable.
* tests/regression.at (parse-gram.y: LALR = IELR): New test
group.
---
 ChangeLog           |    7 +++++++
 tests/atlocal.in    |    2 ++
 tests/regression.at |   21 +++++++++++++++++++++
 3 files changed, 30 insertions(+), 0 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index ca92292..f24be8a 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,10 @@
+2009-09-26  Joel E. Denny  <address@hidden>
+
+       tests: check that parse-gram.y's IELR and LALR are identical.
+       * tests/atlocal.in (abs_top_srcdir): New shell variable.
+       * tests/regression.at (parse-gram.y: LALR = IELR): New test
+       group.
+
 2009-09-19  Alex Rozenman  <address@hidden>
 
        Keep sub-messages aligned. Fix strings for translation.
diff --git a/tests/atlocal.in b/tests/atlocal.in
index 91ba674..2e46329 100644
--- a/tests/atlocal.in
+++ b/tests/atlocal.in
@@ -42,3 +42,5 @@ CONF_JAVA='@CONF_JAVA@'
 
 # We need egrep.
 : ${EGREP='@EGREP@'}
+
+abs_top_srcdir='@abs_top_srcdir@'
diff --git a/tests/regression.at b/tests/regression.at
index 6bfc77e..2482189 100644
--- a/tests/regression.at
+++ b/tests/regression.at
@@ -1237,3 +1237,24 @@ AT_COMPILE([[input]])
 AT_PARSER_CHECK([[./input]])
 
 AT_CLEANUP
+
+
+
+## --------------------------- ##
+## parse-gram.y: LALR = IELR.  ##
+## --------------------------- ##
+
+# If parse-gram.y's LALR and IELR parser tables ever begin to differ, we
+# need to fix parse-gram.y or start using IELR.
+
+AT_SETUP([[parse-gram.y: LALR = IELR]])
+
+# Avoid tests/bison's dark magic by processing a local copy of the
+# grammar.  Avoid differences in synclines by telling bison that the
+# output files have the same name.
+cp $abs_top_srcdir/src/parse-gram.y input.y
+AT_BISON_CHECK([[-o input.c -Dlr.type=lalr input.y && mv input.c lalr.c]])
+AT_BISON_CHECK([[-o input.c -Dlr.type=ielr input.y && mv input.c ielr.c]])
+AT_CHECK([[diff -u lalr.c ielr.c]])
+
+AT_CLEANUP
-- 
1.5.4.3