Re:Scandalous Weird Old Things About The C Preprocessor (2015)
by chubot on Wednesday May 31, 2017 @05:33AM
(#14451278)
I don't think most languages in widespread use have lexers that are regular. Here the same author gives the example of Python's indentation requiring a stack: http://trevorjim.com/python-is-not-context-free/
Also Haskell: http://trevorjim.com/haskell-is-not-context-free/
I'm pretty sure in JavaScript that the /s+/ regex syntax can't be recognized with a regular language. Perl is of course insane -- it's not even statically parseable [1]. Shell isn't context-free.
The theme of this set of posts is that most languages used in practice aren't expressible with CFGs, and I agree. I didn't prove it but he shows how you would prove it.
[1] http://www.oilshell.org/blog/2016/10/20.html (see the end of this post for links about C++, Perl, Make)
The lexical syntax is usually a "regular language" or quite close to one, this includes C. All regular languages are also context-free, the set of regular languages is a strict subset of the context-free languages. Regular languages can be parsed using regular expressions.
And again, there's nothing wrong with being line-oriented. That's not "more powerful" in any sense of the term. Recognizing newlines, SOF, EOF, etc. are really simple things (in the language hierarchy sense) that you can do in regular expressions without using any extensions that make them non-regular (like backreferences), therefore they can be converted to a context-free grammar.
Commonly, a programming language will have regular expressions for its lexer and a context-free grammar for its parser. Since the lexer is technically also context-free, it's possible to combine the lexer and parser into a single stage, but this is a bad idea for various software engineering reasons.
Some older languages have context-free parsers, like C, whose grammar is not context-free (that's not the same as "context-sensitive" which is a particular technical term). One major reason C's grammar is not context-free because it has to distinguish between typedefs and other identifiers.
Of course, a language as a whole is almost never context-free, but we usually use "context-free" to mean that the parser and lexer are context-free.