Better way to represent grammar symbols in C

Question

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 {
    TERMINAL,
    NONTERMINAL
} 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.

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