Pass#1 consists of dozens of parsers. All the “container” statements are already implemented and those missing are the “regular” statements i.e statements that can only be written inside a procedure which carry the actual program flow. I had no need to parse value expressions until now as I got started with statements such as If, Until, While, etc. Most of these standard statements include parts where a value is expected. And value is evaluated from an expression. Expressions can contain operators and operands and together they form a mathematical formula. A result of an expression can be a single value of any data type defined within a CoolBasic program.

The constant value expression parser was made long ago when I was writing the Function statement parser. It converts the expression to postfix notation and then attempts to evaluate it. It was perfectly sufficient for the job, so I decided to try out the same technique for the value expression parser aswell. Value expressions allow practically all expression elements whereas the constant parser implementation was merely partial due to the amount of “illegal” elements for a constant expression. The value expression parsing algorithm grew soon in size and wasn’t exactly the most enjoyable to debug with. Also, the more complicated expression elements such as jagged arrays caused all kinds of nasty problems that would have required ugly exceptions to be made for the algorihm. In order to debug the algorihm perfectly I needed long and complex test expressions. And since you’d need full debug info of what’s currently in the output queue, operator stack, and what’s the current state of the expression, it quickly lead to nice little flood in my Compiler debug window.

So I discarded the entire parser code, and started to think of new ways to check validity of a value expression. After sprawling on the couch (once again) for a couple of hours, I came up with a solution. I’d continue doing things just like I had been doing the entire time for Pass#1. Even expressions can be broken into smaller peaces, and each piece can be validated separately. One error, and the entire expression fails. Sounds like yet another great use of recursion, uh?

If you read compiler literature you’d notice that there are mainly two kinds of commonly used algorihms (not including their sub versions): The LL and LR parsers. They both scan expression terminals from left to right, and try to satisfy the requirements of an expression. The LL-parsers do this by forming the entire expression as a product of terminals and operators it comes across with, whereas the LR-parsers try to simplify the expression down to a single product. These algorithms are also known as “Top-down” and “Bottom-up” parsers. Since basically recursion is like a stack, the easiest way for me, was to use the Bottom-up parsing technique. It’s not by the book, but the basics are the same: Every time a value is expected, new recursive call is initiated. I’m not going to delve into details, but it appears to be working like a charm. Later on I also replaced the constant value expression parser.

So what this means, is that unless I hit unexpected problems, Pass#1 is finally coming toward its end. I still have lots of parsers to implement, but most of them are very simple. I should now have almost all bits of a statement, implemented as a parser. It’s just a puzzle left I need to put together with ready-to-use pieces.

Comments are closed.

Copyright © All Rights Reserved · Green Hope Theme by Sivan & schiy · Proudly powered by WordPress