3 ms·

Although the explanation of what you mean by "context-free grammars" is clear, it seems to me that you should be using "unambiguous grammars" instead. An ambigu

by loicd 6y ago

Although the explanation of what you mean by "context-free grammars" is clear, it seems to me that you should be using "unambiguous grammars" instead. An ambiguous context-free grammar is not going to facilitate the job of an IDE. I also think you are mistaken about the C++ grammar not being context-free. The problem is that it is ambiguous. I could be wrong here since I have not kept up with the C++ standards. So can you provide an example of C++ grammar productions you think are not context-free?

WalterBright 6y ago
The ones where the `template` keyword had to be added to make the template function bodies parse-able.
teleforce 6y ago
Not OP but there were discussions last week regarding this matter in HN [1]. According to the original article C++ is neither context-free nor context-sensitive, it is actually undecidable [2]. [1] https://news.ycombinator.com/item?id=23008599 https://news.ycombinator.com/item?id=23008599 [2]https://medium.com/@mujjingun_23509/full-proof-that-c-grammar-is-undecidable-34e22dd8b664 https://medium.com/@mujjingun_23509/full-proof-that-c-gramma...
- loicd 6y ago
  Thank you for the links, but I am unconvinced. Your medium link claims that to decide between a function and a variable declaration in the given program, the compiler has to solve an instance of the Post Correspondence Problem (which is undecidable). However, this does not mean that the grammar is not context-free! Context-free languages are closed under union [0] so a context-free grammar (CFG) is perfectly happy with an ambiguity like 'a variable declaration or a function declaration'. Also, you can use an ambiguous CFG to parse a language: when the parser needs to choose between two productions, you cheat a bit and look at some external context for help. The grammar being used is still context-free though, even though the terminology becomes confusing. For instance, the ISO C99 standard provides a grammar that is context-free but ambiguous. One of the conflicts involves the `typedef` keyword: typedef-name: identifier primary-expression: identifier One way to solve the ambiguity is to look at the symbol table to determine whether the underlying identifier has been declared as a `typedef` previously. IMO, Walter Bright should talk about "unambiguous grammar" instead of "context-free grammar" when he is criticizing the above situation, because it seems to me to be the proper terminology. As for C++, I have never implemented a C++ front-end (and I hope I'll never have to). However, it looks like the C++ standard specifies an ambiguous context-free grammar, whose ambiguities must be resolved outside the parser. That solving the ambiguities may require solving instances of the Post Correspondence Problem does not change the fact that the grammar is context-free if it is. On the other hand, I fully expect lots of hidden horrors in that standard, hence my question. [0] https://en.wikipedia.org/wiki/Context-free_grammar#Closure_properties https://en.wikipedia.org/wiki/Context-free_grammar#Closure_p...

by loicd 6y ago

WalterBright 6y ago

The ones where the `template` keyword had to be added to make the template function bodies parse-able.

teleforce 6y ago

Not OP but there were discussions last week regarding this matter in HN [1]. According to the original article C++ is neither context-free nor context-sensitive, it is actually undecidable [2]. [1] https://news.ycombinator.com/item?id=23008599 https://news.ycombinator.com/item?id=23008599 [2]https://medium.com/@mujjingun_23509/full-proof-that-c-grammar-is-undecidable-34e22dd8b664 https://medium.com/@mujjingun_23509/full-proof-that-c-gramma...

loicd 6y ago
Thank you for the links, but I am unconvinced. Your medium link claims that to decide between a function and a variable declaration in the given program, the compiler has to solve an instance of the Post Correspondence Problem (which is undecidable). However, this does not mean that the grammar is not context-free! Context-free languages are closed under union [0] so a context-free grammar (CFG) is perfectly happy with an ambiguity like 'a variable declaration or a function declaration'. Also, you can use an ambiguous CFG to parse a language: when the parser needs to choose between two productions, you cheat a bit and look at some external context for help. The grammar being used is still context-free though, even though the terminology becomes confusing. For instance, the ISO C99 standard provides a grammar that is context-free but ambiguous. One of the conflicts involves the `typedef` keyword: typedef-name: identifier primary-expression: identifier One way to solve the ambiguity is to look at the symbol table to determine whether the underlying identifier has been declared as a `typedef` previously. IMO, Walter Bright should talk about "unambiguous grammar" instead of "context-free grammar" when he is criticizing the above situation, because it seems to me to be the proper terminology. As for C++, I have never implemented a C++ front-end (and I hope I'll never have to). However, it looks like the C++ standard specifies an ambiguous context-free grammar, whose ambiguities must be resolved outside the parser. That solving the ambiguities may require solving instances of the Post Correspondence Problem does not change the fact that the grammar is context-free if it is. On the other hand, I fully expect lots of hidden horrors in that standard, hence my question. [0] https://en.wikipedia.org/wiki/Context-free_grammar#Closure_properties https://en.wikipedia.org/wiki/Context-free_grammar#Closure_p...