10 ms·
The context sensitivity of C’s grammar
- eliben 15y agoCool to see this posted here. Just for completeness: this article is part 2 of the one here: http://eli.thegreenplace.net/2007/11/24/the-context-sensitivity-of-cs-grammar/ http://eli.thegreenplace.net/2007/11/24/the-context-sensitiv..., so if the issue interests you, start with that one.
- yan 15y agoThanks for the great blog; always make sure to get to it first in my reader.
- jrockway 15y agoDoes the parser really need to know this information? XX yy; only means one thing: declare( type: XX, variable: yy). Making that work is the job of something else down the pipeline that knows about the concept of types and symbol tables. As an example, Emacs syntax-highlights both "YY xx" and "int xx" the same way.
- eliben 15y agoA complete parser has to be strict. Emacs's syntax-highlighting, as we all know, is very heuristic and approximate. While it does a good job for the common cases, it's easy to break it with more freakish examples. A real compiler can't allow that. To parse this correctly, the parser has to receive a "TYPE-NAME" token for XX and an "IDENTIFIER" token for yy. If the parser receives an IDENTIFIER token for XX, this will result in a parse error.
- boris 15y agoTo be more precise, "a context-free parser has to receive a TYPE-NAME token...". A hand-coded parser would be able to parse things just fine if both XX and yy were IDENTIFIERs. Or, to put it another way, you resort to uglyfying the lexer to overcome definiciencies in the parser.
- judofyr 15y agoYes, the parser needs to know about this information. Example: (A) * B This is either A multiplied by B, or type A casting the dereferenced value of B: http://en.wikipedia.org/wiki/The_lexer_hack http://en.wikipedia.org/wiki/The_lexer_hack
- jrockway 15y agoFair enough. Would the problem be fixed if the C standard said that x (without spaces) had to be dereferencing and that x y (with spaces) had to be multiplication?
- demallien 15y agoIt was as if a million C programmers cried out and were suddenly silenced. Significant whitespace is evil, at least in the context of C where it is not significant anywhere else.
- _delirium 15y agoYeah, if you could purely lexically distinguish dereferencing from multiplication, either because they used a different symbol, or had different mandatory whitespace rules, then there'd be no ambiguity, at least in this example. That's basically what C++ did by requiring the space in: Foo<Bar<Baz> > var; to make it easy to lexically distinguish the '>>' right-shift operator from the '> >' sequence of two successive template-parameter closing symbols. C++0x is changing that though, due to the unpopularity of making programmers accomodate what looks like a parser-implementation hack.
- roel_v 15y agoBut "XX XX;" (the example was given in the article) is valid, and the parser needs to know the difference. The article says that this code is "evil", but I disagree. There is a valid pattern that I use quite often (I described it in an article for ACCU a few years ago, too). It's an example from C++ but I think I could apply it to C as well. Consider (with a modification of the example I used in that article): struct PirateShip { struct Cannons { char* cannon1; char* cannon2; } Cannons; } Now you can use PirateShip s; printf("Name of the first cannon: %s\n", s.Cannons.cannon1); which is very readable and idiomatic (once you get used to it ;) ) More abstract, it provides an idiomatic way to group collections of objects/structs at the source code/syntactic level. (one could name the struct and the member differently, I realize; the benefit of using the same name is when you define constant members in the inner struct, that way you can reference constants and properties with the same name and you never have to think about which one to use.) (also again I use this from C++, there may be things that are different in C, but afaik this part is the same).
- eliben 15y agoI'm not sure how you use "XX XX" in that code sample. Do you refer to the "struct Foo {...} Foo;" idiom? That's quite different, though :)
- barrkel 15y agoThe parser needs to know about it iff you want your parser to disambiguate certain scenarios. An alternative approach is to handle the ambiguous scenarios generically in a specific parser construct (e.g. build a special AST node), and resolve it later after you've collected type information.
- acqq 15y agoAn advice to those who like OP first encounter these topics: try to gain the historical perspective, you'll understand everything much better. Find the sources of the original C compilers, marvel that they are probably smaller than the Yacc and Lex (at least that's how I remember them) and then understand that both Yacc and Lex were never needed for these C compilers. You learn about Yacc and Lex in the school more because of their "educational value" than because they are easiest tools to make a C compiler or parser. As the original authors wrote the compiler the result of not having the context free grammar was just having a few lines of the code more. Their goal was certainly not an academic "parser" purity. Parsing is one of quite uninteresting parts when you're making UNIX and C some 40 yeas ago.
- eliben 15y agoI agree completely about Lex & Yacc, and this is the conclusion I came to at the end of the article. Yacc (leaving Lex out for a moment, since it's a different story) is being taught for its interesting educational value, but once in the wild, you just find that most real-world compilers don't use it. Regarding historical perspective, unfortunately it isn't so easy to gain. I actually consulted a lot of comp.compiler discussions from the early 1990s, but most links in them point to various non-existent FTP sites :-/
- acqq 15y agoDo you a favor and search the net for the oldest preserved sources of C compilers and UNIX. Then take a look at them, especially how concise they are. I'd enjoy reading your post about that experience. :)
- eliben 15y agoSince you appear to be knowledgeable in these matters, perhaps you could point out to such a source :) FWIW I did mention 'tcc' in the article, the "tiny c compiler" with rather compact and clean source code, probably smaller than the code for Bison
- 15y ago
- wbhart 15y agoI've been using an LALR(1) parser generator by Paul Mann http://highperware.com/ http://highperware.com/ which gets around this context sensitivity problem. I've had to hack it a bit to handle scopes, but this wasn't a major problem. It generates an amazing lexer/parser, which can do something like a million lines of code a second. But he hasn't open sourced the parser generator nor ported it from Windows. I've been trying to convince him to do so, and he came oh so close recently. He's been trying to figure out how to make money from it if he Open Sources it. As it is, everyone seems to be totally ignoring it despite its sophistication compared with flex/bison.
- wglb 15y agoSo using yacc and lex to do C compilation is a newish idea. Using yacc makes the hard part harder and the easy part easier (dgc). What is missing from the discussion in a generally good article here is that it isn't so much a "hack to the lexer" but you put information in the symbol table (scope, type) and push out to yacc a symbol with token type attached (variable, typename, etc). As another commenter here says, C compilers weren't originally done with yacc or other parser generator, they were recursive descent.
- paulbmann 15y agoThe LRSTAR binaries are up now with sample projects at http://HighperWare.com http://HighperWare.com
- paulbmann 15y agoConsider this context sensitive C code: typedef unsigned int uint, uint * uintptr; Here is how to specify a sample grammar to handle the above statement with a new product called LRSTAR. Note, this grammar has no conflicts and is LALR(1). Here is the grammar: <identifier> => lookup () Declaration -> VarDecl1 /','... ';' -> typedef VarDecl2 /','... ';' VarDecl1 -> Type... <identifier> VarDecl2 -> Type... <identifier> => defterm(2,{typedef}) Type -> SimpleType... -> Type '*' SimpleType -> char -> int -> short -> unsigned -> {typedef} You can download LRSTAR at http://HighperWare.com http://HighperWare.com.