HDTenEightyP/NetNews huggingface dataset:
From: jos@and.nl (Jos Horsmeier)
Subject: Re: Theoretical CFG question
Reply-To: jos@and.nl (Jos Horsmeier)
Organization: Compilers Central
Date: Sun, 15 Nov 1992 14:57:29 GMT
Keywords: parse, question

norlin@essex.ecn.uoknor.edu (Norman Lin) writes:
|For i>=1, let b(i) denote the string in  1(0+1)   that is the
|binary representation of i.  Construct a CFG generating
|          +
|   {0,1,#}    -   {b(1)#b(2)# ... #b(n) | n>=1}
|
|[ ... ] Does anyone have any ideas about this problem?

If you apply the pumping lemma, it would show that this language is _not_
a context free language, so there exists no CFG that can generate this
language. No word in this language can be written
                      i  i
as UVWXY, such that UV WX Y, for i >= 0 is an element of this language too.
Or am I missing something here?

kind regards,

Jos aka jos@and.nl
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: glew@pdx007.intel.com (Andy Glew)
Subject: Re: Code optimization questions
Reply-To: glew@pdx007.intel.com (Andy Glew)
Organization: Intel Corp., Hillsboro, Oregon
Date: Wed, 18 Nov 1992 20:10:59 GMT
Keywords: optimize, performance

>Is there any info on optimizers that take advantage of profiler
>information [or] runtime assertions?  

The IMPACT compiler group at the University of Illinois under Prof.
Wen-Mei Hwu has done quite a bit of work on profiling feedback. Yes, there
are some published papers.  Look particularly for papers by Hwu and Pohua
(Paul) Chang. Contact hwu@crhc.uiuc.edu or pohua@gomez.intel.com
--
Andy Glew, glew@ichips.intel.com
Intel Corp., M/S JF1-19, 5200 NE Elam Young Pkwy, 
Hillsboro, Oregon 97124-6497
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: clyde@hitech.com.au (Clyde Smith-Stubbs)
Subject: Re: Is this a new idea?
Reply-To: clyde@hitech.com.au (Clyde Smith-Stubbs)
Organization: HI-TECH Software, Brisbane, QLD, Australia.
Date: Wed, 18 Nov 1992 23:48:44 GMT
Keywords: C, design

I seem to have missed the first response:

clyde@hitech.com.au (Clyde Smith-Stubbs) writes:
>   ...you can't parse code that contains references to such things as
>   typedefs that occur earlier in the code, if the typedef is missing
>   or in the middle of being edited....

macrakis@osf.org (Stavros Macrakis) writes:
>   This is a C-specific problem: a bug in the design of C's syntax.  Most
>   other languages don't commit such foolishness, except of course those
>   with extensible syntax.

True.

drw@euclid.mit.edu (Dale R. Worley) writes:
>Almost any language with an extensible set of operators is going to
>run into this problem.

I thought that's what he said? However, the solution is now clear. We
should all immediately abandon C and any languages with extensible syntax,
and perform an appropriate penance for having used such ideologically
unsound tools. A month of COBOL programming sounds appropriate.

And of course by switching to a non-extensible language we will
immediately get the benefit of instant compilation. I'm talking about
BASIC of course.

More seriously, the typedef problem in C does cause parsing difficulties,
but C is here to stay. Rather than pointing fingers at its design, it
would be better to look for ways of solving the problem at hand (which was
speeding up re-compilations).
--
 Clyde Smith-Stubbs       | HI-TECH Software,       | Voice: +61 7 300 5011
 clyde@hitech.com.au      | P.O. Box 103, Alderley, | Fax:   +61 7 300 5246
 ...!nwnexus!hitech!clyde | QLD, 4051, AUSTRALIA.   | BBS:   +61 7 300 5235
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: Atholl Hay <atholl@epcfta.edinburgh.ac.uk>
Subject: Instruction Scheduling Bibliography
Organisation: Edinburgh Portable Compilers
Reply-To: Atholl Hay <atholl@epcfta.edinburgh.ac.uk>
Organization: Compilers Central
Date: Wed, 18 Nov 1992 18:03:52 GMT
Keywords: optimize, architecture, question

Does anyone have a bibliography covering research in the last
10 years or so into techniques of local and global instruction
scheduling?

Thanks,

Atholl Hay

Atholl Hay, atholl@uk.ac.ed.epc from JANET, atholl@epc.ed.ac.uk elsewhere
Phone +44 31 225 6262, Fax +44 31 225 6644
Edinburgh Portable Compilers Ltd
17 Alva Street, Edinburgh, Scotland, EH2 4PH
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: eggert@twinsun.com (Paul Eggert)
Subject: Re: IEEE arithmetic handling
Reply-To: eggert@twinsun.com (Paul Eggert)
Organization: Twin Sun, Inc
Date: Tue, 17 Nov 1992 18:58:37 GMT
Keywords: arithmetic

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

>Fortran does not *conflict* with the IEEE vis-a-vis negative zero. It merely
>says that the processor must never *output* a negatively-signed zero.

But that conflicts with IEEE Std 754-1985, section 5.6, which requires
that converting a number from binary to decimal and back be the identity
if the proper precision and rounding is used.  The Fortran standard says
-0.0 must be output as 0.0; this loses information.

One way to work around the problem is to supply IEEE-specific
binary/decimal conversion routines to the Fortran programmer, but there's
no standard for this, and most implementors don't bother.  So in practice,
I'm afraid that Fortran and IEEE are indeed in conflict here.
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: thewalt@ce.Berkeley.EDU (C. Thewalt)
Subject: byacc help needed
Reply-To: thewalt@ce.Berkeley.EDU (C. Thewalt)
Organization: Dept. of Civil Engineering, University of California, Berkeley
Date: Sun, 22 Nov 1992 17:43:03 GMT
Keywords: yacc, errors, question, comment

I tried to reach the author of byacc (corbett@berkeley.edu) but that
account is dead, so I'd appreciate the help of any yacc experts out there,
byacc in particular.

It appears that the parse state in y.tab.c is controlled by a few scalar
variables.  If this is the case, it would seem possible to squirrel away
copies and do a setjmp whenever we are in an acceptable state, and when
syntax errors occur do a longjmp back to the saved state and reset the
variables.

I'd really like to do this on a line by line basis, and in the event of a
syntax error on a line eat input to the newline and then reset at the
state of the previous line.

Is this feasible?

Chris
thewalt@ce.berkeley.edu
--
Christopher Robin Thewalt               (thewalt@ce.berkeley.edu)
Dept. of Civil Engineering, University of California, Berkeley
[It might be possible, but I'd think it'd be a lot easier to use the yacc
``error'' token.  Corbett's address as of July is Robert.Corbett@Eng.Sun.COM
but he no longer actively supports byacc. -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: preston@miranda.cs.rice.edu (Preston Briggs)
Subject: Re: optimizing for caches
Reply-To: preston@miranda.cs.rice.edu (Preston Briggs)
Organization: Rice University, Houston
Date: Thu, 19 Nov 1992 17:43:02 GMT
Keywords: optimize, architecture, 

Richard Cownie <richard@meiko.com> writes:
>From experiences tuning vector routines for i860's and SPARC's, I've come
>to the conclusion that understanding and exploiting the memory hierarchy
>is essential to obtain good performance on these kinds of problems.  But I
>have yet to see a compiler which tackles this aspect of optimization.

I agree that the problem is terribly important.  On the other hand,
Portland Group's compiler for the i860 certainly attacks the problem, as
does the Kuck preprocessor that is so maligned in discussions of the SPEC
benchmarks.  Additionally, there are several research compilers attacking
these problems (at Stanford, Rice, Illinois, and other places).

There's been a lot of research in the area.  I don't have a good
bibliography for this area; but, a nice starting point might be

	The Cache Performance and Optimization of Blocked Algorithms
	Monica Lam, Edward E. Rothberg, and Michael E. Wolf
	pages 63-74
	ASPLOS IV, 1991

Preston Briggs
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: grover@brahmand.Eng.Sun.COM (Vinod Grover)
Subject: Range Checking (was: And speaking of ...)
Reply-To: grover@brahmand.Eng.Sun.COM (Vinod Grover)
Organization: Sun Microsystems, Mt. View, Ca.
Date: Thu, 19 Nov 1992 07:26:00 GMT
Keywords: performance, optimize, design

cheryl@gallant.apple.com (Cheryl Lins) writes:
>Range and bounds checking are variations on the constant propagation
>problem.  

With proper design, range checking could also be viewed as common
subexpression elimination, code motion, and strength reduction. (In fact
partial redundancy elimination; PL.8 compiler used strength reduction to
eliminate some of the range checks). The intermediate representation could
be augmented with "check_range", "check_nil", etc. expressions for
traditional optimizations to be used.

More powerful techniques are based on abstract interpretation (Cousot &
Cousot [?], and Karr [Acta Informatica 197x); but may not be practical for
use in production quality compilers.

Vinod Grover
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Xref: sparky comp.compilers:1885 misc.jobs.offered:13702
From: danfuzz@wastelands.kaleida.com (Dan Bornstein)
Newsgroups: comp.compilers
Subject: Re: error recovery with yacc
Keywords: yacc, errors
Date: 14 Nov 92 03:55:47 GMT
Article-I.D.: comp.92-11-075
Reply-To: danfuzz@wastelands.kaleida.com (Dan Bornstein)
Organization: Kaleida Labs, Inc.

>I have a problem understanding/using the error recovery mechanisme
>with yacc. Part of my syntax is:
>
>[...]
>     statement_list
>             : /* empty */
>             | statement
>             | statement_list separator
>             | statement_list separator statement
>             ;
>[...]
>
>If some statement is in error then I just want to skip over the 
>next separator (which is a ';' or NEWLINE) and continue the
>parsing of the proc_body with the rest of the statements.
>I added the following rule to the statement_list definition:
>             | error separator statement_list
>( no yyerrok here!) 
>This seems ok, but causes the error to be reduce only just before
>the ENDPROC.
>Somehow it just doesn't feel right to me. Is there a better way?

The way I do it (and usually see it done) would be to reverse
it around:

              | statement_list error separator

meaning, more or less, "A statement list followed by an error and a
separator is still a statement list." The way you originally put it, "A
statement list can start with an error and then a separator, but you still
have to find another statement list after that." So, what yacc was doing
was dutifully finding the longest statement_list following the error and
separator before reporting the error.

Since a statement_list might be empty, you can still get the rule to
reduce given an error at the beginning of the input text.

-Dan Bornstein
danfuzz@kaleida.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: pwau@alcbel.be (Patrick de Wauters)
Subject: Sources from J.P. Bennet's book
Reply-To: pwau@alcbel.be (Patrick de Wauters)
Organization: Compilers Central
Date: Thu, 19 Nov 1992 11:14:39 GMT
Keywords: books, question

Is there an ftp-site from where I can download the sources from J.P.
Bennet`s excellent book "Introduction to Compiling Techniques - A first
Course Using Ansi C, Lex and Yacc"?

Regards,

Patrick Wauters.
email: pwau@alcbel.be

ALCATEL-BELL
Research Centre
Francis Wellesplein 1
B-2018 Antwerpen
Belgium
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: macrakis@osf.org (Stavros Macrakis)
Subject: Re: Is this a new idea?
Reply-To: macrakis@osf.org (Stavros Macrakis)
Organization: OSF Research Institute
Date: Fri, 20 Nov 1992 16:13:26 GMT
Keywords: design

clyde@hitech.com.au (Clyde Smith-Stubbs) said:
   >   ...you can't parse code that contains references to such things as
   >   typedefs that occur earlier in the code, if the typedef is missing
   >   or in the middle of being edited....

I (macrakis@osf.org (Stavros Macrakis)) replied:
   >   This is a C-specific problem: a bug in the design of C's syntax.  Most
   >   other languages don't commit such foolishness, except of course those
   >   with extensible syntax.

clyde@hitech.com.au (Clyde Smith-Stubbs) continued:

   ...the solution is now clear. We should all immediately abandon C

Sounds like a good idea.

   and any languages with extensible syntax,

Not many of those around these days.

   and perform an appropriate penance for having used such
   ideologically unsound tools. A month of COBOL programming sounds
   appropriate.

I don't suggest penance.  I suggest improving the choice of language.

   And of course by switching to a non-extensible language we will
   immediately get the benefit of instant compilation. I'm talking about
   BASIC of course.

Recompilation is actually quite fast if you do it on appropriately-sized
chunks, e.g. individual functions or modules.  Even for C, with its weak
notions of inter-module declarations, it is possible to precompile
definition headers (the processing of which is a major cost in compiling
C, especially if you use large libraries like X).

   More seriously, the typedef problem in C does cause parsing difficulties,
   but C is here to stay. Rather than pointing fingers at its design, it
   would be better to look for ways of solving the problem at hand (which was
   speeding up re-compilations).

Working on better tools for existing languages doesn't preclude working on
better tools _and_ languages.

	-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: preston@dawn.cs.rice.edu (Preston Briggs)
Subject: Re: And speaking of fast compilers...
Reply-To: preston@dawn.cs.rice.edu (Preston Briggs)
Organization: Rice University, Houston
Date: Tue, 17 Nov 1992 02:14:59 GMT
Keywords: performance, Ada, design

sasdrf@unx.sas.com (Dave Frederick) writes:

>One of the hot topics when I last worked on an Ada compiler was doing the
>above range and bounds checking optimization across procedures in a
>package. Interprocedural analysis is quite helpful for determining the
>possibility of these errors on var parameters. Of course, with a 7000-line
>package of page-sized procedures, we could be talking about 200-300
>procedures on which to perform inter-procedural analysis. This could be a
>week's worth of work.

Depends a lot on the exact formulation of the problem.  Some approachs to
problems like interprocedural constant propagation, aliasing, etc. have
worked out very well.  Others are NP-complete.

Back to the fast compiler idea though...

One idea that hasn't been mentioned was explored by Rick Bubenik in his
thesis -- optimistic computation (where explored optimistic compilation as
a particular instance).  Basically, every time you save a source file, it
fires off a new make job on another processor.  If the compile fails due
to errors -- fine, throw it away (but keep the stderr file).  If it
suceeds -- great, now wait for the user to type make!

Rather similar to speculative execution being explored in processor
architecture.  Of course, you may need more hardware, but lots of us work
on big networks of machines.  Or we could even attempt the compile in
background -- after all, I don't use much of the machine to edit.  Of
course, with a network, it makes more sense to fire up a big parallel make
(imagine we're editing an important include file).

I would assume that some of these ideas have also been explored in the
programming environment community.

Preston Briggs
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: chris@gargoyle.uchicago.edu (Chris Johnston)
Subject: Re: Modulo n arithmetics
Reply-To: chris@gargoyle.uchicago.edu (Chris Johnston)
Organization: University of Chicago Computing Organizations
Date: Thu, 19 Nov 1992 19:49:44 GMT
Keywords: arithmetic

fabre@gr.osf.org (Christian Fabre) writes:
>I am wondering if any languages or application heavily rely on
>modulo arithmetics:

Some applications...

How about communication, TCP uses 32bit counters to sequence packets, the
packet following 32 ones is zero.  Trading (stocks/futures) cards are
numbered 000 to 999.  Database rows...  Any counter that can wrap to zero.

You want to be able to sort items arriving out of order and detect missing
items.  The TCP folk call this sequence space arithemtic.  See
/usr/include/netinet/tcp_seq.h

cj
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: bowen@comlab.oxford.ac.uk (Jonathan Bowen)
Newsgroups: comp.compilers
Subject: Re: Two Level Grammars
Keywords: parse, bibliography
Date: 13 Nov 92 10:12:44 GMT
Article-I.D.: comp.92-11-071
Reply-To: bowen@comlab.oxford.ac.uk (Jonathan Bowen)
Organization: Programming Research Group, Oxford University, UK

Lee Leitner <0005507197@mcimail.com> writes:
>I am looking for some reference sources for "two level Grammars" and "Van
>Wijngaarden form" grammars.

The following reference may be of interest:

\bibitem{DW78}
P.\ Deussen and L.M.\ Wegner.
A bibliography of the van Wijngaarden grammars.
{\em Bulletin of the European Association of Theoretical Computer
Science (EATCS)}, {\bf 6}, 1978.

\bibitem{Wegner80}
L.M.\ Wegner.
On parsing two-level grammars.
{\em Acta Informatica}, {\bf 14}, pp.~175--193, 1980.
 
\bibitem{Grune84}
D.\ Grune.
How to produce all sentences from a two-level grammar.
{\em Information Processing Letters},
{\bf 19}, pp.~181--185, 1984.

-- 
Jonathan Bowen, <Jonathan.Bowen@comlab.ox.ac.uk>
Oxford University Computing Laboratory.
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: mty@ntu.ac.sg (Yap Ma Tit)
Newsgroups: comp.compilers
Subject: Re: Sources from J.P. Bennet's book
Keywords: lex, yacc, books
Date: 23 Nov 92 09:12:13 GMT
Article-I.D.: comp.92-11-131
Reply-To: mty@ntu.ac.sg (Yap Ma Tit)
Organization: Nanyang Technological University - Singapore

The sources from J.P. Bennett's book are available in the UK by Email from
the School of Mathematical Sciences at Bath Univ.

To find out how to obtain them send a message to:-

compiler-request@maths.bath.ac.uk

with two lines as follow:

help:
end:

Ma-Tit, Yap
-- 
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: Pascal parser wanted, was COBOL !
Keywords: Pascal
Date: 23 Nov 92 09:40:14 GMT
Article-I.D.: comp.92-11-132
Reply-To: wjw@eb.ele.tue.nl (Willem Jan Withagen)
Organization: Eindhoven University of Technology, The Netherlands

> Does anyone out there know where I could get source for a [Pascal] compiler?
> ... even a subset !

I've collected:
	some pascal compiler sources (in Pascal) 
        An DOS executable Pascal-S compiler
	Very simple and trivial tests for pascal compilers.

And I made a pascal frontend using the Cocktail tools, which include an
attribute driven semantic checker.

all of these are in:
	ftp.eb.ele.tue.nl:/pub/src/pascal

Regards,
	Willem Jan Withagen.

-- 
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;
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: pardo@cs.washington.edu (David Keppel)
Subject: Re: And speaking of fast compilers...
Reply-To: pardo@cs.washington.edu (David Keppel)
Organization: Computer Science & Engineering, U. of Washington, Seattle
Date: Tue, 17 Nov 1992 19:54:32 GMT
Keywords: performance, design, bibliography, comment

sasdrf@unx.sas.com (Dave Frederick) writes:
>[Had the Brand X Ada compiler passed validation?
> A lot of optimizations are compile-time range and bounds checks.]

I do not know if the Brand X compiler was validated.  As the moderator
points out, compiling to C does not imply any loss of type safety (for
that matter, the first validated Ada system was an interpreter...), so it
may well be a validated compiler.

The IBM PL.8 compiler removed a substantial number of the runtime range
and bound checks with only a modest increase in the compile time (the
range-checked code was still 5-10% slower than unchecked code).  So I
doubt that removing bound checks explains why the compiler was slow,
especially given that the compilation was slow (40 minutes v. 6) even with
the slower compiler's optimization OFF.

%A Marc Auslander
%A Martin Hopkins
%T An Overview of the PL.8 Compiler
%P 22-31
%J Proceedings of the ACM SIGPLAN '82 Syumposium on Compiler
Construction
%D June 1982
%P 22-31

%A Rajiv Gupta
%T A Fresh Look at Optimizing Array Bound Checking
%J Proceedings of the ACM SIGPLAN '90 conference on Programming
Language Design and Implementation.
%D June 1990
%P 272

And I haven't read it, but it's the common citation:

%A V. Markstein
%A J. Cocke
%A P. Markstein
%T Optimization of Range Checking
%J Proceedings of the ACM SIGPLAN '82 Syumposium on Compiler
Construction

	;-D oN  ( Bound checked and gaggled )  Pardo
[The PL.8 range checking was quite innovative.  They patented it. -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: wendt@CS.ColoState.EDU (alan l wendt)
Subject: Re: Modulo n arithmetics
Reply-To: wendt@CS.ColoState.EDU (alan l wendt)
Organization: Colorado State University, Computer Science Department
Date: Sun, 15 Nov 1992 16:39:06 GMT
Followup-To: comp.programming
Keywords: arithmetic

Speaking of modulo-n buffering systems.  This is really the wrong group
but I cannot help mentioning that the traditional head-and-tail pointer
technique for circular buffering is the wrong way to do it.  The problem
is that head==tail can mean that the queue is empty or that the queue is
full, so most implementations waste a queue entry so that the queue never
really gets full.

If the algorithm maintains the queue head pointer and the queue length,
instead of head and tail, the two cases can be disambiguated easily!

Horowitz & Sahni (Fundamentals of Computer Algorithms) suggest that one
might maintain an additional boolean to disambiguate the two situations,
which I take as evidence that this idea is not widely disseminated.

Alan Wendt
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers