Why Interpreter Pattern can not be used for complex grammar

[kaizhou]

HI, guys,

I have a question about the Interpreter Pattern. I think that pattern is good and flexible. But according to information from some websites, it is said the g++ compiler and microsoft visual c++ compiler are all hand written recursive descent parser. I think Interpreter Pattern is the most natural way to implement a recursive descent parser in OO way. I meet with the problem when I was reading source code of Lua 5.1. It seems neither g++ or microsoft c++ compiler choose Interpreter Pattern as an approach for implementation.

Besides, in a web page( http://www.vincehuston.org/dp/interpreter.html ) I saw this "The pattern doesn't address parsing. When the grammar is very complex, other techniques (such as a parser) are more appropriate." I don't understand why Interpreter Pattern is not capable of complex grammar. Please help me understand if you have any clue of this.

Btw, I don't understand why they use recursive descent parser other than Yacc to generate a parser. Yacc doesn't have to trace back during parsing and Yacc is capable of doing some optimization to state switch table of parser.

[pm_kirkham]

Implementations of expression grammar parsers often use the interpreter pattern. The difference between such systems and the example in the web page you cite is that the interpreter is interpreting the grammar, not the input file.

As interpreters, they can have worse performance than hand-crafted or code generation based parsers. On the other hand, their structure reflects the grammar and they allow very quick edit/test/debug cycles on grammars. I've used them for small domain specific languages (typically structured so you can parse a line at a time, independent of context), but without memoization it would probably not perform well enough for languages where there is a lot of context.

[kaizhou]

Implementations of expression grammar parsers often use the interpreter pattern. The difference between such systems and the example in the web page you cite is that the interpreter is interpreting the grammar, not the input file.

As interpreters, they can have worse performance than hand-crafted or code generation based parsers. On the other hand, their structure reflects the grammar and they allow very quick edit/test/debug cycles on grammars. I've used them for small domain specific languages (typically structured so you can parse a line at a time, independent of context), but without memoization it would probably not perform well enough for languages where there is a lot of context.

Thank you for your information of Parsing Expression Grammar.

My question still stays unsolved. Why does Interpreter Pattern implemented interpreter give worse performance than hand-crafted parsers? Because of too much virtual function calls?But the efficiency consumed by virtual function calls seems to be only a small amount, like 10% or some other small number.

Still, I think code generated based parsers could be much more efficient then hand-crafted code, there is no back tracking there.

[pm_kirkham]

In addition to virtual calls, the compiler hasn't the opportunity to inline constants, so there's a lot more memory traffic. Comparing the current character to the literal 'A' and doing a virtual call which compares it to this.character are very different sequences - a memory access, a virtual call, another memory access vs two machine instructions operating on a register and a literal. I'd be surprised if the difference is only 10%, though whether it matters with modern CPU speed/IO speed is more debatable.

Whatever technique you use, you can remove or reduce the cost of backtracking, but in a direct implementation of the GoF pattern this isn't done.

Whether or not you need backtracking (or another mechanism for exploring alternatives with common prefixes) depends on the grammar rather than the implementation.