HDTenEightyP/NetNews huggingface dataset:
From: bburshte@pyrps5.eng.pyramid.com (Boris Burshteyn)
Newsgroups: comp.compilers
Subject: Full LR(1) Parser Generator
Keywords: LR(1), comment
Date: 21 Aug 92 22:13:11 GMT
Article-I.D.: comp.92-08-138
Reply-To: bburshte@pyrps5.eng.pyramid.com (Boris Burshteyn)
Organization: Compilers Central

USSA (Universal Syntax and Semantics Analyzer) is a minimal state full LR1
parser generator. It uses an optimized version of David Spector's
algorithm published in SIGPLAN NOTICES, V.23 N. 12 1988 ("Efficient Full
LR(1) Parser Generation").

USSA is written in C++ and produces tables in the form of C++ objects.
The skeleton parser is also written in C++. USSA has some additional
features such as several grammars in a single source (converted to several
C++ parser objects which can be executed from a single program), multiple
grammar inheritance, regular expressions, real time parsing, generator
(which automatically generates sample sentences of the defined language),
run-time communication between compilers for different grammars, default
lexer... YACC grammar definitions may be easily converted to USSA format.

USSA is already a production quality parser generator and is intensively
used in one of Pyramid Technology Corporation's development projects. We
intend to optimize it to run faster and to produce smaller tables.  The
following is a comparison between USSA and YACC on Pyramid S-series
machines (MIPS R3000, UNIX SVR4).

In most cases USSA has better or comparable with YACC tables.  Note, that
space is measured in the number of elements.  However, YACC generates
tables from int(s) (on PYRAMID), but USSA - from short(s).  

Time is min from several runs of YACC and USSA by UNIX time command.  

grammar         yacc      ussa             yacc     ussa
		space     space            time     time
-------         ----      ----             ----     ----

ansic           3661      2674             3.0      0.7
ussa(incomplete)2381      1945             0.9      0.6
dBase4          8939      5890             14.8     3.2
f77             4597      4650             3.0      1.3
lex             373       281              1.0      0.0
yacc            563       278              0.0      0.0
pascal          1957      2160             0.9      0.4
prolog          877       784              0.2      0.1


Sincerely, Boris Burshteyn (bburshte@pyramid.com).
[So can we get a copy?  Sounds great. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: tony@cs.colorado.edu
Newsgroups: comp.compilers
Subject: Eli Mailing List
Keywords: tools
Date: 13 Aug 92 17:47:26 GMT
Reply-To: tony@cs.colorado.edu
Organization: University of Colorado at Boulder

This message is to announce the creation of a mailing list for the Eli
compiler construction system (see a recent release announcement in this
newsgroup).  The mailing list will be devoted to discussions about Eli,
announcements of bug fixes, new features and releases and so on.

If you want to be added to the eli mailing list, send mail saying so to:

	eli-request@cs.colorado.edu

To send mail to everyone on the list, send to:

	eli@cs.colorado.edu

All mail of general interest to the Eli community should be sent to the
"eli" address.

Mail concerning bug reports should be sent to:

	elibugs@cs.colorado.edu

All other mail concerning Eli such as orders for printed documentation or
tapes of the system should be sent to:

	compiler@cs.colorado.edu

Cheers,
--
Tony Sloane, Computer Science Department, University of Colorado at Boulder
tony@cs.colorado.edu
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: wjw@eb.ele.tue.nl (Willem Jan Withagen)
Newsgroups: comp.compilers
Subject: Re: constant folding at parse time
Keywords: parse, optimize, comment
Date: 21 Aug 92 08:44:59 GMT
Reply-To: wjw@eb.ele.tue.nl (Willem Jan Withagen)
Organization: Compilers Central

you write:
=> example.  But what about an expression such as "4 + y + 4"?  As I see it,
=> a shift-reduce parser following the rule
=> 
=> expr -> expr + expr
=>       | CONST
=>       | ID

And John says:
=> [The only approach I've seen is pretty much brute force -- when you have a
=> subtree with multiple instances of an associative operator, flatten the
=> tree into a list, sort the list to put all the constants together,
=> collapse the constants, and remake a tree.  It is my dim recollection that
=> the Ritchie PDP-11 compiler actually did this, because you can get
=> significant savings in some kinds of addressing expressions. -John]

Now I don't want to open another tarpit again, but this certainly is going
to have effects on the semantics of the used program. When it is only
applied to address calculation which comes from arrays, ... then the user
would not always have to find out. But what about:
	y := maxint-1;
	...... (nothing for y)
	x := maxint-y+10;
This might or might not give the correct results.

And it gets even more tricky when the user has used ()'s to make shure that
thing were done in the proper order. 
  - Do we then annotate the intermediate code that it should not be 
    reorganised? 
  - Or do we only reorganise when we can show that there is no
    danger?
    And how do we show this?
  - what about Floating point stuff?

	Willem Jan

PS: In the compiler I'm doing I've decided to put an IM->IM
    cse-eliminator (as attribute evaluator) which can be applied 
    whenever on the IM-tree.
    These questions arise from the fact that I think that agresive
    actions could do more harm than that they are worth.

-- 
Digital Information Systems Group, Room EH 10.35 
Eindhoven University of Technology   
P.O. 513                     		Tel: +31-40-473401,Fax: +31-40-448375
5600 MB Eindhoven            		The Netherlands
Internet:  wjw@eb.ele.tue.nl    
X400:      C=nl;ADMD=400net;PRMD=surf;O=tue;OU=ele;OU=eb;S=WJW;
[This was for integer expressions in C, which traditionally haven't paid
much attention to overflows.  You're right, though, particularly for floating
point expressions users will not appreciate arbitrary rearragement. -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:1386 comp.os.msdos.programmer:8559
From: choup@CGRB.ORST.EDU (Ping Chou)
Newsgroups: comp.compilers,comp.os.msdos.programmer
Subject: Re: 8086 object code
Keywords: linker, question, 386
Date: 16 Aug 92 05:04:47 GMT
Reply-To: choup@CGRB.ORST.EDU (Ping Chou)
Organization: Biological Computing Consortium, OSU, Corvallis, OR.

bromage@mullauna.cs.mu.OZ.AU (Andrew Bromage) writes:
>Does anybody know where I can get a copy of the specification [for Microsoft
>compatible object modules?]

Try PC TECH JOURNAL, OCT. 1985, P63-81

On a related topic. Is there any 32 bits .OBJ format other than Intel
OMF-386 and Phar Lap Easy OMF-386? Say, the LINK386 comes with OS/2 2.0
can link 16 bits OMF-86 object file but can't understand record types
generated by Intel C code builder. It would be odd if IBM doesn't have the
the vision of 32 bits .OBJ format. Any info on this?

Ping
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: twpierce@amhux1.amherst.EDU (Tim Pierce)
Newsgroups: comp.compilers
Subject: Re: constant folding at parse time
Keywords: parse, attribute
Date: 19 Aug 92 15:53:46 GMT
Reply-To: Tim Pierce <twpierce@amhux1.amherst.EDU>
Organization: Amherst College, Amherst MA

The discussion about constant folding has intrigued me a little bit, and
I've been a little stumped figuring out how I would implement this in the
general case.  Writing code into mknode() to fold the addition or
multiplication of two nodes with constant value makes sense to me, for
example.  But what about an expression such as "4 + y + 4"?  As I see it,
a shift-reduce parser following the rule

expr -> expr + expr
      | CONST
      | ID

would process this expression as follows:

4 + y + 4
CONST + y + 4
expr + y + 4
expr + ID + 4
expr + expr + 4
expr + 4
expr + CONST
expr + expr
expr

At no time does the parser have any inkling that there are two constant
terms in this expression that can be folded together.  In order to encode
this recognition, I imagine you'd have to fix the parser to rearrange
terms in some order that would permit constant folding.  I've checked the
dragon book (second edition) but they seemed pretty vague on
implementation ideas.  Any thoughts?
-- 
Tim Pierce, twpierce@amherst.edu, (BITnet: TWPIERCE@AMHERST)
[The only approach I've seen is pretty much brute force -- when you have a
subtree with multiple instances of an associative operator, flatten the
tree into a list, sort the list to put all the constants together,
collapse the constants, and remake a tree.  It is my dim recollection that
the Ritchie PDP-11 compiler actually did this, because you can get
significant savings in some kinds of addressing expressions. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: drw@euclid.mit.edu (Dale R. Worley)
Newsgroups: comp.compilers
Subject: Re: Simple constant folding in bison parser
Keywords: yacc, attribute
Date: 17 Aug 92 19:25:22 GMT
Reply-To: drw@euclid.mit.edu (Dale R. Worley)
Organization: MIT Dept. of Tetrapilotomy, Cambridge, MA, USA

drw@kronecker.mit.edu (Dale R. Worley) writes:
   Really, what you're doing is constructing a synthesized (passed-upwards)
   attribute (constant vs. non-constant), but most LALR parser generators
   don't support that.  When you're parsing C, you want a lot of these
   attributes, and you want the attributes to control some aspects of the
   parsing.  The result is that some productions are cloned 6 or 8 times.
   Ugh.

   [This certainly works, but I'd think it'd be a lot easier to handle
   synthesized attributes in the value cells, where they're easy to
   construct and pass up the tree. -John]

It would be for constant folding, but in C, some of the attributes affect
the parsing process, and so can't be added on in a layer of processing
that the parser is blind to.  If I remember correctly, an important action
is to classify declarators as to whether the identifier being declared is
(at present) a typedef name or not.  Typedef-redeclaring declarators can
only appear in declarations that contain "type specifiers" (i.e., int,
float, struct, etc.).  If this restriction is not expressed in the grammar
productions, the grammar is still unambiguous (I think), but it is not
LALR(1).

What one would really like to write in the parser is a synthesized
attribute (which is just passed upward in most declarator-building
productions), and then constrain the appropriate productions to use only
declarators with the proper values of the attribute.

Dale Worley		Dept. of Math., MIT		drw@math.mit.edu
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: scott@bbx.basis.com (Scott Amspoker)
Newsgroups: comp.compilers
Subject: Re: constant folding at parse time
Keywords: parse, attribute
Date: 20 Aug 92 15:41:14 GMT
Reply-To: scott@bbx.basis.com (Scott Amspoker)
Organization: BASIS International, Ltd., Albuquerque NM USA

markh@csd4.csd.uwm.edu (Hunk) writes:
>A expression evaluation routine I wrote for an expression parser in a
>recently released assembler (C-expression syntax is handled) is set up in
>such a way that all constant subexpressions will be reduced to leaf nodes
>during parsing.  The question about whether a given expression is constant
>or not doesn't even arise because it's already been handled by the parser.
>Basically, if the expression tree returned by the parser is a leaf node
>then it's a constant, otherwise it's not.

It all depends on what you call a constant.  The address of a global
object is a constant and may be used in an initializer list:

   char c[10];
   char *cp = &c[2];

The address of c[2] is a constant but cannot be folded by the compiler.
Because of this, we have had to use a flag in a parse tree node to
indicate the 'constant' status of the sub-expression.

-- 
Scott Amspoker, Basis International, Albuquerque, NM
scott@bbx.basis.com
[I've worked with compilers that considered a constant to be a numeric
offset plus an optional static symbol address.  This can be very convenient
for generating addressing code. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: pk@cs.tut.fi (Kellom{ki Pertti)
Newsgroups: comp.compilers
Subject: Re: Why is compiled basic slower than C? (Basic is the future)
Keywords: interpreter
Date: 21 Aug 92 08:08:50 GMT
Reply-To: pk@cs.tut.fi (Kellom{ki Pertti)
Organization: Tampere Univ. of Technology, Finland.

burley@geech.gnu.ai.mit.edu (Craig Burley) writes:
   Nevertheless, interpreters are still, to varying degrees
   for each language, easier to write than compilers.

True. I could write a small interpreter, be it for Basic or Lisp, with a
fairly reasonable effort, because I could write it without any competence
in (my case) Sparc assembly. If I were to write a compiler for the same
language, I would have to start worrying about register windows and all
that stuff.

When it comes to the early personal computer Basic interpreters, though, I
would suspect that people writing them were more fluent with assembly that
high level languages.
--
Pertti Kellom\"aki
  Tampere Univ. of TeXnology
      Software Systems Lab
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: David.Chase@Eng.Sun.COM (David Chase)
Newsgroups: comp.compilers
Subject: Re: Garbage Collection
Keywords: storage, GC
Date: 13 Aug 92 21:42:09 GMT
Reply-To: David.Chase@Eng.Sun.COM (David Chase)
Organization: Compilers Central

>        Correct me if I'm wrong, but you seem to be saying that you're
> using the stack and the registers as roots of garbage collection.  ...
> If we decide, in an attempt to be _really_conservative_,
> to assume everything is a pointer, then we pay a double penalty: since
> we're wasting time moving junk around, garbage collection takes longer,
> and since we're not reclaiming storage that is actually free, we collect
> more often.

>      It seems clear that this naive approach won't be satisfactory, so
> what can we do?

I'd suggest reading "Garbage Collection in an Uncooperative
Environment" by Boehm and Weiser in _Software Practice and Experience_,
September 1988.

Their naive and clearly unsatisfactory approach works quite well, in
practice.

David Chase
Sun
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: jos@and.nl (Jos Horsmeier)
Newsgroups: comp.compilers
Subject: Re: Adding garbage collection to C++
Keywords: C, GC
Date: 14 Aug 92 09:03:48 GMT
Reply-To: jos@and.nl (Jos Horsmeier)
Organization: AND Software BV Rotterdam

In article <92-08-063@comp.compilers> the moderator appends:

|[It is my impression that an ANSI C program is allowed to copy a pointer to
|a long and later back to a pointer of the same type.  This sort of thing
|makes it hard to find all the live data. -John]

True, all true, but you'd better not say these kind of things in
comp.std.c, they'll nail your head to the floor for this ;-)

A pointer is _not_ an integral number, it's not even an _address_.
Casting a pointer to and from an integral number type causes
implementation defined behavior. The only exception to the rule is the
number 0. [*] When casted to the appropriate pointer type, it yields a
value somewhere in memory where no object will ever be stored. 

Since ANSI-C arrived, the concept of a pointer type has changed slightly.
In the good old days when things such as ints, longs, pointers and the
whole world could be stored in a 32 bit word, life was easy (boy, did I
love those VAXes,) but more esoteric hardware architectures nowadays
forbid such actions: pointers can be up to 256 bits wide, pointers can be
some `magical' thingies, stored in a separate space in your machine etc.
They are _not_ numbers. IMHO the concept of a pointer can be explained by
looking upon them as a tuple: and address with some type information
attached to it. As the standard states it:

ANSI-C 3.1.2.5 Types

[ ... ] A pointer type may be derived from a function type, an object
type, or an incomplete type, called the referenced type. A pointer type
describes an object whose value provides a reference to an entity of the
referenced type. A pointer type derived from the referenced type T is
sometimes called `pointer to T.' [ ... ]

Sorry if I sounded pedantic about it ...

kind regards,

Jos aka jos@and.nl

[*] The compiler provides the appropriate cast here, i.e. during runtime,
    the following code is not conformant, i.e. the resulting value is
    _not_ necessarily a NULL pointer value.

    char* p;
    long  i;

    i= 0;
    p= (char*)i;
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Xref: sparky comp.compilers:1349 comp.os.msdos.programmer:8507
From: bromage@mullauna.cs.mu.OZ.AU (Andrew Bromage)
Newsgroups: comp.compilers,comp.os.msdos.programmer
Subject: 8086 object code
Keywords: linker, question, 386
Date: 12 Aug 92 01:28:14 GMT
Reply-To: bromage@mullauna.cs.mu.OZ.AU (Andrew Bromage)
Organization: Computer Science, University of Melbourne, Australia

I am trying to write a code generator for an 8086-family chip.

Intel has an object module format especially designed for this chip, which
would be the logical choice for relocatable code. I remember seeing a
description of this in the MS-DOS Programmers Reference 3.2, which is
going back a few years now, but seems to have been left out of V5.0, which
is the current release.

I believe that the format is also described in the MS-DOS Encyclopaedia,
but my opinion is that this is not worth buying for one chapter (the price
in Oz is very expensive).

Does anybody know where I can get a copy of the specification?

Thanks in advance etc.

bromage@mullauna.cs.mu.oz.au
[I have an old Intel document that describes the format, but Microsoft has
added a lot to Intel's original spec to support fancy debuggers and library
systems. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: coatta@cs.ubc.ca (Terry Coatta)
Newsgroups: comp.compilers
Subject: Set Generators
Keywords: question, theory
Date: 20 Aug 92 18:32:36 GMT
Reply-To: coatta@cs.ubc.ca (Terry Coatta)
Organization: Computer Science, University of B.C., Vancouver, B.C., Canada

In a system that I am working on, sets of objects are often specified via
membership predicates.  In order to generate the sets involved the
membership predicate is essentially evaluated for all objects in the
system, and when it evaluates to true, the object is added to the set
being generated.  For many of the predicates I can, however, generate (by
hand) a recursive procedure which enumerates the set.  For example, the
set of objects in a tree can be specified via a predicate something like:

      All X such that Path(Root, X)

   where Path(X, Y) =
      Y is a child of X 
      OR
         there exists a Z, which is a child of X 
         AND Path(Z, Y)

(the actual syntax for this specification within the system is, of course,
quite different from the above, but I hope the example is clear).

This set can be very easily generated simply by doing a depth first
traversal of the tree.

What 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.
--
Terry Coatta (coatta@cs.ubc.ca)
Dept. of Computer Science, UBC, Vancouver BC, Canada
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: Diomidis Spinellis <dds@doc.imperial.ac.uk>
Subject: Re: Why is compiled basic slower than C
Reply-To: Diomidis Spinellis <dds@doc.imperial.ac.uk>
Organization: Compilers Central
Date: Wed, 12 Aug 1992 12:12:03 GMT
Keywords: Basic, C, performance

BASIC has many features that are inherently slow.  Comparable programs
written in C do not rely on such features, and therefore, generate faster
code.  The most important features of BASIC that result to slow code are:

1. All numeric computations are done in floating point by default.
   One must explicitly name a variable with a special integer suffix
   code, to declare it as an integer.

2. String operations rely on the dynamic memory allocation and
   garbage collection.  Both are slower than the staticaly
   allocated string memory / programer controlled allocation and
   disposal schemes that C programmers use.


Furthermore, in PC environments, C programs often directly control the
hardware of the output devices (e.g. screen) by using pointers to the
memory associated with them (e.g. screen buffer).  The same operation can
be expressed in BASIC only in a more roundabout way (usualy through a POKE
operation) and will therefore be slower.

Diomidis
--
Diomidis Spinellis    Internet: <dds@doc.ic.ac.uk>  UUCP: ...!uknet!icdoc!dds
Department of Computing, Imperial College, London SW7
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers