I want to write a regular grammar that follows the C language. I almost wrote the grammar, but was not able to resolve how to define a variable.

Def: A variable can be any combination of characters, but it should not be an existing keyword.

I tried writing something like this but not sure how to write it:

<Var> -> {a-z}+ (!b<Kew1>|<Kew2>|<Kew3>|<Kew4>)

Here <Kew1>.. <Kew4> are already defined keywords like int, for, while, read, ...

  • $\begingroup$ This is usually done in a lexical pass. $\endgroup$
    – user16034
    Nov 29, 2022 at 15:57

1 Answer 1


Actual compilers cheat here, instead of doing a full per character grammar they instead do a per token grammar.

This means that there is a tokenizer which will preparse the character stream with a regular language parser and emit a stream of tokens. These tokens are then the whitespace, operators, keywords, identifiers, etc.. This has the guarantee that a Identifier token is never going to be a keyword.

<Var> -> Identifier

If you really want to have the per character grammar you will need to implement the DFA for parsing the keywords as a grammar:

<Var> -> (all letters that aren't the start of a keyword) {a-z}*
<Var> -> i ({a-mo-z} {a-z}*)?
<Var> -> in ({a-su-z} {a-z}*)?
<KeyWordINT> -> int

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.