The Recursive Descent Parser

[Aurel]

hi jack
Yes you have right IF we use this program as finished or completed
but if you wish to add more operation under factor() function then makes no sense to use
ELSE...
so probably should be better to use ELSEIF method
but that is another story.
In fact match just operate under parens () in another word if parens exists.
hmmm is that ok ?

[Ed Davis]

As we can see this few functions are really simple.

Try this expression: 1+2+3

The answer should be 6, but the evaluator returns 3.  I think recursion in qb64 is broken.

Hmmm.  Searching old messages, only broken if 0 arguments.  I changed expr# and term# to take a single argument, changed the calls to the same, and now it works fine.

Will this be fixed one day, or is it for backwards compatibility or something and thus will remain as it is?

[jack]

@Ed Davis
would you post the code please?

[Aurel]

I think recursion in qb64 is broken

no ..is not
it is problem in evaluator because i get same error in o2 version ..too
I don't understand exatly what you mean under single argument?

[SMcNeill]

I think recursion in qb64 is broken

no ..is not
it is problem in evaluator because i get same error in o2 version ..too
I don't understand exatly what you mean under single argument?

Read the issue and a fix here: https://www.qb64.org/forum/index.php?topic=704.msg5802#msg5802

Basically, the following is broken:

Code: QB64: [Select]

1. DIM SHARED X
2. X = 5
3. PRINT F
4.  
5. FUNCTION F
6. IF X = 0 THEN F = 1 ELSE PRINT "*": X = X - 1: F = F
7. END FUNCTIOn

Luke was going to try and sort out a solution to the issue in the evaltype routine, but has been busy with life in general and hasn’t gotten around to it yet.  If you use zero-argument recursion a lot, you might want to apply my patch to QB64.bas and recompile the EXE.  If not, and it’s a once-in-a-bluemoon issue, just pass a dummy parameter to the function.

Instead of:

FUNCTION foo
   Foo = foo
END FUNCTION

Use:

Function Foo (dummy)
   Foo = Foo (Whatever)
END FUNCTION

[Ed Davis]

I think recursion in qb64 is broken

no ..is not
it is problem in evaluator because i get same error in o2 version ..too
I don't understand exatly what you mean under single argument?

Original version, but with a different expression - should show 6, but it shows 3:

Code: QB64: [Select]

1. 'recursive descent token evaluator - original version
2. DIM SHARED tc AS LONG
3. DIM SHARED tokens(8) AS STRING * 1
4. DIM SHARED token AS STRING
5.  
6. tc = 0
7. tokens(1) = "1"
8. tokens(2) = "+"
9. tokens(3) = "2"
10. tokens(4) = "+"
11. tokens(5) = "3"
12.  
13. 'execute---------------
14. CALL gettok 'start
15. DIM res AS DOUBLE
16. res = expr#
17. PRINT res
18. END
19.  
20. SUB gettok ()
21.     tc = tc + 1
22.     token = tokens(tc)
23. END SUB
24.  
25. FUNCTION expr# ()
26.     DIM v AS DOUBLE
27.     v = term#
28.     IF token = "+" THEN
29.         gettok
30.         v = v + term#
31.     END IF
32.     IF token = "-" THEN
33.         gettok
34.         v = v - term#
35.     END IF
36.     expr# = v
37. END FUNCTION
38.  
39. FUNCTION term# ()
40.     DIM v AS DOUBLE
41.     v = factor#
42.     IF token = "*" THEN
43.         gettok
44.         v = v * factor#
45.     END IF
46.     IF token = "/" THEN
47.         gettok
48.         v = v / factor#
49.     END IF
50.     term# = v
51. END FUNCTION
52.  
53. FUNCTION factor# ()
54.     DIM v AS DOUBLE
55.     IF ASC(token) > 47 AND ASC(token) < 58 THEN 'nums
56.         v = VAL(token)
57.         gettok
58.     END IF
59.     IF ASC(token) = 40 AND ASC(token) <> 41 THEN 'match (...)
60.         gettok
61.         v = expr#
62.         gettok
63.     END IF
64.     factor# = v
65. END FUNCTION
66.  

Updated version, but using one (dummy) argument for expr and term - gets the right answer:

Code: QB64: [Select]

1. 'recursive descent token evaluator - added dummy arguments
2. DIM SHARED tc AS LONG
3. DIM SHARED tokens(8) AS STRING * 1
4. DIM SHARED token AS STRING
5.  
6. tc = 0
7. tokens(1) = "1"
8. tokens(2) = "+"
9. tokens(3) = "2"
10. tokens(4) = "+"
11. tokens(5) = "3"
12.  
13. 'execute---------------
14. CALL gettok 'start
15. DIM res AS DOUBLE
16. res = expr#(0)
17. PRINT res
18. END
19.  
20. SUB gettok ()
21.     tc = tc + 1
22.     token = tokens(tc)
23. END SUB
24.  
25. FUNCTION expr# (x as integer)
26.     DIM v AS DOUBLE
27.     v = term#(0)
28.     IF token = "+" THEN
29.         gettok
30.         v = v + expr#(0)
31.     ELSEIF token = "-" THEN
32.         gettok
33.         v = v - expr#(0)
34.     END IF
35.     expr# = v
36. END FUNCTION
37.  
38. FUNCTION term# (x as integer)
39.     DIM v AS DOUBLE
40.     v = factor#
41.     IF token = "*" THEN
42.         gettok
43.         v = v * term#(0)
44.     ELSEIF token = "/" THEN
45.         gettok
46.         v = v / term#(0)
47.     END IF
48.     term# = v
49. END FUNCTION
50.  
51. FUNCTION factor# ()
52.     DIM v AS DOUBLE
53.     IF ASC(token) > 47 AND ASC(token) < 58 THEN 'nums
54.         v = VAL(token)
55.         gettok
56.     ELSEIF ASC(token) = 40 AND ASC(token) <> 41 THEN 'match (...)
57.         gettok
58.         v = expr#(0)
59.         gettok
60.     END IF
61.     factor# = v
62. END FUNCTION
63.  

See this message: https://www.qb64.org/forum/index.php?topic=676.msg5776#msg5776
for a confirmation of the recursion bug.

Interestingly, FreeBasic, in QB mode, also has the same problem.  However, when compiled in normal FreeBasic mode (some minor changes have to be made to the code), it works fine.

[Aurel]

Hmm that is interesting and as i said same problem i found in o2 version
I don't look first time what was going on using token one by one (in each step)
then when i look again into my old interpretr i figured that i use
while loop with operators +,-,*,/
so probably this loop add one turn more for "dummy" effect and
now everything work as it should be .
strange thing ..i must try with null too...

[bplus]

I don't think you guys have it fixed yet:

Code: QB64: [Select]

1. _TITLE "Recursive descent token evaluator by Aurel"
2. 'trenslation by @jack 19.3.2019
3. ' nope! now use Ed Davis fix: https://www.qb64.org/forum/index.php?topic=33.15
4. 'mod by B+ 2019-03-20 so that can test any number of expressions
5.  
6. DIM SHARED tc AS LONG
7. DIM SHARED token AS STRING
8. DIM res AS DOUBLE
9. 'tc = 0
10. 'tokens(1) = "2"
11. 'tokens(2) = "*"
12. 'tokens(3) = "("
13. 'tokens(4) = "3"
14. 'tokens(5) = "+"
15. 'tokens(6) = "4"
16. 'tokens(7) = ")"
17.  
18. DO
19.     INPUT "Enter an expression to evaluate: ", eval$
20.     le = LEN(eval$)
21.     IF le THEN
22.         tc = 0
23.         REDIM SHARED tokens(1 TO le + 1) AS STRING * 1
24.         FOR i = 1 TO le
25.             tokens(i) = MID$(eval$, i, 1)
26.         NEXT
27.         'execute---------------
28.         'CALL gettok 'start
29.         gettok
30.         res = expr#(0)
31.         PRINT res
32.     END IF
33. LOOP UNTIL le = 0
34.  
35. 'recursive descent token evaluator - added dummy arguments  (fixed set? by Ed Davis)
36. SUB gettok ()
37.     tc = tc + 1
38.     token = tokens(tc)
39. END SUB
40.  
41. FUNCTION expr# (x AS INTEGER)
42.     DIM v AS DOUBLE
43.     v = term#(0)
44.     IF token = "+" THEN
45.         gettok
46.         v = v + expr#(0)
47.     ELSEIF token = "-" THEN
48.         gettok
49.         v = v - expr#(0)
50.     END IF
51.     expr# = v
52. END FUNCTION
53.  
54. FUNCTION term# (x AS INTEGER)
55.     DIM v AS DOUBLE
56.     v = factor#
57.     IF token = "*" THEN
58.         gettok
59.         v = v * term#(0)
60.     ELSEIF token = "/" THEN
61.         gettok
62.         v = v / term#(0)
63.     END IF
64.     term# = v
65. END FUNCTION
66.  
67. FUNCTION factor# ()
68.     DIM v AS DOUBLE
69.     IF ASC(token) > 47 AND ASC(token) < 58 THEN 'nums
70.         v = VAL(token)
71.         gettok
72.     ELSEIF ASC(token) = 40 AND ASC(token) <> 41 THEN 'match (...)
73.         gettok
74.         v = expr#(0)
75.         gettok
76.     END IF
77.     factor# = v
78. END FUNCTION
79.  
80.  

Wait this was limited to only single digits? :P

[Aurel]

Wait this was limited to only single digits?

No i think NOT limited to one digit.
token should use any number like "12345"
First i will check again o2 version then i try fix qb64 version ok?

[Ed Davis]

I don't think you guys have it fixed yet:

Wait this was limited to only single digits? :P

Correct.  There isn't a real scanner - it just assumes single characters, no spaces allowed.  I guess Aurel posted it to "get his feet wet" with QB64?  So it is at best a simple demo, nothing more.

I like your colors, by the way!

[Aurel]

In another words
if we wish to enter expression and evaluate it , we need TOKENIZER
to split our expression into tokens( read numbers & operators )
is that ok.

[Aurel]

well i tryed  this without dummy load and with additional while loop
like i do in o2 but nothing ...
token taken are
1
+
2
  0

[bplus]

Aurel your attempts here have me skimming over Erik's massive and successful undertaking and having me appreciate all over again Erik's effort. :)

[Aurel]

Yes Mark
Erik really do big work with his SICK engine ...
and is not very easy to follow all what he do in it.
It is great but little bit too complex for me.
He use large amount of string processing which confuses me..
of course i understand them all but as i said is not easy to get what is what(for me
even i have experience in that things)- of course not like Ed ;)

[Aurel]

Hi..
I just forund in my old programs one created by author of qb64
i called that program GALEON BASIC.
This program is posted on old forum ..long time ago.
There is a interesting way used for evaluating expression with GOTO command..
so can i publish it here ?