Path: csiph.com!news.mixmin.net!aioe.org!.POSTED!not-for-mail From: "Rod Pemberton" Newsgroups: alt.os.development Subject: Re: C parser ramblings, language design, etc Date: Wed, 30 Sep 2015 20:32:33 -0400 Organization: Aioe.org NNTP Server Lines: 263 Message-ID: References: NNTP-Posting-Host: n4wpt9zq8xR26Ttf9mo2BA.user.speranza.aioe.org Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1; format=flowed; delsp=yes Content-Transfer-Encoding: 7bit X-Complaints-To: abuse@aioe.org User-Agent: Opera Mail/12.16 (Linux) X-Notice: Filtered by postfilter v. 0.8.2 Xref: csiph.com alt.os.development:8861 On Sun, 20 Sep 2015 18:48:58 -0400, Rod Pemberton wrote: > On Mon, 14 Sep 2015 17:29:16 -0400, James Harris wrote: >> else if symbol is RIGHT_BRACE >> parser is confused not knowing which LEFT_BRACE it pairs with > > You don't need to know which brace goes with which brace as > long as all braces are properly paired. An up/down counter > can keep track of scope level and provide a count of missing > braces. I should clarify on that. I thought there were five or so proven ways to generate branches and target branch labels from braces. In addition to walking or backtracking the AST, I thought the following were proven solutions: a) symbol lookup table b) integer LIFO (push/pop) stack c) an up/down counter for the scope level and some block counters for each scope level, either 15 (C89) or 127 (C99) d) an up/down counter with a resettable up counter My results are: a) fails. I think this is for the same reason as 'd)' fails, which is information loss, but it just might be the way I attempted to solve it ... b) works. c) works. d) fails. If 'd)' works, for the life of me, I can't seem to get it to do so right now ... I was attempting another method that used peak detection of counters on the braces, but it's flawed for more than a level or two of nesting. So, that's another fail. AIUI, all loops and conditionals in C can be rewritten into this form: /* pre-loop actions */ cond= ... ; /* entry value */ while(cond) { ... /* end-of-loop actions */ cond= ... ; /* repeat or exit condition */ } Obviously, multiple block if-then statements must be broken down into single blocks and for() and do-while() must be rewritten into while() to use this. E.g., cond=1 for a do-while() upon entry and then cond would be set appropriately at the end of the block. for() would be unrolled. if() would be broken into single blocks, with cond=0 at the end of block, etc. So, for each braced block, { ... } I wan't to produce a generic conditional code block from the braces, such as: bxxxx: jz fxxxx ... jmp bxxx: fxxxx: where 'xxxx' is a unique integer for that block, where 'f' represents a forward branch, and 'b' represents a backward branch, and 'fxxxx' and 'bxxxx' are the actual labels used once 'xxxx' is filled in, i.e., b0000 f0000 ... b0009 f0009 ... etc. So, there at least three succesful methods. Here are two down-n-dirty (no C niceties) C programs demonstrating using a integer LIFO stack 'b)' and up/down counter with level counters 'c)'. /* integer LIFO stack */ #include #define SIZE 1024 unsigned long stack[1024],sp; unsigned long up_ctr=0,branch=0,idx=0; #define TABSZ 2 void indent(int idx) { printf("%*c",idx*TABSZ,' '); } void filter(char *c) { /* filter out quotes, comments, character constants here */ } void push(unsigned long r) { /* add stack overflow check here */ stack[sp]=r; sp++; } void pop(unsigned long *r) { /* add stack underflow check here */ sp--; *r=stack[sp]; } void brclvl(char c) { switch(c) { case '{': branch=up_ctr; idx++; indent(idx); printf("b%08lx:\n",branch); indent(idx); printf("jz f%08lx\n",branch); push(branch); up_ctr++; break; case '}': pop(&branch); indent(idx); printf("jmp b%08lx\n",branch); indent(idx); printf("f%08lx:\n",branch); idx--; break; } } int main(void) { char c; while(1) { c=getchar(); filter(&c); brclvl(c); if(feof(stdin)) break; } return(0); } /* end */ /* up/down counter w/level counters */ #include /* C89 15 nesting levels */ /* C99 127 nesting levels */ #if 1 #define MAX 15 #endif #if 0 #define MAX 127 #endif unsigned long idx=0; unsigned short nst[MAX]; unsigned short up_ctr=0,branch=0; #define TABSZ 2 void indent(int idx) { printf("%*c",idx*TABSZ,' '); } void filter(char *c) { /* filter out quotes, comments, character constants here */ } void brclvl(char c) { switch(c) { case '{': branch=nst[up_ctr]; idx++; indent(idx); printf("b%04hx%04hx:\n",up_ctr,branch); indent(idx); printf("jz f%04hx%04hx\n",up_ctr,branch); up_ctr++; break; case '}': up_ctr--; branch=nst[up_ctr]; nst[up_ctr]++; indent(idx); printf("jmp b%04hx%04hx\n",up_ctr,branch); indent(idx); printf("f%04hx%04hx:\n",up_ctr,branch); idx--; break; } } int main(void) { char c; /* memset */ for(idx=0;idx