(TLDR) To build a parser for a recursive grammar by composition of individual parsers (e.g. with a parser combinator framework), there are often circular dependencies between some of the individual parsers. While circular dependencies are generally a sign of bad design, is this a valid case where the circular dependency is inevitable? If so, which solution would be preferable to deal with the circular dependency? Or are parser combinators just a bad idea altogether? (/TLDR)
There are other questions asking about dependency injection with circular dependencies. Typically, the answer is to change the design to avoid the circularity.
- How to solve circular dependency?
- How to handle "circular dependency" in dependency injection
- Is circular Dependency Injection a good practice?
I have come across a typical case where I encounter circular dependencies: If I want to have different services to inspect a recursive structure.
I have been thinking about other examples, but so far the best I come up with is a parser for a recursive grammar. Let's use json as an example, because it is simple and well-known.
- A json "value" can be a string (
".."), an object ({..}) or an array ([..]). - A string is simple to parse, and has no further children.
- An object is made up of keys and values, and the surrounding object syntax.
- An array is made up of values, and the surrounding array syntax.
- A "key" within an object is basically the same as a string.
Now I am going to create a number of parser objects:
- A value parser, which depends on the other 3 parsers.
- An object parser, which depends on string parser and value parser.
- An array parser, which depends on value parser.
- A string parser.
I want to manage the 4 parsers with a dependency injection container.
Or, even if I don't want a container, we still have to figure out in which order to create the different parsers. There is a chicken-and-egg problem.
There are known solutions to this, which can be observed in existing parser libraries. So far I have mostly seen the "stub" solution.
- Avoid the circular dependency..
.. by passing the value parser as an argument to the object and array parsers' parse() method.
This works, but it taints the signature of the parse() method. Imagine we want this to be something like a parser combinator, which can be reused for other grammars. We would want a parser interface that is generic and independent of the specific grammar, so we can't have it require a specific parser to be passed around.
- Use a stub.
Instead of requiring each dependency in the constructor, we could use a set() or add() method on one of the parsers. E.g. we first create an empty value parser ("stub"), and then add the object, array and string parsers to it via the add() method.
- Use a proxy.
Instead of creating the actual value parser, we create a proxy object, with a reference to the container. Only when the parse() method is called the first time on the proxy value parser, the real value parser is created.
Now this is all fine, and I suppose it is just a matter of taste, which solution I prefer.
But how does this fit with the typical high-horse response that circular dependencies are a sign of bad design? The example seems totally valid, and there is an entire class of problems like this.
Best Answer
ParseObjectandParseValuemethods can both call each other.