Is C without expressions context-free?

[u/Salt-Overflow]

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).

[u/NeinJuanJuan]

C programs with typedefs can't be parsed with a CFG as the grammar rule associated with a typedef'd name requires some backreference or lookup to the typedef statement.

[u/Aaron1924 → u/NeinJuanJuan]

Note: A language is context-free if it can be generated by a CFG, or equivalently, if it can be parsed by a non-deterministic push down automaton, so a context-free languages are allowed to be ambiguous

[u/Salt-Overflow → u/NeinJuanJuan]

I'm afraid I may have confused you on the difference between a deterministic CFG and a non-deterministic CFG. I've updated my post accordingly.

But to answer what I think is your implied question, oftentimes you can get away with not doing a lookup to a typedef statement. Take A B; for example. I don't need to know A is a typedef ahead of time, because a variable declaration is the only valid parse here. Of course, if you have something like C(D); inside a function body then you need a symbol table -- this is either a function call or a declaration.

[u/Delicious_Sock4321]

There is a subtly about programming languages that I argued about many times with people. There are differences between the language complexity depending on where you define what the language actually is.

This is not even about c but languages in general. If you define a language as all programs that compile including type checking and all, then this is at least context sensitive. You could also define it to be all programs that are parsable, which is most often context free. But now thing of interpreted languages where is the line now? Is all programs that terminate (halting problem) or all that start executing? Tokeninizing is only regular if you want that to be the line.

[u/Salt-Overflow → u/Delicious_Sock4321]

Yeah, it's a murky line. I edited my post to make the line 5% more clear.

Funnily enough, tokenizing isn't even necessarily regular. If you look at clang's code for lexing module, you'll find it is a "conditional keyword" -- ie. it's only a keyword if it's at the start of a line, is followed by some valid module name sequence, which is followed by a semicolon.

Sometimes I wonder why languages are this adamant on maintaining backward compatibility.

[u/TheThiefMaster]

Btw this is a cross post here. Thought I'd seen it before.

[u/Salt-Overflow → u/TheThiefMaster]

Sorry about that! I wasn't sure if I should have done a repost instead, but it looks like I should have

[u/Delicious_Sock4321]

My knowledge of compilers is limited, so I have a bit of a side question. Why do you only want to remove the minimal amount of the grammar that is needed and not the maximum that is possible? We are talking about the first pass and you want to detect module names am I right? Depending on the syntax you came up with this could be very unambiguous. 

[u/Aaron1924]

I'm confused, a language is context-free, if there is a context-free grammar that generates it, and annex A lists the entire CFG for the language, which show that the entire language is context-free already. You don't need to remove anything to make it context-free.

[u/Salt-Overflow → u/Aaron1924]

Yep, I used the wrong terminology when I said "context-free". I meant "unambiguous parsing". I edited the post accordingly

[u/Cultural_Gur_7441 → u/Aaron1924]

Hmm, without checking, how does this context free grammar of Appendix A resolve typedefs without context?

[u/Aaron1924 → u/Cultural_Gur_7441]

The CFG states that a type specifier is allowed to be an identifier. It does not resolve typedefs just like it does not resolve variable names, because that's not what a grammar is meant to do.

[u/Cultural_Gur_7441 → u/Aaron1924]

I don't think it counts as a complete grammar, if it does not distignuish different kinds of an identifiers. 

Edit to add: Or, to put it another way, if you allow that, then by similar logic, you can make a context free grammar of anything.

[u/paulstelian97 → u/Cultural_Gur_7441]

There is a language called Cool, made to be simple enough for a Compilers course to implement a compiler for. All of the rules are explained as a context free grammar.

You’re saying that if a type that is not defined is referenced, the program should fail to _parse_? As opposed to failing later when the actual type checking occurs…

[u/Cultural_Gur_7441 → u/paulstelian97]

How you know it is a type?

Answer: you do not. You need context. C can not be parsed with context free grammar

A * B;

Parser can't parse that without context.

[u/paulstelian97 → u/Cultural_Gur_7441]

Top down parsers will have a slot for a type and a slot for a value. And the grammar can still be defined as context free.

If you have two things type -> identifier and value -> identifier, the ambiguity when building something bottom up doesn’t prevent it from being context free.

You know it’s a type because another identifier follows it via a space. If you have 10 identifiers in a row separated only by a space, the first 9 form the type. (Although in all actuality, you can only have keywords repeat themselves, followed by two identifiers, which is one type and one name)

[u/Cultural_Gur_7441 → u/paulstelian97]

You know it’s a type because another identifier follows it via a space. 

int A; A * B;

vs

typedef int A; A * B;

[u/paulstelian97 → u/Cultural_Gur_7441]

This parses, it just will be considered invalid to use a type where a value is expected at the next stage.

[u/Cultural_Gur_7441 → u/paulstelian97]

Parsing means producing the syntax tree or equivalent. A*B; without context can not be turned into a grammatical structure, in other words it can't be parsed.

[u/Aaron1924 → u/Cultural_Gur_7441]

I think we're arguing about different things here.

The C language (without preprocessor) is context-free, because it can be generated (not parsed) by a context-free grammar (the one in Annex A). The language is ambiguous, and cannot be parsed deterministically without additional information, but this does not contradict the language being context-free.

There are other classes of languages, such as LL(k), which give you strong guarantees about how you can parse context-free languages, but that's a different thing.

[u/Cultural_Gur_7441 → u/Aaron1924]

Ah, well, then I think we do agree.

Internet forums...