From akim@epita.fr Tue Dec 12 12:55:16 2000
Received: from [163.5.255.10] (helo=hermes.epita.fr)
	by fencepost.gnu.org with esmtp (Exim 3.16 #1 (Debian))
	id 145tdy-0006qq-00
	for <bug-bison@gnu.org>; Tue, 12 Dec 2000 12:55:14 -0500
Received: from goa.lrde.epita.fr (mail@goa.lrde.epita.fr [10.223.13.2])
	by hermes.epita.fr id SAA15158
	Tue, 12 Dec 2000 18:50:16 GMT
Received: from nostromo.lrde.epita.fr ([10.223.13.52] ident=mail)
	by goa.lrde.epita.fr with esmtp (Exim 3.12 #1 (Debian))
	id 145thB-0007kV-00; Tue, 12 Dec 2000 18:58:33 +0100
Received: from akim by nostromo.lrde.epita.fr with local (Exim 3.20 #1 (Debian))
	id 145tgg-0005Zu-00; Tue, 12 Dec 2000 18:58:02 +0100
To: "Online Korea"<olk@olk.co.kr>
Cc: bug-bison@gnu.org
Subject: Re: Using alloca
References: <014100428181cb0SMTP7@smtp7.thrunet.com>
From: Akim Demaille <akim@epita.fr>
Date: 12 Dec 2000 18:58:02 +0100
In-Reply-To: "Online Korea"'s message of "Wed, 29 Nov 2000 03:30:06 +0900"
Message-ID: <mv466kpjzdh.fsf@nostromo.lrde.epita.fr>
Lines: 3
User-Agent: Gnus/5.0807 (Gnus v5.8.7) XEmacs/21.1 (Channel Islands)
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

Thanks for your suggestion.  The next release will provide a means not
to use alloca.  The interface is not settled, but we are aware of the
need.


From haberg@matematik.su.se Wed Dec 13 04:26:46 2000
Received: from knatte.tninet.se ([195.100.94.10])
	by fencepost.gnu.org with smtp (Exim 3.16 #1 (Debian))
	id 1468BS-0007l9-00
	for <bug-bison@gnu.org>; Wed, 13 Dec 2000 04:26:46 -0500
Received: (qmail 1373 invoked from network); 13 Dec 2000 10:26:42 +0100
Received: from delenn.tninet.se (HELO algonet.se) (195.100.94.104)
  by knatte.tninet.se with SMTP; 13 Dec 2000 10:26:42 +0100
Received: from  [195.100.226.136] (du136-226.ppp.su-anst.tninet.se [195.100.226.136])
 by delenn.tninet.se (BLUETAIL Mail Robustifier 2.2.1) with ESMTP
 id 535776.699601.976delenn-s2 for <bug-bison@gnu.org>
 ; Wed, 13 Dec 2000 10:26:41 +0100
X-Sender: haberg@pop.matematik.su.se (Unverified)
Message-Id: <v03110701b65ceec11f60@[195.100.226.134]>
In-Reply-To: <mv466kpjzdh.fsf@nostromo.lrde.epita.fr>
References: "Online Korea"'s message of "Wed, 29 Nov 2000 03:30:06 +0900"
 <014100428181cb0SMTP7@smtp7.thrunet.com>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Wed, 13 Dec 2000 10:25:33 +0100
To: bug-bison@gnu.org
From: Hans Aberg <haberg@matematik.su.se>
Subject: Re: Using alloca
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

At 18:58 +0100 0-12-12, Akim Demaille wrote:
>Thanks for your suggestion.  The next release will provide a means not
>to use alloca.  The interface is not settled, but we are aware of the
>need.

What is the advantage of using alloca over malloc?

  Hans Aberg




From haberg@matematik.su.se Wed Dec 13 18:25:19 2000
Received: from musse.tninet.se ([195.100.94.12])
	by fencepost.gnu.org with smtp (Exim 3.16 #1 (Debian))
	id 146LGx-00031I-00
	for <bug-bison@gnu.org>; Wed, 13 Dec 2000 18:25:19 -0500
Received: (qmail 13803 invoked from network); 14 Dec 2000 00:25:16 +0100
Received: from garibaldi.tninet.se (HELO algonet.se) (195.100.94.103)
  by musse.tninet.se with SMTP; 14 Dec 2000 00:25:16 +0100
Received: from  [195.100.226.140] (du140-226.ppp.su-anst.tninet.se [195.100.226.140])
 by garibaldi.tninet.se (BLUETAIL Mail Robustifier 2.2.1) with ESMTP
 id 516835.749914.976garibaldi-s1 for <bug-bison@gnu.org>
 ; Thu, 14 Dec 2000 00:25:14 +0100
X-Sender: haberg@pop.matematik.su.se (Unverified)
Message-Id: <v03110700b65db1e4f851@[195.100.226.154]>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Thu, 14 Dec 2000 00:24:01 +0100
To: Bison Bugs <bug-bison@gnu.org>
From: Hans Aberg <haberg@matematik.su.se>
Subject: Bison extra $$ assignment problem
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

I have found a problem with an extra assignment the parser that Bison
generates, which could cause a C++ program to fail. The section in
bison.simple is the following:

yyreduce:
  /* yyn is the number of a rule to reduce with.  */
  yylen = yyr2[yyn];

  /* If YYLEN is nonzero, implement the default value of the action:
     `{dollar}{dollar} = {dollar}1'.

     Otherwise, the following line sets YYVAL to the semantic value of
     the lookahead token.  This behavior is undocumented and Bison
     users should not rely upon it.  Assigning to YYVAL
     unconditionally makes the parser a bit smaller, and it avoids a
     GCC warning that YYVAL may be used uninitialized.  */
  yyval = yyvsp[1-yylen];

It is this extra assignment $$ = $1 that may cause problems under C++:

I used
#define YYSTYPE my_type
class my_type {
public:
...
  std::string text;
  std::auto_ptr<std::string> condition;
...
};

and a semantic action
     { $$.condition = std::auto_ptr<std::string>(new std::string($1.text)); }
and later, in another rule, the seemingly harmless action
(*)  { $$.condition = $1.condition; }

The problem is no this that auto_ptr own a pointer with is transferred to
another auto_ptr via assignment, and then sets its own pointer to 0. So
when Bison throws in the extra $$ = $1, the pointer that $1.condition owns
is transferred to $$.condition, and in the later semantic action (*), the
now 0 pointer of $1.condition is transferred to $$:

The result is that, instead of transferring a pointer from $1.condition to
$$.condition, it is deleted!

Under C this cannot happen because one is not allowed to write ones own
operator=.

But this means that if Bison should have official C++ support in the
future, this extra assignment cannot be there (or one should at least be
able to ensure it is not there by some Bison option).



  Hans Aberg




From akim@epita.fr Thu Dec 14 07:56:25 2000
Received: from [163.5.255.10] (helo=hermes.epita.fr)
	by fencepost.gnu.org with esmtp (Exim 3.16 #1 (Debian))
	id 146Xvr-0004Me-00
	for <bug-bison@gnu.org>; Thu, 14 Dec 2000 07:56:24 -0500
Received: from goa.lrde.epita.fr (mail@goa.lrde.epita.fr [10.223.13.2])
	by hermes.epita.fr id NAA07325
	Thu, 14 Dec 2000 13:55:20 GMT
Received: from nostromo.lrde.epita.fr ([10.223.13.52] ident=mail)
	by goa.lrde.epita.fr with esmtp (Exim 3.12 #1 (Debian))
	id 146Y3A-0007gj-00; Thu, 14 Dec 2000 14:03:56 +0100
Received: from akim by nostromo.lrde.epita.fr with local (Exim 3.20 #1 (Debian))
	id 146Y2e-0003LC-00; Thu, 14 Dec 2000 14:03:24 +0100
To: Hans Aberg <haberg@matematik.su.se>
Cc: bug-bison@gnu.org
Subject: Re: Using alloca
References: <014100428181cb0SMTP7@smtp7.thrunet.com>
	<v03110701b65ceec11f60@[195.100.226.134]>
From: Akim Demaille <akim@epita.fr>
Date: 14 Dec 2000 14:03:24 +0100
In-Reply-To: Hans Aberg's message of "Wed, 13 Dec 2000 10:25:33 +0100"
Message-ID: <mv4k893yx2b.fsf@nostromo.lrde.epita.fr>
Lines: 121
User-Agent: Gnus/5.0807 (Gnus v5.8.7) XEmacs/21.1 (Channel Islands)
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

>>>>> "Hans" == Hans Aberg <haberg@matematik.su.se> writes:

Hans> What is the advantage of using alloca over malloc?

Plenty!

Automatic Storage with Variable Size
------------------------------------

   The function `alloca' supports a kind of half-dynamic allocation in
which blocks are allocated dynamically but freed automatically.

   Allocating a block with `alloca' is an explicit action; you can
allocate as many blocks as you wish, and compute the size at run time.
But all the blocks are freed when you exit the function that `alloca'
was called from, just as if they were automatic variables declared in
that function.  There is no way to free the space explicitly.

   The prototype for `alloca' is in `stdlib.h'.  This function is a BSD
extension.

 - Function: void * alloca (size_t SIZE);
     The return value of `alloca' is the address of a block of SIZE
     bytes of memory, allocated in the stack frame of the calling
     function.

   Do not use `alloca' inside the arguments of a function call--you
will get unpredictable results, because the stack space for the
`alloca' would appear on the stack in the middle of the space for the
function arguments.  An example of what to avoid is `foo (x, alloca
(4), y)'.

`alloca' Example
................

   As an example of the use of `alloca', here is a function that opens
a file name made from concatenating two argument strings, and returns a
file descriptor or minus one signifying failure:

     int
     open2 (char *str1, char *str2, int flags, int mode)
     {
       char *name = (char *) alloca (strlen (str1) + strlen (str2) + 1);
       stpcpy (stpcpy (name, str1), str2);
       return open (name, flags, mode);
     }

Here is how you would get the same results with `malloc' and `free':

     int
     open2 (char *str1, char *str2, int flags, int mode)
     {
       char *name = (char *) malloc (strlen (str1) + strlen (str2) + 1);
       int desc;
       if (name == 0)
         fatal ("virtual memory exceeded");
       stpcpy (stpcpy (name, str1), str2);
       desc = open (name, flags, mode);
       free (name);
       return desc;
     }

   As you can see, it is simpler with `alloca'.  But `alloca' has
other, more important advantages, and some disadvantages.


Advantages of `alloca'
......................

   Here are the reasons why `alloca' may be preferable to `malloc':

   * Using `alloca' wastes very little space and is very fast.  (It is
     open-coded by the GNU C compiler.)

   * Since `alloca' does not have separate pools for different sizes of
     block, space used for any size block can be reused for any other
     size.  `alloca' does not cause memory fragmentation.

   * Nonlocal exits done with `longjmp' (*note Non-Local Exits::)
     automatically free the space allocated with `alloca' when they exit
     through the function that called `alloca'.  This is the most
     important reason to use `alloca'.

     To illustrate this, suppose you have a function
     `open_or_report_error' which returns a descriptor, like `open', if
     it succeeds, but does not return to its caller if it fails.  If
     the file cannot be opened, it prints an error message and jumps
     out to the command level of your program using `longjmp'.  Let's
     change `open2' (*note Alloca Example::) to use this subroutine:

          int
          open2 (char *str1, char *str2, int flags, int mode)
          {
            char *name = (char *) alloca (strlen (str1) + strlen (str2) + 1);
            stpcpy (stpcpy (name, str1), str2);
            return open_or_report_error (name, flags, mode);
          }

     Because of the way `alloca' works, the memory it allocates is
     freed even when an error occurs, with no special effort required.

     By contrast, the previous definition of `open2' (which uses
     `malloc' and `free') would develop a memory leak if it were
     changed in this way.  Even if you are willing to make more changes
     to fix it, there is no easy way to do so.


Disadvantages of `alloca'
.........................

   These are the disadvantages of `alloca' in comparison with `malloc':

   * If you try to allocate more memory than the machine can provide,
     you don't get a clean error message.  Instead you get a fatal
     signal like the one you would get from an infinite recursion;
     probably a segmentation violation (*note Program Error Signals::).

   * Some non-GNU systems fail to support `alloca', so it is less
     portable.  However, a slower emulation of `alloca' written in C is
     available for use on systems with this deficiency.



From haberg@matematik.su.se Thu Dec 14 10:26:12 2000
Received: from musse.tninet.se ([195.100.94.12])
	by fencepost.gnu.org with smtp (Exim 3.16 #1 (Debian))
	id 146aGp-0001C4-00
	for <bug-bison@gnu.org>; Thu, 14 Dec 2000 10:26:11 -0500
Received: (qmail 2984 invoked from network); 14 Dec 2000 16:26:08 +0100
Received: from garibaldi.tninet.se (195.100.94.103)
  by musse.tninet.se with SMTP; 14 Dec 2000 16:26:08 +0100
Received: from  [195.100.226.133] (du145-226.ppp.su-anst.tninet.se [195.100.226.145])
 by garibaldi.tninet.se (BLUETAIL Mail Robustifier 2.2.1) with ESMTP
 id 829285.804345.976garibaldi-s2
 ; Thu, 14 Dec 2000 15:32:25 +0100
X-Sender: haberg@pop.matematik.su.se
Message-Id: <v03110701b65e84911792@[195.100.226.133]>
In-Reply-To: <mv4k893yx2b.fsf@nostromo.lrde.epita.fr>
References: Hans Aberg's message of "Wed, 13 Dec 2000 10:25:33 +0100"
 <014100428181cb0SMTP7@smtp7.thrunet.com>
 <v03110701b65ceec11f60@[195.100.226.134]>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Thu, 14 Dec 2000 15:31:09 +0100
To: Akim Demaille <akim@epita.fr>
From: Hans Aberg <haberg@matematik.su.se>
Subject: Re: Using alloca
Cc: bug-bison@gnu.org
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

At 14:03 +0100 0-12-14, Akim Demaille wrote:
>Hans> What is the advantage of using alloca over malloc?
>
>Plenty!
...

Thank you for your detailed reply about the use of alloca.

I also received the following excellent description by Florian Krohm, but
sorrily enough, he didn't cc the Bison list (sorry Florian if you get upset
by me making your letter public!):

At 08:30 -0500 0-12-13, Florian Krohm wrote:
>Memory allocated with alloca is allocated on the stack.
>This is usually a cheap operation much cheaper than
>going through malloc. Also, when you return from a
>function that allocated some memory using alloca, that
>dynamic memory is automatically freed since the
>stack frame for that function gets thrown away. You
>can argue that this is convenient. You could also argue that
>is encourages sloppy coding practices.. You decide.
>
>As far as I know alloca is not part of POSIX, however it
>is part of X/Open. So it might not be available everywhere..

Akim Demaille wrote:
>   The prototype for `alloca' is in `stdlib.h'.  This function is a BSD
>extension.

On my computer it is in <alloca.h>. If it is found in <stdlib.h>, that C
compiler will probably not conform to the C ISO-IEC-ANSI standard.

>Advantages of `alloca'
>......................
>   Here are the reasons why `alloca' may be preferable to `malloc':
>
>   * Using `alloca' wastes very little space and is very fast.  (It is
>     open-coded by the GNU C compiler.)
>
>   * Since `alloca' does not have separate pools for different sizes of
>     block, space used for any size block can be reused for any other
>     size.  `alloca' does not cause memory fragmentation.

The reason malloc & C++ operator new() often are slow is often that they
are poorly written. For example, a way to avoid memory fragmentation with
malloc is to only allocate block of size 2^n in separate sections, one for
each n. I guess alloca is still going to be faster though.

>   * Nonlocal exits done with `longjmp' (*note Non-Local Exits::)
>     automatically free the space allocated with `alloca' when they exit
>     through the function that called `alloca'.  This is the most
>     important reason to use `alloca'.

The way to do it under C++ is to wrap up & delete in a class and then to
use exceptions instead of longjump. Then it makes no difference if one is
using operator new or alloca.

>Disadvantages of `alloca'
>.........................
>
>   These are the disadvantages of `alloca' in comparison with `malloc':
>
>   * If you try to allocate more memory than the machine can provide,
>     you don't get a clean error message.  Instead you get a fatal
>     signal like the one you would get from an infinite recursion;
>     probably a segmentation violation (*note Program Error Signals::).

I surmise that even if the OS knows how to enlarge the stack, allocating
large chunks with alloca might be slow, as the stack then must be enlarged.

>   * Some non-GNU systems fail to support `alloca', so it is less
>     portable.  However, a slower emulation of `alloca' written in C is
>     available for use on systems with this deficiency.

I gather one must have a function that is called when the function calling
alloca expires. In C++ that is not so difficult (just allocate an automatic
variable, and use its "delete"), but I wonder how to it in C.

Also add the alloca disadvantage
  * alloca cannot be used if the dynamic allocation should live longer
    than the function it was called from.


  Hans Aberg




From haberg@matematik.su.se Fri Dec 15 12:52:24 2000
Received: from knatte.tninet.se ([195.100.94.10])
	by fencepost.gnu.org with smtp (Exim 3.16 #1 (Debian))
	id 146z1r-0000yv-00
	for <bug-bison@gnu.org>; Fri, 15 Dec 2000 12:52:23 -0500
Received: (qmail 29614 invoked from network); 15 Dec 2000 18:52:05 +0100
Received: from garibaldi.tninet.se (HELO algonet.se) (195.100.94.103)
  by knatte.tninet.se with SMTP; 15 Dec 2000 18:52:05 +0100
Received: from  [195.100.226.132] (du132-226.ppp.su-anst.tninet.se [195.100.226.132])
 by garibaldi.tninet.se (BLUETAIL Mail Robustifier 2.2.1) with ESMTP
 id 824974.902723.976garibaldi-s2 for <bug-bison@gnu.org>
 ; Fri, 15 Dec 2000 18:52:03 +0100
X-Sender: haberg@pop.matematik.su.se (Unverified)
Message-Id: <v03110700b66003d6d507@[195.100.226.162]>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Fri, 15 Dec 2000 18:51:00 +0100
To: Bison Bugs <bug-bison@gnu.org>
From: Hans Aberg <haberg@matematik.su.se>
Subject: Faster token table lookups
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

Token table lookups in the parser that Bison generates (cf. the manual, the
%token_table option & sec 4.2.1) can be speeded up if Bison writes a token
table with the names sorted alphabetically: A search in yytname takes now
average linear time; by contrast, a sorted table can be searched in at most
log_2 time.

The suggest that Bison writes another table with pairs
struct name_index_type {
  char* name;
  long index;
};
in an array
name_index_type yytname_index[] = { ... };
name_index_type yytname_index_size[] = ...;

where the "name" fields are sorted alphabetically, "index" is the index
number that Bison uses.

A search algorithm (in C) for such a sorted table by halving intervals is:

long find_sorted(name_index_type a[], unsigned long size, const char* s) {
  unsigned long low = 0, high = size;
  while (low != high) {
    int i = low + (high - low)/2;
    int c = std::strcmp(s, a[i].text);
    switch ((c > 0) - (c < 0)) {
      case -1: high = i; break;
      case 1: low = i + 1; break;
      default: return a[i].index;
    }
  }
  return -1;
}

which returns -1 if the lookup s was not found; otherwise the return is the
index of the found name in the table. -- I.e., one should call
   find_sorted(yytname_index, yytname_index_size, my_search_string);
to find which number Bison is using.

  Hans Aberg




From akim@epita.fr Tue Dec 19 08:40:25 2000
Received: from [163.5.255.10] (helo=hermes.epita.fr)
	by fencepost.gnu.org with esmtp (Exim 3.16 #1 (Debian))
	id 148N0D-0002BU-00
	for <bug-bison@gnu.org>; Tue, 19 Dec 2000 08:40:25 -0500
Received: from goa.lrde.epita.fr (mail@goa.lrde.epita.fr [10.223.13.2])
	by hermes.epita.fr id OAA14093
	Tue, 19 Dec 2000 14:39:13 GMT
Received: from nostromo.lrde.epita.fr ([10.223.13.52] ident=mail)
	by goa.lrde.epita.fr with esmtp (Exim 3.12 #1 (Debian))
	id 148N0E-0003LK-00; Tue, 19 Dec 2000 14:40:26 +0100
Received: from akim by nostromo.lrde.epita.fr with local (Exim 3.20 #1 (Debian))
	id 148N0B-0006xR-00; Tue, 19 Dec 2000 14:40:23 +0100
To: Hans Aberg <haberg@matematik.su.se>
Cc: Bison Bugs <bug-bison@gnu.org>
Subject: Re: Bison-1.28a Skeleton file #line suggest
References: <v03110701b601ecacead0@[195.100.226.132]>
From: Akim Demaille <akim@epita.fr>
Date: 19 Dec 2000 14:40:23 +0100
In-Reply-To: Hans Aberg's message of "Thu, 5 Oct 2000 10:37:20 +0200"
Message-ID: <mv4itogfs1k.fsf@nostromo.lrde.epita.fr>
Lines: 8
User-Agent: Gnus/5.0807 (Gnus v5.8.7) XEmacs/21.1 (Channel Islands)
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

>>>>> "Hans" == Hans Aberg <haberg@matematik.su.se> writes:

Hans> It strikes me though that it would be better to allow one having
Hans> lines with %line in the skeleton file, and Bison then supplies
Hans> the complete #line <line-number> "<file-name>"

It's done now.  But it still uses #line as a marker, not %line.
Thanks for the suggestion.


From akim@epita.fr Tue Dec 19 08:42:03 2000
Received: from [163.5.255.10] (helo=hermes.epita.fr)
	by fencepost.gnu.org with esmtp (Exim 3.16 #1 (Debian))
	id 148N1m-0002Cg-00
	for <bug-bison@gnu.org>; Tue, 19 Dec 2000 08:42:02 -0500
Received: from goa.lrde.epita.fr (mail@goa.lrde.epita.fr [10.223.13.2])
	by hermes.epita.fr id OAA14327
	Tue, 19 Dec 2000 14:41:14 GMT
Received: from nostromo.lrde.epita.fr ([10.223.13.52] ident=mail)
	by goa.lrde.epita.fr with esmtp (Exim 3.12 #1 (Debian))
	id 148N2B-0003M5-00; Tue, 19 Dec 2000 14:42:27 +0100
Received: from akim by nostromo.lrde.epita.fr with local (Exim 3.20 #1 (Debian))
	id 148N29-0006yB-00; Tue, 19 Dec 2000 14:42:25 +0100
To: Hans Aberg <haberg@matematik.su.se>
Cc: Bison Bugs <bug-bison@gnu.org>
Subject: Re: Faster token table lookups
References: <v03110700b66003d6d507@[195.100.226.162]>
From: Akim Demaille <akim@epita.fr>
Date: 19 Dec 2000 14:42:25 +0100
In-Reply-To: Hans Aberg's message of "Fri, 15 Dec 2000 18:51:00 +0100"
Message-ID: <mv4elz4fry6.fsf@nostromo.lrde.epita.fr>
Lines: 17
User-Agent: Gnus/5.0807 (Gnus v5.8.7) XEmacs/21.1 (Channel Islands)
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

>>>>> "Hans" == Hans Aberg <haberg@matematik.su.se> writes:

Hans> Token table lookups in the parser that Bison generates (cf. the
Hans> manual, the %token_table option & sec 4.2.1) can be speeded up
Hans> if Bison writes a token table with the names sorted
Hans> alphabetically: A search in yytname takes now average linear
Hans> time; by contrast, a sorted table can be searched in at most
Hans> log_2 time.

Hi Hans,

I don't understand your point.  AFAIK we never lookup for anything in
this table.  It's used the other way round: we have the token numbers,
we want to know their `human' names, and that a simple matter of
reading a cell of an array.

So I don't know what you are talking about.


From haberg@matematik.su.se Tue Dec 19 10:57:36 2000
Received: from hromeo.algonet.se ([194.213.74.51])
	by fencepost.gnu.org with smtp (Exim 3.16 #1 (Debian))
	id 148P8x-0007hW-00
	for <bug-bison@gnu.org>; Tue, 19 Dec 2000 10:57:36 -0500
Received: (qmail 23609 invoked from network); 19 Dec 2000 16:57:27 +0100
Received: from delenn.tninet.se (HELO algonet.se) (195.100.94.104)
  by hromeo.algonet.se with SMTP; 19 Dec 2000 16:57:27 +0100
Received: from  [195.100.226.144] (du144-226.ppp.su-anst.tninet.se [195.100.226.144])
 by delenn.tninet.se (BLUETAIL Mail Robustifier 2.2.1) with ESMTP
 id 480598.241445.977delenn-s0
 ; Tue, 19 Dec 2000 16:57:25 +0100
X-Sender: haberg@pop.matematik.su.se
Message-Id: <v03110700b6652eba88fe@[195.100.226.134]>
In-Reply-To: <mv4elz4fry6.fsf@nostromo.lrde.epita.fr>
References: Hans Aberg's message of "Fri, 15 Dec 2000 18:51:00 +0100"
 <v03110700b66003d6d507@[195.100.226.162]>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Tue, 19 Dec 2000 16:45:46 +0100
To: Akim Demaille <akim@epita.fr>
From: Hans Aberg <haberg@matematik.su.se>
Subject: Re: Faster token table lookups
Cc: Bison Bugs <bug-bison@gnu.org>
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

At 14:42 +0100 0-12-19, Akim Demaille wrote:
>> Token table lookups in the parser that Bison generates (cf. the
>> manual, the %token_table option & sec 4.2.1) can be speeded up
>> if Bison writes a token table with the names sorted
>> alphabetically
...
>I don't understand your point.  AFAIK we never lookup for anything in
>this table.  It's used the other way round: we have the token numbers,
>we want to know their `human' names, and that a simple matter of
>reading a cell of an array.
>
>So I don't know what you are talking about.

It would merely be a convenience to those that want to make a lot of name
table lookups. I think there is a suggestion one can implement it in the
lexer function yylex: instead of returning a macro number directly, it
makes a table lookup, and returns that number to Bison.

For example,
  int lookup(const char*);  // Make a string lookup & return the Bison macro
                            // number
  %token implies "=>"
and instead of
  yylex() {
    ...
    return implies;
    ...
  }
one writes
  yylex() {
    ...
    return lookup("=>");
    ...
  }

This makes the macro name "implies" unnecessary, and one oculd have skipped
it, if
  %token "=>"
would have been legal.

This could be convenient if speed isn't crucial, if one does not want to
invent a lot of macro names.

-- I haven't used that setup myself. This is how I figure it might be used
though.

-- Normally, this table would not be used at all, and it should be either
an option to have it written out, or one could let the linker remove it.

  Hans Aberg




From haberg@matematik.su.se Tue Dec 19 10:57:39 2000
Received: from hromeo.algonet.se ([194.213.74.51])
	by fencepost.gnu.org with smtp (Exim 3.16 #1 (Debian))
	id 148P90-0007he-00
	for <bug-bison@gnu.org>; Tue, 19 Dec 2000 10:57:38 -0500
Received: (qmail 23669 invoked from network); 19 Dec 2000 16:57:31 +0100
Received: from delenn.tninet.se (HELO algonet.se) (195.100.94.104)
  by hromeo.algonet.se with SMTP; 19 Dec 2000 16:57:31 +0100
Received: from  [195.100.226.144] (du144-226.ppp.su-anst.tninet.se [195.100.226.144])
 by delenn.tninet.se (BLUETAIL Mail Robustifier 2.2.1) with ESMTP
 id 821498.241448.977delenn-s0
 ; Tue, 19 Dec 2000 16:57:28 +0100
X-Sender: haberg@pop.matematik.su.se
Message-Id: <v03110701b66533349638@[195.100.226.134]>
In-Reply-To: <mv4itogfs1k.fsf@nostromo.lrde.epita.fr>
References: Hans Aberg's message of "Thu, 5 Oct 2000 10:37:20 +0200"
 <v03110701b601ecacead0@[195.100.226.132]>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Tue, 19 Dec 2000 16:46:51 +0100
To: Akim Demaille <akim@epita.fr>
From: Hans Aberg <haberg@matematik.su.se>
Subject: Re: Bison-1.28a Skeleton file #line suggest
Cc: Bison Bugs <bug-bison@gnu.org>
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

At 14:40 +0100 0-12-19, Akim Demaille wrote:
>Hans> It strikes me though that it would be better to allow one having
>Hans> lines with %line in the skeleton file, and Bison then supplies
>Hans> the complete #line <line-number> "<file-name>"
>
>It's done now.  But it still uses #line as a marker, not %line.
>Thanks for the suggestion.

You are welcome.

  Hans Aberg




From haberg@matematik.su.se Tue Dec 19 10:57:44 2000
Received: from angel.algonet.se ([194.213.74.112])
	by fencepost.gnu.org with smtp (Exim 3.16 #1 (Debian))
	id 148P96-0007hr-00
	for <bug-bison@gnu.org>; Tue, 19 Dec 2000 10:57:44 -0500
Received: (qmail 6440 invoked from network); 19 Dec 2000 16:57:38 +0100
Received: from delenn.tninet.se (HELO algonet.se) (195.100.94.104)
  by angel.algonet.se with SMTP; 19 Dec 2000 16:57:38 +0100
Received: from  [195.100.226.144] (du144-226.ppp.su-anst.tninet.se [195.100.226.144])
 by delenn.tninet.se (BLUETAIL Mail Robustifier 2.2.1) with ESMTP
 id 130879.241456.977delenn-s0 for <bug-bison@gnu.org>
 ; Tue, 19 Dec 2000 16:57:36 +0100
X-Sender: haberg@pop.matematik.su.se
Message-Id: <v03110704b66534d3f7be@[195.100.226.134]>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Tue, 19 Dec 2000 16:56:15 +0100
To: Bison Bugs <bug-bison@gnu.org>
From: Hans Aberg <haberg@matematik.su.se>
Subject: Bison & Unicode
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

One possibility to get Bison to work with Unicode would be enhance it so it
can understand character sets (and "start conditions"), and then use it
twice, as a lexer and then as a parser. Would that be too inefficient?

  Hans Aberg




From haberg@matematik.su.se Tue Dec 19 19:04:59 2000
Received: from knatte.tninet.se ([195.100.94.10])
	by fencepost.gnu.org with smtp (Exim 3.16 #1 (Debian))
	id 148Wkc-0002YW-00
	for <bug-bison@gnu.org>; Tue, 19 Dec 2000 19:04:59 -0500
Received: (qmail 6353 invoked from network); 20 Dec 2000 01:04:56 +0100
Received: from delenn.tninet.se (HELO algonet.se) (195.100.94.104)
  by knatte.tninet.se with SMTP; 20 Dec 2000 01:04:56 +0100
Received: from  [195.100.226.134] (du129-226.ppp.su-anst.tninet.se [195.100.226.129])
 by delenn.tninet.se (BLUETAIL Mail Robustifier 2.2.1) with ESMTP
 id 84416.270695.977delenn-s1
 ; Wed, 20 Dec 2000 01:04:55 +0100
X-Sender: haberg@pop.matematik.su.se
Message-Id: <v03110703b665a4873728@[195.100.226.134]>
In-Reply-To: <C41D82BF5BACD311B1B600A0C9EAF0CF1B1323@es01-bos>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Wed, 20 Dec 2000 01:03:55 +0100
To: "Keefe, Dan" <Dan_Keefe@bmc.com>
From: Hans Aberg <haberg@matematik.su.se>
Subject: RE: Bison & Unicode
Cc: Bison Bugs <bug-bison@gnu.org>
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

At 14:13 -0600 0-12-19, Keefe, Dan wrote:
>While I agree that this would be a possible solution, I think that keeping
>a parser (Bison) and a lexer (Flex) separate makes more sense.  Currently
>Flex (or lex) is responsible for tokenization and makes these tokens available
>for Bison (or yacc). Since Bison only cares about what type of token it
>gets in >order to determine what rule to follow, there should be no
>dependency between >the current state in the parser and the token input
>stream structure since the >token type can be determined in the lexer
>exclusively.  On the other hand, >semantic actions need to avail
>themselves of the text (or converted value of >the text) of the current
>token.  In this situation, it must be the case that >the parser has
>knowledge of at least the data type being used by the lexer in >order to
>pass this data to other functional parts of the program.  It seems to >me
>that exposing the lexer's data type is the fundamental problem and this
>>could be done by commonly declared type for the lexer and parser.
>Although it >may be nice to also expose the encoding scheme and code page
>to the parser, >this is certainly not necessary since this can be
>encapsulated exterior to the >parser.
>
>I think that embedding lexical analysis capability within a parser would
>reduce the level of abstraction of these separate concerns and cause more
>>problems than it would be worth.

Which lexical analyzer do you intend to you with Unicode? :-)

-- By the way, there is a combined lexical-analyzer/compiler-compiler,
http://www.antlr.org/.

-- But in my post I suggested that Bison is invoked twice, so
lexing/parsing would still be separate (yyparse of one becomes yylex of the
other). Even though I think that if one create a "language hierarchy", with
the sentences of the language below being the tokens of the one above, it
can be reduced to a single grammar, by simply making the sentence-tokens
into variables.

-- I have no idea now do get by doing such a thing; I just want to know if
there is some obvious reason for not trying it, such as efficiency.

  Hans Aberg
                  * Email: Hans Aberg <mailto:haberg@member.ams.org>
                  * Home Page: <http://www.matematik.su.se/~haberg/>
                  * AMS member listing: <http://www.ams.org/cml/>




From akim@epita.fr Wed Dec 20 05:42:29 2000
Received: from [163.5.255.10] (helo=hermes.epita.fr)
	by fencepost.gnu.org with esmtp (Exim 3.16 #1 (Debian))
	id 148ghZ-0001Kc-00
	for <bug-bison@gnu.org>; Wed, 20 Dec 2000 05:42:29 -0500
Received: from goa.lrde.epita.fr (mail@goa.lrde.epita.fr [10.223.13.2])
	by hermes.epita.fr id LAA07806
	Wed, 20 Dec 2000 11:41:21 GMT
Received: from nostromo.lrde.epita.fr ([10.223.13.52] ident=mail)
	by goa.lrde.epita.fr with esmtp (Exim 3.12 #1 (Debian))
	id 148gho-00089k-00; Wed, 20 Dec 2000 11:42:44 +0100
Received: from akim by nostromo.lrde.epita.fr with local (Exim 3.20 #1 (Debian))
	id 148ghl-0002BH-00; Wed, 20 Dec 2000 11:42:41 +0100
To: Hans Aberg <haberg@matematik.su.se>
Cc: Bison Bugs <bug-bison@gnu.org>
Subject: Re: Faster token table lookups
References: <v03110700b66003d6d507@[195.100.226.162]>
	<v03110700b6652eba88fe@[195.100.226.134]>
From: Akim Demaille <akim@epita.fr>
Date: 20 Dec 2000 11:42:41 +0100
In-Reply-To: Hans Aberg's message of "Tue, 19 Dec 2000 16:45:46 +0100"
Message-ID: <mv43dfjwezi.fsf@nostromo.lrde.epita.fr>
Lines: 9
User-Agent: Gnus/5.0807 (Gnus v5.8.7) XEmacs/21.1 (Channel Islands)
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

>>>>> "Hans" == Hans Aberg <haberg@matematik.su.se> writes:

Hans> It would merely be a convenience to those that want to make a
Hans> lot of name table lookups. I think there is a suggestion one can
Hans> implement it in the lexer function yylex: instead of returning a
Hans> macro number directly, it makes a table lookup, and returns that
Hans> number to Bison.

Then why not, send a patch :)


From haberg@matematik.su.se Wed Dec 20 15:48:50 2000
Received: from musse.tninet.se ([195.100.94.12])
	by fencepost.gnu.org with smtp (Exim 3.16 #1 (Debian))
	id 148qAL-0006OA-00
	for <bug-bison@gnu.org>; Wed, 20 Dec 2000 15:48:50 -0500
Received: (qmail 4591 invoked from network); 20 Dec 2000 21:48:47 +0100
Received: from delenn.tninet.se (HELO algonet.se) (195.100.94.104)
  by musse.tninet.se with SMTP; 20 Dec 2000 21:48:47 +0100
Received: from  [195.100.226.148] (du148-226.ppp.su-anst.tninet.se [195.100.226.148])
 by delenn.tninet.se (BLUETAIL Mail Robustifier 2.2.1) with ESMTP
 id 293943.345325.977delenn-s0
 ; Wed, 20 Dec 2000 21:48:45 +0100
X-Sender: haberg@pop.matematik.su.se (Unverified)
Message-Id: <v03110703b66689d04740@[195.100.226.130]>
In-Reply-To: <mv43dfjwezi.fsf@nostromo.lrde.epita.fr>
References: Hans Aberg's message of "Tue, 19 Dec 2000 16:45:46 +0100"
 <v03110700b66003d6d507@[195.100.226.162]>
 <v03110700b6652eba88fe@[195.100.226.134]>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Wed, 20 Dec 2000 21:48:31 +0100
To: Akim Demaille <akim@epita.fr>
From: Hans Aberg <haberg@matematik.su.se>
Subject: Re: Faster token table lookups
Cc: Bison Bugs <bug-bison@gnu.org>
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

At 11:42 +0100 0-12-20, Akim Demaille wrote:
>> ... to those that want to make a
>> lot of name table lookups. I think there is a suggestion one can
>> implement it in the lexer function yylex: instead of returning a
>> macro number directly, it makes a table lookup, and returns that
>> number to Bison.
...
>Then why not, send a patch :)

If it is a Bison patch you are asking for, I may do so if I start to use
the feature. The implementation itself is not so difficult, I think: Just
put the names on a std::map together with the Bison lookup numbers as
values, and then write that map out. Then all you at Gnu has to do is
turning the patch over to the Gnu C++-to-C rewriting team. :-)

- Actually, it is OK with Bison to simply write
  %token "=>"
instead of
  %token implies "=>"
and if one is doing that, the only way to find Bison's lookup number in the
yylex function is to use the lookup table.

- One could speed up the lookup even further by caching the numbers so
found, even though I do not see the details of such an implementation yet.

  Hans Aberg




From haberg@matematik.su.se Fri Dec 22 05:23:53 2000
Received: from knatte.tninet.se ([195.100.94.10])
	by fencepost.gnu.org with smtp (Exim 3.16 #1 (Debian))
	id 149PMf-0001M2-00
	for <bug-bison@gnu.org>; Fri, 22 Dec 2000 05:23:53 -0500
Received: (qmail 24575 invoked from network); 22 Dec 2000 11:23:50 +0100
Received: from delenn.tninet.se (HELO algonet.se) (195.100.94.104)
  by knatte.tninet.se with SMTP; 22 Dec 2000 11:23:50 +0100
Received: from  [195.100.226.150] (du150-226.ppp.su-anst.tninet.se [195.100.226.150])
 by delenn.tninet.se (BLUETAIL Mail Robustifier 2.2.1) with ESMTP
 id 482054.480624.977delenn-s0
 ; Fri, 22 Dec 2000 11:23:44 +0100
X-Sender: haberg@pop.matematik.su.se (Unverified)
Message-Id: <v03110700b668d412b91c@[195.100.226.161]>
In-Reply-To: <mv43dfjwezi.fsf@nostromo.lrde.epita.fr>
References: Hans Aberg's message of "Tue, 19 Dec 2000 16:45:46 +0100"
 <v03110700b66003d6d507@[195.100.226.162]>
 <v03110700b6652eba88fe@[195.100.226.134]>
Mime-Version: 1.0
Content-Type: multipart/mixed; boundary="============_-1234641871==_============"
Date: Fri, 22 Dec 2000 11:21:31 +0100
To: Akim Demaille <akim@epita.fr>
From: Hans Aberg <haberg@matematik.su.se>
Subject: Re: Faster token table lookups
Cc: Bison Bugs <bug-bison@gnu.org>
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

--============_-1234641871==_============
Content-Type: text/plain; charset="us-ascii"

At 11:42 +0100 0-12-20, Akim Demaille wrote:
>> It would merely be a convenience to those that want to make a
>> lot of name table lookups. I think there is a suggestion one can
>> implement it in the lexer function yylex: instead of returning a
>> macro number directly, it makes a table lookup, and returns that
>> number to Bison.
>
>Then why not, send a patch :)

I made that patch: The patched file "output.c" is attached. (Instructions
for putting it in, see below.)

I realized that it was unnecessary to sort the names, but merely an array
with the typecodes, and a comparison function using the unsorted lookup
"tags" table expanding to the lookup names. Then I applied a heapsort to
that, with max number of comparisons O(n log n), where n is the table size.
Writing it out then was simple; just a modification of the script Bison
uses to wrote out the unsorted table.

- It also writes out two functions that can be used to find the typecodes:
  int yytypecode(const char* s);
  int yytypecode_cache(const char* s, int* cache);
using fast binary search, at most 1 + log_2 n comparisons.

- These functions will translate to Yacc numbers if those are used; with
%raw, they will produce Bison's internal numbers.

- If the name-prefix is changed, the "yy" of these functions will change
accordingly (by two extra written out macros).

- If the name is not found, both functions return -1.

- One simply uses these functions as replacements for the token macros:
If
  %token identifier
is declared, one can in the lexer write
  return yytokencode("identifier");
And if
  %token "=>"
one can write
  return yytokencode("\"=>\"");
including the extra as the name on the table us exactly "=>" and not =>.
A character code '+' would be reached with
  return yytokencode("\'+\'");

The yytypecode_cache function can be used to cache the lookup number so it
only lookup the number once: If the "cache" argument is NULL or have a
dereferenced value < -1, a lookup is made just as in the case of
yytokencode(). If is != NULL and the dereferenced value < -1, the lookup
value will be written into it. And if it is != NULL and the dereferenced
value >= -1, it simply returns that value.

So one simply uses it as follows:
  int identifier_ = -2; /* Define a cache */
  ...
  return yytypecode_cache("identifier", &identifier_);

Then, the first time yytypecode_cache is called, it will make a table
lookup, but on subsequent calls, it will merely use the lookup number found
earlier.

- In order to implement the patch, one should add between output_stos() and
output_rule_data() the following
  #define SWAP(x, y) ...
  static void adjust(int tc[], int m, register int n) ...
  static void output_name_typecode_table(void) ...
In output_rule_data(), one should add the
  output_name_typecode_table();
call right after
    /* add a NULL entry to list of tokens */
  fprintf (ftable, ", NULL\n};\n");
And in output_headers() one should add the lines
  fprintf (ftable, "#define yytypecode %stypecode\n", spec_name_prefix);
  fprintf (ftable, "#define yytypecode_cache %stypecode_cache\n",
    spec_name_prefix);
in the "if (spec_name_prefix)" conditional.

--============_-1234641871==_============
Content-Type: text/plain; name="output.c"; charset="us-ascii"
Content-Disposition: attachment; filename="output.c"

/* Output the generated parsing program for bison,
   Copyright (C) 1984, 1986, 1989, 1992, 2000 Free Software Foundation, Inc.

   This file is part of Bison, the GNU Compiler Compiler.

   Bison 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 2, or (at your option)
   any later version.

   Bison 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 Bison; see the file COPYING.  If not, write to the Free
   Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
   02111-1307, USA.  */


/* The parser tables consist of these tables.
   Starred ones needed only for the semantic parser.
   Double starred are output only if switches are set.

   yytranslate = vector mapping yylex's token numbers into bison's token
   numbers.

   ** yytname = vector of string-names indexed by bison token number

   ** yytoknum = vector of yylex token numbers corresponding to entries
   in yytname

   yyrline = vector of line-numbers of all rules.  For yydebug printouts.

   yyrhs = vector of items of all rules.
   This is exactly what ritems contains.  For yydebug and for semantic
   parser.

   yyprhs[r] = index in yyrhs of first item for rule r.

   yyr1[r] = symbol number of symbol that rule r derives.

   yyr2[r] = number of symbols composing right hand side of rule r.

   * yystos[s] = the symbol number of the symbol that leads to state s.

   yydefact[s] = default rule to reduce with in state s,
   when yytable doesn't specify something else to do.
   Zero means the default is an error.

   yydefgoto[i] = default state to go to after a reduction of a rule that
   generates variable ntokens + i, except when yytable
   specifies something else to do.

   yypact[s] = index in yytable of the portion describing state s.
   The lookahead token's type is used to index that portion
   to find out what to do.

   If the value in yytable is positive,
   we shift the token and go to that state.

   If the value is negative, it is minus a rule number to reduce by.

   If the value is zero, the default action from yydefact[s] is used.

   yypgoto[i] = the index in yytable of the portion describing
   what to do after reducing a rule that derives variable i + ntokens.
   This portion is indexed by the parser state number, s,
   as of before the text for this nonterminal was read.
   The value from yytable is the state to go to if
   the corresponding value in yycheck is s.

   yytable = a vector filled with portions for different uses,
   found via yypact and yypgoto.

   yycheck = a vector indexed in parallel with yytable.
   It indicates, in a roundabout way, the bounds of the
   portion you are trying to examine.

   Suppose that the portion of yytable starts at index p
   and the index to be examined within the portion is i.
   Then if yycheck[p+i] != i, i is outside the bounds
   of what is actually allocated, and the default
   (from yydefact or yydefgoto) should be used.
   Otherwise, yytable[p+i] should be used.

   YYFINAL = the state number of the termination state.
   YYFLAG = most negative short int.  Used to flag ??
   YYNTBASE = ntokens.
*/

#include "system.h"
#include "getargs.h"
#include "xalloc.h"
#include "files.h"
#include "gram.h"
#include "LR0.h"
#include "complain.h"
#include "output.h"
#include "lalr.h"
#include "reader.h"
#include "conflicts.h"

extern void berror PARAMS((const char *));



static int nvectors;
static int nentries;
static short **froms;
static short **tos;
static short *tally;
static short *width;
static short *actrow;
static short *state_count;
static short *order;
static short *base;
static short *pos;
static short *table;
static short *check;
static int lowzero;
static int high;



static inline void
output_short_table (FILE *out,
		    const char *table_name,
		    short *short_table,
		    short first_value,
		    short begin, short end)
{
  int i, j;

  fprintf (out, "static const short %s[] = {%6d", table_name, first_value);

  j = 10;
  for (i = begin; i < end; i++)
    {
      putc (',', out);

      if (j >= 10)
	{
	  putc ('\n', out);
	  j = 1;
	}
      else
	{
	  j++;
	}

      fprintf (out, "%6d", short_table[i]);
    }

  fprintf (out, "\n};\n");
}


/*--------------------------------------------------------------.
| output_headers -- Output constant strings to the beginning of |
| certain files.                                                |
`--------------------------------------------------------------*/

#define	GUARDSTR	\
"\n\
#include \"%s\"\n\
extern int yyerror;\n\
extern int yycost;\n\
extern char * yymsg;\n\
extern YYSTYPE yyval;\n\
\n\
yyguard(n, yyvsp, yylsp)\n\
register int n;\n\
register YYSTYPE *yyvsp;\n\
register YYLTYPE *yylsp;\n\
{\n\
  yyerror = 0;\n\
  yycost = 0;\n\
  yymsg = 0;\n\
  switch (n)\n\
    {"

#define	ACTSTR		\
"\n\
#include \"%s\"\n\
extern YYSTYPE yyval;\n\
extern int yychar;\n\
\n\
yyaction(n, yyvsp, yylsp)\n\
register int n;\n\
register YYSTYPE *yyvsp;\n\
register YYLTYPE *yylsp;\n\
{\n\
  switch (n)\n\
    {"

#define	ACTSTR_SIMPLE	"\n  switch (yyn) {\n"

void
output_headers (void)
{
  if (semantic_parser)
    fprintf (fguard, GUARDSTR, attrsfile);

  if (no_parser_flag)
    return;

  fprintf (faction, (semantic_parser ? ACTSTR : ACTSTR_SIMPLE), attrsfile);
/*  if (semantic_parser)	JF moved this below
    fprintf(ftable, "#include \"%s\"\n", attrsfile);
  fprintf(ftable, "#include <stdio.h>\n\n");
*/

  /* Rename certain symbols if -p was specified.  */
  if (spec_name_prefix)
    {
      fprintf (ftable, "#define yyparse %sparse\n", spec_name_prefix);
      fprintf (ftable, "#define yylex %slex\n", spec_name_prefix);
      fprintf (ftable, "#define yyerror %serror\n", spec_name_prefix);
      fprintf (ftable, "#define yylval %slval\n", spec_name_prefix);
      fprintf (ftable, "#define yychar %schar\n", spec_name_prefix);
      fprintf (ftable, "#define yydebug %sdebug\n", spec_name_prefix);
      fprintf (ftable, "#define yynerrs %snerrs\n", spec_name_prefix);
      fprintf (ftable, "#define yytypecode %stypecode\n", spec_name_prefix);
      fprintf (ftable, "#define yytypecode_cache %stypecode_cache\n",
spec_name_prefix);
    }
}


/*-------------------------------------------------------.
| Output constant strings to the ends of certain files.  |
`-------------------------------------------------------*/

void
output_trailers (void)
{
  if (semantic_parser)
    fprintf (fguard, "\n    }\n}\n");

  fprintf (faction, "\n");

  if (no_parser_flag)
    return;

  if (semantic_parser)
    fprintf (faction, "    }\n");
  fprintf (faction, "}\n");
}



static void
output_token_translations (void)
{
  int i, j;
/*   short *sp; JF unused */

  if (translations)
    {
      fprintf (ftable,
	       "\n#define YYTRANSLATE(x) ((unsigned)(x) <= %d ?
yytranslate[x] : %d)\n",
	       max_user_token_number, nsyms);

      if (ntokens < 127)	/* play it very safe; check maximum element
value.  */
	fprintf (ftable, "\nstatic const char yytranslate[] = {     0");
      else
	fprintf (ftable, "\nstatic const short yytranslate[] = {     0");

      j = 10;
      for (i = 1; i <= max_user_token_number; i++)
	{
	  putc (',', ftable);

	  if (j >= 10)
	    {
	      putc ('\n', ftable);
	      j = 1;
	    }
	  else
	    {
	      j++;
	    }

	  fprintf (ftable, "%6d", token_translations[i]);
	}

      fprintf (ftable, "\n};\n");
    }
  else
    {
      fprintf (ftable, "\n#define YYTRANSLATE(x) (x)\n");
    }
}


static void
output_gram (void)
{
  int j;
  short *sp;

  /* With the ordinary parser,
     yyprhs and yyrhs are needed only for yydebug. */
  /* With the no_parser option, all tables are generated */
  if (!semantic_parser && !no_parser_flag)
    fprintf (ftable, "\n#if YYDEBUG != 0\n");

  output_short_table (ftable, "yyprhs", rrhs,
		      0, 1, nrules + 1);

  fprintf (ftable, "\nstatic const short yyrhs[] = {%6d", ritem[0]);

  j = 10;
  for (sp = ritem + 1; *sp; sp++)
    {
      putc (',', ftable);

      if (j >= 10)
	{
	  putc ('\n', ftable);
	  j = 1;
	}
      else
	{
	  j++;
	}

      if (*sp > 0)
	fprintf (ftable, "%6d", *sp);
      else
	fprintf (ftable, "     0");
    }

  fprintf (ftable, "\n};\n");

  if (!semantic_parser && !no_parser_flag)
    fprintf (ftable, "\n#endif\n");
}


static void
output_stos (void)
{
  output_short_table (ftable, "yystos", accessing_symbol,
		      0, 1, nstates);
}

#define SWAP(x, y) (temp = (x), (x) = (y), (y) = temp)

static void adjust(int tc[], int m, register int n) {
  register int *b, j, k, temp;
  b = tc - 1;
  j = m;
  k = m * 2;
  while (k <= n) {
    if (k < n && strcmp(tags[b[k]], tags[b[k+1]]) < 0)  ++k;
    if (strcmp(tags[b[j]], tags[b[k]]) < 0)  SWAP(b[j], b[k]);
    j = k;
    k *= 2;
  }
}


static void output_name_typecode_table(void) {
  int* tc; /* The value is a type-code in the tags table. */
  int i, j, temp, k;

  tc = calloc(nsyms, sizeof(int));

  for (i=0; i<nsyms; ++i) /* Create unsorted table. */
    tc[i] = i;

  /* Heap sort tc[], the comparison defined by tags[tc[i]]:
     See Harbison, Steele, "C, A reference manual", sec. 4.3.2. */
  for (j = nsyms/2; j > 0; --j)  adjust(tc, j, nsyms);
  for (j = nsyms-1; j > 0; --j) {
    SWAP(tc[0], tc[j]);
    adjust(tc, 1, j);
  }

  putc('\n', ftable);

  /* Output the size of the sorted symbol names table: */
  fprintf(ftable, "static const int yytname_typecode_size = %d;\n\n", nsyms);

  /* Output the struct for use with the table of sorted symbol names: */
  fputs("struct name_typecode_t { char* name; int typecode; };\n\n", ftable);

  /* Output the table of sorted symbol names:  */

  fputs("static const name_typecode_t yytname_typecode[] = {\n", ftable);

  j = 0;
  k = nsyms - 1;
  for (i = 0; i < nsyms; ++i) {
    char *p;
    if (j > 75) {
      putc ('\n', ftable);
      j = 0;
    }
    else if (i != 0) {
      putc (' ', ftable);
      ++j;
    }

    fputs("{\"", ftable);
    j += 2;

    for (p = tags[tc[i]]; p && *p; p++) {
      if (*p == '"' || *p == '\\') {
        fprintf (ftable, "\\%c", *p);
        j += 2;
      }
      else if (*p == '\n') {
        fprintf (ftable, "\\n");
        j += 2;
      }
      else if (*p == '\t') {
        fprintf (ftable, "\\t");
        j += 2;
      }
      else if (*p == '\b') {
        fprintf (ftable, "\\b");
        j += 2;
      }
      else if (*p < 040 || *p >= 0177) {
        fprintf (ftable, "\\%03o", *p);
        j += 4;
      }
      else {
        putc (*p, ftable);
        j++;
      }
    }
    temp = tc[i];
    fprintf(ftable, "\", %d}", temp);
    j += 5 + (temp >= 10) + (temp >= 100) + (temp >= 1000) + (temp >= 10000);
    if (i < k) {
      fputs(",", ftable);
      ++j;
    }
  }
  fputs("\n};\n", ftable);

  /* Output the type-code lookup functions:  */

  fputs(
    "\nint yytypecode(const char* s);\n"
    "int yytypecode_cache(const char* s, int* cache);\n\n"
    "int yytypecode(const char* s) {\n"
    "  int low = 0, high = yytname_typecode_size;\n"
    "  while (low != high) {\n"
    "    int i = low + (high - low)/2;\n"
    "    int c = strcmp(s, yytname_typecode[i].name);\n"
    "    switch ((c > 0) - (c < 0)) {\n"
    "      case -1: high = i; break;\n"
    "      case 1: low = i + 1; break;\n", ftable);
  if (!raw_flag)
    fputs(
    "      /* Add 254 to translate from Bison to Yacc type-code: */\n"
    "      default: return yytname_typecode[i].typecode + 254;\n", ftable);
  else
    fputs(
    "      default: return yytname_typecode[i].typecode;\n", ftable);
  fputs(
    "    }\n"
    "  }\n"
    "  return -1;\n"
    "}\n\n", ftable);

  fputs(
    "int yytypecode_cache(const char* s, int* cache) {\n"
    "  if (cache != NULL && *cache >= -1)  return *cache;\n"
    "  int low = 0, high = yytname_typecode_size;\n"
    "  while (low != high) {\n"
    "    int i = low + (high - low)/2;\n"
    "    int c = strcmp(s, yytname_typecode[i].name);\n"
    "    switch ((c > 0) - (c < 0)) {\n"
    "      case -1: high = i; break;\n"
    "      case 1: low = i + 1; break;\n", ftable);
  if (!raw_flag)
    fputs(
    "      /* Add 254 to translate from Bison to Yacc type-code: */\n"
    "      default: { int tc = yytname_typecode[i].typecode + 254;\n", ftable);
  else
    fputs(
    "      default: { int tc = yytname_typecode[i].typecode;\n", ftable);
  fputs(
    "        if (cache != NULL)  *cache = tc;\n"
    "        return tc; }\n"
    "    }\n"
    "  }\n"
    "  if (cache != NULL)  *cache = -1;\n"
    "  return -1;\n"
    "}\n", ftable);

  free(tc);
}


static void
output_rule_data (void)
{
  int i;
  int j;

  fputs ("\n\
#if YYDEBUG != 0\n\
/* YYRLINE[yyn]: source line where rule number YYN was defined. */\n",
	 ftable);

  output_short_table (ftable, "yyrline", rline,
		      0, 1, nrules + 1);

  fputs ("#endif\n\n", ftable);

  if (token_table_flag || no_parser_flag)
    {
      fprintf (ftable, "#define YYNTOKENS %d\n", ntokens);
      fprintf (ftable, "#define YYNNTS %d\n", nvars);
      fprintf (ftable, "#define YYNRULES %d\n", nrules);
      fprintf (ftable, "#define YYNSTATES %d\n", nstates);
      fprintf (ftable, "#define YYMAXUTOK %d\n\n", max_user_token_number);
    }

  if (!token_table_flag && !no_parser_flag)
    fprintf (ftable, "\n#if YYDEBUG != 0 || defined (YYERROR_VERBOSE)\n\n");

  /* Output the table of symbol names.  */

  fprintf (ftable,
	   "static const char * const yytname[] = {   \"%s\"", tags[0]);

  j = strlen (tags[0]) + 44;
  for (i = 1; i < nsyms; i++)
    /* this used to be i<=nsyms, but that output a final "" symbol
       almost by accident */
    {
      char *p;
      putc (',', ftable);
      j++;

      if (j > 75)
	{
	  putc ('\n', ftable);
	  j = 0;
	}

      putc ('\"', ftable);
      j++;

      for (p = tags[i]; p && *p; p++)
	{
	  if (*p == '"' || *p == '\\')
	    {
	      fprintf (ftable, "\\%c", *p);
	      j += 2;
	    }
	  else if (*p == '\n')
	    {
	      fprintf (ftable, "\\n");
	      j += 2;
	    }
	  else if (*p == '\t')
	    {
	      fprintf (ftable, "\\t");
	      j += 2;
	    }
	  else if (*p == '\b')
	    {
	      fprintf (ftable, "\\b");
	      j += 2;
	    }
	  else if (*p < 040 || *p >= 0177)
	    {
	      fprintf (ftable, "\\%03o", *p);
	      j += 4;
	    }
	  else
	    {
	      putc (*p, ftable);
	      j++;
	    }
	}

      putc ('\"', ftable);
      j++;
    }
  /* add a NULL entry to list of tokens */
  fprintf (ftable, ", NULL\n};\n");

  output_name_typecode_table();

  if (!token_table_flag && !no_parser_flag)
    fprintf (ftable, "#endif\n\n");

  /* Output YYTOKNUM. */
  if (token_table_flag)
    {
      output_short_table (ftable, "yytoknum", user_toknums,
			  0, 1, ntokens + 1);
    }

  /* Output YYR1. */
  fputs ("\
/* YYR1[YYN]: Symbol number of symbol that rule YYN derives. */\n", ftable);

  output_short_table (ftable, "yyr1", rlhs,
		      0, 1, nrules + 1);
  XFREE (rlhs + 1);

  putc ('\n', ftable);

  /* Output YYR2. */
  fputs ("\
/* YYR2[YYN]: Number of symbols composing right hand side of rule YYN. */\n\
static const short yyr2[] = {     0", ftable);
  j = 10;
  for (i = 1; i < nrules; i++)
    {
      putc (',', ftable);

      if (j >= 10)
	{
	  putc ('\n', ftable);
	  j = 1;
	}
      else
	{
	  j++;
	}

      fprintf (ftable, "%6d", rrhs[i + 1] - rrhs[i] - 1);
    }

  putc (',', ftable);
  if (j >= 10)
    putc ('\n', ftable);

  fprintf (ftable, "%6d\n};\n", nitems - rrhs[nrules] - 1);
  XFREE (rrhs + 1);
}


static void
output_defines (void)
{
  fprintf (ftable, "\n\n#define\tYYFINAL\t\t%d\n", final_state);
  fprintf (ftable, "#define\tYYFLAG\t\t%d\n", MINSHORT);
  fprintf (ftable, "#define\tYYNTBASE\t%d\n", ntokens);
}


/*------------------------------------------------------------------.
| Decide what to do for each type of token if seen as the lookahead |
| token in specified state.  The value returned is used as the      |
| default action (yydefact) for the state.  In addition, actrow is  |
| filled with what to do for each kind of token, index by symbol    |
| number, with zero meaning do the default action.  The value       |
| MINSHORT, a very negative number, means this situation is an      |
| error.  The parser recognizes this value specially.               |
|                                                                   |
| This is where conflicts are resolved.  The loop over lookahead    |
| rules considered lower-numbered rules last, and the last rule     |
| considered that likes a token gets to handle it.                  |
`------------------------------------------------------------------*/

static int
action_row (int state)
{
  int i;
  int j;
  int k;
  int m = 0;
  int n = 0;
  int count;
  int default_rule;
  int nreds;
  int max;
  int rule;
  int shift_state;
  int symbol;
  unsigned mask;
  unsigned *wordp;
  reductions *redp;
  shifts *shiftp;
  errs *errp;
  int nodefault = 0;		/* set nonzero to inhibit having any
default reduction */

  for (i = 0; i < ntokens; i++)
    actrow[i] = 0;

  default_rule = 0;
  nreds = 0;
  redp = reduction_table[state];

  if (redp)
    {
      nreds = redp->nreds;

      if (nreds >= 1)
	{
	  /* loop over all the rules available here which require
	     lookahead */
	  m = lookaheads[state];
	  n = lookaheads[state + 1];

	  for (i = n - 1; i >= m; i--)
	    {
	      rule = -LAruleno[i];
	      wordp = LA + i * tokensetsize;
	      mask = 1;

	      /* and find each token which the rule finds acceptable
	         to come next */
	      for (j = 0; j < ntokens; j++)
		{
		  /* and record this rule as the rule to use if that
		     token follows.  */
		  if (mask & *wordp)
		    actrow[j] = rule;

		  mask <<= 1;
		  if (mask == 0)
		    {
		      mask = 1;
		      wordp++;
		    }
		}
	    }
	}
    }

  shiftp = shift_table[state];

  /* Now see which tokens are allowed for shifts in this state.  For
     them, record the shift as the thing to do.  So shift is preferred
     to reduce.  */

  if (shiftp)
    {
      k = shiftp->nshifts;

      for (i = 0; i < k; i++)
	{
	  shift_state = shiftp->shifts[i];
	  if (!shift_state)
	    continue;

	  symbol = accessing_symbol[shift_state];

	  if (ISVAR (symbol))
	    break;

	  actrow[symbol] = shift_state;

	  /* Do not use any default reduction if there is a shift for
	     error */
	  if (symbol == error_token_number)
	    nodefault = 1;
	}
    }

  errp = err_table[state];

  /* See which tokens are an explicit error in this state (due to
     %nonassoc).  For them, record MINSHORT as the action.  */

  if (errp)
    {
      k = errp->nerrs;

      for (i = 0; i < k; i++)
	{
	  symbol = errp->errs[i];
	  actrow[symbol] = MINSHORT;
	}
    }

  /* Now find the most common reduction and make it the default action
     for this state.  */

  if (nreds >= 1 && !nodefault)
    {
      if (consistent[state])
	default_rule = redp->rules[0];
      else
	{
	  max = 0;
	  for (i = m; i < n; i++)
	    {
	      count = 0;
	      rule = -LAruleno[i];

	      for (j = 0; j < ntokens; j++)
		{
		  if (actrow[j] == rule)
		    count++;
		}

	      if (count > max)
		{
		  max = count;
		  default_rule = rule;
		}
	    }

	  /* actions which match the default are replaced with zero,
	     which means "use the default" */

	  if (max > 0)
	    {
	      for (j = 0; j < ntokens; j++)
		{
		  if (actrow[j] == default_rule)
		    actrow[j] = 0;
		}

	      default_rule = -default_rule;
	    }
	}
    }

  /* If have no default rule, the default is an error.
     So replace any action which says "error" with "use default".  */

  if (default_rule == 0)
    for (j = 0; j < ntokens; j++)
      {
	if (actrow[j] == MINSHORT)
	  actrow[j] = 0;
      }

  return default_rule;
}


static void
save_row (int state)
{
  int i;
  int count;
  short *sp;
  short *sp1;
  short *sp2;

  count = 0;
  for (i = 0; i < ntokens; i++)
    {
      if (actrow[i] != 0)
	count++;
    }

  if (count == 0)
    return;

  froms[state] = sp1 = sp = XCALLOC (short, count);
  tos[state] = sp2 = XCALLOC (short, count);

  for (i = 0; i < ntokens; i++)
    {
      if (actrow[i] != 0)
	{
	  *sp1++ = i;
	  *sp2++ = actrow[i];
	}
    }

  tally[state] = count;
  width[state] = sp1[-1] - sp[0] + 1;
}


/*------------------------------------------------------------------.
| Figure out the actions for the specified state, indexed by        |
| lookahead token type.                                             |
|                                                                   |
| The YYDEFACT table is output now.  The detailed info is saved for |
| putting into YYTABLE later.                                       |
`------------------------------------------------------------------*/

static void
token_actions (void)
{
  int i;
  short *yydefact = XCALLOC (short, nstates);

  actrow = XCALLOC (short, ntokens);
  for (i = 0; i < nstates; ++i)
    {
      yydefact[i] = action_row (i);
      save_row (i);
    }
  XFREE (actrow);

  output_short_table (ftable, "yydefact", yydefact,
		      yydefact[0], 1, nstates);
  XFREE (yydefact);
}


static void
free_shifts (void)
{
  shifts *sp, *sptmp;	/* JF derefrenced freed ptr */

  XFREE (shift_table);

  for (sp = first_shift; sp; sp = sptmp)
    {
      sptmp = sp->next;
      XFREE (sp);
    }
}


static void
free_reductions (void)
{
  reductions *rp, *rptmp;	/* JF fixed freed ptr */

  XFREE (reduction_table);

  for (rp = first_reduction; rp; rp = rptmp)
    {
      rptmp = rp->next;
      XFREE (rp);
    }
}



static void
save_column (int symbol, int default_state)
{
  int i;
  int m;
  int n;
  short *sp;
  short *sp1;
  short *sp2;
  int count;
  int symno;

  m = goto_map[symbol];
  n = goto_map[symbol + 1];

  count = 0;
  for (i = m; i < n; i++)
    {
      if (to_state[i] != default_state)
	count++;
    }

  if (count == 0)
    return;

  symno = symbol - ntokens + nstates;

  froms[symno] = sp1 = sp = XCALLOC (short, count);
  tos[symno] = sp2 = XCALLOC (short, count);

  for (i = m; i < n; i++)
    {
      if (to_state[i] != default_state)
	{
	  *sp1++ = from_state[i];
	  *sp2++ = to_state[i];
	}
    }

  tally[symno] = count;
  width[symno] = sp1[-1] - sp[0] + 1;
}

static int
default_goto (int symbol)
{
  int i;
  int m;
  int n;
  int default_state;
  int max;

  m = goto_map[symbol];
  n = goto_map[symbol + 1];

  if (m == n)
    return -1;

  for (i = 0; i < nstates; i++)
    state_count[i] = 0;

  for (i = m; i < n; i++)
    state_count[to_state[i]]++;

  max = 0;
  default_state = -1;

  for (i = 0; i < nstates; i++)
    {
      if (state_count[i] > max)
	{
	  max = state_count[i];
	  default_state = i;
	}
    }

  return default_state;
}


/*-------------------------------------------------------------------.
| Figure out what to do after reducing with each rule, depending on  |
| the saved state from before the beginning of parsing the data that |
| matched this rule.                                                 |
|                                                                    |
| The YYDEFGOTO table is output now.  The detailed info is saved for |
| putting into YYTABLE later.                                        |
`-------------------------------------------------------------------*/

static void
goto_actions (void)
{
  int i, j, k;

  state_count = XCALLOC (short, nstates);

  k = default_goto (ntokens);
  fprintf (ftable, "\nstatic const short yydefgoto[] = {%6d", k);
  save_column (ntokens, k);

  j = 10;
  for (i = ntokens + 1; i < nsyms; i++)
    {
      putc (',', ftable);

      if (j >= 10)
	{
	  putc ('\n', ftable);
	  j = 1;
	}
      else
	{
	  j++;
	}

      k = default_goto (i);
      fprintf (ftable, "%6d", k);
      save_column (i, k);
    }

  fprintf (ftable, "\n};\n");
  XFREE (state_count);
}


/* The next few functions decide how to pack the actions and gotos
   information into yytable. */

static void
sort_actions (void)
{
  int i;
  int j;
  int k;
  int t;
  int w;

  order = XCALLOC (short, nvectors);
  nentries = 0;

  for (i = 0; i < nvectors; i++)
    {
      if (tally[i] > 0)
	{
	  t = tally[i];
	  w = width[i];
	  j = nentries - 1;

	  while (j >= 0 && (width[order[j]] < w))
	    j--;

	  while (j >= 0 && (width[order[j]] == w) && (tally[order[j]] < t))
	    j--;

	  for (k = nentries - 1; k > j; k--)
	    order[k + 1] = order[k];

	  order[j + 1] = i;
	  nentries++;
	}
    }
}


static int
matching_state (int vector)
{
  int i;
  int j;
  int k;
  int t;
  int w;
  int match;
  int prev;

  i = order[vector];
  if (i >= nstates)
    return -1;

  t = tally[i];
  w = width[i];

  for (prev = vector - 1; prev >= 0; prev--)
    {
      j = order[prev];
      if (width[j] != w || tally[j] != t)
	return -1;

      match = 1;
      for (k = 0; match && k < t; k++)
	{
	  if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k])
	    match = 0;
	}

      if (match)
	return j;
    }

  return -1;
}


static int
pack_vector (int vector)
{
  int i;
  int j;
  int k;
  int t;
  int loc = 0;
  int ok;
  short *from;
  short *to;

  i = order[vector];
  t = tally[i];

  assert (t);

  from = froms[i];
  to = tos[i];

  for (j = lowzero - from[0]; j < MAXTABLE; j++)
    {
      ok = 1;

      for (k = 0; ok && k < t; k++)
	{
	  loc = j + from[k];
	  if (loc > MAXTABLE)
	    fatal (_("maximum table size (%d) exceeded"), MAXTABLE);

	  if (table[loc] != 0)
	    ok = 0;
	}

      for (k = 0; ok && k < vector; k++)
	{
	  if (pos[k] == j)
	    ok = 0;
	}

      if (ok)
	{
	  for (k = 0; k < t; k++)
	    {
	      loc = j + from[k];
	      table[loc] = to[k];
	      check[loc] = from[k];
	    }

	  while (table[lowzero] != 0)
	    lowzero++;

	  if (loc > high)
	    high = loc;

	  return j;
	}
    }

  berror ("pack_vector");
  return 0;			/* JF keep lint happy */
}


static void
pack_table (void)
{
  int i;
  int place;
  int state;

  base = XCALLOC (short, nvectors);
  pos = XCALLOC (short, nentries);
  table = XCALLOC (short, MAXTABLE);
  check = XCALLOC (short, MAXTABLE);

  lowzero = 0;
  high = 0;

  for (i = 0; i < nvectors; i++)
    base[i] = MINSHORT;

  for (i = 0; i < MAXTABLE; i++)
    check[i] = -1;

  for (i = 0; i < nentries; i++)
    {
      state = matching_state (i);

      if (state < 0)
	place = pack_vector (i);
      else
	place = base[state];

      pos[i] = place;
      base[order[i]] = place;
    }

  for (i = 0; i < nvectors; i++)
    {
      if (froms[i])
	XFREE (froms[i]);
      if (tos[i])
	XFREE (tos[i]);
    }

  XFREE (froms);
  XFREE (tos);
  XFREE (pos);
}

/* the following functions output yytable, yycheck
   and the vectors whose elements index the portion starts */

static void
output_base (void)
{
  output_short_table (ftable, "yypact", base,
		      base[0], 1, nstates);

  putc ('\n', ftable);

  output_short_table (ftable, "yypgoto", base,
		      base[nstates], nstates + 1, nvectors);

  XFREE (base);
}


static void
output_table (void)
{
  fprintf (ftable, "\n\n#define\tYYLAST\t\t%d\n\n\n", high);
  output_short_table (ftable, "yytable", table,
		      table[0], 1, high + 1);
  XFREE (table);
}


static void
output_check (void)
{
  output_short_table (ftable, "yycheck", check,
		      check[0], 1, high + 1);
  XFREE (check);
}

/* compute and output yydefact, yydefgoto, yypact, yypgoto, yytable
   and yycheck.  */

static void
output_actions (void)
{
  nvectors = nstates + nvars;

  froms = XCALLOC (short *, nvectors);
  tos = XCALLOC (short *, nvectors);
  tally = XCALLOC (short, nvectors);
  width = XCALLOC (short, nvectors);

  token_actions ();
  free_shifts ();
  free_reductions ();
  XFREE (lookaheads);
  XFREE (LA);
  XFREE (LAruleno);
  XFREE (accessing_symbol);

  goto_actions ();
  XFREE (goto_map + ntokens);
  XFREE (from_state);
  XFREE (to_state);

  sort_actions ();
  pack_table ();
  putc ('\n', ftable);
  output_base ();
  output_table ();
  putc ('\n', ftable);
  output_check ();
}

/* copy the parser code into the ftable file at the end.  */

static void
output_parser (void)
{
  int c;
  static int number_of_dollar_signs = 0;
#ifdef DONTDEF
  FILE *fpars;
#else
#define fpars fparser
#endif

  if (pure_parser)
    fprintf (ftable, "#define YYPURE 1\n\n");

#ifdef DONTDEF
  /* JF no longer needed 'cuz open_extra_files changes the currently
     open parser from bison.simple to bison.hairy */
  if (semantic_parser)
    fpars = fparser;
  else
    fpars = fparser1;
#endif

  /* Loop over lines in the standard parser file.  */

  while (1)
    {
      int write_line = 1;

      c = getc (fpars);

      /* See if the line starts with `#line.
         If so, set write_line to 0.  */
      if (no_lines_flag)
	if (c == '#')
	  {
	    c = getc (fpars);
	    if (c == 'l')
	      {
		c = getc (fpars);
		if (c == 'i')
		  {
		    c = getc (fpars);
		    if (c == 'n')
		      {
			c = getc (fpars);
			if (c == 'e')
			  write_line = 0;
			else
			  fprintf (ftable, "#lin");
		      }
		    else
		      fprintf (ftable, "#li");
		  }
		else
		  fprintf (ftable, "#l");
	      }
	    else
	      fprintf (ftable, "#");
	  }

      /* now write out the line... */
      for (; c != '\n' && c != EOF; c = getc (fpars))
	if (write_line)
	  {
	    if (c == '$')
	      {
		number_of_dollar_signs++;
		assert (number_of_dollar_signs == 1);
		/* `$' in the parser file indicates where to put the actions.
		   Copy them in at this point.  */
		rewind (faction);
		for (c = getc (faction); c != EOF; c = getc (faction))
		  putc (c, ftable);
		/* Skip the end of the line containing `$'. */
		write_line = 0;
	      }
	    else
	      putc (c, ftable);
	  }
      if (c == EOF)
	break;
      putc (c, ftable);
    }
  assert (number_of_dollar_signs == 1);
}

static void
output_program (void)
{
  int c;

  if (!no_lines_flag)
    fprintf (ftable, "#line %d \"%s\"\n", lineno, infile);

  c = getc (finput);
  while (c != EOF)
    {
      putc (c, ftable);
      c = getc (finput);
    }
}


static void
free_itemsets (void)
{
  core *cp, *cptmp;

  XFREE (state_table);

  for (cp = first_state; cp; cp = cptmp)
    {
      cptmp = cp->next;
      XFREE (cp);
    }
}


/*----------------------------------------------------------.
| Output the parsing tables and the parser code to ftable.  |
`----------------------------------------------------------*/

void
output (void)
{
  int c;

  /* output_token_defines(ftable);      / * JF put out token defines FIRST */
  if (!semantic_parser)		/* JF Put out other stuff */
    {
      rewind (fattrs);
      while ((c = getc (fattrs)) != EOF)
	putc (c, ftable);
    }
  reader_output_yylsp (ftable);
  if (debug_flag)
    fputs ("\
#ifndef YYDEBUG\n\
# define YYDEBUG 1\n\
#endif\n\
\n",
	   ftable);

  if (semantic_parser)
    fprintf (ftable, "#include \"%s\"\n", attrsfile);

  if (!no_parser_flag)
    fprintf (ftable, "#include <stdio.h>\n\n");

  /* Make "const" do nothing if not in ANSI C.  */
  fputs ("\
#ifndef __cplusplus\n\
# ifndef __STDC__\n\
#  define const\n\
# endif\n\
#endif\n\
\n",
	 ftable);

  free_itemsets ();
  output_defines ();
  output_token_translations ();
/*   if (semantic_parser) */
  /* This is now unconditional because debugging printouts can use it.  */
  output_gram ();
  XFREE (ritem);
  if (semantic_parser)
    output_stos ();
  output_rule_data ();
  output_actions ();
  if (!no_parser_flag)
    output_parser ();
  output_program ();
}

--============_-1234641871==_============
Content-Type: text/plain; charset="us-ascii"

  Hans Aberg

--============_-1234641871==_============--



From akim@epita.fr Fri Dec 22 05:43:01 2000
Received: from [163.5.255.10] (helo=hermes.epita.fr)
	by fencepost.gnu.org with esmtp (Exim 3.16 #1 (Debian))
	id 149PfA-00027r-00
	for <bug-bison@gnu.org>; Fri, 22 Dec 2000 05:43:00 -0500
Received: from goa.lrde.epita.fr (mail@goa.lrde.epita.fr [10.223.13.2])
	by hermes.epita.fr id LAA23604
	Fri, 22 Dec 2000 11:40:38 GMT
Received: from nostromo.lrde.epita.fr ([10.223.13.52] ident=mail)
	by goa.lrde.epita.fr with esmtp (Exim 3.12 #1 (Debian))
	id 149PeY-0001HZ-00; Fri, 22 Dec 2000 11:42:22 +0100
Received: from akim by nostromo.lrde.epita.fr with local (Exim 3.20 #1 (Debian))
	id 149PeW-00014t-00; Fri, 22 Dec 2000 11:42:20 +0100
To: Hans Aberg <haberg@matematik.su.se>
Cc: Bison Bugs <bug-bison@gnu.org>
Subject: Re: Faster token table lookups
References: <v03110700b66003d6d507@[195.100.226.162]>
	<v03110700b6652eba88fe@[195.100.226.134]>
	<v03110700b668d412b91c@[195.100.226.161]>
From: Akim Demaille <akim@epita.fr>
Date: 22 Dec 2000 11:42:20 +0100
In-Reply-To: Hans Aberg's message of "Fri, 22 Dec 2000 11:21:31 +0100"
Message-ID: <mv4snnglotv.fsf@nostromo.lrde.epita.fr>
Lines: 12
User-Agent: Gnus/5.0807 (Gnus v5.8.7) XEmacs/21.1 (Channel Islands)
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

Hi Hans,

Thanks for the patch!  I don't have time to read it now, but 1. I need
documentation for it, i.e., the ChangeLog that goes with it, 2. if it
is big, I need you to sign papers to the FSF, 3. I think it is not
relative to the current state of CVS Bison since I think I saw fguard
which no longer exists.

I won't look at it before January.  Are you sure it is worth the
trouble?  My opinion is that 1. nobody uses those tables to parse, and
2. those who do certainly process these tables before using them.  Let
it be for bsearch or some other method they might want to use.


From haberg@matematik.su.se Fri Dec 22 06:38:38 2000
Received: from knatte.tninet.se ([195.100.94.10])
	by fencepost.gnu.org with smtp (Exim 3.16 #1 (Debian))
	id 149QX0-0008Mg-00
	for <bug-bison@gnu.org>; Fri, 22 Dec 2000 06:38:38 -0500
Received: (qmail 11712 invoked from network); 22 Dec 2000 12:38:36 +0100
Received: from delenn.tninet.se (HELO algonet.se) (195.100.94.104)
  by knatte.tninet.se with SMTP; 22 Dec 2000 12:38:36 +0100
Received: from  [195.100.226.150] (du145-226.ppp.su-anst.tninet.se [195.100.226.145])
 by delenn.tninet.se (BLUETAIL Mail Robustifier 2.2.1) with ESMTP
 id 431979.485114.977delenn-s0
 ; Fri, 22 Dec 2000 12:38:34 +0100
X-Sender: haberg@pop.matematik.su.se
Message-Id: <v03110702b668e7a35205@[195.100.226.150]>
In-Reply-To: <mv4snnglotv.fsf@nostromo.lrde.epita.fr>
References: Hans Aberg's message of "Fri, 22 Dec 2000 11:21:31 +0100"
 <v03110700b66003d6d507@[195.100.226.162]>
 <v03110700b6652eba88fe@[195.100.226.134]>
 <v03110700b668d412b91c@[195.100.226.161]>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Fri, 22 Dec 2000 12:35:58 +0100
To: Akim Demaille <akim@epita.fr>
From: Hans Aberg <haberg@matematik.su.se>
Subject: Re: Faster token table lookups
Cc: Bison Bugs <bug-bison@gnu.org>
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

At 11:42 +0100 0-12-22, Akim Demaille wrote:
>I won't look at it before January.

I though I should give you something to do during the Christmas
holidays.... :-)

>  Are you sure it is worth the
>trouble?

You should have told me before writing the patch...

> My opinion is that 1. nobody uses those tables to parse, and
>2. those who do certainly process these tables before using them.

Isn't there a contradiction here? :-) (Those that do not use the tables
processes them before using them.)

>  Let
>it be for bsearch or some other method they might want to use.

Well, if one should somehow use it, I think I implemented the fastest one,
so there would be no point for any other to implement something else.

Otherwise, for the usability, I have no idea. :-)

One use is to diminish the cluttering of the namespaces. I use three Bison
invokations, and I worry a little with name conflicts with Flex which
defines start-condition macros).

Also, I use Flex reading Bison's header, which means that the Flex file
must be recompiled every time the Bison file is used, which could be
avoided using those functions.

And if one somehow wants to have a lexer that produces type-codes
dynamically, one could use these functions.

Otherwise, I have no idea; it is a feature mentioned in the manual, sec.
4.2.1, and I got curios about it. The reason for using macros alone is
speed, but the question is how much this dynamical variation slows down it:
If it is not too much, one could just as well use that version. (Computers
have improved a lot since the original code was written, so more dynamic
stuff is permissible nowadays.)

So if somebody is interested in experimenting with the approach, you got
the code.

>I think it is not
>relative to the current state of CVS Bison since I think I saw fguard
>which no longer exists.

Right. I have been busy using Bison, so have not had time using the latest
version (as I would have to patch it up for the MacOS CW IDE plugin that I
use). -- Just replace "fguard" with whatever you put the output.

  Hans Aberg




From haberg@matematik.su.se Fri Dec 22 08:25:34 2000
Received: from hromeo.algonet.se ([194.213.74.51])
	by fencepost.gnu.org with smtp (Exim 3.16 #1 (Debian))
	id 149SCT-0005XJ-00
	for <bug-bison@gnu.org>; Fri, 22 Dec 2000 08:25:34 -0500
Received: (qmail 6186 invoked from network); 22 Dec 2000 14:25:32 +0100
Received: from garibaldi.tninet.se (HELO algonet.se) (195.100.94.103)
  by hromeo.algonet.se with SMTP; 22 Dec 2000 14:25:32 +0100
Received: from  [195.100.226.150] (du136-226.ppp.su-anst.tninet.se [195.100.226.136])
 by garibaldi.tninet.se (BLUETAIL Mail Robustifier 2.2.1) with ESMTP
 id 580437.491530.977garibaldi-s0
 ; Fri, 22 Dec 2000 14:25:30 +0100
X-Sender: haberg@pop.matematik.su.se
Message-Id: <v03110703b668f8593f19@[195.100.226.150]>
In-Reply-To: <mv4snnglotv.fsf@nostromo.lrde.epita.fr>
References: Hans Aberg's message of "Fri, 22 Dec 2000 11:21:31 +0100"
 <v03110700b66003d6d507@[195.100.226.162]>
 <v03110700b6652eba88fe@[195.100.226.134]>
 <v03110700b668d412b91c@[195.100.226.161]>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Fri, 22 Dec 2000 14:24:11 +0100
To: Akim Demaille <akim@epita.fr>
From: Hans Aberg <haberg@matematik.su.se>
Subject: Re: Faster token table lookups
Cc: Bison Bugs <bug-bison@gnu.org>
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

At 11:42 +0100 0-12-22, Akim Demaille wrote:
>My opinion is that 1. nobody uses those tables to parse, and
>2. those who do certainly process these tables before using them.

What is the typical processing of those tables that you know of?

-- A possible use of those name tables could be if one for some reason want
to return a semantic variable, say if you have a context dependency.

  Hans Aberg




From haberg@matematik.su.se Sat Dec 23 16:50:34 2000
Received: from musse.tninet.se ([195.100.94.12])
	by fencepost.gnu.org with smtp (Exim 3.16 #1 (Debian))
	id 149wYj-0005eV-00
	for <bug-bison@gnu.org>; Sat, 23 Dec 2000 16:50:34 -0500
Received: (qmail 8138 invoked from network); 23 Dec 2000 22:50:31 +0100
Received: from garibaldi.tninet.se (HELO algonet.se) (195.100.94.103)
  by musse.tninet.se with SMTP; 23 Dec 2000 22:50:31 +0100
Received: from  [195.100.226.128] (du128-226.ppp.su-anst.tninet.se [195.100.226.128])
 by garibaldi.tninet.se (BLUETAIL Mail Robustifier 2.2.1) with ESMTP
 id 736749.608227.977garibaldi-s1 for <bug-bison@gnu.org>
 ; Sat, 23 Dec 2000 22:50:27 +0100
X-Sender: haberg@pop.matematik.su.se (Unverified)
Message-Id: <v03110700b66960af72b6@[195.100.226.128]>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Sat, 23 Dec 2000 22:49:14 +0100
To: Bison Bugs <bug-bison@gnu.org>
From: Hans Aberg <haberg@matematik.su.se>
Subject: bison-20001221
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

I picked down ftp://alpha.gnu.org/gnu/cvs/bison-20001221.tgz. Some bugs:

- The file version.texi, needed by bison.texinfo is not in the distribution.

- On a number of places there is
  include <config.h>
It should be
  include "config.h"

- Files "files.c" and "complain.c" reads the macro definition differently:
"files.c" somehow gets it from "error.h", I think, whereas "complain.c"
does not read it at all. So I had to throw in
#ifndef __attribute__
#define __attribute__(x)
#endif
into the file "complain.h" in order to be sure is always defined (which
should be empty on my system).

- File "files.c" uses stpcpy() and strndup() which is not in the C standard
(and I have no other mentioning of it). So I put in definitions (hope it is
correct):
char* strndup(const char* s, size_t n);
char* stpcpy(char* s1, const char* s2);

char* strndup(const char* s, size_t n) {
  char* ret;
  size_t len = strlen(s);
  if (n >= len)
    return strcpy(xmalloc(len + 1), s);
  ret = strncpy(xmalloc(n + 1), s, n);
  ret[n] = '\0';
  return ret;
}

char* stpcpy(char* s1, const char* s2) {
  strcpy(s1, s2);
  return s1 + strlen(s1);
}

  - compute_base_names() uses strndup() which is not in the C standard, and
for which I have found no reference; it also uses stpcpy().


- File "xstrdup.c", "xmalloc.c", and others, contains platform specific
seemingly unneeded
  #include <sys/types.h>
Also, no prototype
  char *xstrdup (const char *string);

- In files "output.c", output_headers(), and "print.c", print_grammar(), I
got problems with the fact that pre-MacOS X only allows stack allocations
<= 32 kB, here exceeded by the "obstack_..." macros. This just something
platform specific of an old OS, but I think in general, it is wise to not
allocate more on the stack than needed. (For example, each obstack_fgrow1
asks for a stack allocation of 4 kB, whereas in output_headers() the actual
allocation needed for each obstack_fgrow1 is less than 64 B.)
  - I got around the problem by changing the obstack_fgrow1 macro
containing a static array:
  static char buf[4096];
Not pure anymore, but it does not make any difference in my port.
  - Perhaps the obstack should be made into FILE* objects. I didn't see the
growth policy, but if one doubles the stack size whenever it becomes short,
recopying should only be of linear order (2n, if n is the number of
characters allocated).

- There seems to be no file "config.hin" in the distribution, which means
on platforms without "make" the package cannot be used.

- Files "quote.c", "quote_arg.c" includes platform specific <sys/types.h>.
Unnecessary if "quotearg.h" includes <size_t.h>. Also,
  #include <quotearg.h>
  #include <quote.h>
only works if one puts the stuff in the library; not if one takes down
Bison and compiles it directly;
  #include "quotearg.h"
  #include "quote.h"
is safer.

- File "quote_arg.c", "else" clause of "#if HAVE_MBRTOWC": macro "iswprint"
is already in the C-standard, so redefining it here causes an error.

- File "main.c", main() does not have a return value -- produces a warning
from the compiler.

- File "bison.simple",
  int
  yyparse (YYPARSE_PARAM_ARG)
     YYPARSE_PARAM_DECL
does not have a prototype -- produces a compiler warning for example when
compiling under C++.

- The new dynamically computed #line directives are great. -- The filename,
however show up with a full pathname. Perhaps some may want that, but
suppose the sources are distributed to another computer with another
filepath -- then that is broken. So I suggest instead if the single "char*
skeleton", which currently full path-name, using two "skeleton_name" and
"skeleton_path"; then one can use "skeleton_name" in the #line directives.
  - I realize when I write this that it probably happens because I tweaked
"skeleton_find" to output the full pathname. I therefore tweaked it back in
output_parser().

  Seasons Greetings,

  Hans Aberg




From haberg@matematik.su.se Sat Dec 23 16:51:56 2000
Received: from hromeo.algonet.se ([194.213.74.51])
	by fencepost.gnu.org with smtp (Exim 3.16 #1 (Debian))
	id 149wa3-0005f8-00
	for <bug-bison@gnu.org>; Sat, 23 Dec 2000 16:51:55 -0500
Received: (qmail 17630 invoked from network); 23 Dec 2000 22:51:49 +0100
Received: from delenn.tninet.se (HELO algonet.se) (195.100.94.104)
  by hromeo.algonet.se with SMTP; 23 Dec 2000 22:51:49 +0100
Received: from  [195.100.226.128] (du128-226.ppp.su-anst.tninet.se [195.100.226.128])
 by delenn.tninet.se (BLUETAIL Mail Robustifier 2.2.1) with ESMTP
 id 706002.608299.977delenn-s2
 ; Sat, 23 Dec 2000 22:51:39 +0100
X-Sender: haberg@pop.matematik.su.se (Unverified)
Message-Id: <v03110700b66acd68d789@[195.100.226.128]>
Mime-Version: 1.0
Content-Type: multipart/mixed; boundary="============_-1234514193==_============"
Date: Sat, 23 Dec 2000 22:48:37 +0100
To: Bison Bugs <bug-bison@gnu.org>
From: Hans Aberg <haberg@matematik.su.se>
Subject: Re: Faster token table lookups
Cc: Akim Demaille <akim@epita.fr>
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

--============_-1234514193==_============
Content-Type: text/plain; charset="us-ascii"

Here is a patch I made for the
ftp://alpha.gnu.org/gnu/cvs/bison-20001221.tgz version, if somebody wants
to experiment with the feature during the holidays :-).

  Seasons Greetings,

--============_-1234514193==_============
Content-Type: text/plain; name="output.c"; charset="us-ascii"
Content-Disposition: attachment; filename="output.c"

/* Output the generated parsing program for bison,
   Copyright 1984, 1986, 1989, 1992, 2000 Free Software Foundation, Inc.

   This file is part of Bison, the GNU Compiler Compiler.

   Bison 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 2, or (at your option)
   any later version.

   Bison 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 Bison; see the file COPYING.  If not, write to the Free
   Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
   02111-1307, USA.  */


/* The parser tables consist of these tables.
   Starred ones needed only for the semantic parser.
   Double starred are output only if switches are set.

   yytranslate = vector mapping yylex's token numbers into bison's token
   numbers.

   ** yytname = vector of string-names indexed by bison token number

   ** yytoknum = vector of yylex token numbers corresponding to entries
   in yytname

   yyrline = vector of line-numbers of all rules.  For yydebug printouts.

   yyrhs = vector of items of all rules.
   This is exactly what ritems contains.  For yydebug and for semantic
   parser.

   yyprhs[r] = index in yyrhs of first item for rule r.

   yyr1[r] = symbol number of symbol that rule r derives.

   yyr2[r] = number of symbols composing right hand side of rule r.

   * yystos[s] = the symbol number of the symbol that leads to state s.

   yydefact[s] = default rule to reduce with in state s,
   when yytable doesn't specify something else to do.
   Zero means the default is an error.

   yydefgoto[i] = default state to go to after a reduction of a rule that
   generates variable ntokens + i, except when yytable
   specifies something else to do.

   yypact[s] = index in yytable of the portion describing state s.
   The lookahead token's type is used to index that portion
   to find out what to do.

   If the value in yytable is positive,
   we shift the token and go to that state.

   If the value is negative, it is minus a rule number to reduce by.

   If the value is zero, the default action from yydefact[s] is used.

   yypgoto[i] = the index in yytable of the portion describing
   what to do after reducing a rule that derives variable i + ntokens.
   This portion is indexed by the parser state number, s,
   as of before the text for this nonterminal was read.
   The value from yytable is the state to go to if
   the corresponding value in yycheck is s.

   yytable = a vector filled with portions for different uses,
   found via yypact and yypgoto.

   yycheck = a vector indexed in parallel with yytable.
   It indicates, in a roundabout way, the bounds of the
   portion you are trying to examine.

   Suppose that the portion of yytable starts at index p
   and the index to be examined within the portion is i.
   Then if yycheck[p+i] != i, i is outside the bounds
   of what is actually allocated, and the default
   (from yydefact or yydefgoto) should be used.
   Otherwise, yytable[p+i] should be used.

   YYFINAL = the state number of the termination state.
   YYFLAG = most negative short int.  Used to flag ??
   YYNTBASE = ntokens.
*/

#include "system.h"
#include "obstack.h"
#include "quotearg.h"
#include "getargs.h"
#include "xalloc.h"
#include "files.h"
#include "gram.h"
#include "LR0.h"
#include "complain.h"
#include "output.h"
#include "lalr.h"
#include "reader.h"
#include "conflicts.h"

extern void berror PARAMS((const char *));



static int nvectors;
static int nentries;
static short **froms;
static short **tos;
static short *tally;
static short *width;
static short *actrow;
static short *state_count;
static short *order;
static short *base;
static short *pos;
static short *table;
static short *check;
static int lowzero;
static int high;



static inline void
output_short_or_char_table (struct obstack *oout,
			    const char *comment,
			    const char *type,
			    const char *table_name,
			    short *short_table,
			    short first_value,
			    short begin, short end)
{
  int i, j;

  if (comment)
    obstack_fgrow1 (oout, "/* %s. */\n", comment);

  obstack_fgrow3 (oout, "static const %s %s[] =\n{\n  %6d",
		  type, table_name, first_value);

  j = 1;
  for (i = begin; i < end; i++)
    {
      obstack_1grow (oout, ',');

      if (j >= 10)
	{
	  obstack_sgrow (oout, "\n  ");
	  j = 1;
	}
      else
	{
	  j++;
	}

      obstack_fgrow1 (oout, "%6d", short_table[i]);
    }

  obstack_sgrow (oout, "\n};\n");
}


static inline void
output_short_table (struct obstack *oout,
		    const char *comment,
		    const char *table_name,
		    short *short_table,
		    short first_value,
		    short begin, short end)
{
  output_short_or_char_table (oout, comment, "short", table_name, short_table,
			      first_value, begin, end);
}


/*--------------------------------------------------------------.
| output_headers -- Output constant strings to the beginning of |
| certain files.                                                |
`--------------------------------------------------------------*/

/* Don't put the `%s' insides quotes, since it quotearg puts them. */

#define	GUARDSTR	\
"\n\
#include %s\n\
extern int yyerror;\n\
extern int yycost;\n\
extern char * yymsg;\n\
extern YYSTYPE yyval;\n\
\n\
yyguard(n, yyvsp, yylsp)\n\
register int n;\n\
register YYSTYPE *yyvsp;\n\
register YYLTYPE *yylsp;\n\
{\n\
  yyerror = 0;\n\
  yycost = 0;\n\
  yymsg = 0;\n\
  switch (n)\n\
    {"

#define	ACTSTR		\
"\n\
#include %s\n\
extern YYSTYPE yyval;\n\
extern int yychar;\n\
\n\
yyaction(n, yyvsp, yylsp)\n\
register int n;\n\
register YYSTYPE *yyvsp;\n\
register YYLTYPE *yylsp;\n\
{\n\
  switch (n)\n\
    {"

#define	ACTSTR_SIMPLE	"\n  switch (yyn) {\n"

void
output_headers (void)
{
  char *attrsfile_quoted = quotearg_style (c_quoting_style, attrsfile);
  if (semantic_parser)
    obstack_fgrow1 (&guard_obstack, GUARDSTR, attrsfile_quoted);

  if (no_parser_flag)
    return;

  if (semantic_parser)
    obstack_fgrow1 (&action_obstack, ACTSTR, attrsfile_quoted);
  else
    obstack_sgrow (&action_obstack, ACTSTR_SIMPLE);

  /* Rename certain symbols if -p was specified.  */
  if (spec_name_prefix)
  {
    obstack_fgrow1 (&table_obstack,
		      "#define yyparse %sparse\n", spec_name_prefix);
    obstack_fgrow1 (&table_obstack,
		      "#define yylex %slex\n", spec_name_prefix);
    obstack_fgrow1 (&table_obstack,
		      "#define yyerror %serror\n", spec_name_prefix);
    obstack_fgrow1 (&table_obstack,
		      "#define yylval %slval\n", spec_name_prefix);
    obstack_fgrow1 (&table_obstack,
		      "#define yychar %schar\n", spec_name_prefix);
    obstack_fgrow1 (&table_obstack,
		      "#define yydebug %sdebug\n", spec_name_prefix);
    obstack_fgrow1 (&table_obstack,
		      "#define yynerrs %snerrs\n", spec_name_prefix);
    obstack_fgrow1 (&table_obstack,
		      "#define yytypecode %stypecode\n", spec_name_prefix);
    obstack_fgrow1 (&table_obstack,
		      "#define yytypecode_cache %stypecode_cache\n",
spec_name_prefix);
  }
}


/*-------------------------------------------------------.
| Output constant strings to the ends of certain files.  |
`-------------------------------------------------------*/

void
output_trailers (void)
{
  if (semantic_parser)
    obstack_sgrow (&guard_obstack, "\n    }\n}\n");

  obstack_1grow (&action_obstack, '\n');

  if (no_parser_flag)
    return;

  if (semantic_parser)
    obstack_sgrow (&action_obstack, "    }\n");

  obstack_sgrow (&action_obstack, "}\n");
}



static void
output_token_translations (void)
{
  obstack_sgrow (&table_obstack, "\
\n\
/* YYRANSLATE(YYLEX) -- Bison token number corresponding to YYLEX. */\n");

  if (translations)
    {
      obstack_fgrow2 (&table_obstack,
      "#define YYTRANSLATE(x) ((unsigned)(x) <= %d ? yytranslate[x] : %d)\
\n\
\n",
	       max_user_token_number, nsyms);

      output_short_or_char_table (&table_obstack,
	     "YYRANSLATE[YYLEX] -- Bison token number corresponding to YYLEX",
		    ntokens < 127 ? "char" : "short",
		    "yytranslate", token_translations,
		    0, 1, max_user_token_number + 1);
    }
  else
    {
      obstack_sgrow (&table_obstack,
			   "\n#define YYTRANSLATE(x) (x)\n");
    }
}


static void
output_gram (void)
{
  /* With the ordinary parser,
     yyprhs and yyrhs are needed only for yydebug. */
  /* With the no_parser option, all tables are generated */
  if (!semantic_parser && !no_parser_flag)
    obstack_sgrow (&table_obstack, "\n#if YYDEBUG != 0\n");

  output_short_table (&table_obstack, NULL, "yyprhs", rrhs,
		      0, 1, nrules + 1);

  {
    size_t yyrhs_size = 1;
    short *yyrhs, *sp;
    int i;

    for (sp = ritem + 1; *sp; sp++)
      ++yyrhs_size;
    yyrhs = XMALLOC (short, yyrhs_size);

    for (sp = ritem + 1, i = 1; *sp; ++sp, ++i)
      yyrhs[i] = *sp > 0 ? *sp : 0;

    output_short_table (&table_obstack, NULL, "yyrhs", yyrhs,
			ritem[0], 1, yyrhs_size);
    XFREE (yyrhs);
  }

  if (!semantic_parser && !no_parser_flag)
    obstack_sgrow (&table_obstack, "\n#endif\n");
}


static void
output_stos (void)
{
  output_short_table (&table_obstack, NULL, "yystos", accessing_symbol,
		      0, 1, nstates);
}


#define SWAP(x, y) (temp = (x), (x) = (y), (y) = temp)

static void adjust(int tc[], int m, register int n) {
  register int *b, j, k, temp;
  b = tc - 1;
  j = m;
  k = m * 2;
  while (k <= n) {
    if (k < n && strcmp(tags[b[k]], tags[b[k+1]]) < 0)  ++k;
    if (strcmp(tags[b[j]], tags[b[k]]) < 0)  SWAP(b[j], b[k]);
    j = k;
    k *= 2;
  }
}


static void output_name_typecode_table(void) {
  int* tc; /* The value is a type-code in the tags table. */
  int i, j, temp, k;

  tc = calloc(nsyms, sizeof(int));

  for (i=0; i<nsyms; ++i) /* Create unsorted table. */
    tc[i] = i;

  /* Heap sort tc[], the comparison defined by tags[tc[i]]:
     See Harbison, Steele, "C, A reference manual", sec. 4.3.2. */
  for (j = nsyms/2; j > 0; --j)  adjust(tc, j, nsyms);
  for (j = nsyms-1; j > 0; --j) {
    SWAP(tc[0], tc[j]);
    adjust(tc, 1, j);
  }

  obstack_sgrow(&table_obstack, "\n");

  /* Output the size of the sorted symbol names table: */
  obstack_fgrow1(&table_obstack, "static const int yytname_typecode_size =
%d;\n\n", nsyms);

  /* Output the struct for use with the table of sorted symbol names: */
  obstack_sgrow(&table_obstack, "struct name_typecode_t { char* name; int
typecode; };\n\n");

  /* Output the table of sorted symbol names:  */

  obstack_sgrow(&table_obstack, "static const name_typecode_t
yytname_typecode[] = {\n  ");

  j = 0;
  k = nsyms - 1;
  for (i = 0; i < nsyms; ++i) {
    char *p;
    if (j > 75) {
      obstack_sgrow(&table_obstack, "\n  ");
      j = 2;
    }
    else if (i != 0) {
      obstack_sgrow(&table_obstack, " ");
      ++j;
    }

    obstack_sgrow(&table_obstack, "{\"");
    j += 2;

    for (p = tags[tc[i]]; p && *p; p++) {
      if (*p == '"' || *p == '\\') {
        obstack_fgrow1(&table_obstack, "\\%c", *p);
        j += 2;
      }
      else if (*p == '\n') {
        obstack_sgrow(&table_obstack, "\\n");
        j += 2;
      }
      else if (*p == '\t') {
        obstack_sgrow(&table_obstack, "\\t");
        j += 2;
      }
      else if (*p == '\b') {
        obstack_sgrow(&table_obstack, "\\b");
        j += 2;
      }
      else if (*p < 040 || *p >= 0177) {
        obstack_fgrow1(&table_obstack, "\\%03o", *p);
        j += 4;
      }
      else {
        obstack_1grow(&table_obstack, *p);
        j++;
      }
    }
    temp = tc[i];
    obstack_fgrow1(&table_obstack, "\", %d}", temp);
    j += 5 + (temp >= 10) + (temp >= 100) + (temp >= 1000) + (temp >= 10000);
    if (i < k) {
      obstack_sgrow(&table_obstack, ",");
      ++j;
    }
  }
  obstack_sgrow(&table_obstack, "\n};\n");

  /* Output the type-code lookup functions:  */

  obstack_sgrow(&table_obstack,
    "\nint yytypecode(const char* s);\n"
    "int yytypecode_cache(const char* s, int* cache);\n\n"
    "int yytypecode(const char* s) {\n"
    "  int low = 0, high = yytname_typecode_size;\n"
    "  while (low != high) {\n"
    "    int i = low + (high - low)/2;\n"
    "    int c = strcmp(s, yytname_typecode[i].name);\n"
    "    switch ((c > 0) - (c < 0)) {\n"
    "      case -1: high = i; break;\n"
    "      case 1: low = i + 1; break;\n");
  if (!raw_flag)
    obstack_sgrow(&table_obstack,
    "      /* Add 254 to translate from Bison to Yacc type-code: */\n"
    "      default: return yytname_typecode[i].typecode + 254;\n");
  else
    obstack_sgrow(&table_obstack,
    "      default: return yytname_typecode[i].typecode;\n");
  obstack_sgrow(&table_obstack,
    "    }\n"
    "  }\n"
    "  return -1;\n"
    "}\n\n");

  obstack_sgrow(&table_obstack,
    "int yytypecode_cache(const char* s, int* cache) {\n"
    "  if (cache != NULL && *cache >= -1)  return *cache;\n"
    "  int low = 0, high = yytname_typecode_size;\n"
    "  while (low != high) {\n"
    "    int i = low + (high - low)/2;\n"
    "    int c = strcmp(s, yytname_typecode[i].name);\n"
    "    switch ((c > 0) - (c < 0)) {\n"
    "      case -1: high = i; break;\n"
    "      case 1: low = i + 1; break;\n");
  if (!raw_flag)
    obstack_sgrow(&table_obstack,
    "      /* Add 254 to translate from Bison to Yacc type-code: */\n"
    "      default: { int tc = yytname_typecode[i].typecode + 254;\n");
  else
    obstack_sgrow(&table_obstack,
    "      default: { int tc = yytname_typecode[i].typecode;\n");
  obstack_sgrow(&table_obstack,
    "        if (cache != NULL)  *cache = tc;\n"
    "        return tc; }\n"
    "    }\n"
    "  }\n"
    "  if (cache != NULL)  *cache = -1;\n"
    "  return -1;\n"
    "}\n");

  free(tc);
}


static void
output_rule_data (void)
{
  int i;
  int j;
  short *short_tab = NULL;

  obstack_sgrow (&table_obstack, "\n\
#if YYDEBUG != 0\n");

  output_short_table (&table_obstack,
           "YYRLINE[YYN] -- source line where rule number YYN was defined",
		      "yyrline", rline,
		      0, 1, nrules + 1);

  obstack_sgrow (&table_obstack, "#endif\n\n");

  if (token_table_flag || no_parser_flag)
    {
      obstack_fgrow1 (&table_obstack, "#define YYNTOKENS %d\n", ntokens);
      obstack_fgrow1 (&table_obstack, "#define YYNNTS %d\n", nvars);
      obstack_fgrow1 (&table_obstack, "#define YYNRULES %d\n", nrules);
      obstack_fgrow1 (&table_obstack, "#define YYNSTATES %d\n", nstates);
      obstack_fgrow1 (&table_obstack, "#define YYMAXUTOK %d\n\n",
		      max_user_token_number);
    }

  /* Output the table of symbol names.  */
  if (!token_table_flag && !no_parser_flag)
    obstack_sgrow (&table_obstack,
			 "\n#if YYDEBUG != 0 || defined YYERROR_VERBOSE\n\n");
  obstack_sgrow (&table_obstack, "\
/* YYTNAME[TOKEN_NUM] -- String name of the token TOKEN_NUM. */\n");
  obstack_sgrow (&table_obstack,
	   "static const char *const yytname[] =\n{\n  ");

  j = 0;
  for (i = 0; i < nsyms; i++)
    /* this used to be i<=nsyms, but that output a final "" symbol
       almost by accident */
    {
      /* Width of the next token, including the two quotes, the coma
	 and the space.  */
      int strsize = 4;
      char *p;

      for (p = tags[i]; p && *p; p++)
	if (*p == '"' || *p == '\\' || *p == '\n' || *p == '\t'
	    || *p == '\b')
	  strsize += 2;
	else if (*p < 040 || *p >= 0177)
	  strsize += 4;
	else
	  strsize++;

      if (j + strsize > 75)
	{
	  obstack_sgrow (&table_obstack, "\n  ");
	  j = 2;
	}

      obstack_1grow (&table_obstack, '\"');
      for (p = tags[i]; p && *p; p++)
	{
	  if (*p == '"' || *p == '\\')
	    obstack_fgrow1 (&table_obstack, "\\%c", *p);
	  else if (*p == '\n')
	    obstack_sgrow (&table_obstack, "\\n");
	  else if (*p == '\t')
	    obstack_sgrow (&table_obstack, "\\t");
	  else if (*p == '\b')
	    obstack_sgrow (&table_obstack, "\\b");
	  else if (*p < 040 || *p >= 0177)
	    obstack_fgrow1 (&table_obstack, "\\%03o", *p);
	  else
	    obstack_1grow (&table_obstack, *p);
	}

      obstack_sgrow (&table_obstack, "\", ");
      j += strsize;
    }
  /* add a NULL entry to list of tokens */
  obstack_sgrow (&table_obstack, "NULL\n};\n");

  output_name_typecode_table();

  if (!token_table_flag && !no_parser_flag)
    obstack_sgrow (&table_obstack, "#endif\n\n");

  /* Output YYTOKNUM. */
  if (token_table_flag)
    {
      output_short_table (&table_obstack,
		  "YYTOKNUM[YYLEX] -- Index in YYTNAME corresponding to YYLEX",
			  "yytoknum", user_toknums,
			  0, 1, ntokens + 1);
    }

  /* Output YYR1. */
  output_short_table (&table_obstack,
	      "YYR1[YYN] -- Symbol number of symbol that rule YYN derives",
		      "yyr1", rlhs,
		      0, 1, nrules + 1);
  XFREE (rlhs + 1);

  obstack_1grow (&table_obstack, '\n');

  /* Output YYR2. */
  short_tab = XMALLOC (short, nrules + 1);
  for (i = 1; i < nrules; i++)
    short_tab[i] = rrhs[i + 1] - rrhs[i] - 1;
  short_tab[nrules] = nitems - rrhs[nrules] - 1;
  output_short_table (&table_obstack,
        "YYR2[YYN] -- Number of symbols composing right hand side of rule YYN",
		      "yyr2", short_tab,
		      0, 1, nrules + 1);
  obstack_1grow (&table_obstack, '\n');

  XFREE (short_tab);

  XFREE (rrhs + 1);
}


static void
output_defines (void)
{
  obstack_fgrow1 (&table_obstack, "\n\n#define\tYYFINAL\t\t%d\n", final_state);
  obstack_fgrow1 (&table_obstack, "#define\tYYFLAG\t\t%d\n", MINSHORT);
  obstack_fgrow1 (&table_obstack, "#define\tYYNTBASE\t%d\n", ntokens);
}


/*------------------------------------------------------------------.
| Decide what to do for each type of token if seen as the lookahead |
| token in specified state.  The value returned is used as the      |
| default action (yydefact) for the state.  In addition, actrow is  |
| filled with what to do for each kind of token, index by symbol    |
| number, with zero meaning do the default action.  The value       |
| MINSHORT, a very negative number, means this situation is an      |
| error.  The parser recognizes this value specially.               |
|                                                                   |
| This is where conflicts are resolved.  The loop over lookahead    |
| rules considered lower-numbered rules last, and the last rule     |
| considered that likes a token gets to handle it.                  |
`------------------------------------------------------------------*/

static int
action_row (int state)
{
  int i;
  int j;
  int k;
  int m = 0;
  int n = 0;
  int count;
  int default_rule;
  int nreds;
  int max;
  int rule;
  int shift_state;
  int symbol;
  unsigned mask;
  unsigned *wordp;
  reductions *redp;
  shifts *shiftp;
  errs *errp;
  int nodefault = 0;		/* set nonzero to inhibit having any
default reduction */

  for (i = 0; i < ntokens; i++)
    actrow[i] = 0;

  default_rule = 0;
  nreds = 0;
  redp = reduction_table[state];

  if (redp)
    {
      nreds = redp->nreds;

      if (nreds >= 1)
	{
	  /* loop over all the rules available here which require
	     lookahead */
	  m = lookaheads[state];
	  n = lookaheads[state + 1];

	  for (i = n - 1; i >= m; i--)
	    {
	      rule = -LAruleno[i];
	      wordp = LA + i * tokensetsize;
	      mask = 1;

	      /* and find each token which the rule finds acceptable
	         to come next */
	      for (j = 0; j < ntokens; j++)
		{
		  /* and record this rule as the rule to use if that
		     token follows.  */
		  if (mask & *wordp)
		    actrow[j] = rule;

		  mask <<= 1;
		  if (mask == 0)
		    {
		      mask = 1;
		      wordp++;
		    }
		}
	    }
	}
    }

  shiftp = shift_table[state];

  /* Now see which tokens are allowed for shifts in this state.  For
     them, record the shift as the thing to do.  So shift is preferred
     to reduce.  */

  if (shiftp)
    {
      k = shiftp->nshifts;

      for (i = 0; i < k; i++)
	{
	  shift_state = shiftp->shifts[i];
	  if (!shift_state)
	    continue;

	  symbol = accessing_symbol[shift_state];

	  if (ISVAR (symbol))
	    break;

	  actrow[symbol] = shift_state;

	  /* Do not use any default reduction if there is a shift for
	     error */
	  if (symbol == error_token_number)
	    nodefault = 1;
	}
    }

  errp = err_table[state];

  /* See which tokens are an explicit error in this state (due to
     %nonassoc).  For them, record MINSHORT as the action.  */

  if (errp)
    {
      k = errp->nerrs;

      for (i = 0; i < k; i++)
	{
	  symbol = errp->errs[i];
	  actrow[symbol] = MINSHORT;
	}
    }

  /* Now find the most common reduction and make it the default action
     for this state.  */

  if (nreds >= 1 && !nodefault)
    {
      if (consistent[state])
	default_rule = redp->rules[0];
      else
	{
	  max = 0;
	  for (i = m; i < n; i++)
	    {
	      count = 0;
	      rule = -LAruleno[i];

	      for (j = 0; j < ntokens; j++)
		{
		  if (actrow[j] == rule)
		    count++;
		}

	      if (count > max)
		{
		  max = count;
		  default_rule = rule;
		}
	    }

	  /* actions which match the default are replaced with zero,
	     which means "use the default" */

	  if (max > 0)
	    {
	      for (j = 0; j < ntokens; j++)
		{
		  if (actrow[j] == default_rule)
		    actrow[j] = 0;
		}

	      default_rule = -default_rule;
	    }
	}
    }

  /* If have no default rule, the default is an error.
     So replace any action which says "error" with "use default".  */

  if (default_rule == 0)
    for (j = 0; j < ntokens; j++)
      {
	if (actrow[j] == MINSHORT)
	  actrow[j] = 0;
      }

  return default_rule;
}


static void
save_row (int state)
{
  int i;
  int count;
  short *sp;
  short *sp1;
  short *sp2;

  count = 0;
  for (i = 0; i < ntokens; i++)
    {
      if (actrow[i] != 0)
	count++;
    }

  if (count == 0)
    return;

  froms[state] = sp1 = sp = XCALLOC (short, count);
  tos[state] = sp2 = XCALLOC (short, count);

  for (i = 0; i < ntokens; i++)
    {
      if (actrow[i] != 0)
	{
	  *sp1++ = i;
	  *sp2++ = actrow[i];
	}
    }

  tally[state] = count;
  width[state] = sp1[-1] - sp[0] + 1;
}


/*------------------------------------------------------------------.
| Figure out the actions for the specified state, indexed by        |
| lookahead token type.                                             |
|                                                                   |
| The YYDEFACT table is output now.  The detailed info is saved for |
| putting into YYTABLE later.                                       |
`------------------------------------------------------------------*/

static void
token_actions (void)
{
  int i;
  short *yydefact = XCALLOC (short, nstates);

  actrow = XCALLOC (short, ntokens);
  for (i = 0; i < nstates; ++i)
    {
      yydefact[i] = action_row (i);
      save_row (i);
    }
  XFREE (actrow);

  output_short_table (&table_obstack,
  "YYDEFACT[S] -- default rule to reduce with in state S when YYTABLE\n\
   doesn't specify something else to do.  Zero means the default is an\n\
   error",
		      "yydefact", yydefact,
		      yydefact[0], 1, nstates);
  obstack_1grow (&table_obstack, '\n');
  XFREE (yydefact);
}


static void
free_shifts (void)
{
  shifts *sp, *sptmp;	/* JF derefrenced freed ptr */

  XFREE (shift_table);

  for (sp = first_shift; sp; sp = sptmp)
    {
      sptmp = sp->next;
      XFREE (sp);
    }
}


static void
free_reductions (void)
{
  reductions *rp, *rptmp;	/* JF fixed freed ptr */

  XFREE (reduction_table);

  for (rp = first_reduction; rp; rp = rptmp)
    {
      rptmp = rp->next;
      XFREE (rp);
    }
}



static void
save_column (int symbol, int default_state)
{
  int i;
  short *sp;
  short *sp1;
  short *sp2;
  int count;
  int symno;

  short begin = goto_map[symbol];
  short end = goto_map[symbol + 1];

  count = 0;
  for (i = begin; i < end; i++)
    {
      if (to_state[i] != default_state)
	count++;
    }

  if (count == 0)
    return;

  symno = symbol - ntokens + nstates;

  froms[symno] = sp1 = sp = XCALLOC (short, count);
  tos[symno] = sp2 = XCALLOC (short, count);

  for (i = begin; i < end; i++)
    {
      if (to_state[i] != default_state)
	{
	  *sp1++ = from_state[i];
	  *sp2++ = to_state[i];
	}
    }

  tally[symno] = count;
  width[symno] = sp1[-1] - sp[0] + 1;
}

static int
default_goto (int symbol)
{
  int i;
  int m;
  int n;
  int default_state;
  int max;

  m = goto_map[symbol];
  n = goto_map[symbol + 1];

  if (m == n)
    return -1;

  for (i = 0; i < nstates; i++)
    state_count[i] = 0;

  for (i = m; i < n; i++)
    state_count[to_state[i]]++;

  max = 0;
  default_state = -1;

  for (i = 0; i < nstates; i++)
    {
      if (state_count[i] > max)
	{
	  max = state_count[i];
	  default_state = i;
	}
    }

  return default_state;
}


/*-------------------------------------------------------------------.
| Figure out what to do after reducing with each rule, depending on  |
| the saved state from before the beginning of parsing the data that |
| matched this rule.                                                 |
|                                                                    |
| The YYDEFGOTO table is output now.  The detailed info is saved for |
| putting into YYTABLE later.                                        |
`-------------------------------------------------------------------*/

static void
goto_actions (void)
{
  int i;

  short *yydefgoto = XMALLOC (short, nsyms - ntokens);
  state_count = XCALLOC (short, nstates);

  for (i = ntokens; i < nsyms; ++i)
    {
      int default_state = default_goto (i);
      save_column (i, default_state);
      yydefgoto[i - ntokens] = default_state;
    }

  output_short_table (&table_obstack, NULL, "yydefgoto", yydefgoto,
		      yydefgoto[0], 1, nsyms - ntokens);

  XFREE (state_count);
  XFREE (yydefgoto);
}


/* The next few functions decide how to pack the actions and gotos
   information into yytable. */

static void
sort_actions (void)
{
  int i;
  int j;
  int k;
  int t;
  int w;

  order = XCALLOC (short, nvectors);
  nentries = 0;

  for (i = 0; i < nvectors; i++)
    {
      if (tally[i] > 0)
	{
	  t = tally[i];
	  w = width[i];
	  j = nentries - 1;

	  while (j >= 0 && (width[order[j]] < w))
	    j--;

	  while (j >= 0 && (width[order[j]] == w) && (tally[order[j]] < t))
	    j--;

	  for (k = nentries - 1; k > j; k--)
	    order[k + 1] = order[k];

	  order[j + 1] = i;
	  nentries++;
	}
    }
}


static int
matching_state (int vector)
{
  int i;
  int j;
  int k;
  int t;
  int w;
  int match;
  int prev;

  i = order[vector];
  if (i >= nstates)
    return -1;

  t = tally[i];
  w = width[i];

  for (prev = vector - 1; prev >= 0; prev--)
    {
      j = order[prev];
      if (width[j] != w || tally[j] != t)
	return -1;

      match = 1;
      for (k = 0; match && k < t; k++)
	{
	  if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k])
	    match = 0;
	}

      if (match)
	return j;
    }

  return -1;
}


static int
pack_vector (int vector)
{
  int i;
  int j;
  int k;
  int t;
  int loc = 0;
  int ok;
  short *from;
  short *to;

  i = order[vector];
  t = tally[i];

  assert (t);

  from = froms[i];
  to = tos[i];

  for (j = lowzero - from[0]; j < MAXTABLE; j++)
    {
      ok = 1;

      for (k = 0; ok && k < t; k++)
	{
	  loc = j + from[k];
	  if (loc > MAXTABLE)
	    fatal (_("maximum table size (%d) exceeded"), MAXTABLE);

	  if (table[loc] != 0)
	    ok = 0;
	}

      for (k = 0; ok && k < vector; k++)
	{
	  if (pos[k] == j)
	    ok = 0;
	}

      if (ok)
	{
	  for (k = 0; k < t; k++)
	    {
	      loc = j + from[k];
	      table[loc] = to[k];
	      check[loc] = from[k];
	    }

	  while (table[lowzero] != 0)
	    lowzero++;

	  if (loc > high)
	    high = loc;

	  return j;
	}
    }

  berror ("pack_vector");
  return 0;			/* JF keep lint happy */
}


static void
pack_table (void)
{
  int i;
  int place;
  int state;

  base = XCALLOC (short, nvectors);
  pos = XCALLOC (short, nentries);
  table = XCALLOC (short, MAXTABLE);
  check = XCALLOC (short, MAXTABLE);

  lowzero = 0;
  high = 0;

  for (i = 0; i < nvectors; i++)
    base[i] = MINSHORT;

  for (i = 0; i < MAXTABLE; i++)
    check[i] = -1;

  for (i = 0; i < nentries; i++)
    {
      state = matching_state (i);

      if (state < 0)
	place = pack_vector (i);
      else
	place = base[state];

      pos[i] = place;
      base[order[i]] = place;
    }

  for (i = 0; i < nvectors; i++)
    {
      if (froms[i])
	XFREE (froms[i]);
      if (tos[i])
	XFREE (tos[i]);
    }

  XFREE (froms);
  XFREE (tos);
  XFREE (pos);
}

/* the following functions output yytable, yycheck
   and the vectors whose elements index the portion starts */

static void
output_base (void)
{
  output_short_table (&table_obstack, NULL, "yypact", base,
		      base[0], 1, nstates);

  obstack_1grow (&table_obstack, '\n');

  output_short_table (&table_obstack, NULL, "yypgoto", base,
		      base[nstates], nstates + 1, nvectors);

  XFREE (base);
}


static void
output_table (void)
{
  obstack_fgrow1 (&table_obstack, "\n\n#define\tYYLAST\t\t%d\n\n\n", high);
  output_short_table (&table_obstack, NULL, "yytable", table,
		      table[0], 1, high + 1);
  XFREE (table);
}


static void
output_check (void)
{
  output_short_table (&table_obstack, NULL, "yycheck", check,
		      check[0], 1, high + 1);
  XFREE (check);
}

/* compute and output yydefact, yydefgoto, yypact, yypgoto, yytable
   and yycheck.  */

static void
output_actions (void)
{
  nvectors = nstates + nvars;

  froms = XCALLOC (short *, nvectors);
  tos = XCALLOC (short *, nvectors);
  tally = XCALLOC (short, nvectors);
  width = XCALLOC (short, nvectors);

  token_actions ();
  free_shifts ();
  free_reductions ();
  XFREE (lookaheads);
  XFREE (LA);
  XFREE (LAruleno);
  XFREE (accessing_symbol);

  goto_actions ();
  XFREE (goto_map + ntokens);
  XFREE (from_state);
  XFREE (to_state);

  sort_actions ();
  pack_table ();
  obstack_1grow (&table_obstack, '\n');
  output_base ();
  output_table ();
  obstack_1grow (&table_obstack, '\n');
  output_check ();
}

/*------------------------------------------.
| Copy the parser code into TABLE_OBSTACK.  |
`------------------------------------------*/

static void
output_parser (void)
{
  int c;
  FILE *fskel;
  size_t line;
  const char *skeleton = NULL;
  int actions_dumped = 0;

  if (pure_parser)
    obstack_sgrow (&table_obstack, "#define YYPURE 1\n\n");

  /* Loop over lines in the standard parser file.  */
  if (semantic_parser)
    skeleton = skeleton_find ("BISON_HAIRY", BISON_HAIRY);
  else
    skeleton = skeleton_find ("BISON_SIMPLE", BISON_SIMPLE);
  fskel = xfopen (skeleton, "r");

  /* Set LINE to 2, not 1: `#line LINENUM' -- Here LINENUM is a
     decimal integer constant.  This specifies that the line number of
     the *following* line of input, in its original source file, was
     LINENUM.  */
  line = 2;

  while (1)
    {
      enum line_type_e
	{
	  regular_line,
	  sync_line,	/* #line. */
	  actions_line	/* %% actions. */
	};
      enum line_type_e line_type = regular_line;

      c = getc (fskel);

      /* Is this line special? */
      if (c == '#')
	{
	  /* See if it's a `#line' line. */
	  if ((c = getc (fskel)) == 'l')
	    if ((c = getc (fskel)) == 'i')
	      if ((c = getc (fskel)) == 'n')
		if ((c = getc (fskel)) == 'e')
		  line_type = sync_line;
		else
		  obstack_sgrow (&table_obstack, "#lin");
	      else
		obstack_sgrow (&table_obstack, "#li");
	    else
	      obstack_sgrow (&table_obstack, "#l");
	  else
	    obstack_sgrow (&table_obstack, "#");
	}
      else if (c == '%')
	{
	  /* See if it's a `%% actions' line. */
	  if ((c = getc (fskel)) == '%')
	    if ((c = getc (fskel)) == ' ')
	      if ((c = getc (fskel)) == 'a')
		if ((c = getc (fskel)) == 'c')
		  if ((c = getc (fskel)) == 't')
		    if ((c = getc (fskel)) == 'i')
		      if ((c = getc (fskel)) == 'o')
			if ((c = getc (fskel)) == 'n')
			  if ((c = getc (fskel)) == 's')
			    line_type = actions_line;
			  else
			    obstack_sgrow (&table_obstack, "%% action");
			else
			  obstack_sgrow (&table_obstack, "%% actio");
		      else
			obstack_sgrow (&table_obstack, "%% acti");
		    else
		      obstack_sgrow (&table_obstack, "%% act");
		  else
		    obstack_sgrow (&table_obstack, "%% ac");
		else
		  obstack_sgrow (&table_obstack, "%% a");
	      else
		obstack_sgrow (&table_obstack, "%% ");
	    else
	      obstack_sgrow (&table_obstack, "%%");
	  else
	    obstack_sgrow (&table_obstack, "%");
	}

      switch (line_type)
	{
	case sync_line:
	  if (!no_lines_flag)
#if __MWERKS__ && macintosh
	    obstack_fgrow2 (&table_obstack, "#line %d %s\n",
			    line, quotearg_style (c_quoting_style,
			      semantic_parser? BISON_HAIRY : BISON_SIMPLE));
#else
	    obstack_fgrow2 (&table_obstack, "#line %d %s\n",
			    line, quotearg_style (c_quoting_style, skeleton));
#endif

	  /* Skip the end of line. */
	  for (; c != '\n' && c != EOF; c = getc (fskel))
	    /* nothing */;
	  break;

	case actions_line:
	  {
	    size_t size = obstack_object_size (&action_obstack);

	    actions_dumped++;
	    assert (actions_dumped == 1);
	    obstack_grow (&table_obstack,
			  obstack_finish (&action_obstack),
			  size);
	  }

	  /* Skip the end of line. */
	  for (; c != '\n' && c != EOF; c = getc (fskel))
	    /* nothing */;
	  break;

	case regular_line:
	  for (; c != '\n' && c != EOF; c = getc (fskel))
	    obstack_1grow (&table_obstack, c);
	}

      if (c == EOF)
	break;
      obstack_1grow (&table_obstack, c);
      line++;
    }
  assert (actions_dumped == 1);
  xfclose (fskel);
}

static void
output_program (void)
{
  int c;

  if (!no_lines_flag)
    obstack_fgrow2 (&table_obstack, "#line %d %s\n",
		    lineno, quotearg_style (c_quoting_style, infile));

  while ((c = getc (finput)) != EOF)
    obstack_1grow (&table_obstack, c);
}


static void
free_itemsets (void)
{
  core *cp, *cptmp;

  XFREE (state_table);

  for (cp = first_state; cp; cp = cptmp)
    {
      cptmp = cp->next;
      XFREE (cp);
    }
}


/*----------------------------------------------------------.
| Output the parsing tables and the parser code to ftable.  |
`----------------------------------------------------------*/

void
output (void)
{
  /* output_token_defines(ftable);      / * JF put out token defines FIRST */

  /* If using a simple parser the definition of YYSTYPE are put into
     TABLE_OBSTACK.  */
  if (!semantic_parser)
    {
      size_t size = obstack_object_size (&attrs_obstack);
      obstack_grow (&table_obstack, obstack_finish (&attrs_obstack), size);
    }
  reader_output_yylsp (&table_obstack);
  if (debug_flag)
    obstack_sgrow (&table_obstack, "\
#ifndef YYDEBUG\n\
# define YYDEBUG 1\n\
#endif\n\
\n");

  if (semantic_parser)
    obstack_fgrow1 (&table_obstack, "#include %s\n",
		    quotearg_style (c_quoting_style, attrsfile));

  if (!no_parser_flag)
    obstack_sgrow (&table_obstack, "#include <stdio.h>\n\n");

  /* Make "const" do nothing if not in ANSI C.  */
  obstack_sgrow (&table_obstack, "\
#ifndef __cplusplus\n\
# ifndef __STDC__\n\
#  define const\n\
# endif\n\
#endif\n\
\n");

  free_itemsets ();
  output_defines ();
  output_token_translations ();
/*   if (semantic_parser) */
  /* This is now unconditional because debugging printouts can use it.  */
  output_gram ();
  XFREE (ritem);
  if (semantic_parser)
    output_stos ();
  output_rule_data ();
  output_actions ();
  if (!no_parser_flag)
    output_parser ();
  output_program ();
}

--============_-1234514193==_============
Content-Type: text/plain; charset="us-ascii"

  Hans Aberg

--============_-1234514193==_============--



From rms@santafe.edu Tue Dec 26 09:29:14 2000
Received: from pele.santafe.edu ([192.12.12.119])
	by fencepost.gnu.org with esmtp (Exim 3.16 #1 (Debian))
	id 14Av6I-0005cI-00; Tue, 26 Dec 2000 09:29:14 -0500
Received: from wijiji.santafe.edu (wijiji [192.12.12.5])
	by pele.santafe.edu (8.9.3/8.9.1) with ESMTP id HAA06628;
	Tue, 26 Dec 2000 07:29:11 -0700 (MST)
Received: (from rms@localhost)
	by wijiji.santafe.edu (8.9.3+Sun/8.9.1) id HAA17437;
	Tue, 26 Dec 2000 07:29:11 -0700 (MST)
Date: Tue, 26 Dec 2000 07:29:11 -0700 (MST)
Message-Id: <200012261429.HAA17437@wijiji.santafe.edu>
X-Authentication-Warning: wijiji.santafe.edu: rms set sender to rms@wijiji.santafe.edu using -f
From: Richard Stallman <rms@gnu.org>
To: haberg@matematik.su.se
CC: akim@epita.fr, bug-bison@gnu.org, help-bison@gnu.org
In-reply-to: <v03110705b610ddd8661a@[195.100.226.134]> (message from Hans
	Aberg on Mon, 16 Oct 2000 19:24:59 +0200)
Subject: Re: Bison and C++
Reply-to: rms@gnu.org
References: <v0311070db60fb91f6357@[195.100.226.144]> (message from Hans
 Aberg on Sun, 15 Oct 2000 22:14:08 +0200)
 <v03110701b60df035f07d@[195.100.226.157]> (message from Hans Aberg on
 Sat, 14 Oct 2000 13:41:01 +0200)
 <v03110702b608a4ede719@[195.100.226.147]> (message from Hans Aberg on
 Tue, 10 Oct 2000 12:59:28 +0200) Hans Aberg's message of "Sat, 7 Oct 2000
 15:25:33 +0200" <v03110706b604d0018bec@[195.100.226.145]>
 <v03110702b608a4ede719@[195.100.226.147]>
 <v03110701b60df035f07d@[195.100.226.157]>
 <v0311070db60fb91f6357@[195.100.226.144]> <v03110705b610ddd8661a@[195.100.226.134]>
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

    When debugging takes place, one sees the original source code in the debug
    window (.c file in C), with an arrow pointing at the line where the PC
    (program counter) currently is.

M-x gdb in Emacs will do this for you.

    It keeps track of _all_ data relevant for debugging for you.
    Thus, one never has to write down which variables to debug.

Could you be more specific?  What is the feature you would like?  What
information is in this data?  I am having trouble understanding what
you've said.

     For debugging
    C++ code, I have found it especially important that one can follow the
    dynamic type of a polymorphic pointer -- without that feature, it is rather
    hopeless trying to debug massively dynamic data.

I am not completely sure what this means, since I don't use C++.  But
it could be an important feature for us to add.  Could you be more
specific?

I have a feeling this feature is not related specifically to Bison,
but rather a more general issue about C++ (and maybe other languages),
and supporting the general feature will automatically take care of
Bison.



From haberg@matematik.su.se Tue Dec 26 17:10:06 2000
Received: from angel.algonet.se ([194.213.74.112])
	by fencepost.gnu.org with smtp (Exim 3.16 #1 (Debian))
	id 14B2II-0007eX-00
	for <bug-bison@gnu.org>; Tue, 26 Dec 2000 17:10:06 -0500
Received: (qmail 18657 invoked from network); 26 Dec 2000 23:10:03 +0100
Received: from delenn.tninet.se (HELO algonet.se) (195.100.94.104)
  by angel.algonet.se with SMTP; 26 Dec 2000 23:10:03 +0100
Received: from  [195.100.226.129] (du129-226.ppp.su-anst.tninet.se [195.100.226.129])
 by delenn.tninet.se (BLUETAIL Mail Robustifier 2.2.1) with ESMTP
 id 219180.868600.977delenn-s2
 ; Tue, 26 Dec 2000 23:10:00 +0100
X-Sender: haberg@pop.matematik.su.se
Message-Id: <v03110700b66eb9e093e4@[195.100.226.129]>
In-Reply-To: <200012261429.HAA17437@wijiji.santafe.edu>
References: <v03110705b610ddd8661a@[195.100.226.134]> (message from Hans
 Aberg on Mon, 16 Oct 2000 19:24:59 +0200)
 <v0311070db60fb91f6357@[195.100.226.144]> (message from Hans Aberg on
 Sun, 15 Oct 2000 22:14:08 +0200)
 <v03110701b60df035f07d@[195.100.226.157]> (message from Hans Aberg on
 Sat, 14 Oct 2000 13:41:01 +0200)
 <v03110702b608a4ede719@[195.100.226.147]> (message from Hans Aberg on
 Tue, 10 Oct 2000 12:59:28 +0200) Hans Aberg's message of "Sat, 7 Oct 2000
 15:25:33 +0200" <v03110706b604d0018bec@[195.100.226.145]>
 <v03110702b608a4ede719@[195.100.226.147]>
 <v03110701b60df035f07d@[195.100.226.157]>
 <v0311070db60fb91f6357@[195.100.226.144]>
 <v03110705b610ddd8661a@[195.100.226.134]>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Tue, 26 Dec 2000 23:08:53 +0100
To: rms@gnu.org
From: Hans Aberg <haberg@matematik.su.se>
Subject: Re: Bison and C++
Cc: akim@epita.fr, bug-bison@gnu.org
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

[I removed the help-bison@gnu.org cc, the topic seems to be not of any
importance for that list.]

At 07:29 -0700 0-12-26, Richard Stallman wrote:
>    When debugging takes place, one sees the original source code in the debug
>    window (.c file in C), with an arrow pointing at the line where the PC
>    (program counter) currently is.
>
>M-x gdb in Emacs will do this for you.

Thank you; I will try it out, if I get access to GNU tools (which will
happen when I switch to MacOS X.

If it is the same feature we are speaking about: What I meant is that the
arrow points at the .y source file when stepping around. So one should see
the Bison rules with an arrow.

I have since learnt that this cannot currently be done with the Metrowerks
CodeWarrior (CW) IDE by third party developers, because the format of their
symbolic files are not public.

When a regular C/C++ source is compiled, the CW, apart from the object .o
file, also writes a special .sym file with information for the debugger
about which names should be debugged, their format, and so on, sufficient
for debugging. If I would have implemented the feature I wanted for Bison,
it would have been necessary to directly write a .sym file with the
information about the .y rules.

Perhaps this process can be explained by adding extensions (which is not
the way it is done by the compiler, but what I do here simply to illustrate
the reasoning. So suppose a file <name>.c is compiled, and call the
produced object file <name>.c.o with the ".c" retained, in order to keep
track of its origin. Then, for debugging purposes, one also gets a
<name>.c.sym file which the debugger can use to debug the <name>.c.o file.

Now, with bison I start with a <name>.y file, and get a <name>.c file
(skipping the actual "tab" extension). Now it seems that I should also
somehow produce a <name>.y.sym file, which the debugger uses together with
the <name>.c.sym to debug the final <name>.c.o file. -- I do not see the
actual details, but this is the idea that comes to my mind.

The thing is that if one tries to debug the <name>.c.o file directly, it is
extremely hard, because it just goes around in a very long loop. So it is
hard from that interaction alone to figure out what is going on. -- Somehow
the data that is now available in the debugging files ought to be made
available in interactive debugging.

>I have a feeling this feature [the one discussed below] is not related
>specifically to >Bison,
>but rather a more general issue about C++ (and maybe other languages),
>and supporting the general feature will automatically take care of
>Bison.

Right. So perhaps it should be taken off the bugs-bison list; I leave that
at your discretion.

>    It keeps track of _all_ data relevant for debugging for you.
>    Thus, one never has to write down which variables to debug.
>
>Could you be more specific?  What is the feature you would like?  What
>information is in this data?  I am having trouble understanding what
>you've said.

First, you must understand that I have not used GDB for a few years. When I
used it, I recall one had to use special command to write in the source
file; there were separate debugging source files one had to write . There
is not anything wrong with this system, because it might be needed for
especially tricky debugging.

But the GUI debuggers I used first developed so that one could view a
variable in the GUI debugger by typing its name. But now the CW IDE
debugger has done away with that altogether: All variables are already
present in the debugger and can be reached directly, and no names need to
be typed. One can even select a name in the source code, and hold down the
pointing devise onto it, and all possible information about that variable
is displayed. This is very convenient for most debugging, because it is
fast and very easy access. In non-debugging mode, one can in this way find
the place where any name is declared or defined, so it is very easy to
check out the source codes.

I cannot describe it any better; the best way to figure it out is probably
to get hold of a copy of the IDE, and check it out. The one reason I can
think of using the CW IDE over GNU is that GNU might not have this very
convenient feature.

>     For debugging
>    C++ code, I have found it especially important that one can follow the
>    dynamic type of a polymorphic pointer -- without that feature, it is
>rather
>    hopeless trying to debug massively dynamic data.
>
>I am not completely sure what this means, since I don't use C++.  But
>it could be an important feature for us to add.  Could you be more
>specific?

C++ has makes available various runtime information (RTTI). C++ has a
single one form of a polymorphic variable, or an object which can change
its type at runtime, namely the polymorphic pointer: If one has a class A
and derives from it a class B, then one can write
  A* ap = new B();
The static type pointer to an  A  named  ap  now points to a dynamically
allocated  B  pointer. It means that in the C++ static typing, this is just
an  ap  pointer, but C++ has mechanism for keeping track of the dynamic
type  B, for example, via "virtual functions", or by using C++ RTTI. (In
C++, in order for A* to qualify as a "polymorphic type", it must contain at
least one "virtual function". If a function name, say "f" is declared
virtual in A, and is called later statcially in the C++ code by "ap->f()",
then if B has a copy that is identical in typing to that of A::f, in
runtime, B::f will be called.)

Now to the debugging: If the debugger only handles C++ static typing, it
will show that  ap  is an  A, and will only display that structure of it
(the names in that class and their values).

But if the debugger handles C++ dynamic data, it will show that the  ap  is
actually a  B, and will show that (the names in that class  B  and their
values).

The CW IDE has a feature that says that it will "attempt" to display the
dynamic type. Once upon the time this feature also worked, and I found it
extremely useful when working with a program using a lot of dynamic data
typing. (However, it does not work currently -- in an upgrade, the
functionality of the feature was lost, and the latest upgrades have not
fixed that bug.)

But as a said, I think this is a very useful debugging feature when
debugging a polymorphic variable: If one produces a program that juggles
such a polymorphic pointer, it is in practise impossible to figure out what
it contains at any given runtime moment. But with the feature, one simply
goes in, and checks its value.

  Hans Aberg




From bob@rattlesnake.com Wed Dec 27 09:18:40 2000
Received: from megalith.rattlesnake.com ([140.186.114.245])
	by fencepost.gnu.org with esmtp (Exim 3.16 #1 (Debian))
	id 14BHPc-0000Vs-00
	for <bug-bison@gnu.org>; Wed, 27 Dec 2000 09:18:40 -0500
Received: by rattlesnake.com
	via sendmail from stdin
	id <m14BHPa-000BCPC@megalith.rattlesnake.com> (Debian Smail3.2.0.102)
	for bug-bison@gnu.org; Wed, 27 Dec 2000 09:18:38 -0500 (EST) 
Message-Id: <m14BHPa-000BCPC@megalith.rattlesnake.com>
Date: Wed, 27 Dec 2000 09:18:38 -0500 (EST)
From: "Robert J. Chassell" <root@megalith.rattlesnake.com>
To: bug-bison@gnu.org
Subject: Bison manual does not mention Emacs
Reply-to: bob@rattlesnake.com
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

The manual for Bison version 1.28, 1999 Jan 14, 
bison.texinfo, does not mention GNU Emacs.  

I think we all just assumed that anyone editing with Emacs would visit
a file and see what happens -- Emacs does the right thing.
But I just came across a person who did not do that.

A one line sentence would work:

    You can edit bison or yacc files using GNU Emacs.

But it would be really nice if someone who understood this sort of
thing would write a short chapter, `Editing with GNU Emacs'.  
People may not think of syntaxic highlighting (font lock), etags, M-x
compile, M-x gdb, and the new Info-lookup and ebnf2ps commands.

-- 
    Robert J. Chassell                  bob@rattlesnake.com
    Rattlesnake Enterprises             http://www.rattlesnake.com


From rms@santafe.edu Wed Dec 27 23:57:16 2000
Received: from pele.santafe.edu ([192.12.12.119])
	by fencepost.gnu.org with esmtp (Exim 3.16 #1 (Debian))
	id 14BV7s-0004CU-00; Wed, 27 Dec 2000 23:57:16 -0500
Received: from aztec.santafe.edu (aztec [192.12.12.49])
	by pele.santafe.edu (8.9.3/8.9.1) with ESMTP id VAA08242;
	Wed, 27 Dec 2000 21:57:14 -0700 (MST)
Received: (from rms@localhost)
	by aztec.santafe.edu (8.9.3+Sun/8.9.1) id VAA01899;
	Wed, 27 Dec 2000 21:57:14 -0700 (MST)
Date: Wed, 27 Dec 2000 21:57:14 -0700 (MST)
Message-Id: <200012280457.VAA01899@aztec.santafe.edu>
X-Authentication-Warning: aztec.santafe.edu: rms set sender to rms@aztec.santafe.edu using -f
From: Richard Stallman <rms@gnu.org>
To: haberg@matematik.su.se
CC: akim@epita.fr, bug-bison@gnu.org
In-reply-to: <v03110700b66eb9e093e4@[195.100.226.129]> (message from Hans
	Aberg on Tue, 26 Dec 2000 23:08:53 +0100)
Subject: Re: Bison and C++
Reply-to: rms@gnu.org
References: <v03110705b610ddd8661a@[195.100.226.134]> (message from Hans
 Aberg on Mon, 16 Oct 2000 19:24:59 +0200)
 <v0311070db60fb91f6357@[195.100.226.144]> (message from Hans Aberg on
 Sun, 15 Oct 2000 22:14:08 +0200)
 <v03110701b60df035f07d@[195.100.226.157]> (message from Hans Aberg on
 Sat, 14 Oct 2000 13:41:01 +0200)
 <v03110702b608a4ede719@[195.100.226.147]> (message from Hans Aberg on
 Tue, 10 Oct 2000 12:59:28 +0200) Hans Aberg's message of "Sat, 7 Oct 2000
 15:25:33 +0200" <v03110706b604d0018bec@[195.100.226.145]>
 <v03110702b608a4ede719@[195.100.226.147]>
 <v03110701b60df035f07d@[195.100.226.157]>
 <v0311070db60fb91f6357@[195.100.226.144]>
 <v03110705b610ddd8661a@[195.100.226.134]> <v03110700b66eb9e093e4@[195.100.226.129]>
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

    If it is the same feature we are speaking about: What I meant is that the
    arrow points at the .y source file when stepping around. So one should see
    the Bison rules with an arrow.

I believe that works, thanks to the #line directive.

    When a regular C/C++ source is compiled, the CW, apart from the object .o
    file, also writes a special .sym file with information for the debugger
    about which names should be debugged, their format, and so on, sufficient
    for debugging.

I am not sure what "which names should be debugged" means.

GCC also outputs information about all the variable names and their
data types, and this too should be "sufficient for debugging".
This is what -g does.  However, it could be that the other compiler
includes a particular kind of information which GCC does not generate.
If so, we might be able to think about adding something additional
*if you could give a more specific suggestion*.

    First, you must understand that I have not used GDB for a few years. When I
    used it, I recall one had to use special command to write in the source
    file; there were separate debugging source files one had to write .

I am not sure what you mean, but I don't believe this is true with GDB.

    Now to the debugging: If the debugger only handles C++ static typing, it
    will show that  ap  is an  A, and will only display that structure of it
    (the names in that class and their values).

    But if the debugger handles C++ dynamic data, it will show that the  ap  is
    actually a  B, and will show that (the names in that class  B  and their
    values).

That is specific enough that I can pass it along to the GDB developers.
Thanks.



From haberg@matematik.su.se Thu Dec 28 05:14:48 2000
Received: from knatte.tninet.se ([195.100.94.10])
	by fencepost.gnu.org with smtp (Exim 3.16 #1 (Debian))
	id 14Ba59-0000CI-00
	for <bug-bison@gnu.org>; Thu, 28 Dec 2000 05:14:48 -0500
Received: (qmail 26935 invoked from network); 28 Dec 2000 11:14:45 +0100
Received: from delenn.tninet.se (HELO algonet.se) (195.100.94.104)
  by knatte.tninet.se with SMTP; 28 Dec 2000 11:14:45 +0100
Received: from  [195.100.226.131] (du140-226.ppp.su-anst.tninet.se [195.100.226.140])
 by delenn.tninet.se (BLUETAIL Mail Robustifier 2.2.1) with ESMTP
 id 238421.998483.977delenn-s2
 ; Thu, 28 Dec 2000 11:14:43 +0100
X-Sender: haberg@pop.matematik.su.se
Message-Id: <v03110701b670bde72640@[195.100.226.131]>
In-Reply-To: <200012280457.VAA01899@aztec.santafe.edu>
References: <v03110700b66eb9e093e4@[195.100.226.129]> (message from Hans
 Aberg on Tue, 26 Dec 2000 23:08:53 +0100)
 <v03110705b610ddd8661a@[195.100.226.134]> (message from Hans Aberg on
 Mon, 16 Oct 2000 19:24:59 +0200)
 <v0311070db60fb91f6357@[195.100.226.144]> (message from Hans Aberg on
 Sun, 15 Oct 2000 22:14:08 +0200)
 <v03110701b60df035f07d@[195.100.226.157]> (message from Hans Aberg on
 Sat, 14 Oct 2000 13:41:01 +0200)
 <v03110702b608a4ede719@[195.100.226.147]> (message from Hans Aberg on
 Tue, 10 Oct 2000 12:59:28 +0200) Hans Aberg's message of "Sat, 7 Oct 2000
 15:25:33 +0200" <v03110706b604d0018bec@[195.100.226.145]>
 <v03110702b608a4ede719@[195.100.226.147]>
 <v03110701b60df035f07d@[195.100.226.157]>
 <v0311070db60fb91f6357@[195.100.226.144]>
 <v03110705b610ddd8661a@[195.100.226.134]>
 <v03110700b66eb9e093e4@[195.100.226.129]>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Thu, 28 Dec 2000 10:58:46 +0100
To: rms@gnu.org
From: Hans Aberg <haberg@matematik.su.se>
Subject: Re: Bison and C++
Cc: akim@epita.fr, bug-bison@gnu.org
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

At 21:57 -0700 0-12-27, Richard Stallman wrote:
>    If it is the same feature we are speaking about: What I meant is that the
>    arrow points at the .y source file when stepping around. So one should see
>    the Bison rules with an arrow.
>
>I believe that works, thanks to the #line directive.

So it is perhaps at least some of the information I asked for. I would need
to get hold of copy of GDB and try it out, in order to be more specific.

>    When a regular C/C++ source is compiled, the CW, apart from the object .o
>    file, also writes a special .sym file with information for the debugger
>    about which names should be debugged, their format, and so on, sufficient
>    for debugging.
>
>I am not sure what "which names should be debugged" means.
>
>GCC also outputs information about all the variable names and their
>data types, and this too should be "sufficient for debugging".
>This is what -g does.  However, it could be that the other compiler
>includes a particular kind of information which GCC does not generate.
>If so, we might be able to think about adding something additional
>*if you could give a more specific suggestion*.

I would need to get hold of GDB in order to be more specific (or asking
somebody well acquainted with both it and CW). If I find out something, I
will get back to you.

  Hans Aberg




From haberg@matematik.su.se Thu Dec 28 16:33:00 2000
Received: from angel.algonet.se ([194.213.74.112])
	by fencepost.gnu.org with smtp (Exim 3.16 #1 (Debian))
	id 14BkfU-0004x6-00
	for <bug-bison@gnu.org>; Thu, 28 Dec 2000 16:33:00 -0500
Received: (qmail 18448 invoked from network); 28 Dec 2000 20:46:16 +0100
Received: from delenn.tninet.se (HELO algonet.se) (195.100.94.104)
  by angel.algonet.se with SMTP; 28 Dec 2000 20:46:16 +0100
Received: from  [195.100.226.131] (du143-226.ppp.su-anst.tninet.se [195.100.226.143])
 by delenn.tninet.se (BLUETAIL Mail Robustifier 2.2.1) with ESMTP
 id 185225.32774.978delenn-s2
 ; Thu, 28 Dec 2000 20:46:14 +0100
X-Sender: haberg@pop.matematik.su.se
Message-Id: <v0311070bb67142f06b34@[195.100.226.131]>
In-Reply-To: <200012280457.VAA01899@aztec.santafe.edu>
References: <v03110700b66eb9e093e4@[195.100.226.129]> (message from Hans
 Aberg on Tue, 26 Dec 2000 23:08:53 +0100)
 <v03110705b610ddd8661a@[195.100.226.134]> (message from Hans Aberg on
 Mon, 16 Oct 2000 19:24:59 +0200)
 <v0311070db60fb91f6357@[195.100.226.144]> (message from Hans Aberg on
 Sun, 15 Oct 2000 22:14:08 +0200)
 <v03110701b60df035f07d@[195.100.226.157]> (message from Hans Aberg on
 Sat, 14 Oct 2000 13:41:01 +0200)
 <v03110702b608a4ede719@[195.100.226.147]> (message from Hans Aberg on
 Tue, 10 Oct 2000 12:59:28 +0200) Hans Aberg's message of "Sat, 7 Oct 2000
 15:25:33 +0200" <v03110706b604d0018bec@[195.100.226.145]>
 <v03110702b608a4ede719@[195.100.226.147]>
 <v03110701b60df035f07d@[195.100.226.157]>
 <v0311070db60fb91f6357@[195.100.226.144]>
 <v03110705b610ddd8661a@[195.100.226.134]>
 <v03110700b66eb9e093e4@[195.100.226.129]>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Thu, 28 Dec 2000 20:30:53 +0100
To: rms@gnu.org
From: Hans Aberg <haberg@matematik.su.se>
Subject: Re: Bison and C++
Cc: akim@epita.fr, bug-bison@gnu.org
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

At 21:57 -0700 0-12-27, Richard Stallman wrote:
>    When a regular C/C++ source is compiled, the CW, apart from the object .o
>    file, also writes a special .sym file with information for the debugger
>    about which names should be debugged, their format, and so on, sufficient
>    for debugging.
>
>I am not sure what "which names should be debugged" means.
>
>GCC also outputs information about all the variable names and their
>data types, and this too should be "sufficient for debugging".
>This is what -g does.  However, it could be that the other compiler
>includes a particular kind of information which GCC does not generate.
>If so, we might be able to think about adding something additional
>*if you could give a more specific suggestion*.
>
>    First, you must understand that I have not used GDB for a few years.
>When I
>    used it, I recall one had to use special command to write in the source
>    file; there were separate debugging source files one had to write .
>
>I am not sure what you mean, but I don't believe this is true with GDB.

I go this information from Andrew Cunningham <andrewc@vasci.com>:
>Typically the vendors (e.g Apple with Project Builder and HP-UX with WDB)
>wrap a proprietary GUI around GDB, which after all is just a command line
>tool.
>
>Those GUI is the only thing you can really compare to the CW IDE debugger.
>Given that PB is in early stages of development, I can only compare WDB to
>CW IDE and I would say that both have all the functionality I would ever
>need. I think the CW IDE has been constrained by having to run on MacOS so
>some of the more powerful ( = obscure) features of GDB are missing, just
>because the OS never supported it.

So what I speak about is really this graphics IDE (integrated development
environment), a GUI put on top of the compiler (as GCC) and the debugger
(as GDB). The only think needed is that the compiler and debugger are able
to provide the information needed to create that GUI. So what I am asking
for is something like that HP WDB, which Andrew says has the functionality
he ever would need. Wasn't there an xdb for X-windows?

I made such a compiler plugin for Bison with the CW IDE, and it wasn't very
difficult to get it to display compiler information. But it is limited in
that much of the information I would want it to display evidently depends
on an inhouse formats (sources are not public). So therefore I think it
would important to have a GNU IDE for X-windows where all formats are
public.

  Hans Aberg




From rms@santafe.edu Fri Dec 29 22:20:13 2000
Received: from pele.santafe.edu ([192.12.12.119])
	by fencepost.gnu.org with esmtp (Exim 3.16 #1 (Debian))
	id 14CCZ3-0002nw-00; Fri, 29 Dec 2000 22:20:13 -0500
Received: from aztec.santafe.edu (aztec [192.12.12.49])
	by pele.santafe.edu (8.9.3/8.9.1) with ESMTP id UAA26593;
	Fri, 29 Dec 2000 20:20:11 -0700 (MST)
Received: (from rms@localhost)
	by aztec.santafe.edu (8.9.3+Sun/8.9.1) id UAA04519;
	Fri, 29 Dec 2000 20:20:10 -0700 (MST)
Date: Fri, 29 Dec 2000 20:20:10 -0700 (MST)
Message-Id: <200012300320.UAA04519@aztec.santafe.edu>
X-Authentication-Warning: aztec.santafe.edu: rms set sender to rms@aztec.santafe.edu using -f
From: Richard Stallman <rms@gnu.org>
To: haberg@matematik.su.se
CC: akim@epita.fr, bug-bison@gnu.org
In-reply-to: <v0311070bb67142f06b34@[195.100.226.131]> (message from Hans
	Aberg on Thu, 28 Dec 2000 20:30:53 +0100)
Subject: Re: Bison and C++
Reply-to: rms@gnu.org
References: <v03110700b66eb9e093e4@[195.100.226.129]> (message from Hans
 Aberg on Tue, 26 Dec 2000 23:08:53 +0100)
 <v03110705b610ddd8661a@[195.100.226.134]> (message from Hans Aberg on
 Mon, 16 Oct 2000 19:24:59 +0200)
 <v0311070db60fb91f6357@[195.100.226.144]> (message from Hans Aberg on
 Sun, 15 Oct 2000 22:14:08 +0200)
 <v03110701b60df035f07d@[195.100.226.157]> (message from Hans Aberg on
 Sat, 14 Oct 2000 13:41:01 +0200)
 <v03110702b608a4ede719@[195.100.226.147]> (message from Hans Aberg on
 Tue, 10 Oct 2000 12:59:28 +0200) Hans Aberg's message of "Sat, 7 Oct 2000
 15:25:33 +0200" <v03110706b604d0018bec@[195.100.226.145]>
 <v03110702b608a4ede719@[195.100.226.147]>
 <v03110701b60df035f07d@[195.100.226.157]>
 <v0311070db60fb91f6357@[195.100.226.144]>
 <v03110705b610ddd8661a@[195.100.226.134]>
 <v03110700b66eb9e093e4@[195.100.226.129]> <v0311070bb67142f06b34@[195.100.226.131]>
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

    So therefore I think it
    would important to have a GNU IDE for X-windows where all formats are
    public.

I will try to get people to work on that.


From haberg@matematik.su.se Sat Dec 30 10:56:22 2000
Received: from hromeo.algonet.se ([194.213.74.51])
	by fencepost.gnu.org with smtp (Exim 3.16 #1 (Debian))
	id 14COMn-00032t-00
	for <bug-bison@gnu.org>; Sat, 30 Dec 2000 10:56:21 -0500
Received: (qmail 27693 invoked from network); 30 Dec 2000 16:56:19 +0100
Received: from delenn.tninet.se (HELO algonet.se) (195.100.94.104)
  by hromeo.algonet.se with SMTP; 30 Dec 2000 16:56:19 +0100
Received: from  [195.100.226.143] (du143-226.ppp.su-anst.tninet.se [195.100.226.143])
 by delenn.tninet.se (BLUETAIL Mail Robustifier 2.2.1) with ESMTP
 id 721814.191777.978delenn-s2
 ; Sat, 30 Dec 2000 16:56:17 +0100
X-Sender: haberg@pop.matematik.su.se
Message-Id: <v03110701b673b4ad064c@[195.100.226.131]>
In-Reply-To: <200012300320.UAA04519@aztec.santafe.edu>
References: <v0311070bb67142f06b34@[195.100.226.131]> (message from Hans
 Aberg on Thu, 28 Dec 2000 20:30:53 +0100)
 <v03110700b66eb9e093e4@[195.100.226.129]> (message from Hans Aberg on
 Tue, 26 Dec 2000 23:08:53 +0100)
 <v03110705b610ddd8661a@[195.100.226.134]> (message from Hans Aberg on
 Mon, 16 Oct 2000 19:24:59 +0200)
 <v0311070db60fb91f6357@[195.100.226.144]> (message from Hans Aberg on
 Sun, 15 Oct 2000 22:14:08 +0200)
 <v03110701b60df035f07d@[195.100.226.157]> (message from Hans Aberg on
 Sat, 14 Oct 2000 13:41:01 +0200)
 <v03110702b608a4ede719@[195.100.226.147]> (message from Hans Aberg on
 Tue, 10 Oct 2000 12:59:28 +0200) Hans Aberg's message of "Sat, 7 Oct 2000
 15:25:33 +0200" <v03110706b604d0018bec@[195.100.226.145]>
 <v03110702b608a4ede719@[195.100.226.147]>
 <v03110701b60df035f07d@[195.100.226.157]>
 <v0311070db60fb91f6357@[195.100.226.144]>
 <v03110705b610ddd8661a@[195.100.226.134]>
 <v03110700b66eb9e093e4@[195.100.226.129]>
 <v0311070bb67142f06b34@[195.100.226.131]>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Sat, 30 Dec 2000 16:55:05 +0100
To: rms@gnu.org
From: Hans Aberg <haberg@matematik.su.se>
Subject: Re: Bison and C++
Cc: akim@epita.fr, bug-bison@gnu.org
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

At 20:20 -0700 0-12-29, Richard Stallman wrote:
>    So therefore I think it
>    would important to have a GNU IDE for X-windows where all formats are
>    public.
>
>I will try to get people to work on that.

This sounds great.

One thing that comes to my mind is that the IDE I know of (Metrowerks CW)
does not have the same capacities as "make", for example when tracing
dependencies. This is very apparent with the Bison plugin I made: For
example, if one lets Bison output a header file and some other file
includes that file, this dependency is normally not discovered by the IDE.

So if GNU decides to do an IDE, I think that one requirement should be that
it has at least the capacity of "make".

  Hans Aberg




From haberg@matematik.su.se Sat Dec 30 17:16:34 2000
Received: from hromeo.algonet.se ([194.213.74.51])
	by fencepost.gnu.org with smtp (Exim 3.16 #1 (Debian))
	id 14CUIj-0001Ti-00
	for <bug-bison@gnu.org>; Sat, 30 Dec 2000 17:16:33 -0500
Received: (qmail 29492 invoked from network); 30 Dec 2000 23:16:32 +0100
Received: from delenn.tninet.se (HELO algonet.se) (195.100.94.104)
  by hromeo.algonet.se with SMTP; 30 Dec 2000 23:16:32 +0100
Received: from  [195.100.226.141] (du141-226.ppp.su-anst.tninet.se [195.100.226.141])
 by delenn.tninet.se (BLUETAIL Mail Robustifier 2.2.1) with ESMTP
 id 105801.214591.978delenn-s2 for <bug-bison@gnu.org>
 ; Sat, 30 Dec 2000 23:16:31 +0100
X-Sender: haberg@pop.matematik.su.se (Unverified)
Message-Id: <v03110701b673dd1584f8@[195.100.226.143]>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Sat, 30 Dec 2000 20:12:17 +0100
To: Bison Bugs <bug-bison@gnu.org>
From: Hans Aberg <haberg@matematik.su.se>
Subject: yytname ' & " character codes
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

Isn't the following a bug:

If one in the .y on file uses
  '\"' or '"',  it shows up as "'\\\"'"
  '\'', it shows up as "'\\''"
in the yytname array.

Wouldn't one expect that these be printed in the .c file that when yytname
is compiled, one gets back the original character codes?

Then '\"' should be printed as "'\"'", and '\'' should be printed as "'\''"
or "'''".

-- If one should use the yytname and similar tables for lookups, not only
printing, then it seems reasonable to store character codes on the binary
format
  '<byte>'
as one then knows that the second byte is always the character code one is
looking for.

  Hans Aberg




From rms@santafe.edu Sun Dec 31 18:38:02 2000
Received: from pele.santafe.edu ([192.12.12.119])
	by fencepost.gnu.org with esmtp (Exim 3.16 #1 (Debian))
	id 14Cs37-0001qt-00; Sun, 31 Dec 2000 18:38:01 -0500
Received: from aztec.santafe.edu (aztec [192.12.12.49])
	by pele.santafe.edu (8.9.3/8.9.1) with ESMTP id QAA28944;
	Sun, 31 Dec 2000 16:37:58 -0700 (MST)
Received: (from rms@localhost)
	by aztec.santafe.edu (8.9.3+Sun/8.9.1) id QAA06722;
	Sun, 31 Dec 2000 16:37:58 -0700 (MST)
Date: Sun, 31 Dec 2000 16:37:58 -0700 (MST)
Message-Id: <200012312337.QAA06722@aztec.santafe.edu>
X-Authentication-Warning: aztec.santafe.edu: rms set sender to rms@aztec.santafe.edu using -f
From: Richard Stallman <rms@gnu.org>
To: haberg@matematik.su.se
CC: akim@epita.fr, bug-bison@gnu.org
In-reply-to: <v03110701b673b4ad064c@[195.100.226.131]> (message from Hans
	Aberg on Sat, 30 Dec 2000 16:55:05 +0100)
Subject: Re: Bison and C++
Reply-to: rms@gnu.org
References: <v0311070bb67142f06b34@[195.100.226.131]> (message from Hans
 Aberg on Thu, 28 Dec 2000 20:30:53 +0100)
 <v03110700b66eb9e093e4@[195.100.226.129]> (message from Hans Aberg on
 Tue, 26 Dec 2000 23:08:53 +0100)
 <v03110705b610ddd8661a@[195.100.226.134]> (message from Hans Aberg on
 Mon, 16 Oct 2000 19:24:59 +0200)
 <v0311070db60fb91f6357@[195.100.226.144]> (message from Hans Aberg on
 Sun, 15 Oct 2000 22:14:08 +0200)
 <v03110701b60df035f07d@[195.100.226.157]> (message from Hans Aberg on
 Sat, 14 Oct 2000 13:41:01 +0200)
 <v03110702b608a4ede719@[195.100.226.147]> (message from Hans Aberg on
 Tue, 10 Oct 2000 12:59:28 +0200) Hans Aberg's message of "Sat, 7 Oct 2000
 15:25:33 +0200" <v03110706b604d0018bec@[195.100.226.145]>
 <v03110702b608a4ede719@[195.100.226.147]>
 <v03110701b60df035f07d@[195.100.226.157]>
 <v0311070db60fb91f6357@[195.100.226.144]>
 <v03110705b610ddd8661a@[195.100.226.134]>
 <v03110700b66eb9e093e4@[195.100.226.129]>
 <v0311070bb67142f06b34@[195.100.226.131]> <v03110701b673b4ad064c@[195.100.226.131]>
Sender: bug-bison-admin@gnu.org
Errors-To: bug-bison-admin@gnu.org
X-BeenThere: bug-bison@gnu.org
X-Mailman-Version: 2.0
Precedence: bulk
List-Help: <mailto:bug-bison-request@gnu.org?subject=help>
List-Post: <mailto:bug-bison@gnu.org>
List-Subscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=subscribe>
List-Id: Bug reports for Bison, the GNU parser generator <bug-bison.gnu.org>
List-Unsubscribe: <http://mail.gnu.org/mailman/listinfo/bug-bison>,
	<mailto:bug-bison-request@gnu.org?subject=unsubscribe>
List-Archive: <http://mail.gnu.org/pipermail/bug-bison/>

    So if GNU decides to do an IDE, I think that one requirement should be that
    it has at least the capacity of "make".

Any sort of development environment we write will USE make, just as it
will use GCC, etc.


