4 ms·

Can you give me an example grammar to help visualize your statement? I can probably make a note or clarification. I think one other point I forgot to mention

Can you give me an example grammar to help visualize your statement? I can probably make a note or clarification. I think one other point I forgot to mention was that the production rule for the # directives would have to look something like include-directive: beginning-of-file # INCLUDE ... newline-from-previous-line # INCLUDE ... Since 'beginning-of-file' isn't really something you can reduce to a token I justified that it would be context sensitive.

xigency 9y ago
The best explanation is that context free languages are a superset of regular languages, and it's totally possible to write a regular expression without any extensions for that case: (^|\n)#\s*INCLUDE.
kpxxx 9y ago
> Since 'beginning-of-file' isn't really something you can reduce to a token... Of course you can, generate a token immediately upon opening a file. Nothing special about b-o-f or b-o-l. Similar to EOF.
chubot 9y ago
FWIW, I haven't thought too much about the case of the preprocessor, but this series of blog posts might help: http://trevorjim.com/how-to-prove-that-a-programming-language-is-context-free/ http://trevorjim.com/how-to-prove-that-a-programming-languag... My initial thoughts are that the property of being context-free only refers to a parser, not to the lexer. A lexer can be line-oriented, as mentioned. The blog post mentions the lexer issue. The definition of a context-free language is fuzzy because you could have an infinitely powerful lexer, but he gives a precise definition.
- klodolph 9y ago
  In the strictest sense, "context-free" applies to either a grammar or a language. A language is context-free if there exists a context-free grammar for it, but there might be several grammars for the same language. 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.
  - chubot 9y ago
    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/ http://trevorjim.com/python-is-not-context-free/ Also Haskell: http://trevorjim.com/haskell-is-not-context-free/ 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 http://www.oilshell.org/blog/2016/10/20.html (see the end of this post for links about C++, Perl, Make)

xigency 9y ago

The best explanation is that context free languages are a superset of regular languages, and it's totally possible to write a regular expression without any extensions for that case: (^|\n)#\s*INCLUDE.

kpxxx 9y ago

> Since 'beginning-of-file' isn't really something you can reduce to a token... Of course you can, generate a token immediately upon opening a file. Nothing special about b-o-f or b-o-l. Similar to EOF.

chubot 9y ago

FWIW, I haven't thought too much about the case of the preprocessor, but this series of blog posts might help: http://trevorjim.com/how-to-prove-that-a-programming-language-is-context-free/ http://trevorjim.com/how-to-prove-that-a-programming-languag... My initial thoughts are that the property of being context-free only refers to a parser, not to the lexer. A lexer can be line-oriented, as mentioned. The blog post mentions the lexer issue. The definition of a context-free language is fuzzy because you could have an infinitely powerful lexer, but he gives a precise definition.

klodolph 9y ago
In the strictest sense, "context-free" applies to either a grammar or a language. A language is context-free if there exists a context-free grammar for it, but there might be several grammars for the same language. 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.
- chubot 9y ago
  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/ http://trevorjim.com/python-is-not-context-free/ Also Haskell: http://trevorjim.com/haskell-is-not-context-free/ 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 http://www.oilshell.org/blog/2016/10/20.html (see the end of this post for links about C++, Perl, Make)