Why Interpreter Pattern can not be used for complex grammar

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. But I think Interpreter Pattern is the most natural way to implement a recursive descent parser. I meet with the problem when I was reading source code of Lua 5.1. So I guess neither g++ or microsoft c++ compiler uses Interpreter Pattern as an approach to implement.

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 can do some optimization to state switch table of parser.


  • edited November -1

    I'm not familiar with compilers. The same things I read about interpreter pattern, that is used only for simple grammars.

    I was curious and I googled a little bit and I found a few things:


    Python uses the Interpreter pattern to generate bytecode for a parse tree. Other languages also do type checking, type reconstruction, and optimization analyses like liveness analysis. The optimization itself is usually not done by successive traversal, but rather by dynamic programming.
    SCM, a Scheme interpreter, directly executes the parse tree, making small optimizations as it goes along. SCM is now called Guile.
    Inventor/VRML uses the Interpreter pattern to render a graphical scene. Nodes may define geometry like cones, cubes, and polygonal meshes, may alter the drawing state like current color or 3D position, may spontaneously produce information like detecting collisions or reporting the current time, or may modify other nodes in order to maintain constraints. Thus the tree can embed information about how it should change to form an animation. Inventor uses the node sharing, default action, liveness analysis, and caching techniques.
    Text editors and Web browsers use the Interpreter pattern to lay out documents and check spelling. For example, an equation in TeX is represented as a tree where internal nodes are operators, e.g. square root, and leaves are variables.

    I also found on wikipedia that Interpreter pattern is used for:

    Specialized database query languages such as SQL.
    Specialized computer languages which are often used to describe communication protocols
    Most general-purpose computer languages actually incorporate several specialized languages.

    In other place I found that the interpreter is not used for compilers and complex grammars because it's not efficient: http://www.ddj.com/cpp/184401605. This could be a reason...

    Please let us know if you find something interesting...
  • edited November -1
    Thank you , Cubic, i learned an useful optimization approach, template in your links.

    I don't think virtual function call could consume so much efficiency in the implementation of a compiler. I know the mechanism, but generally those trade off is quite small, like 10% at most. Still I'm a little curious about that.