C++ Recursive Descent Parser: Global Variable Dilemma

Question

I'll come straight to the point. I'm trying to create a Recursive Descent Parser in C++ for a hobby project which involves creating my own minimalist programming language.

One thing that puzzles me, though, is a dilemma about global variables. Clearly recursive descent requires me to implement multiple functions for each grammar patterns, which recursively parse the entire code. However, in about all examples of the parser I saw on the internet, none of the functions take any parameters and don't even return anything.

That would, normally, indicate the need of using global variables. But I'm rather worried about using them, as it is generally considered a bad idea to use global variables.

So, all I wish to know is:

Would using global variables in this case be fine? Or is there a better alternative?

Considering the C implementation of a Recursive Descent Parser in Wikipedia contains a global variable to store the current token as well, should I go with that method?

Though I must also inform you the tokenstream class I implemented allows LL(k) look-ahead, so storing just the current token in a global variable might not be enough.

Sorry if this question was already asked before, but I'm in a serious dilemma and thus seriously require your help.

Thanks in advance.

My conclusion: I realized that there's multiple solutions to this problem, as described in the answers below. I heard both sides of the argument and came to the conclusion that making a Parser class would be the best option because that way not only will it be organized but I can also run multiple instances of the Parser at the same time.

Another option would be to pass the tokenstream or the current token as a parameter to the grammar functions and return a value from the functions as well, but I didn't choose that as it might make the code more complicated.

Just simply using global variables inside an unnamed namespace (for internal linking) would also work but the first two methods are much more organized.

This is what I understood from the argument and I explained my choice so that anyone who views this in the future can be helped.

I hope I was of help.

Thanks to everyone again

Answer 1

The group of methods which belong to one parser are tightly coupled because of the nature of the problem. The parser has some state to manage which is shared between all those functions. So putting that state into a variable outside the local scope of those functions makes perfect sense. Passing the state from one function to another would just result in two dozen or more functions with the same first parameter "context" or "parsing_state" or something like this, which won't bring any advantages over globals.

However, to make this clear - I don't recommend to make this "really" a global variable in C++. As mentioned in a comment by @1201ProgramAlarm, it makes sense to encapsulate the whole parser in a class in C++, and design the state as one or more member variables of that class. So those variables are only "global" within the context of the parser, and not global for the whole program.

Answer 2

Would using global variables in this case be fine?

Sure. It's a hobby project, meaning maintainability isn't a super high priority. Your examples use them, so if you also use them the examples will be easier to follow.

Or is there a better alternative?

That said, you are totally right that global variables are to be avoided and will cause you all sorts of problems if you want to deviate from the examples much. A better alternative would be to pass the string (or token sequence) you're looking to parse into each function, along with a context if needs be.

In an ideal world you'd just return some sort of syntax tree that represents the parsed input. But some languages will require you to mutate the context or environment as you parse it. And all languages need to deal with input that won't parse correctly.

I would generally encourage you to avoid the globals, but if you're looking to learn programming language design then it might be prudent to just follow the examples. That will let you get your language implemented the fastest so you can focus on the task at hand.

Answer 3

I don't see much (if any) reason to use any global variables. The parser functions rarely pass many parameters, because there's not normally any real dependency between them (i.e., not much you'd need to pass as a parameter from one to another).

At least as typically implemented, the only dependency on the outside world is in the lexer, where it needs to read input from somewhere. Everything else just uses the lexer to read tokens when needed. I'd pass the source as a parameter to (for example) a constructor for the lexer object. Here's an example that's simplistic, but works to at least a minimal degree:

#include <iostream>
#include <string>
#include <cctype>

class lex {
    std::istream &is;
public:
    lex(std::istream &is) : is(is) {}

    char token() { 
        char ch;
        is >> ch;
        return ch;
    }

    template <class T>
    lex &operator>>(T &t) { is >> t; return *this; }

    void unget() { is.unget(); }
};

int expression(lex &);

int factor(lex &L) { 
    int val = 0;
    char ch = L.token();
    if (ch == '(') {
        val = expression(L);
        ch = L.token();
        if (ch != ')') {
            std::string error = std::string("Expected ')', got: ") + ch;
            throw std::runtime_error(error.c_str());
        }
    }
    else if (isdigit(ch)) {
        L.unget();
        L >> val;
    }
    else throw std::runtime_error("Unexpected character");
    return val;
}

int term(lex &L) { 
    int ch;
    int val = factor(L);
    ch = L.token();
    if (ch == '*' || ch == '/') {
        int b = term(L);
        if (ch == '*')
            val *= b;
        else
            val /= b;
    }
    else L.unget();
    return val;
}

int expression(lex &L) {
    int val = term(L);
    char ch = L.token();
    if (ch == '-' || ch=='+') {
        int b = expression(L);
        if (ch == '+')
            val += b;
        else
            val -= b;
    }
    else L.unget();
    return val;
}

int main(int argc, char **argv) {
    lex L(std::cin);
    try {
        std::cout << expression(L);
    }
    catch(std::exception &e) {
        std::cerr << e.what();
    }
    return 0;
}