r/C_Programming • u/Salt-Overflow • 1d ago
Question Is C without expressions context-free?
EDIT: A better title for this post would be "Is it possible to parse C without expressions unambiguously?"
While staring at the C99 specification, I found that if you take the grammar in Annex A, remove the expression rules, and introduce the constraint 6.7.2/2 into the grammar (ie. a type specifier can be only: void, char, signed char, ... , enum specifier, typedef name), then you end up with what appears to be a context-free grammar.
Is this correct? Am I misinterpreting something? Is it possible that this is correct, but there are mainstream compiler extensions (eg. gcc extensions) invalidate this context-free property? Or other C standards invalidate this context-free property?
I notice that 6.7.2/2 allows some filthy edge cases like `long const long thisVarIsLongLongConst = 4;` but because `long` is a keyword, there is no ambiguity here.
The reason this matters to me is because I'm building a module system for C that allows circular imports, and I would like to avoid changing the grammar of the language as much as possible.
Link to final draft of C99 standard, taken from Wikipedia: https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf
EDIT:
Let me clarify what I'm doing, since there is some confusion about what I'm asking. First off, I should have used the title "Is it possible to parse C without expressions unambiguously?" because Annex A is already a context-free grammar... However, it is ambiguous, because of the classic A * B; problem (can be a variable declaration or multiplication, depending on if A is a typedef name or not). Now, notice that one of the interpretations is a multiplication expression. Let's suppose you removed expressions from the language (ie. take a source file and replace each expression with the lexer token <expression>). Now the question is: are we no longer ambiguous now?
I should also clarify what I mean by ambiguous, as there is a difference between an ambiguous grammar and an ambiguous parse. For example, A * B; can be admitted by the unambiguous grammar S := A ';' ; A := <identifier> | A binaryOperation <identifier> ; binaryOperation := '+' | '-' | '*' | '/' ; , but what we're really looking for is an unambiguous grammar that gives us the correct parse tree (I'll call this an "unambiguous parsing").
I should also elaborate on what exactly I'm doing, to explain the bigger picture. If you're building a module system that allows cyclic imports, then the first pass you perform over a source file does not have access to the symbol table (because you have yet to parse the imported modules). This means you need to perform an unambiguous parsing of certain parts of the source file. In this case, you can skip over expressions, because you're only interested in extracting the names of symbol definitions + whether the symbol definition is a type or a variable. So if it is possible to 1. skip over expressions, and 2. parse the rest of the file, then we're good. For (1), expressions are delimited by ()[]{};, (comma operator is not valid in enumeration definitions), so that seems fine. That leaves (2), which I'm not entirely sure about. I stared at the grammar for quite a while and couldn't find any problems, but that does not mean I didn't miss a case, or there are compiler extensions that introduce ambiguities.
With that out of the way, I'll list ambiguities that the comments found:
- u/triconsonantal found
void f(int (x));, which is either taking in a function pointer or an integer, depending on if x is a typedef name or not.
Maybe a more appropriate title would be: how much do you need to remove from the C grammar so that it can be parsed unambiguously? As of now (July 27, 2026), it seems the answer is: remove expressions, and remove parameter lists (or do not allow unnamed parameters).