3

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

10

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.

  • Thanks a lot for assuring me that global variables in this case would not be wrong, since everyone almost always recommends against global variables. By the way, instead of putting them in a class, I can put them in an unnamed namespace. It would be the same, right? – Arnil Sep 3 at 3:53
  • 2
    @Arnil: well, I am not really recommding globals here, actually I am recommending to create a class. Putting the parser's state into class members allows you to have more than one instance of the parser in parallel, and it may help to keep the program evolvable when when you add more things than just the parser. – Doc Brown Sep 3 at 5:37
  • That is a really nice idea, I'll just go with it. Thanks a lot, I have accepted your answer. I'll also edit my question to contain the conclusion I've come to and why so people with this dilemma in the future can easily choose – Arnil Sep 3 at 5:50
  • 2
    For reference, here's Clang's C-family recursive descent parser, which is using exactly this way of doing things: github.com/llvm/llvm-project/blob/master/clang/include/clang/… – Sebastian Redl Sep 3 at 6:55
1

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.

  • 3
    Since OP is using C++ all the global variables and functions could be stuffed into a class... – 1201ProgramAlarm Sep 2 at 18:34
  • I am pretty sure that in a recursive decent parser trying to pass things like the token sequence from one function to another won't necesarily improve the readability and maintainability of the code. – Doc Brown Sep 2 at 18:46
  • 1
    @DocBrown - my experience says otherwise. It also makes each production super easy to unit test. – Telastyn Sep 2 at 19:39
  • I appreciate you taking time to answer, it gave me a lot of insight. But I think I'd just go with global variables for now, since extra parameters and returning a value might make the code look unnecessarily complex, like others pointed out – Arnil Sep 3 at 3:49
1

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;
}
  • But would passing the lexer as a parameter increase the chance of a stack overflow? I suppose that probably wouldn't be the case since it's being passed by a reference, but just to be clear – Arnil Sep 3 at 5:12
  • @Arnil: stack usage is most probably not the problem here. But when you do not have just 3 parser methods like in this (over-)simplistic example, but 30 (which is still few for a real language), all getting the same lex object as a parameter and passing it around, and maybe 50 other methods, which don't belong to the parser, then it makes sense to put the 30 parser methods into one class and make the "lex" object a member of that class. – Doc Brown Sep 3 at 5:42
  • @JerryCoffin: sure, one can "emulate" objects in C-like C++ by creating a data structure together with operations which get a reference to that data structure as parameter. Or one can directly use the "class" syntax of C++, which makes this more smooth and does not require the programmer to pass the parameter explicitly to each function, because the compiler generates the "this" parameter implicitly. I personally prefer to use the second approach, I think that is a good "use case" for classes. – Doc Brown Sep 3 at 13:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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