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: Sun, 13 Sep 2015 06:27:56 -0400 Organization: Aioe.org NNTP Server Lines: 205 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:8775 On Sat, 12 Sep 2015 08:49:21 -0400, James Harris wrote: > "Rod Pemberton" wrote in message > news:op.x4tmp0ssyfako5@localhost... >> base types comprising multiple >> words, e.g., "long long", > > Not too hard to handle, I would have thought. That depends on the parser design. Most base types are a single word with some qualifiers etc. But, both "long" and "long long" are base types. "longlong" is not recognized, i.e., requiring whitespace in-between, without regard for the length of or type of whitespace. You can end up with newlines in-between. So, "long long" is fine for a "maximal munch" algorithm, but not necessarily other parsers. >> implicit int's, > > I am not sure about how hard this would be to handle. It may be similar > to your long long case: just remember what's already been declared and > react accordingly. When typedef's were introduced, they created a conflict in the grammar. The result was that typedef's were obsoleted from C. It's possible that a non-grammar based parser may not have any issues. > Isn't C's rule that declaration mimics use much more of a problem for > parsing declarations? You don't necessarily know the type when you see > the identifier and the type can be split between typedef and where the > typedef is used. > > For example, > > typedef int T[4]; > > T a[5]; > > The declaration combines the [4] and the [5] together. > >> no keyword for typedef usage, > > My guess is that the compiler has to see the typedef first and, > effectively, adds the typedef name to its list of type-declaring > keywords. So after > > typedef T > > it then regards "T" as it would "int" so when it sees the T in something > like > > static T x > > it knows that T is a type name. Not too hard to parse. See reply to Alexei. Also, it requires symbol or lookup tables. For a lex and yacc style parser, this creates problems because the lexer must communicate with the parser, which they aren't designed to do. >> conflict with implicit int's and typedef's, ... etc all >> complicate very simple C parsers. >> >> E.g., since braces are optional in C, there isn't much useful >> information for parsing, from statements like this: >> >> do while(x--); while(x--); > > That's a good one. I had to stare at it for a while to work it > out so I have to agree that it's not easy for a human to parse. :-) Yeah, I had to look at it a few times even though I knew how I got to it and what the correct interpretation was. If I saw that in real code, I would pause for a moment. E.g., the do and first while makes one think of an infinite for or while loop: for(;;); while(1); do while(1); /* NOT a do-while infinite loop, incomplete */ do ; while(1); /* infinite loop, complete */ Is a space required before the semicolon after 'do' in the last example? If not, then ... do; while(1); >> That's confusing for a human and a simple parser. It could be >> recognized by both as either of these: >> >> do { while(x--); } while(x--); >> do {} while (x--); while(x--); >> >> Which 'while' goes with the 'do'? Only the first one is correct, >> but how do you determine that from the braceless syntax above? >> You get a 'while' prior to the 'while' you need. > > This should be easy for a compiler, IMO, as long as the compiler is > properly written. I say that because a compiler will work forward a > symbol at a time. Yes, 'long' then forward to another symbol 'long' ... Where is the "long long"? ;-) I.e., the two 'longs' must be combined in the AST, perhaps? This would've been easier to parse with one keyword. > After > > do > > the compiler will expect a statement. Note, a statement, not a {compound > statement}. Only *after* the statement will it expect a while clause. > What the compiler should look for, then, is > > DO statement WHILE '(' expression ')' ';' > > (That is from the link I will place at the end.) > > As long as it sees a recognisable *statement* it will accept it, even if > that statement is a while loop. Easy. That works for grammar based parsers. That make not work for others which might detect a 'while' too early, without an easy way to track scope level, such as braces for a compound statement. They would need a method to track and pair do's and while's correctly. Solutions like counters and flags might not work, i.e., may need stack or state-machine. >> and with exceptionally easy parsing. That's why >> my language > > Your own language is of interest. AFAIK this is the first time you have > written any specifics about it. I've mentioned the techniques previously on c.l.m. I also recall posting an assembly example that no one liked, probably a.l.a. It was RPN assembly plus character directed parsing. I thought I posted a sample of the higher-level language a while back, somewhere. > This may have been more appropriate for > comp.lang.misc, though, and even although some people read both groups > you may get some further comments and interest there. It's still ultra-primitive: if-else, loop, characters, strings, byte integer, larger integer, Forth like functionality to access memory. The interpreter version, instead of the compiled version, looks more likely to be useful, at this point. >> uses space delimited parsing, like Forth, with >> character directed parsing. I.e., a character in front of >> each keyword, operator, etc in the language, tells the parser >> what is coming next. > > Are there enough symbols in ASCII to express all the different > syntactic elements that you want to distinguish...? That's an issue, but I haven't used too many so far. I use this technique for a number of related projects. The high-level language only uses fifteen. The interpreter uses the same fifteen. The general x86 assembler uses thirteen. It emits hex, not binary. The hex to binary app uses seventeen. Another assembler only for the high-level language uses two. It's a minimal assembler used specifically during development with the high-level language until the general x86 assembler becomes more complete ... or not. > If you use too many won't the code look ugly? Yes, that's an issue ... I changed a few around already. They need to be both easily remembered and not too awkward to view. I tried to use ones familiar to me from other languages, where possible. If the language set becomes too large, then this will become a problem, i.e., using a wrong char. Obviously, this would be less noticeable for intermediate stages of compiling, i.e., unseen assembly or for code backends or even for CLIs with a small command set. >> I also did some work on my larger C parser project. > > It sounds as though you are making progress on it. There is a useful > grammar in > > [link] > > If you closely follow something like that it should make your life > a lot easier. There won't be any problem with where labels can go, > what statements can appear where, when braces are needed etc. I have that grammar, and a version I updated. This doesn't follow a grammar. It's more of a state-machine, based upon a few switch() statements and numerous flags, perhaps more like two actually. Rod Pemberton -- Just how many texting and calendar apps does humanity need?