HDTenEightyP/NetNews huggingface dataset:
From: ejy@hrmsc.att.com (Eugene Yurek)
Subject: Re: A Non-LALR(1) Parser Generator
Reply-To: ejy@hrmsc.att.com (Eugene Yurek)
Organization: AT&T
Date: Tue, 18 Aug 1992 17:50:36 GMT
Keywords: LR(1)

bromage@mullauna.cs.mu.oz.au (Andrew Bromage):
>[are there non-LALR parser generators?]
> D Pager has produced a few algorithms which may be of some use.
>	...
> The first (ie simpler) algorithm was used in a parser compiler called
> "LR", the availability of which I know nothing about.
> 
> It was reviewed in:
> Wetherell and Shannon, "LR - automatic parser generator and LR(1) parser",
> IEEE Transactions on Software Engineering, SE-7, pp 274-278, 1981.

I, at one time (I may still have the source laying around somewhere)
played with a copy of the LR parser generator.  It is all written in
Fortran (as I remember).  It accepts a somewhat preprocessed BNF
(cannibalized) notation.

Charlie Wetherell originally wrote LR along with Shannon for some
government entity they were either employed for or were working on a
contract for, so, consequently, the entire source is in the public domain.

The source tape is available from the government (some program repository,
though I can't remember which one).  It comes with a sample parser for the
tables it generates.

This generator is not easy to use compared to YACC.  You cannot provide
semantic actions within the grammar.  They must be handled in a separate
source file, and manually tied back to the productions in the BNF (yuk!!).
Basically, I'm saying that LR works well, however, its not that easy to
use (though this is a subjective observation on my part). And as I said
above, you're going to need a Fortran compiler, and some patience to use
it.  It is, however, the only LR(1) parser generator that I've ever come
across (please, no flames!!!).
--
Gene Yurek
ejy@hrmsg.att.com	AT&T Bell Laboratories, Middletown, NJ
[One of the reasons that yacc became so popular is that it let you put the
action code next to the grammar rule to which it applies.  Until then all the
parser generators I knew of required that you match up the rules and the code
yourself. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Xref: sparky comp.compilers:1387 comp.lang.c:12391
From: behrenss@Informatik.TU-Muenchen.DE (Soenke Behrens)
Newsgroups: comp.compilers,comp.lang.c
Subject: Re: Two-pass C compilers
Keywords: C
Date: 16 Aug 92 13:21:15 GMT
Reply-To: behrenss@Informatik.TU-Muenchen.DE (Soenke Behrens)
Organization: Technische Universitaet Muenchen, Germany

Hmmm ... beat me if I something silly, but: Is there any way around
a two-pass compiler? (Or even more passes)

First pass: Reading in the source, preprocessing it, building a symbol table.
Second pass: Generate p-Code
Third pass: Optimize p-Code (Note: Do not mix with 2nd pass or you are
in deep trouble)
Fourth pass: Generate native code in linkable object file

Soenke
-- 
behrenss@informatik.tu-muenchen.de
FIDO: 2:246/13 Soenke Behrens
[I would call those compiler phases, and use "pass" to mean reading the source
code.  A classic two-pass assembler reads the source once to establish values
for the symbols and again to generate object code and maybe a listing using
the symbol values. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: tmb@arolla.idiap.ch (Thomas M. Breuel)
Newsgroups: comp.compilers
Subject: Re: Adding garbage collection to C++
Keywords: C, GC, design
Date: 19 Aug 92 15:46:52 GMT
Reply-To: tmb@arolla.idiap.ch (Thomas M. Breuel)
Organization: IDIAP (Institut Dalle Molle d'Intelligence Artificielle
	Perceptive)

fjh@munta.cs.mu.OZ.AU (Fergus James HENDERSON) writes:

   >[you can detect and remember any pointer that is hidden by type punning,
   >writing to files, etc.]

   This may be true in theory, but it seems like it would be very difficult
   in practice (especially if you allow separate compilation) and might lead
   to memory leaks.

   Presumably you have to consider every conversion from (T **) to (void *)
   potentially dangerous, since the (void *) could be used to hide away the
   (T *) pointer, using memcpy(), fwrite(), or some such.  But such
   conversions may be relatively common.

As I said before, I don't advocate this scheme. It's a cute solution to an
interesting puzzle, nothing more.

In practice, a C/C++ standard with GC should state that if you intend to
scramble the bits of a pointer, you better keep an unscrambled version of
the pointer around somewhere for the GC to find.

I don't think this would affect many programs, and the ones that would be
affected by it could simply be run with the GC turned off (since they were
presumably written before GC was added to the language).

					Thomas.
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: g89r4255@hippo.ru.ac.za (Lt Sajid Rahim)
Subject: Need an ftp site for code generation source code.
Reply-To: g89r4255@hippo.ru.ac.za (Lt Sajid Rahim)
Organization: Rhodes University, Grahamstown, South Africa
Date: Fri, 14 Aug 1992 09:38:15 GMT
Keywords: FTP, 386, question

I am looking for an Ftp site where I can obtain information about code
generatros for the 8086 processor. I am interested in transporting a
subset of Pascal which is at present an interpreter based language to
MDSOS code by converting all the pseudocode generated by the compiler into
8086 obj code.

Sincerely

Sajid
---------------------------------------------------------------------
--   Sajid Rahim, Dept of Computer Science, Rhodes University,     --
--   Grahamstown, South Africa. Internet : g89r4255@hippo.ru.ac.za --
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: tmb@idiap.ch
Newsgroups: comp.compilers
Subject: Re: Adding garbage collection to C++
Keywords: C, GC
Date: 17 Aug 92 16:04:23 GMT
Reply-To: tmb@idiap.ch
Organization: IDIAP (Institut Dalle Molle d'Intelligence Artificielle
	Perceptive)

bill@amber.ssd.csd.harris.com (Bill Leonard) writes:

>[How do you garbage collect multi-threaded programs where some pointers to
>shared memory are kept in per-thread private storage]

>  I think you basically have to give up on garbage collecting such strange
>  objects.  But their existence forces me to advocate that garbage
>  collection only happen if I specifically ask for it (thus begging for
>  language extensions), rather than automatically.

You don't need a language extension, nor do you need "garbage
collection only [to] happen if [you] specifically ask for it". Simply
retain a pointer to the object in the address space of A. In fact, you
can encapsulate this behavior nicely inside your "send" procedure.

					Thomas.
[So how do you ever collect storage that's ever been shared between two
threads?  In fairness, this isn't unique to C -- it'd be a problem in any
situation where you have a shared heap with unshared pointers. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: maxtal@extro.ucc.su.OZ.AU (John MAX Skaller)
Newsgroups: comp.compilers
Subject: GC for C
Keywords: storage, GC, C
Date: 16 Aug 92 23:33:06 GMT
Reply-To: maxtal@extro.ucc.su.OZ.AU (John MAX Skaller)
Organization: MAXTAL P/L C/- University Computing Centre, Sydney

As I understand it, a conservative garbage collector works
by checking the stack for any pointer like words, and assuming
these root collectable objects.

What happens in a system like Windows when the user gives away
the object addresses to the operating system, so for most
objects there are no roots on the stack, because the stack
is empty most of the time?

[The object pointer is stored in Window memory, owned by the OS,
by the object is on the heap as usual.]

Wouldn't this mean GC would have to be carried out at the OS level?
-- 
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
	Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
[Either the OS has to do the GC, or else there has to be some way for the
user level GC to see the OS's pointers into its address space. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: jeremy@sw.oz.au (Jeremy Fitzhardinge)
Newsgroups: comp.compilers
Subject: SUMMARY:  Constant folding in the parser
Summary: It's best not to
Keywords: parse, optimize
Date: 12 Aug 92 09:04:23 GMT
Reply-To: jeremy@sw.oz.au (Jeremy Fitzhardinge)
Organization: Softway Pty Ltd

A week ago or so, I asked whether a non-ambigious grammar can be
constructed to eliminate constant expressions without explicit semantic
analysis of the parse tree.

The most popular answer was "Keep semantic analysis away from the parser",
and do the constant elimination as the tree is constructed.  This can be
generalized to putting off such optimisations until the tree is completely
built, so that other transformations can be done.

Thanks to:
John R. Levine <johnl@iecc.cambridge.ma.us>
twpierce@amhux1.amherst.edu (Tim Pierce)
kurt@tc.fluke.COM (Kurt Guntheroth)
"Jorge Tapia Jopia" <jtapia@vandi.ars.cl>
e86jh@efd.lth.se (Jens Hansson)
nelson@berlioz.nsc.com (Taed Nelson)

	J
--
jeremy@softway.sw.oz.au ph:+61 2 698 2322-x122 fax:+61 2 699 9174
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Xref: sparky comp.compilers:1426 comp.lang.c++:12690
From: eifrig@beanworld.cs.jhu.edu (Jonathan Eifrig)
Subject: Multi-Threading and Garbage Collection
Reply-To: eifrig@beanworld.cs.jhu.edu (Jonathan Eifrig)
Organization: The Johns Hopkins University CS Department
Date: Sat, 15 Aug 1992 21:01:21 GMT
Keywords: storage, GC, parallel

boehm@parc.xerox.com (Hans Boehm) writes:
>eifrig@beanworld.cs.jhu.edu (Jonathan Eifrig) writes:
>>
>>	I just don't see how you're going to allow garbage collection to
>>occur _anywhere_ and handle any sort of tagged heap.  Are you assuming
>>that procedure calls and heap allocations are atomic?  What happens if I
>>have to garbage collect while I'm in the middle of allocating a record,
>>and haven't written the length of the record to the heap yet?
>
>There are two ways of dealing with this.  With high allocation rates, you
>probably need to give each thread its own chunk of memory that it can
>allocate from without synchronization.  With lower allocation rates,
>allocation can acquire a lock to prevent conflicts.  The PCR allocator
>acquires and releases a monitor lock (perhaps with some minor shortcut)
>for each allocation.  This isn't free, but the only cost is during
>allocation.  With Cedar-like (or Modula-3 like or C-like) allocation
>frequencies this probably makes sense.  It's almost never a bottleneck.
>With SML-of-NJ like allocation rates, it's a bad idea.

	Of course, even if the allocation rate _per_thread_ is fairly low,
one can still get into trouble if the number of threads is very high.  If
enough threads are executing, it becomes likely that _some_ thread is
suspended in the middle of allocation, making any allocation by any other
thread _very_ expensive.  Generally, though, this isn't much of a problem,
since few programs have a lot of threads.  It is another good argument
against a single, multi-process heap (at the operating system lever),
however.

	Strangely enough, I've recently stumbled onto a short
communication by Appel relating an interesting brute-force way around this
problem.  One partitions the heap into several pages, and assign these
pages to threads on a as-needed basis; this allows each thread to allocate
without interfering with the others.  When all the pages have run out, a
single, process-level garbage collector is used to recover the garbage
pages.

	The _code_ of each thread is examined to determine if it was in
the process of allocating when it was suspended.  If so, the allocation is
completed by the garbage collector by interpreting the machine
instructions of the thread.  This is of course extremely expensive, but
since garbage collection is such a rare event the amortized cost can be
cheaper than manipulating some sort of monitor or semaphore.

	(Appel, Andrew W, "Allocation Without Locking," _Soft._Prac._Exp
19(7) pp. 703-5)

--
Jack Eifrig (eifrig@cs.jhu.edu)       The Johns Hopkins University, C.S. Dept.
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: hudson@cs.umass.edu
Newsgroups: comp.compilers
Subject: Re: Adding garbage collection to C++
Keywords: parallel, GC, bibliography
Date: 17 Aug 92 15:07:38 GMT
Reply-To: hudson@cs.umass.edu
Organization: Dept of Comp and Info Sci, Univ of Mass (Amherst)

bill@amber.ssd.csd.harris.com (Bill Leonard) writes:
>[Garbage collection across multiple processes is hard ...]

pardo@cs.washington.edu (David Keppel) lists a lot of good references, but
left out an earlier reference which suggested solutions to a lot of these
problems a long time ago. It's a good read.

@PHDTHESIS{Bis77,
	AUTHOR = "Peter B. Bishop",
	TITLE = "Computer Systems with a Very Large Address Space and
		Garbage Collection",
	SCHOOL = "Massachusetts Institute of Technology",
	YEAR = 1977,
	MONTH = may,
	ADDRESS = "Cambridge, MA"
}

Basically Bishop (in 1977) said that if one thread finds an object in its
data space ("area") that is only reachable by another thread then that
object is migrated to the other thread's area.
--
                Richard L. Hudson, Research Associate
                University Computing Services
                Lederle Graduate Research Center
                University of Massachusetts
                Amherst, MA  01003
                (413) 545-1220; Hudson@cs.umass.edu
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: kadhim@riker.cs.colorado.edu (Basim Kadhim)
Newsgroups: comp.compilers
Subject: Eli compiler construction system - version 3.3.1
Keywords: tools, FTP
Date: 12 Aug 92 06:06:10 GMT
Reply-To: kadhim@riker.cs.colorado.edu (Basim Kadhim)
Organization: University of Colorado, Boulder

Version 3.3.1 of the Eli compiler construction system is now available
either on magnetic tape or via anonymous ftp (ftp.cs.colorado.edu,
128.138.243.151, pub/cs/distribs/eli).  Complete system documentation is
also available in two formats: Tex dvi format and PostScript.  This
release has been tested on the following machine/os combinations (reported
by "uname"):

   Sun3: SunOS Release 4.1 Version 1
   Sun4: SunOS Release 4.1.2 Version 2
   DECstation: ULTRIX Release 4.2 Version 0
   HP 9000/340: HP-UX Release B.08.00 Version B
   IBM RS 6000: AIX Release 1 Version 3

Eli integrates off-the-shelf tools and libraries with specialized language
processors to generate complete compilers quickly and reliably.  It
simplifies the development of new special-purpose languages,
implementation of existing languages on new hardware and extension of the
constructs and features of existing languages.  A paper describing the
system appears in the February, 1992 issue of "Communications of the ACM"
(pages 121-131).

Version 3.3.1 provides enhanced facilities for modularity in attribute
grammars: symbol computation, inheritance and rule attributes.  Rules need
be specified only if they introduce attribute computations.  (This
dramatically reduces specification size.) Version 3.3.1 also includes a
new property definition language that allows users to create additional
definition table access operations.

To order a magnetic tape or printed documentation, or to obtain
additional information about Eli, contact either:

   Software Engineering Group
   Department of Electrical and Computer Engineering
   University of Colorado
   Boulder, CO  80309-0425
   USA

   compiler@cs.colorado.edu

or:

   Prof. Dr. U. Kastens
   Universtaet Paderborn, FB17
   Warburgerstr. 100
   D-4790 Paderborn
   GERMANY

   compiler@uni-paderborn.de
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: fjh@munta.cs.mu.OZ.AU (Fergus James HENDERSON)
Newsgroups: comp.compilers
Subject: Re: Adding garbage collection to C++
Keywords: C++, GC, design, comment
Date: 21 Aug 92 07:22:25 GMT
Reply-To: fjh@munta.cs.mu.OZ.AU (Fergus James HENDERSON)
Followup-To: comp.lang.c++
Organization: Computer Science, University of Melbourne, Australia

tmb@arolla.idiap.ch (Thomas M. Breuel) writes:

>As I said before, I don't advocate this scheme. It's a cute solution to an
>interesting puzzle, nothing more.

Ah, yes, but I was disputing whether you had solved the puzzle! :-)
I would certainly agree that the question is purely academic.
To be fair, however, I think that the puzzle should include at least
the following rules: any solution must 
	- work for any strictly conforming program;
	- allow separate compilation;
	- not cause memory leaks.
Unfortunately including these conditions makes the puzzle unsolveable, IMHO :-(.

(We seem to have strayed away from serious compiler buisiness.
Follow-ups to comp.lang.c++).

-- 
Fergus Henderson             fjh@munta.cs.mu.OZ.AU      
[Enough already of this discussion, it's getting mired in details. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: tchannon@black.demon.co.uk (Tim Channon)
Subject: Why is compiled basic slower than C?
Reply-To: tchannon@black.demon.co.uk (Tim Channon)
Organization: Compilers Central
Date: Sat, 15 Aug 1992 00:16:15 GMT
Keywords: Basic, performance

Have you examined GFA BASIC for the IBM pc compatible or AtariST?

This is German software and can be interpreted or compiled. There are a
good few lessons to others about how to make GUI programming simple.

Development is ongoing.

A number of years ago I needed to write a specialist editor/comms program
on the AtariST. This was done using an early version of the language (the
compiler arrived with me during writing the program). In a week or so of
odd moments I succeeded in producing a program with a full GUI, error
handling (alert boxs etc.).  No assembler whatever was needed and
execution speed was excellent when compiled with comparable execution
speed to C or Modula2.  The same people marketed a serious drafting
package...

What about Basic2C?

There are a number of major commercial business packages written in the UK
which use compiled Basic. They work fine but unless you look or know how
can you tell the language used?

I don't use that implementation of Basic now but it looks much improved.
(mostly Modula2 or C for pc's, Forth and assembler for embedded)

  TC. 
    E-mail: tchannon@black.demon.co.uk or tchannon@cix.compulink.co.uk
                             

-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: macrakis@osf.org (Stavros Macrakis)
Newsgroups: comp.compilers
Subject: Re: Set Generators
Keywords: theory
Date: 21 Aug 92 17:28:19 GMT
Article-I.D.: comp.92-08-136
Reply-To: macrakis@osf.org (Stavros Macrakis)
Organization: OSF Research Institute

coatta@cs.ubc.ca (Terry Coatta) writes:

   In a system that I am working on, sets of objects are often
   specified via membership predicates.  ... I am looking for are
   hints or help on a ``mechanical'' process for taking membership
   predicates and ``compiling'' them in to (imperative) procedures
   which will generate the set in question.

There has been considerable work on this problem.  Of course, it is
completely intractable in general, however for many useful and interesting
cases, there are good results.

Researchers working in this area include Cordell Green, Dave Barstow,
Martin Feather.  Manfred Broy, John Darlington, and others work on closely
related problems.

Green's company, Reasoning Systems (Palo Alto, CA), sells a product called
Refine which does precisely this (among other things).

	-s
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: soi!chip@uu3.psi.com (Chip Morris)
Subject: Re: Code Generation by Coagulation?
Reply-To: soi!chip@uu3.psi.com (Chip Morris)
Organization: Compilers Central
Date: Tue, 18 Aug 1992 12:44:58 GMT
Keywords: optimize

Jeremy Fitzhardinge writes:

>I've been looking through the paper "Code Generation by Coagualtion"
>by Michael Karr, published in 1984.  I'm wondering if this work has
>been followed up or further investigated.  

I directed the implementation of Karr's ideas, with extensions, and
reported on it in the 1991 SIGPLAN PLDI conference.  I can send copies of
the paper if you can't get your hands on a proceedings.

We still have lots of ideas, and the code is here at Software Options, but
our research funding source wanted us to move on to other topics.
Inquiries and discussion are welcome.  It would be particularly nice to
hook it onto a C or FORTRAN front-end for some industrial-strength
benchmarking.
--
Chip Morris, Senior Engineer
Software Options, Inc., 22 Hilliard St., Cambridge MA 02138  (617) 497-5054
chip@soi.com
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: fjh@munta.cs.mu.OZ.AU (Fergus James HENDERSON)
Subject: Re: Why is compiled basic slower than C? (Basic is the future)
Reply-To: fjh@munta.cs.mu.OZ.AU (Fergus James HENDERSON)
Organization: Computer Science, University of Melbourne, Australia
Date: Tue, 18 Aug 1992 10:27:34 GMT
Keywords: interpreter, performance

>... languages you
>might call `interpreted', like Lisp, Prolog, ML, and Snobol, in fact have
>very good compilers, which make major differences in runtime.

Compiled Prolog is almost invariably a slightly different language from
the original interpreted Prolog. The reason for this is the following:

>burley@geech.gnu.ai.mit.edu (Craig Burley) writes:
>   ...There is another major issue regarding interpretation which puts
>   both BASIC and C in the "compiled" camp: whether the running
>   program has a means to modify itself at run time.  LISP, for
>   example, belongs in the "interpreted" camp.
>
>This is not really a problem.  The amount of Lisp code which actually
>modifies the program written by the programmer is just minuscule.  Much
>more code _generates_ pieces of Lisp, typically using the `macro' feature.
>But almost all cases of macro usage are handled straightforwardly in Lisp
>compilers.  There are a few cases where Lisp code generates code on the
>fly, then executes it.  This is handled by having an interpreter loaded
>along with the compiled code, and assuring that code can work correctly in
>such a mixed environment.  In fact, most Lisp implementations _assume_ a
>mixed environment....

(I think that a good definition of interpreted language is one where even
if you compile it, you must load an interpreter or compiler with the
object code.)

Many old Prolog programs modify themselves using assert and retract.
Prolog compilers handle this by using the above techniques, but also by
making a slight change to the language: programmers are required to
declare predicates that will be modified with assert/retract as "dynamic".

Without these declarations, it is very difficult get reasonable efficiency
of the compiled code.
-- 
Fergus Henderson             fjh@munta.cs.mu.OZ.AU      
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.