Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #106299
| From | BartC <bc@freeuk.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: C Compilers QoI |
| Date | 2017-03-16 23:19 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <oaf6dg$ag4$1@dont-email.me> (permalink) |
| References | <oa8pdp$nok$1@dont-email.me> <34beb369-0da0-4746-895b-28d276a5592d@googlegroups.com> |
On 16/03/2017 22:10, ed_davis2@yahoo.com wrote:
> On Tuesday, March 14, 2017 at 9:01:34 AM UTC-4, Bart wrote:
>> except that the 'a=b+c*d;' line was repeated a million times. (Also
>> those lines are in an include file, but I don't think that matters.)
>>
>> ------------------------------
>
> This is pretty interesting!
>
> I had to give it a test with my own toy micro/tiny C compiler,
> which compiles to stack Virtual Machine code.
>
> My compiler crashed!
>
> It built the parse tree (simple binary tree), but in processing
> the tree - doing a post order tree traversal - it ran out of
> stack space recursing on sequences:
OK, so you're using a recursive process even for linear sequences. You
say that you fixed that.
I get the same problem with input like this:
L1:
L2:
L3:
...
L1000000:
a=b+c*d;
But label statements I believe are defined recursively. (Actually, so is
a normal statement sequence probably. Labels however are unusual in
needing to be associated with a following statement.)
Several compilers also have trouble even with only 100K labels, or if
they don't have trouble, they take ages.
(I'm not going to bother fixing it as I can't get excited about needing
to compile huge numbers of successive labels. The same with block scopes
nested 100,000 levels deep. Conceivably, real code could consist of tens
of thousands of sequential statements, but labels and blocks nested that
deep is much less likely.)
> After that, it took 2.5 seconds to build the parse tree and
> generate very inefficient stack machine code.
A lot better than some of the big compilers!
> The parse tree itself took about 120 megs of memory.
>
> Based on this, I updated my "sequence" generating code to be a
> linear list, and updated the case above to be:
>
> case nd_Sequence:
> do {
> code_gen(x->left);
> x = x->right;
> } while (x != NULL);
> break;
>
> This happily runs with the default stack space, never recursing
> more than 5 or 6 times for the test in question. Thinking some
> more, I guess I really only need the binary tree for expressions.
>
> Questions: How did you handle the parse tree? Is it a combination
> binary tree and list? Something else?
I use a combination of tree and list. Not binary trees. A long sequence
of statements forms a list.
Well, actually my trees can branch up to three ways. Two ways might be
used for binary ops for example. But otherwise I don't use binary trees
for sorting or anything like that.
Example AST display for five lines of 'a=b+c*d;':
http://pastebin.com/HYzdP61C
The prefixes '1' and '2' indicate which of 3 branches, but each branch
can be a list so the '1' is repeated on each list item as it's part of
the same branch.
--
bartc
Back to comp.lang.c | Previous | Next — Previous in thread | Find similar | Unroll thread
C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 13:01 +0000
Re: C Compilers QoI mark.bluemel@gmail.com - 2017-03-14 06:16 -0700
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-14 06:42 -0700
Re: C Compilers QoI "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-03-14 06:56 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 15:58 +0000
Re: C Compilers QoI "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-03-14 09:22 -0700
Re: C Compilers QoI scott@slp53.sl.home (Scott Lurndal) - 2017-03-14 16:54 +0000
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-14 10:24 -0700
Re: C Compilers QoI scott@slp53.sl.home (Scott Lurndal) - 2017-03-14 17:58 +0000
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-14 14:12 -0700
Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-14 16:34 -0500
Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-14 17:36 -0500
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 23:06 +0000
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-14 16:20 -0700
Re: C Compilers QoI antispam@math.uni.wroc.pl - 2017-03-15 02:32 +0000
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-15 12:49 +0000
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-15 11:56 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-15 23:09 +0000
Re: C Compilers QoI scott@slp53.sl.home (Scott Lurndal) - 2017-03-16 18:17 +0000
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-16 11:47 -0700
Re: C Compilers QoI Ian Collins <ian-news@hotmail.com> - 2017-03-17 07:50 +1300
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-16 12:59 -0700
Re: C Compilers QoI David Brown <david.brown@hesbynett.no> - 2017-03-16 21:24 +0100
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-16 14:23 -0700
Re: C Compilers QoI Ian Collins <ian-news@hotmail.com> - 2017-03-17 11:30 +1300
Re: C Compilers QoI Ian Collins <ian-news@hotmail.com> - 2017-03-17 11:38 +1300
Re: C Compilers QoI Gareth Owen <gwowen@gmail.com> - 2017-03-17 05:07 +0000
Re: C Compilers QoI Ian Collins <ian-news@hotmail.com> - 2017-03-17 20:26 +1300
Re: C Compilers QoI Gareth Owen <gwowen@gmail.com> - 2017-03-17 07:59 +0000
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-16 16:14 -0700
Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-16 22:54 -0500
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-17 09:01 -0700
Re: C Compilers QoI Ian Collins <ian-news@hotmail.com> - 2017-03-26 14:16 +1300
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-26 14:19 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-26 22:43 +0100
Re: C Compilers QoI GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-03-27 01:28 +0200
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-26 22:07 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-27 11:28 +0100
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-27 07:38 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-27 16:23 +0100
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-27 08:55 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-27 17:01 +0100
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-27 10:03 -0700
Re: C Compilers QoI GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-03-27 17:58 +0200
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-27 03:54 -0700
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-27 08:46 -0700
Re: C Compilers QoI scott@slp53.sl.home (Scott Lurndal) - 2017-03-27 17:47 +0000
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-27 11:48 -0700
Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-27 15:37 -0500
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-27 14:46 -0700
Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-27 20:28 -0500
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-28 01:18 -0700
Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-28 18:24 -0500
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-29 07:40 -0700
Re: C Compilers QoI David Brown <david.brown@hesbynett.no> - 2017-03-29 17:05 +0200
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-29 11:07 -0700
Re: C Compilers QoI antispam@math.uni.wroc.pl - 2017-03-31 04:04 +0000
Re: C Compilers QoI bartc <bc@freeuk.com> - 2017-03-31 10:53 +0100
Re: C Compilers QoI Malcolm McLean <malcolm.mclean5@btinternet.com> - 2017-03-31 07:35 -0700
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-31 08:07 -0700
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-31 07:54 -0700
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-31 07:43 -0700
Re: C Compilers QoI Ian Collins <ian-news@hotmail.com> - 2017-03-17 11:21 +1300
Re: C Compilers QoI Ian Collins <ian-news@hotmail.com> - 2017-03-17 11:24 +1300
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-16 22:15 +0000
Re: C Compilers QoI scott@slp53.sl.home (Scott Lurndal) - 2017-03-17 12:31 +0000
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-16 15:24 -0700
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-16 16:03 -0700
Re: C Compilers QoI scott@slp53.sl.home (Scott Lurndal) - 2017-03-17 12:39 +0000
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-17 08:27 -0700
Re: C Compilers QoI antispam@math.uni.wroc.pl - 2017-03-16 01:35 +0000
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-16 02:18 +0000
Re: C Compilers QoI antispam@math.uni.wroc.pl - 2017-03-18 00:45 +0000
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-18 13:12 +0000
Re: C Compilers QoI antispam@math.uni.wroc.pl - 2017-03-18 20:31 +0000
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-18 17:31 -0700
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-16 09:22 -0700
Re: C Compilers QoI Nick Bowler <nbowler@draconx.ca> - 2017-03-24 16:13 +0000
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-24 12:32 -0700
Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-24 22:13 -0500
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-25 13:05 -0700
Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-27 15:44 -0500
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-27 14:51 -0700
Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-27 20:31 -0500
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 17:26 +0000
Re: C Compilers QoI Andrew Haley <andrew29@littlepinkcloud.invalid> - 2017-03-15 12:02 -0500
Re: C Compilers QoI David Brown <david.brown@hesbynett.no> - 2017-03-14 15:00 +0100
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-14 07:36 -0700
Re: C Compilers QoI David Brown <david.brown@hesbynett.no> - 2017-03-14 15:57 +0100
Re: C Compilers QoI Andrey Tarasevich <andreytarasevich@hotmail.com> - 2017-03-14 08:11 -0700
Re: C Compilers QoI BGB <cr88192@hotmail.com> - 2017-03-29 23:51 -0500
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 15:28 +0000
Re: C Compilers QoI David Brown <david.brown@hesbynett.no> - 2017-03-14 21:41 +0100
Re: C Compilers QoI Keith Thompson <kst-u@mib.org> - 2017-03-14 09:26 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 18:23 +0000
Re: C Compilers QoI Keith Thompson <kst-u@mib.org> - 2017-03-14 12:05 -0700
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-14 09:35 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 17:08 +0000
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-14 10:24 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 17:34 +0000
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-14 11:55 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 19:03 +0000
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 19:06 +0000
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-14 12:10 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 21:14 +0000
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-14 14:42 -0700
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-14 14:53 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 23:20 +0000
Re: C Compilers QoI antispam@math.uni.wroc.pl - 2017-03-15 02:43 +0000
Re: C Compilers QoI jacobnavia <jacob@jacob.remcomp.fr> - 2017-03-14 19:39 +0100
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 19:10 +0000
Re: C Compilers QoI antispam@math.uni.wroc.pl - 2017-03-14 19:29 +0000
Re: C Compilers QoI Noob <root@127.0.0.1> - 2017-03-15 09:27 +0100
Re: C Compilers QoI ed_davis2@yahoo.com - 2017-03-16 15:10 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-16 23:19 +0000
csiph-web