Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

So I have a program whose purpose is to take text files and parse them into a binary format that an embedded system understands. However, the text format I've inherited that I need to parse is sufficiently complex enough that after refactoring the main parse routine I'm left with a class with more than 50 methods that almost all look something like parseChannel, parseWCommand, parseVCommand, parsePCommand, parseLoop, parseHex, parseInt, etc. etc. etc.

Needless to say, the class, from its declaration, looks huge and daunting.

However, the methods to interface with the class are extremely simple, just parse (compile the text, figure out its compiled size) and link (fix the pointers once the location in memory is known, return the finalized raw binary data). Really, to the user the class has virtually no other reason for existence besides those two functions, but there's so much seemingly useless fluff in the class declaration that it's hard to even see what it's supposed to do. There's a similar situation going on with the rather massive number of data members that, again, are useless to everything but the class's internal methods that need them to talk to each other, though I don't know if that's as much of an issue.

I've considered making a separate class solely for parsing that's used within the parse method, but it seems strange to me to build an entirely separate class that's only used in a single method in a single class. It seems a bit...superfluous, I guess? And I don't even know if that's attacking the right problem.


I guess in the end, here's what I'm asking:

  1. Is this seemingly-huge class actually a problem? I don't think it's strictly a "god object", but it superficially looks like one.
  2. If it is a problem, what are the best method(s) to fix it?
share|improve this question
1  
Out of curiosity, are all your parse* methods private? I think in general parsers tend to end up like you describe which is why people use things like Yacc/Bison to generate the parser for them; they help reduce the amount of boilerplate you have to read through to understand what's going on. –  Evicatos Dec 19 '13 at 1:25
    
Yes, all the parse* methods are private. Theoretically I could've gone with Yacc or Bison to do this, but a number of reasons (namely backwards compatibility, which was basically a #1 priority) basically led to me copying a good 90% of the code from the previous implementation of this project instead. Not that I necessarily regret that decision, but...well, okay, I kinda do. –  Matt Sz. Dec 19 '13 at 4:16
    
Have a look at "combinator parser"'s they lend themselves very much to an OOP design leveraging polymorphism and composition. –  Marjan Venema Dec 19 '13 at 8:16

4 Answers 4

Ditch the OOP

The member functions probably don’t need to be. You can have the Parser class provide a few primitive operations (accept character, backtrack, &c.) and implement the rest of the parser as free functions taking a Parser reference. They can live in the source file (under an anonymous namespace) thus keeping the header nice and minimal.

In this sense, Parser is really a minimal wrapper around a stream state.

Also, it helps to factor out combinators such as many, choice, and so on, to avoid writing error-prone and verbose manual loops.

Sketch

In Parse.h, your entire public API.

unique_ptr<const Program> parse(istream&);

Your parser state can be entirely private to Parse.cpp.

struct Parser {

  Parser(istream& stream) : stream(stream) {}

  bool accept(const char expected) {
    char actual;
    if (!stream.get(actual)) return false;
    if (expected == actual) return true;
    stream.seekg(-1, ios::cur);
    return false;
  }

  template<class F, class O>
  bool accept_if(F predicate, O output) {
    char actual;
    if (!stream.get(actual)) return false;
    if (predicate(actual)) {
      *output++ = actual;
      return true;
    }
    return false;
  }

  void expect(const char expected) { if (!accept(expected)) throw ...; }

  void push_mark() { marks.push_back(stream.tellg()); }
  void pop_mark() { stream.seekg(marks.back()); drop_mark(); }
  void drop_mark() { marks.pop_back(); }

private:
  istream& stream;
  vector<istream::pos_type> marks;
};

The public API implementation just forwards to the start production of a grammar with a new parser.

unique_ptr<const Program> parse(istream& stream) {
  return parse_program(Parser(stream));
}

Output iterators are a fairly convenient way to produce multiple results.

template<class F, class O>
bool many_if(Parser& parser, F predicate, O output) {
  bool success;
  while (parser.accept_if(predicate, output)) success = true;
  return success;
}

Pointers have the advantage of a conversion to bool.

unique_ptr<const Expression> number(Parser& parser) {
  string digits;
  auto append = back_inserter(digits);
  return many_if(isdigit, append) ? make_unique<Number>(digits) : nullptr;
}

And so on. The real strengths of C++ to leverage when writing parsers are:

  • Generic programming
  • Iterators
  • Streams

Objects, not so much.

share|improve this answer
2  
These are often called "parse combinator libraries". Parsec is one of the most –  jozefg Dec 19 '13 at 4:14
2  
Write more about this. I saw the title and immediately thought "yep, parsers eat another OO devotee..", also think more about how monads are dirtily sort-of implemented in OO - usually something like an interface IMaybe<U> { public IMaybe<T> bind(...); } where the functionality instead of in free-functions exists as members on the resultant types - as opposed to the OO approach which ends up attempting free functions and resulting in a static mega-class. More need be written on doing parsers right from the FP perspective - the other answers here are staying in the OO vain and very flawed –  Jimmy Hoffa Dec 19 '13 at 4:48

I think you are stuck -- a big grammer needs a big parser.

You may be able to split the grammar into "sub grammers", e.g. one grammar for "object desrciptions" and another grammar for "action rules"; but this is only possible if your grammar can be broken down cleanly into separate "stanzas".

share|improve this answer

I assume that the parser was written in a procedural style. If so, around 50 methods (= rules in your grammar) are to be expected for a small to medium-sized language. As there is no way to cut down on that, any criticism on the number of functions is void.

However, it is often the case that your grammar can be viewed as multiple largely unconnected subgrammars. For example in Markdown (the markup our posts here are using), the block-level grammar and the inline grammar are mostly separate. If your language has a similar distinction, writing various separate parsers that interface with each other would not only improve your design but also testability.

There is also a difference between parsing and lexing – some of your functions like parseInt don't necessarily belong into the parser level (but that very much depends).

If the only public methods of your parser object are parse and link, then there is no problem because the rest can be private, and implemented with whatever design you want. The link method however does probably not belong to a parser, and might have to be factored out into a seperate class – apply the Single Responsibility Principle as it makes sense.

A note on the term God Object: This term is used when

  • a class has too many responsibilities,
  • uses mutating global state instead of encapsulated state (aka. smaller objects) or function arguments, and
  • is written in a procedural, rather than object-oriented style.

The first two are real code smells that have to be adressed: The first is obvious, and the second is absolutely unecessary in a parser, which can be implemented just fine without mutating any state (assuming you are trying to build an AST). The third can be a valid criticism, but sometimes (e.g. with parsers), a procedural or functional solution is more elegant than an object-oriented one.

share|improve this answer
1  
Actually, the language is simple enough that it doesn't need an AST--it's roughly on par with ASM in terms of complexity (but in none of the ways that would make just building a table to deal with the input easy). However, this helped me to realize the significantly larger problem that I should have seen at the start: instead of passing data around to a parser and then to a linker, parse and link were actual methods of the data type (i.e. data.parse() instead of parser.parse(data)). I'm not a design expert (obviously, since I'm asking questions), but I'm assuming that was a mistake. –  Matt Sz. Dec 19 '13 at 4:41
    
-1 for "As there is no way to cut down on that, any criticism on the number of functions is void." this is both defeatist and an absolute statement which betrays the belief that you think your knowledge of parsers is absolute, something I wouldn't say anybody's knowledge of parsers is. (Not to mention it's completely wrong in my experience you can definitely reduce numbers of functions through various generic approaches..) –  Jimmy Hoffa Dec 19 '13 at 19:59

There's a similar situation going on with the rather massive number of data members that, again, are useless to everything but the class's internal methods that need them to talk to each other

I suspect that is the real issue. Having a class to be a container for a lot of private functions, for a program written in a non-OO style is not a problem for its own (as others have stated here) - as long as you have mostly pure functions, without any state or access to data members. Such functions can be still tested one by one, and when you change the behaviour of one function, the risk of breaking other functions is still very small.

But when these many functions depend also on many data members and communicate by them, then you are on the road to "spagetti code", because now you introduce dependencies where "everything depends on everything", and a change in one part of your parser may result in unwanted side effects on the other parts.

So my advice is: make your parser functions more functional. Make the communication more explicit - don't use "global variables" (your member variables are in fact global from the viewpoint of your parser), but explicit input and output parameters. This will most probably increase the maintainability and evolvability to a degree that you can still handle it when your parser gets more and more methods over the lifetime of your system.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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