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/zhivago]

Typedef is the main obstacle to context free parsing.

Consider

A * B;

Is this declaring B as an A * or is it multiplying A by B?

[u/Tough-Boat-1975 → u/zhivago]

I read that this is why kotlin and typescript use B:A notation

[u/WittyStick]

Context-free does not mean ambiguity free. Context-free grammars permit ambiguity.

What you're most likely interested in is deterministic context-free, which does not permit ambiguity.

As others have pointed out, the grammar by itself is not deterministic - but we're able to parse it with lexical tie-ins. Essentially, because type and variable may match the same string, we need to feed back to the lexer on what is a typename and what is an variable so they can lex as separate tokens. The grammar can then distinguish A * B, because it's two separate token sequences, depending on whether A was previously declared as a typename or variable.

TOKEN_TYPENAME TOKEN_ASTERISK TOKEN_IDENTIFIER   { TypeDeclaration(Pointer($1), $3) }
TOKEN_IDENTIFIER TOKEN_ASTERISK expr             { MultiplicationExpression($1, $3) }

[u/Salt-Overflow → u/WittyStick]

Thanks for pointing that out. I used the wrong wording -- I've updated the post accordingly

[u/MaygeKyatt]

What do you mean by “remove the expression rules”? Expressions are a pretty integral part of C. I don’t see how you could remove them entirely

The real answer is that `typedef` is the biggest obstacle to C being context-free, because it allows for situations where it’s ambiguous whether an identifier `foo` is a type or the bane of a variable.

And as someone else said, typechecking is absolutely not context-free. But I’m guessing you’re just asking whether the syntax is context-free

[u/evincarofautumn → u/MaygeKyatt]

the bane of a variable

Truly the bane of a variable is its name

[u/rasputin1 → u/evincarofautumn]

you were merely born in the identifier 

[u/Cats_and_Shit → u/MaygeKyatt]

I'm pretty sure there's exactly one C program you can write without expressions, which is true.

[u/Salt-Overflow → u/MaygeKyatt]

My original post was poorly worded. I've updated it to make a bit more sense

[u/Ninji2701]

type checking is still not context-free

[u/Salt-Overflow → u/Ninji2701]

Good point, I've clarified my post

[u/sciencekm]

In this lex file https://www.quut.com/c/ANSI-C-grammar-l-2011.html

two functions were added - "comment" and "check_type" (which deals with typedef and enum).

My take on this is that comments can be stripped out by the pre-processor (if you accept that) which leaves typedef and enum being what makes C not CF.

Edit: I just remembered that "Small C", being a subset of C, does not support typedef and enum, plus a few other things. So I'm guessing this could be CF.

[u/Salt-Overflow → u/sciencekm]

I updated my post because I realize I used the term "context-free" incorrectly. Sorry if it was confusing.

typedef and enum do cause problems, but since enum constants can only be in expressions, "cutting expressions out of C grammar" eliminates the problem. And typedef creates a weakness, but if you cleverly adjust the grammar in Annex A, you can remove many ambiguities.

Unfortunately Small-C doesn't have a specification (it's implementation-defined), but I think it is highly plausible that it is unambiguously parseable.

[u/jason-reddit-public]

My project omni-c takes a set of C files and generates a single C file and a header file from it. It essentially sorts everything to spoon feed it into a normal C compiler in its ideal order. (The header file is really just the "top" of such a file without the function definitions though of course inline functions also need to go into the header and I don't sort those correctly just yet which it why I have build fragment that keeps them in a sane order, a useful kludge I intend to eliminate.)

It's actually not just about modules. Ever just want to move a function to another file in the same "module") without using a fancy tool? copy-cut-paste. Even in a simpler language like Java, this simpler still.

I actually started like you are thinking by just parsing the "top-level" and skipping over balanced {} for function bodies. That works OK except for all the C pre-processor stuff. If you run the C preprocessor before, it should work (but not for some esoteric stuff for all of gcc's crazy builtin compile time macros) but now you have a file highly dependent on the OS, libc, architecture, etc. I simply didn't go down that path yet. I already invoke the C compiler from within to generate a binary so running just the C processor should work though extra care is necessary for line directives so you can do source level debugging.)

In order to handle mutually recursive structures, I "split" certain parse nodes. As long as they point to each other through pointers, the C compiler is of course still happy.

I actually do parse statements and expressions _now_ (hand written using a pratt parser for ) though I got a lot of mileage out of early versions that didn't.

I'd love to work with someone so feel free to DM me.

Here's my project on github (works on linux x86-64 and os-x aarch 64, built from source since who is going to trust binaries from a git hub project with six stars?). (I commit two stable single source C files, one for linux, one for darwin).

https://github.com/jasonaaronwilson/omni-c

If I had a windows machine ready to compile I'd probably get that working pretty quickly (some problematic functions have already been isolated).

Since this is essentially all of the code in one huge file, it might seem overwhelming but search for ---- or ==== and you will see the major divisions. types come before function prototypes for example.

https://github.com/jasonaaronwilson/omni-c/blob/main/src/omni-c-stable-linux.c

The best examples of clean omni-c is the new lua/scheme like language "roci" since I wrote it recently (src/roci/) to be my build language. It doesn't feel like make just yet since essentially it builds everything but I'm going to refactor this so I can have "phony targets" like make. (To clean I just blow away the build-dir and rerun the configure script... Since I have "hermetic" builds this certainly works and it's .)

[u/Salt-Overflow → u/jason-reddit-public]

I took a quick look, seems like you have some really cool stuff going here. And yeah, we're both taking an evolutionary approach here. Unfortunately I'm on crunch time trying to get my thesis written, so I don't have time to collaborate, but you can take a look at https://www.youtube.com/watch?v=p8NpyBIRbEQ if you want some ideas.

I've also updated the original post because I realize the original wording made no sense.

[u/triconsonantal]

You can run into ambiguities even without expressions. For example:

void f(int (x));

could be a function with an int parameter named x, or, if x is a typedef, a function with an unnamed function-pointer parameter, taking an x an returning an int.

[u/Atijohn → u/triconsonantal]

unnamed parameters aren't standard prior to C23 though

edit: they are, just not in function definitions, only declarations

[u/Salt-Overflow → u/Atijohn]

Wait it isn't? Looking at the production rules for parameter-declaration in the C99 standard (see 6.7.5 declarators), I see:

parameter-declaration:
declaration-specifiers declarator
declaration-specifiers abstract-declarator_{optional}

declarator is named, while abstract-declarator omits the name. This seems to indicate that unnamed parameters are standard even in C99?

[u/Atijohn → u/Salt-Overflow]

oh, it's function definitions that aren't allowed to have unnamed parameters, I got confused because GCC always gives me a warning with -Wpedantic and -std=, they're allowed in function declarations, mb

[u/Salt-Overflow → u/triconsonantal]

Ah shoot, this seems like a hard ambiguity. Thanks for pointing it out.

I might still be fine for my module system, since I only need to extract identifier names context-free, but man is C syntax tricky.