Expressions of type a!^b are invalid

[Former user]

Originally reported on Google Code with ID 74

What steps will reproduce the problem?
1. (1+1)!^2
2.
3.

What is the expected output? What do you see instead?
expected 4 as the result, but the parser could not parse the expression

What version of the product are you using? On what operating system?
0.8-alpha, about 3 days old

Please provide any additional information below.

Reported by [e-mail] on 2007-07-17 21:02:17

[Former user]

``` I confirmed the behaviour. Can anyone take the time to try to fix the parser in time for 0.8? If not, I'll have to put it in the 0.9 todo list. Could you try, Wolf? ```

Reported by `helder.pereira.correia` on 2007-07-17 21:23:53 - Status changed: `Accepted`

[Former user]

``` Analysis shows, that the parsing problems are buried in the file "evaluator.cpp" in function "Evaluator::compile". This function gets a list of tokens from the tokenizer, and it takes them, one by one, matching it (together with earlier encountered, so far not processed tokens) against built-in rules. If a rule applies, it issues a sort of pseudo-code, and removes the processed tokens, if not, it appends the token to a pending list, and defers processing until later tokens tell how to deal with it. If input grammar would be nice and regular, no such deferring would be necessary at all, and parsers could be simple and straightforward. Unfortunately, mankind hasn't been aware of parsing problems in past centuries, and developed a not so nice grammar for mathematical terms. However, until a few months ago, the only irregularity SpeedCrunch really had to deal with, was the operator precedence. But new operators like '!' introduced another class of tokens. They made matters even nastier, because postfix operators always change the meaning of the tokens before. The parser has to defer any processing until it definitely knows, no postfix operator is following. In order to meet these new requirements, I think, the parser has to be redesigned to some extent. This already tells us, that fixing the parser problem(s) is much more than a one-liner, and I'm not sure, whether you should really rewrite the parser (rules) in such a late state of release. Because fixing one problem might introduce others somewhere else. And you cannot catch them without extensive testing. In order to let expressions like "1!^2" execute properly, I have a makeshift patch ready. It touches about 40 lines of code, though, and makes conceptional changes by reordering and deleting existing rules. It does not eliminate the need of a redesign and does not solve all problems with postfix operators (sqrt 4! will still be evaluated as (sqrt 4)!, but this is currently broken anyway and worth a separate bug entry). It might well break the parsing of other expressions, I don't know, but maybe, you will get away with it. You will find a patched version of evaluator.cpp in the floatnum brunch. I leave it to you, whether you apply it or not.

Wolf Lammen ```

Reported by `[e-mail]` on 2007-07-18 15:27:39

[Former user]

``` I'm thinking of rewriting the parser. After all this attempt, I guess the better way is to output AST first and THEN generated the reverse-polish version (i.e. the opcodes) to be executed by the virtual machine, unlike the current table-based approach to directly output the opcodes.

This rewrite hopefully will be available along with the RPN support, as they kind of support each other.

```

Reported by `ariya.hidayat` on 2007-07-20 14:47:10

[Former user]

``` Good idea. If user requests demand a quick (and dirty) fix, one can still try to extend the current parser. This is not too difficult, but requires time for testing.

Wolf Lammen ```

Reported by `[e-mail]` on 2007-07-20 16:06:21

[Former user]

``` Ariya: could that new parser easily support definition of functions (most important, like "myFunc(x;y)=average(x;y)*0.5" ) and lists for matrix definition and such (like "myMat=1;2];[3;4", "det(myMat)" or "det(1;2];[3;4") ? ```

Reported by `helder.pereira.correia` on 2007-07-21 16:45:40

[Former user]

``` Wouldn't it be easier to use an automatically generated parser, using lexx+bison? ```

Reported by `shambler.com` on 2007-07-22 12:15:54

[Former user]

``` I'm not sure about the percent operator of Speedcrunch, which is treated specially. All other expressions can be handled by bison. IMHO, if possible, one should switch over to shamblers suggestion. Maybe I find some time next week to give it a try.

Wolf Lammen ```

Reported by `[e-mail]` on 2007-07-22 21:09:53

[Former user]

``` I'm making no more last hour changes on the parser for this release as it could break something, so let's continue this discussion for 0.9 and I'm totally up for Yonatan's (shambler) proposal (if someone knows how to deal with bison or similar tools). ```

Reported by `helder.pereira.correia` on 2007-07-22 21:56:13 - Labels added: Milestone-0.9

[Former user]

``` Lex is not needed because we have already a working and fast tokenizer. Bison is quite showing its age and not suitable for C++ (although there is C++ version of it). Probably Lemon is the best possible choice since it's fantastically simple. Of course there are tons of other parser generator.

In general math expression grammar is not too difficult, so it's even possible to write the parser by hand, just like I have done for what we have now. The problem is because I did not write the parser taking the latest features possibilities in mind, and that's why it's difficult to extend the current parser.

Personally, even with generated parser, I'd like to wait a bit until QLALR gets more polishes and/or even included in Qt.

```

Reported by `ariya.hidayat` on 2007-07-24 17:48:33

[Former user]

``` I already looked at flex and bison, and for the scanner part, I was not so impressed. Essentially it looks for regular expressions. But all regular expressions SpeedCrunch needs so far are very simple, so I don't think the overall effect justifies the inclusion of the extra library package flex is built upon. That does not hold for bison. bison is definitely powerful enough to be of use. It's right what Ariya said, bison parsers expect a C interface, so scanner and evaluator have to be "downgraded" to work with this parser. But the goodies are impressive: For instance, you can have a C++ parser right away. And in general, bison supports two language classes: LALR(1) (is that what QLARL is derived one?) and a speculative parsing algorithm that claims to deal with a vast subclass of deterministic context-free (only) languages. That's more than SpeedCrunch needs in the foreseeable future. If you want to change your grammar, updating a configuration file, is all you need to do. The problem that created this thread would have been fixed and tested in less than an hour. So bison is an option (maybe not the best). There is a bison++ version that interacts with C++, but I had no time to look at it. Wolf Lammen ```

Reported by `[e-mail]` on 2007-07-24 20:03:07

[Former user]

``` As I wrote before, we can forget about (f)lex since we have a scanner already.

QLALR is a parser for LALR. It's nice, quite fast and nicely integrated with Qt (i.e. use QString etc). More on QLALR: http://labs.trolltech.com/page/Projects/Compilers/QLALR

And if you like bison, 99% you'd like lemon even more.

I guess if somebody wants to continue this, better create a branch where the replacement code is being worked on. Then we can have different branches for different approach (hand-written, bison, QLALR, lemon). Decision on which back-end will be used can be determined later after comparing how they work.

```

Reported by `ariya.hidayat` on 2007-07-26 13:24:56

[Former user]

``` In one respect bison is superior to lemon or QLALR, because it can deal with non-deterministic, non-LALR(1) languages. Unfortunately, C, C++, Pascal are examples of such languages. For now, and the near future (say a year) any of the above parser generators will do. Wolf Lammen ```

Reported by `[e-mail]` on 2007-07-27 06:49:11

[Former user]

``` I think I'm going to give this bison++ a shot, just to create an appropriate grammar

at first. I also think flex shouldn't be ignored since using it will improve maintainability by allowing easy introduction of new tokens. ```

Reported by `shambler.com` on 2007-07-30 11:45:09

[Former user]

``` I already checked bison++ out. It is based on an old version of bison, it crashes often, does not support all keywords of bison, lacks some documentation. It took me some time (and guessing) to get a complete parser run. Actually I don't see a single advantage of bison++ over a modern parser generator like lemon. So I discourage using this program, I deleted that program from my hard disk already. Wolf Lammen ```

Reported by `[e-mail]` on 2007-07-30 17:45:05

[Former user]

Reported by `helder.pereira.correia` on 2007-11-03 19:41:05 - Labels added: Milestone-0.10 - Labels removed: Milestone-0.9

[Former user]

Reported by `helder.pereira.correia` on 2008-01-06 01:49:55 - Status changed: `Started`

[Former user]

Reported by `helder.pereira.correia` on 2008-02-20 22:14:58 - Labels added: Priority-High, Milestone-0.11 - Labels removed: Priority-Medium, Milestone-0.10

[Former user]

``` implemented makeshift solution from July 2007. Still annoying: a function call takes precedence over the postfix operator !, but that would be hard to fix in the old parser ```

Reported by `wolf.lammen` on 2008-03-21 16:01:07

[Former user]

Reported by `helder.pereira.correia` on 2008-07-19 18:23:25 - Labels removed: Milestone-0.11

[Former user]

Extended related issues mentioned above will be handled separately.

Reported by helder.pereira.correia on 2013-10-12 06:54:00 - Status changed: Fixed - Labels added: Milestone-0.11, OpSys-All