1

Recently I wrote an interpreter for operations on sparse matrices (a "sparse matrix calculator") in lex/yacc. The language is still very bare bones and doesn't even include control structures or parameterized subroutines, yet it is already at several thousand lines of code, and that's not including the matrix classes. In particular, the yacc file is close to two thousand lines in length. Because of this I'm finding it quite difficult to work on. Is this normal or is there a way I can simplify things?

If you want to review my code, it can be found at: http://sourceforge.net/projects/msci/files/libpetey/

  • 1
    welcome to parsing, one of the more complex facets of computing – ratchet freak May 9 '14 at 17:51
  • Is the question exclusively about parsing? I'm asking because none of the responses mention anything about all the other things besides parsing that compilers and interpreters do. – user39685 May 9 '14 at 19:06
7

A few thousand lines for a parser + interpreter that actually does something interesting is not unusual in the least. I looked at the SVN repo and especially your main grammar and noticed various things:

  • You have various utility classes that would make more sense in a general algorithms library. A quicksort implementation, really? IIRC, the C++ standard library already contains such functionality.

    In general, the code seems to be very C-like (aside from the use of classes) and could benefit from building convenient abstractions using the vast array of C++ language features. I see a lot of code reuse via copy&paste.

  • You do not seem to build an AST, but parsing and evaluation happen at the same time. You should decouple parsing from semantic validation from interpretation. Once your yacc grammar only contains a grammar and not half an interpreter, it should become much more maintainable.

    Separating the interpreter from the parser also has the advantage that it's easier to implement complex control flow such as loops, conditionals, or function calls.

  • Your grammar also includes help messages as string literals. Factor such messages out into a resources file, rather than hardcoding everything.

This was just a quick design review. If you're interested in an in-depth criticism of your code, post an excerpt of your code to Code Review.

  • 3
    And beside being bad style, these also explain the staggering (for the amount of functionality implemented) line count. It's not the parser that's two thousand lines, it's parsing, documentation (HELP * productions), diagnostics, and evaluation. – user7043 May 9 '14 at 18:47
  • 1
    +1 for breaking apart the AST parser from the rest, seems everyone who tries to do any sort of interpreter/compiler for the first time doesn't decompose the problem space with an AST as an intermediary interface that allows you to separate your parsing from your evaluation. – Jimmy Hoffa May 9 '14 at 19:52
  • Thanks for this: it gives me a bit to think about. In general, I do prefer the simplicity of C programming when I can get away with it. I believe that primitive types exist for a reason and don't like to encapsulate data unless there is a compelling reason to do so, i.e. a complex or hierarchical data structure such as a sparse matrix. I am also suspicious of black boxes and so tend to code my own abstract data types (most times this is pretty easy). The quicksort, BTW is mainly meant for finding the k-least or k-greatest elements in an array, not that common in standard libraries. – user18850 May 10 '14 at 15:50
  • To continue: one problem I have with building a parse tree is: won't it slow down the interprettor? For a compiler this strategy makes sense, especially if you plan to optimize, but with an interprettor it seems you're doing the same thing twice since yacc already implicitly reduces recursive expressions. Though it would certainly simplify evaluation of control structures. I was rather considering using a stack-based byte-code. This could be saved for later and is more efficient than straight interpretation or a parse tree. – user18850 May 10 '14 at 15:55
  • 1
    @user18850 There is some cost to building a tree and processing it instead of doing the processing on-line. However, it more than pays for the cost with the greater simplicity and flexibility. That flexibility also allows you to pursue optimizations (e.g. bytecode compilation, as you mention) that far outweigh the cost of building a tree, unless most of the code is executed never or only once (rough guideline, no hard data). Finally, your evaluator will probably spend do of the heavy lifting in your sparse matrix code; before you try to optimize parse time benchmark whether it's a hot spot. – user7043 May 10 '14 at 16:43
2

Parsing is inherently complex. It's difficult to do correctly, and even more difficult to do elegantly. A lot of code is not necessarily a sign of a problem. However, there are a lot of things you can do to make it easier.

  • Use functions instead of cramming everything into your yacc file. You want a yacc file to be only the specification of your grammar, putting as much implementation as possible into other files. This lets you debug the grammar more easily, and also helps you recognize redundancy more easily.
  • Spend a lot of time getting your grammar right before you work on implementation. I didn't look at your file in depth, and my yacc is a little rusty, but it seems there is a lot of repetition that could be eliminated with a better grammar. Adding extra non-terminals in certain places can save you a lot of work. In particular, instead of listing all possible combinations of vector, scalar, and matrix expressions separately, try combining them into one non-terminal called a value or something, combine your operators into one non-terminal called op or something (or group based on operator precedence), and write rules like value op value.
  • You're putting a lot of semantics into your parser, where you should focus mainly on structure, and implement the semantics in other files. Try making the output of your parser just an AST. Simple parsers, like the kind you find in tutorials, can skip this step, but you'll find for moderately complex languages you really need that extra layer.
  • Nice points. To make it even simpler, I'd even go so far as to suggest producing a concrete syntax tree (CST) instead of an AST -- then the parse tree will exactly match the input, even including things like unnecessary parentheses. Easier to debug. Not at all sure how well this approach fits into YACC though. – user39685 May 9 '14 at 19:03
  • 1
    @MattFenwick It should be easy to do, but I don't see the benefit. There's little you can do with a CST that isn't much easier to do with an AST, so you'd put the CST->AST step right afterwards anyway, so the only thing you add is another intermediate data structure and more tree traversal code. For debugging later stages, an AST is best. For debugging the operation of the parsers, the CST doesn't help, except in the rare case when the problem is in how the AST simplifies away syntactic details. – user7043 May 9 '14 at 19:40
  • @delnan there's several benefits: 1) separation of concerns -- can change concrete and abstract syntaxes independently; 2) simpler parser; 3) can regenerate the original input; 4) parse tree corresponds directly to input (it seems we disagree on the importance of this for debugging). Of course there are costs as well. – user39685 May 9 '14 at 20:32
  • 1
    @MattFenwick I don't see this as a concern that needs separating; the CST->AST simplification is almost trivial when done directly in the parser (and hence extracting it hardly simplifies the parser), and the CST is not interesting on its own. Regenerating the original input you'll have to expand on; as I said I expect the CST->AST step to happen immediately afterwards anyway, so there isn't any pass in between that would have to reconstruct the input. – user7043 May 9 '14 at 20:59
  • @delnan I disagree on all points. I think the root of our disagreement is different implicit assumptions about the language and how the parser will be used. Needless to say, without understanding each other's assumptions, this conversation is 100% pointless. – user39685 May 10 '14 at 14:52

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.