I'm trying to build a simple compiler for a subset of the C language in C. To achieve this, I needed to figure out a way to represent the grammar symbols. Basically, each symbol can either be a "terminal" or a "non-terminal". Each "terminal" must be associated with a string that can be recognized by the lexer as a lexeme. My first (trivial) idea was to represent the symbols as follows:

enum SymbolType {
} typedef SymbolType;

struct Symbol {
    SymbolType type;
    char* content;
} typedef Symbol;

However, for symbols that are NONTERMINAL, the content field would be completely wasted, as these don't need to be associated with a string of characters. Space would be used inefficiently.

Another idea that I had was to have a single char* field, of which a NULL value would indicate that the symbol is NONTERMINAL while a non-NULL value would mean that the symbol is TERMINAL. However, I'm not sure if creating a whole struct to store a single field is efficient either, or if the aformentioned approach could result in some problems that I failed to anticipate.

struct Symbol {
    char* content;
} typedef Symbol;

I'm not sure if this could affect the choice of the optimal way to represent the grammar symbols, but I'm planning to implement the parsing step using a top-down LL(1) parser.

I'm thinking of representing the rules as the following, but that is also subject to improvement:

struct Rule {
  Symbol* pleft;
  Symbol** prights;
  int rights_count
} typedef Rule;

Here pleft is a pointer to the symbol at the left side of the rule and prights is an array of size rights_count that contains (in order) the pointers to the symbols at the right side of the rule. There is only one symbol at the left side of the rule because I'll only start with a context-free grammar, and then decide thereafter whether to scale things to also include parts of the C language that require having a context-sensitive grammar.

  • 3
    I wouldn't worry about the space efficiency, since a complete grammar for C is small compared to, say, a large compilation unit.
    – Erik Eidt
    Jan 27 at 16:52
  • "Space would be used inefficiently" - now that we have gigabytes instead of kilobytes of memory this is not as relevant as it used to be. Write clear clean code instead. Jan 27 at 17:01
  • 6
    @MehdiCharife Well, it is easier to make clean, well-written code faster, than making fast code clean and well-written. Especially if this is your first compiler. Jan 27 at 17:21
  • 1
    It is definitely quite easy to make these kinds of changes to a fully-working compiler. This is not a thing that you have to decide at the beginning.
    – user253751
    Jan 27 at 19:22
  • 1
    @user253751 I'm trying to model the symbols independently from the grammar rules. A rule will be presented by struct Rule which holds a pointer to the symbol at the left side of the rule and an array of pointers to the symbols at the right side of the rule. This can make things easier when deciding to scale things up and add new production rules to the grammar. Jan 27 at 19:40

1 Answer 1


You absolutely should not worry about this until your compiler is working. It's completely needless and . Do whatever is easiest, then worry about the tiny memory savings later, if you still want to.

However, if you did want to do this for some reason, a memory-efficient design would be:

  • Order the symbols so that all the terminals have the lowest IDs.
  • Store the number of terminal symbols.
  • Make an array, only that exact length, containing the strings for each symbol.

If symbol_id < N_TERMINALS then it's a terminal and terminal_strings[symbol_id] provides the string. If symbol_id >= N_TERMINALS then it's a non-terminal.

It seems like you don't need a struct for each symbol - only an ID number. Attempting to make everything into a struct is a symptom of OOP indoctrination :)

  • This. The “what is the simplest thing I can get away with?” question, is often more helpful than you should expect in software design. Feb 13 at 3:44

Your Answer

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

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