cotner@bosco.berkeley.edu (07/29/88)
A friend of mine would like to write a small C compiler for a project. (The rest of the class are writing Pascal compilers). However, he needs a formal language description of C, and so far neither one of us have been able to find one. If any one out there in netland can suggest a reference we would both appreciate it. 10Q --carl cotner@bosco.Berkeley.EDU P.S. I usually don't read this newsgroup, so please e-mail
smryan@garth.UUCP (Steven Ryan) (07/30/88)
> However, he needs >a formal language description of C, and so far neither one of us have been >able to find one. You can get a language description out of K+R, but forget about a formal definition unless you want to do it yourself.
gwyn@brl-smoke.ARPA (Doug Gwyn ) (07/30/88)
In article <1104@garth.UUCP> smryan@garth.UUCP (Steven Ryan) writes: >>However, he needs a formal language description of C, and so far >>neither one of us have been able to find one. >You can get a language description out of K+R, but forget about a formal >definition unless you want to do it yourself. If you don't know what you're talking about, then please shut up. The fellow can probably get what he's looking for, and more, by talking with the people at Metaware, Tom Penello for example. They specialize in formal semantics. Metaware advertises their compiler in various PC magazines.
smryan@garth.UUCP (Steven Ryan) (07/31/88)
In article <8270@brl-smoke.ARPA> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes: >>You can get a language description out of K+R, but forget about a formal >>definition unless you want to do it yourself. > >If you don't know what you're talking about, then please shut up. If you know what you're talking about, show us. >The fellow can probably get what he's looking for, and more, by >talking with the people at Metaware, Tom Penello for example. >They specialize in formal semantics. Metaware advertises their >compiler in various PC magazines. A compiler is not a definition. A compiler is an implementation of a definition. They specialise in formal semantics? What have they actually done? When I talk about formal definition I do not mean the usual garbage you see in Ans languages or stuff like K+R. I mean something like the PL/I definition or the Revised Algol 68 Report. Formal syntax, context free and context sensitive, and formal semantics. If there was a formal definition, three-quarters of the topics in comp.lang.c would never appear.
gwyn@brl-smoke.ARPA (Doug Gwyn ) (07/31/88)
In article <1112@garth.UUCP> smryan@garth.UUCP (Steven Ryan) writes: >In article <8270@brl-smoke.ARPA> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes: >>The fellow can probably get what he's looking for, and more, by >>talking with the people at Metaware, Tom Penello for example. >A compiler is not a definition. A compiler is an implementation of a >definition. Thanks for explaining something totally irrelevant. "Gee, I didn't know that." Metaware does have a formal semantic specification of C. Penello tried to get X3J11 to use such a method instead of the combined formal grammar and English that was actually adopted. I mentioned Metaware's compiler ads to help the fellow get in touch with them since I didn't have their address or phone number at hand.
gwyn@brl-smoke.ARPA (Doug Gwyn ) (08/01/88)
In article <6492@bloom-beacon.MIT.EDU> wesommer@athena.mit.edu (William Sommerfeld) writes: >I have sitting in front of me the 1.31.87 version of "High C Language >Reference Manual". That is NOT the formal semantic specification to which I was referring. Geez, don't any of you know what formal semantics are?? I have no comments on the quality or lack thereof of MetaWare's C compiler product(s). That was not the topic under discussion.
jos@philapd.UUCP (Jos Vos) (08/01/88)
In article <12707@agate.BERKELEY.EDU> cotner@bosco.berkeley.edu writes: >A friend of mine would like to write a small C compiler for a project. >(The rest of the class are writing Pascal compilers). However, he needs >a formal language description of C, and so far neither one of us have been >able to find one. In "C: A Reference Manual", written by Harbison & Steele, a LALR(1) grammar is included in an appendix. You *should* be able to feed it to YACC, for instance, but I have never tried it! Of course (?), this is only a *syntactic* description, not a *semantic* one. -- # Jos Vos # Internet jos@philapd.UUCP # # Philips TDS, Dept SSP # # # P.O. Box 245 # UUCP ..!mcvax!philapd!jos # # 7300 AE Apeldoorn, The Netherlands # Phone +31 55 433181 #
mikpe@miraculix.liu.se (Mikael Pettersson) (08/02/88)
In article <1112@garth.UUCP> smryan@garth.UUCP (Steven Ryan) writes: > [...] >If there was a formal definition, three-quarters of the topics in >comp.lang.c would never appear. Since 50% of the garbage in comp.lang.c is written because people don't even read their K&R or H&S properly, how can you expect them to understand the kind of mathematical definition found in, say, denotational or axiomatic semantics? I would like to see a C _language_ (no libraries) definition similair to R3RS (Revised^3 Report on the Algirithmic Language Scheme, can be found in SIGPLAN Dec-86): background, formal syntax, a general description of each construct in the language, and finally a denotational semantics definition. I believe Ravi Sethi wrote such a definition for an ACM conference back in 1980 but I haven't seen it (yet). Mike -- Mikael Pettersson ! Internet:mpe@ida.liu.se Dept of Comp & Info Science ! UUCP: mpe@liuida.uucp -or- University of Linkoping ! {mcvax,munnari,uunet}!enea!liuida!mpe Sweden ! ARPA: mpe%ida.liu.se@uunet.uu.net
smryan@garth.UUCP (Steven Ryan) (08/02/88)
>I have sitting in front of me the 1.31.87 version of "High C Language >Reference Manual". [I wonder if that's a reference to Hi C?] >I'll quote from it, without permission, to see if you think their >formal definition is sufficiently formal: > >\begin{quote} >7.7 for > >Syntax > >Statement -> 'for' '(' First: EL? ';' > Next: EL? ';' > Last: EL? > ')' Body: Statement > >Constraints: > `Next', if present, must have a scalar type. In the style of A68 RR: NEST for statment: for token,NEST for control pack,NEST controlled statement. NEST for control: NEST initial expression,semicolon token, NEST next expression,semicolon token, NEST last expression. NEST initial expression: TYPE NEST expression list. NEST next expression: {This is what I mean by formal context} TYPE NEST expression list, {sensitive grammar. The tools are } where TYPE is scalar type; {available though unused. } EMPTY. NEST final expression: TYPE NEST expression list. NEST controlled statement: loop level NEST statement. {Mark loop for contained break/continue.} >Semantics: > If `Next' is omitted, `1' is implied. > > Except in the matter of a contained _continue_ `Statement' in >the `Body', this statement is exactly equivalent to > > First; while (Next) { Body; Last; } > >Thys, the `First' and `Next' evaluation ends are sequence points. In the for statement S, let F be the first expression, N be the next expression if not null otherwise 1, let be L be the last expression, let C be the controlled statement. The evaluation of S is (a) the evaluation of F (b) the evaluation of N If the yield of N is a true value, (i) the evaluation of C {Need to include something here so that the evaluation of break or continue within C terminates the evaluation of C here and possibly the evaluation of S. It's difficult to do in isolation of the entire grammar, but at least the declaration nest is marked.} (ii) the evaluation of L (iii) the evaluation of the for statement S' with F' empty, N' is N, L' is L, C' is C. If the yield of N is a false value, (iv) the evaluation of S is complete. >Discussion: > The first expression is a convenient place to put any >initialization for the loop. The second specifies a test for >continuing the loop and perhaps an incrementation. The third usually >specifies an operation performed at the end of the loop, such as an >increment of a variable. {How to use the language is not part of the definition--it belongs in tutorials. However to explain some of the subtleties, comments can be included so long as they are not considerred part of the definition.} >\end{quote} > >I wish MetaWare had spent less time making Ada-like extensions to C >(their compiler supports Ada-style "keyword" arguments with defaults, >for example, which you are not going to find in any other compiler), It's nice to see somebody make a stab at a complete definition. Now if if everybody can agree to this definition (assuming it is complete and all ambiguities are resolved) C will finally be formally defined. The fact that contains extensions (what C compiler doesn't?) makes that unlikely.
smryan@garth.UUCP (Steven Ryan) (08/02/88)
>>>The fellow can probably get what he's looking for, and more, by >>>talking with the people at Metaware, Tom Penello for example. As somebody else pointed out, their compiler is unusual and their definition is thus unlikely to be widely accepted. >>A compiler is not a definition. A compiler is an implementation of a >>definition. > >Thanks for explaining something totally irrelevant. >"Gee, I didn't know that." That's alright, son, most people don't know either. How people believe the formal definition of C is something other than `whatever PCC does on a PDP-11?' The only formal definition of Cyber Fortran 200 (FTN200) is the compiler. That's what my project leader said (in essence) when I worked on the compiler. How languages do you know which are defined instead of having reference manuals which are really tutorials in disguise? How often do people resolve a fine point in the language, not by finding the precise production rules, but by coding it up on their favorite box, possibly even going down to the resultant assembly listing?
reggie@pdn.UUCP (George W. Leach) (08/02/88)
In article <843@miraculix.liu.se> mikpe@miraculix.liu.se (Mikael Pettersson) writes: >I believe Ravi Sethi wrote such a definition for an ACM conference back in >1980 but I haven't seen it (yet). I recall seeing three Bell Labs TMs on the Semantics of C, which addressed the issues you stated in your article. I also seem to recall seeing a revision of these into a single paper by Dr. Sethi as well. Alas, I no longer have a copy nor a decent library in which to search for it. I would suspect that it may be found in the ACM SIGPLAN Compiler Construction Proceedings. Your date of 1980 sounds about right plus or minus a year. -- George W. Leach Paradyne Corporation ..!uunet!pdn!reggie Mail stop LF-207 Phone: (813) 530-2376 P.O. Box 2826 NOTE: codas<--->pdn will be gone soon Largo, FL 34649-2826
markg@dbase.UUCP (NFS 3C501) (08/02/88)
In article <12707@agate.BERKELEY.EDU>, cotner@bosco.berkeley.edu writes: > A friend of mine would like to write a small C compiler for a project. > (The rest of the class are writing Pascal compilers). However, he needs > a formal language description of C, and so far neither one of us have been > able to find one. A more complete description of the C language is the ANSI C Standard. It is currently available only in draft form. I'm not sure where to get hold of it. You might try ANSI (American National Standards Institute) located in New York City somewhere or other on Broadway in Manhattan. They do not distribute draft versions of standards but could tell you who does distribute it.
henry@utzoo.uucp (Henry Spencer) (08/03/88)
In article <1112@garth.UUCP> smryan@garth.UUCP (Steven Ryan) writes: >...something like the PL/I >definition or the Revised Algol 68 Report. Formal syntax, context free and >context sensitive, and formal semantics. > >If there was a formal definition, three-quarters of the topics in >comp.lang.c would never appear. Ho ho. No, it's not that simple. The problem with formal definitions like the PL/I definition and the Revised Algol 68 Report is that they are hideously unreadable. X3J11 talked about the possibility earlier on, and quickly rejected it, on the grounds that a less formal description was far more accessible to users and implementors. -- MSDOS is not dead, it just | Henry Spencer at U of Toronto Zoology smells that way. | uunet!mnetor!utzoo!henry henry@zoo.toronto.edu
ldg@druin.ATT.COM (Doug Gibbons) (08/03/88)
Attribute grammars are yet another type of formal language
definition, combining context free syntax with context sensitive
semantics. An MS thesis I did while at the University of Colorado
described the syntax and static semantics of C using an attribute
grammar written in Aladin. Since I was finishing just as X3J11 was
starting, the grammar does not describe ANSIisms.
Below is a grammar excerpt describing a C shift expression. The CFG
production appears first, followed by the attribution and context
conditions which must hold true. With a little effort, you can get a feel
for what is going on here. The "{in|out}" attributes are used to thread
various symbol tables through the production. The interesting things
computed here are:
SHIFT_EXP[1].at_type the expression's type
SHIFT_EXP[1].at_value the expression's value
SHIFT_EXP[1].at_eval_time when value can be known
SHIFT_EXP[1].at_const_exp is it a constant expression?
-------------------------------------------------------------------------------
rule r_39 :
SHIFT_EXP ::= SHIFT_EXP SHIFT_OP ADD_EXP
static
%
% Do the UAC balancing on the operands. Both must be integral types.
% The type is that of the converted left operand. If the right operand
% is negative or greater than the size (in bits) of the type of the
% left after the UAC, then the result is undefined.
%
SHIFT_EXP[1].at_const_exp :=
SHIFT_EXP[2].at_const_exp and ADD_EXP.at_const_exp;
SHIFT_EXP[1].at_eval_time :=
if f_is_defined(SHIFT_EXP[1].at_value) then
sc_constant
else
sc_run_time
fi;
SHIFT_EXP[1].at_id_defs_out := ADD_EXP.at_id_defs_out;
SHIFT_EXP[1].at_lval_class := sc_rval;
SHIFT_EXP[1].at_tag_names_out := ADD_EXP.at_tag_names_out;
SHIFT_EXP[1].at_tag_props_out := ADD_EXP.at_tag_props_out;
SHIFT_EXP[1].at_type :=
f_balance(SHIFT_EXP[2].at_type, ADD_EXP.at_type);
SHIFT_EXP[1].at_value :=
f_eval_binary (
SHIFT_OP.at_op,
SHIFT_EXP[2].at_value,
ADD_EXP.at_value);
SHIFT_EXP[2].at_id_defs_in := SHIFT_EXP[1].at_id_defs_in;
SHIFT_EXP[2].at_tag_names_in := SHIFT_EXP[1].at_tag_names_in;
SHIFT_EXP[2].at_tag_props_in := SHIFT_EXP[1].at_tag_props_in;
ADD_EXP.at_id_defs_in := SHIFT_EXP[2].at_id_defs_out;
ADD_EXP.at_tag_names_in := SHIFT_EXP[2].at_tag_names_out;
ADD_EXP.at_tag_props_in := SHIFT_EXP[2].at_tag_props_out;
condition
f_is_integral(SHIFT_EXP[2].at_type) and
f_is_integral(ADD_EXP.at_type)
message
"error: shift requires integral operands";
condition
not f_is_neg_i(SHIFT_EXP[1].at_value)
message
"warning: result of negative shift is non-portable";
condition
if f_is_defined(ADD_EXP.at_value) then
f_is_gt_i (
ADD_EXP.at_value,
f_mach_val (
f_mach_bit_sizeof(SHIFT_EXP[1].at_type),
sc_uint))
else
true
fi
message
"warning: magnitude of right operand of shift causes undefined value";
end;
-------------------------------------------------------------------------------
-- Doug Gibbons | ldg@druhi.ATT.COM or att!druhi!ldg
-- AT&T Bell Laboratories
-- Denver COmarkhall@pyramid.pyramid.com (Mark Hall) (08/04/88)
If you are not offended by attribute grammars as
language specs, Lee Gibbons' MS Thesis from UC Boulder:
_An_Attribute_Grammar_for_the_C_Programming_Language_
is available by mailing to:
Computer Science Department Attn: Tech Reports
University of Colorado, Boulder
Boulder, CO 80309-0430
(303)492-6361
-Mark Hall (smart mailer): markhall@pyramid.pyramid.com
(uucp paths ):
{amdahl|decwrl|sun|seismo|lll-lcc}!pyramid!markhallgillies@p.cs.uiuc.edu (08/04/88)
Sidestepping all the bickering on what constitutes a formal definition
of a language: If you just want the YACC input for a C parser, see
Notesfile: comp.sources.wanted
Note: "List of currently available sources"
Author: jfh@rpp386.UUCP
File: "c-grammar" (listed within the posting)
Don Gillies, Dept. of Computer Science, University of Illinois
1304 W. Springfield, Urbana, Ill 61801
ARPA: gillies@cs.uiuc.edu UUCP: {uunet,ihnp4,harvard}!uiucdcs!gilliesfeldmark@hanako.stars.flab.Fujitsu.JUNET (08/04/88)
In article <458@ssp15.idca.tds.philips.nl> jos@philapd.UUCP writes: > In "C: A Reference Manual", written by Harbison & Steele, a LALR(1) grammar > is included in an appendix. You *should* be able to feed it to YACC, for > instance, but I have never tried it! I haven't looked at this book in particular, but if it is anything like what appears in K&R, it is probably possible but requires modifications. A long time ago in a place far far away we had to write a C compiler and were advised NOT to use what's in the back of K&R because YACC couldn't process it correctly. Most of us paid little attention, made some modifications which I don' t remember, and came out OK. If you have the time to search for it and understand it, look for the YACC source for the UNIX C compiler. We didn't find out it was there until we were almost finished, so it didn't help much, if you know before you start, it might be useful. :-) Mark Feldman Fujitsu Laboratories Ltd. Artificial Intelligence Laboratory feldmark@hanako.stars.flab.fujitsu.junet (Japan) feldmark%hanako.stars.flab.fujitsu.junet@uunet.uu.net (USA) -- feldmark@hanako.stars.flab.fujitsu.junet (Japan) feldmark%hanako.stars.flab.fujitsu.junet@uunet.uu.net (USA)
smryan@garth.UUCP (Steven Ryan) (08/05/88)
>Ho ho. No, it's not that simple. An apt comment on the future of C and Unix. > The problem with formal definitions like >the PL/I definition and the Revised Algol 68 Report is that they are >hideously unreadable. X3J11 talked about the possibility earlier on, and >quickly rejected it, on the grounds that a less formal description was far >more accessible to users and implementors. The original query was if a formal definition of C existed. Thanks to Happy Hank for agreeing with me that there was none. As far being `unreadable' or less `accessible,' that's too easy a target. As long as we refuse to correct the problems that exists, they will continue.
swarbric@tramp.Colorado.EDU (Frank Swarbrick) (08/05/88)
In article <33973@pyramid.pyramid.com> markhall@pyramid.UUCP (Mark Hall) writes: }If you are not offended by attribute grammars as }language specs, Lee Gibbons' MS Thesis from UC Boulder: } } _An_Attribute_Grammar_for_the_C_Programming_Language_ } }is available by mailing to: } } Computer Science Department Attn: Tech Reports } University of Colorado, Boulder } Boulder, CO 80309-0430 } (303)492-6361 I'm surprised! My very own college having something somewhat impressive available for computer science! And C, even! Hopefully this means that I will actually be *allowed* to use C next semester... (no I don't know why I posted this) Frank Swarbrick (and, yes, the net.cat) swarbric@tramp.Colorado.EDU ...!{ncar|nbires}!boulder!tramp!swarbric "Some people think they're gonna die some day. I got news, ya never got ta go." --Ted Nugent
pardo@june.cs.washington.edu (David Keppel) (08/05/88)
>[ Lee Gibbons' MS Thesis ... C attribute grammar ]
I believe that the Cornell Program Synthesizer also contains a
(pre-ansi) attribute-grammar specification of C. If I understand
correctly, CPS builds you both a structure editor and a compiler
front end from the same attribute grammar.
;-D on ( But first you need the attribute grammar! ) Pardo
--
pardo@cs.washington.edu
{rutgers,cornell,ucsd,ubc-cs,tektronix}!uw-beaver!june!pardobts@sas.UUCP (Brian T. Schellenberger) (08/06/88)
In article <1104@garth.UUCP> smryan@garth.UUCP (Steven Ryan) writes: |> However, he needs |>a formal language description of C, and so far neither one of us have been |>able to find one. | |You can get a language description out of K+R, but forget about a formal |definition unless you want to do it yourself. Well, H&S has a good formal BNF grammar (which I have used). As for semantics, I'd recommend ANSI. It's close enough to finished to be relavent, and it's the only formal (even if it is English-like) semantic description I've ever seen of C. H&S = "Harbison & Steele" Available at local bookstores. -- --Brian, __________________________________________________ the man from |Brian T. Schellenberger ...!mcnc!rti!sas!bts Babble-On |104 Willoughby Lane work: (919) 467-8000 x7783 ____________________________|Cary, NC 27513 home: (919) 469-9389
bart@reed.UUCP (Bart Massey) (08/08/88)
I'm amazed no one's mentioned this -- the Free Software Foundation's GNU C Compiler is a free complete C compiler in C -- unsurprisingly, it includes a complete ANSI C grammar, written in BISON, FSF's YACC-alike... If you wanna know how a fairly good modern C compiler works, you owe it to yourself to chase down a copy of this. Bart Massey UUCP: ..tektronix!reed!bart
henry@utzoo.uucp (Henry Spencer) (08/09/88)
In article <9965@reed.UUCP> bart@reed.UUCP (Bart Massey) writes: >... the Free Software Foundation's GNU C >Compiler is a free complete C compiler in C -- unsurprisingly, it includes a >complete ANSI C grammar, written in BISON, FSF's YACC-alike... >...chase down a copy of this. Remembering, of course, that it may be free but it is *not* public domain. Read the fine print before you plan on using it (as opposed to looking at it), especially for commercial purposes. -- Intel CPUs are not defective, | Henry Spencer at U of Toronto Zoology they just act that way. | uunet!attcan!utzoo!henry henry@zoo.toronto.edu