« previous next »
Pages: 1 2 [3]   Go Down

Author Topic: The Recursive Descent Parser  (Read 12806 times)

0 Members and 1 Guest are viewing this topic.

Offline Ed Davis

  • Newbie
  • Posts: 40
    • View Profile
Re: The Recursive Descent Parser
« Reply #30 on: March 29, 2019, 04:27:56 pm »
Here are a couple of numeric expression parsers I wrote a while back.  Both use all QB64 numeric/logical/boolean operators along with standard Basic precedence, as noted in the Microsoft BASIC manuals, namely:

Code: QB64: [Select]
  1. Operator Precedence in BASIC
  2.  
  3. Highest:   ^
  4.            + - (unary negation)
  5.            *  /
  6.            \ (integer division)
  7.           MOD
  8.            +  -
  9.            =  <>  <  >  <=  >=
  10.           NOT (unary)
  11.           AND
  12.           OR
  13.           XOR
  14.           EQV
  15. Lowest:   IMP
  16.  

The first uses a form of Recursive Descent called Precedence Climbing, which I find easier than traditional Recursive Descent.  The second uses traditional Recursive Descent.  Both support the operators listed above, along with the following functions: abs, atn, cos, exp, fix, int, log, rnd, sgn, sin, sqr, tan.

Hopefully, the code is easy enough to follow.  Feedback is of course appreciated.

Expression Parser using Precedence Climbing:
Code: QB64: [Select]
  2.  
  7.  
  8. 'Simple numeric calculator - uses BASIC precedence rules
  9. '
  10. 'Supports all QB numeric/logical operators, plus the following functions:
  11. '
  12. 'abs, atn, cos, exp, fix, int, log, rnd, sgn, sin, sqr, tan
  13. '
  14. 'Uses Precedence Climbing algorithm
  15. '
  16. 'Operator Precedence in BASIC
  17. '
  18. 'Highest:   ^
  19. '           + - (unary negation)
  20. '           *  /
  21. '           \ (integer division)
  22. '          MOD
  23. '           +  -
  24. '           =  <>  <  >  <=  >=
  25. '          NOT (unary)
  26. '          AND
  27. '          OR
  28. '          XOR
  29. '          EQV
  30. 'Lowest:   IMP
  31. '
  32.  
  33. dim shared input_st as string   'the string to evaluate
  34.  
  35. dim shared tok as integer       ' set by the scanner - one of the values listed below
  36. dim shared id_name as string    ' set by the scanner, if tok is an ID or NUMBER
  37.  
  38. dim shared prec(20) as integer  'array of precedences
  39.  
  40. CONST false = 0
  41. CONST true = not false
  42.  
  43. ' Values for tok - also indexes into prec array - code below depends on this ordering
  44. const POWER     =   1
  45. const NEGATE    =   2
  46. const MULTIPLY  =   3
  47. const DIVIDE    =   4
  48. const INT_DIV   =   5
  49. const MODULUS   =   6
  50. const ADD       =   7
  51. const SUBTRACT  =   8
  52. const EQUAL     =   9
  53. const NOT_EQUAL =  10
  54. const LSS_T     =  11
  55. const GTR_T     =  12
  56. const LSS_T_EQL =  13
  57. const GTR_T_EQL =  14
  58. const NOT_T     =  15
  59. const AND_T     =  16
  60. const OR_T      =  17
  61. const XOR_T     =  18
  62. const EQV_T     =  19
  63. const IMP_T     =  20
  64.  
  65. const ID        = 100
  66. const NUMBER    = 101
  67. const LPAREN    = 102
  68. const RPAREN    = 103
  69.  
  70. ' populate the precedence array - these conicide with the constants above
  71. ' we use the operator constants (above) as indexes into the precedence array
  72. '
  73. prec(POWER)    = 13
  74. prec(NEGATE)   = 12
  75. prec(DIVIDE)   = 11: prec(MULTIPLY) = 11
  76. prec(INT_DIV)  = 10
  77. prec(MODULUS)  = 9
  78. prec(SUBTRACT) = 8: prec(ADD) = 8
  79. prec(GTR_T_EQL)=7:prec(LSS_T_EQL)=7:prec(GTR_T)=7:prec(LSS_T)=7:prec(NOT_EQUAL)=7:prec(EQUAL)=7
  80. prec(NOT_T)    = 6
  81. prec(AND_T)    = 5
  82. prec(OR_T)     = 4
  83. prec(XOR_T)    = 3
  84. prec(EQV_T)    = 2
  85. prec(IMP_T)    = 1
  86.  
  87. input_st = "-1 - 2 - 3 - 4"
  88. print input_st + " = "; eval#
  89.  
  90. input_st = "3 + 6 / 12 * 3 - 2"
  91. print input_st + " = "; eval#
  92.  
  93. input_st = "4 ^ - 2"
  94. print input_st + " = "; eval#
  95.  
  96. input_st = "4 ^ 3 ^ 2"
  97. print input_st + " = "; eval#
  98.  
  99. input_st = "32 / 2 / 2"
  100. print input_st + " = "; eval#
  101.  
  102. input_st = "atn(1) * 4"
  103. print "PI = " + input_st + " = "; eval#
  104.  
  106.     input "Enter a string to evaluate > "; input_st
  107.     if input_st = "" then end
  108.     print "Expression = "; eval#
  109.     ?
  111.  
  112. function eval#
  113.     next_tok
  114.     eval# = evalr#(0)
  116.  
  117. function evalr#(pr as integer)
  118.     dim n as double
  119.  
  120.     n = primary#
  121.  
  122.     do while is_binary%(tok) 'need short circuit for this: and prec(tok) >= pr
  123.         if prec(tok) < pr then exit do
  124.         dim op as integer
  125.         op = tok
  126.         next_tok
  127.         select case op
  128.             case IMP_T     : n = n imp evalr#(prec(op) + 1)
  129.             case EQV_T     : n = n eqv evalr#(prec(op) + 1)
  130.             case XOR_T     : n = n xor evalr#(prec(op) + 1)
  131.             case OR_T      : n = n or  evalr#(prec(op) + 1)
  132.             case AND_T     : n = n and evalr#(prec(op) + 1)
  133.             case GTR_T     : n = n >   evalr#(prec(op) + 1)
  134.             case GTR_T_EQL : n = n >=  evalr#(prec(op) + 1)
  135.             case LSS_T_EQL : n = n <=  evalr#(prec(op) + 1)
  136.             case LSS_T     : n = n <   evalr#(prec(op) + 1)
  137.             case NOT_EQUAL : n = n <>  evalr#(prec(op) + 1)
  138.             case EQUAL     : n = n =   evalr#(prec(op) + 1)
  139.             case SUBTRACT  : n = n -   evalr#(prec(op) + 1)
  140.             case ADD       : n = n +   evalr#(prec(op) + 1)
  141.             case MODULUS   : n = n mod evalr#(prec(op) + 1)
  142.             case INT_DIV   : n = n \   evalr#(prec(op) + 1)
  143.             case DIVIDE    : n = n /   evalr#(prec(op) + 1)
  144.             case MULTIPLY  : n = n *   evalr#(prec(op) + 1)
  145.             case POWER     : n = n ^   evalr#(prec(op) + 1)
  146.             case else: print "Expecting an binary operator": evalr# = 0: exit do
  147.         end select
  148.         if is_relational(op) and is_relational(tok) then
  149.             print "consecutive relational operators not allowed"
  150.             evalr# = 0
  151.         end if
  152.     loop
  153.     evalr# = n
  155.  
  156. function is_binary%(op as integer)
  157.     is_binary% = false
  158.     if op >= MULTIPLY and op <= IMP_T then is_binary% = true: exit function
  159.     if op = POWER then is_binary% = true: exit function
  161.  
  162. function is_relational%(op as integer)
  163.     is_relational% = false
  164.     if op >= EQUAL and op <= GTR_T_EQL then is_relational% = true
  166.  
  167. function primary#
  168.     dim n as double
  169.     dim fun as string
  170.  
  171.     select case tok
  172.         case NUMBER:   n = val(id_name): next_tok
  173.         case ADD:      next_tok: n =     evalr#(prec(NEGATE))
  174.         case SUBTRACT: next_tok: n =    -evalr#(prec(NEGATE))
  175.         case NOT_T:    next_tok: n = not evalr#(prec(NOT_T))
  176.         case LPAREN
  177.             next_tok
  178.             n = evalr#(0)
  179.             call expect(RPAREN, ")")
  180.         case ID
  181.             fun = id_name
  182.             next_tok
  183.             call expect(LPAREN, "(")
  184.             n = evalr#(0)
  185.             call expect(RPAREN, ")")
  186.             n = builtin(fun, n)
  187.         case else: print "Expecting a primary": n = 0
  188.     end select
  189.     primary# = n
  191.  
  192. function builtin#(fun as string, arg as double)
  193.     dim n as double
  194.  
  195.     select case lcase$(fun)
  196.         case "abs": n = abs(arg)
  197.         case "atn": n = atn(arg)
  198.         case "cos": n = cos(arg)
  199.         case "exp": n = exp(arg)
  200.         case "fix": n = fix(arg)
  201.         case "int": n = int(arg)
  202.         case "log": n = log(arg)
  203.         case "rnd": n = rnd(arg)
  204.         case "sgn": n = sgn(arg)
  205.         case "sin": n = sin(arg)
  206.         case "sqr": n = sqr(arg)
  207.         case "tan": n = tan(arg)
  208.         case else: n = 0: print "Expecting a function, found: "; fun
  209.     end select
  210.     builtin# = n
  212.  
  213. sub expect(n as integer, s as string)
  214.     if tok = n then next_tok: exit sub
  215.     print "Expecting: "; s
  217.  
  218. sub next_tok
  219.     id_name = ""
  220.     tok = 0
  221.  
  222.     ' skip spaces
  223.     input_st = ltrim$(input_st)
  224.  
  225.     if input_st = "" then exit sub
  226.  
  227.     ' pick off a few multichar operators
  228.     select case lcase$(left$(input_st, 2))
  229.         case ">=": input_st = mid$(input_st, 3): tok = GTR_T_EQL
  230.         case "<=": input_st = mid$(input_st, 3): tok = LSS_T_EQL
  231.         case "<>": input_st = mid$(input_st, 3): tok = NOT_EQUAL
  232.         case else
  233.             ' now do the rest, based on first letter
  234.         select case lcase$(left$(input_st, 1))
  235.             case "0" to "9"
  236.                 do
  237.                     id_name = id_name + left$(input_st, 1)
  238.                     input_st = mid$(input_st, 2)
  239.                 loop while (left$(input_st, 1) >= "0" and left$(input_st, 1) <= "9") or left$(input_st, 1) = "."
  240.                 tok = NUMBER
  241.             case "a" to "z"
  242.                 do
  243.                     id_name = id_name + left$(input_st, 1)
  244.                     input_st = mid$(input_st, 2)
  245.                 loop while left$(input_st, 1) >= "a" and left$(input_st, 1) <= "z"
  246.                 select case lcase$(id_name)
  247.                     case "mod": tok = MODULUS:
  248.                     case "not": tok = NOT_T:
  249.                     case "and": tok = AND_T:
  250.                     case "or" : tok = OR_T:
  251.                     case "eqv": tok = EQV_T:
  252.                     case "imp": tok = IMP_T:
  253.                     case "xor": tok = XOR_T:
  254.                     case else:  tok = ID:
  255.                 end select
  256.  
  257.             case "^": input_st = mid$(input_st, 2): tok = POWER
  258.             case "*": input_st = mid$(input_st, 2): tok = MULTIPLY
  259.             case "/": input_st = mid$(input_st, 2): tok = DIVIDE
  260.             case "\": input_st = mid$(input_st, 2): tok = INT_DIV
  261.             case "+": input_st = mid$(input_st, 2): tok = ADD
  262.             case "-": input_st = mid$(input_st, 2): tok = SUBTRACT
  263.             case "=": input_st = mid$(input_st, 2): tok = EQUAL
  264.             case "(": input_st = mid$(input_st, 2): tok = LPAREN
  265.             case ")": input_st = mid$(input_st, 2): tok = RPAREN
  266.             case ">": input_st = mid$(input_st, 2): tok = GTR_T
  267.             case "<": input_st = mid$(input_st, 2): tok = LSS_T
  268.             case else: print "Unknown token encountered"
  269.         end select
  270.     end select
  272.  

Expression Parser using Recursive Descent:
Code: QB64: [Select]
  2.  
  7.  
  8. 'Simple numeric calculator - uses BASIC precedence rules
  9. '
  10. 'Supports all QB numeric/logical operators, plus the following functions:
  11. '
  12. 'abs, atn, cos, exp, fix, int, log, rnd, sgn, sin, sqr, tan
  13. '
  14. 'Uses Recursive Descent algorithm
  15. 'This requires one function per precedence level
  16. '
  17. 'Operator Precedence in BASIC
  18. '
  19. 'Highest:   ^
  20. '           + - (unary negation)
  21. '           *  /
  22. '           \ (integer division)
  23. '          MOD
  24. '           +  -
  25. '           =  <>  <  >  <=  >=
  26. '          NOT (unary)
  27. '          AND
  28. '          OR
  29. '          XOR
  30. '          EQV
  31. 'Lowest:   IMP
  32.  
  33. dim shared input_st as string   'the string to evaluate
  34.  
  35. dim shared tok as integer       ' set by the scanner - one of the values listed below
  36. dim shared id_name as string    ' set by the scanner, if tok is an ID or NUMBER
  37.  
  38. CONST false = 0
  39. CONST true = not false
  40.  
  41. ' Values for tok
  42. const POWER     =   1
  43. const NEGATE    =   2
  44. const MULTIPLY  =   3
  45. const DIVIDE    =   4
  46. const INT_DIV   =   5
  47. const MODULUS   =   6
  48. const ADD       =   7
  49. const SUBTRACT  =   8
  50. const EQUAL     =   9
  51. const NOT_EQUAL =  10
  52. const LSS_T     =  11
  53. const GTR_T     =  12
  54. const LSS_T_EQL =  13
  55. const GTR_T_EQL =  14
  56. const NOT_T     =  15
  57. const AND_T     =  16
  58. const OR_T      =  17
  59. const XOR_T     =  18
  60. const EQV_T     =  19
  61. const IMP_T     =  20
  62.  
  63. const ID        = 100
  64. const NUMBER    = 101
  65. const LPAREN    = 102
  66. const RPAREN    = 103
  67.  
  68. input_st = "-1 - 2 - 3 - 4"
  69. print input_st + " = "; eval#
  70.  
  71. input_st = "3 + 6 / 12 * 3 - 2"
  72. print input_st + " = "; eval#
  73.  
  74. input_st = "4 ^ - 2"
  75. print input_st + " = "; eval#
  76.  
  77. input_st = "4 ^ 3 ^ 2"
  78. print input_st + " = "; eval#
  79.  
  80. input_st = "32 / 2 / 2"
  81. print input_st + " = "; eval#
  82.  
  83. input_st = "atn(1) * 4"
  84. print "PI = " + input_st + " = "; eval#
  85.  
  87.     input "Enter a string to evaluate > "; input_st
  88.     if input_st = "" then end
  89.     print "Expression = "; eval#
  90.     ?
  92.  
  93. function eval#
  94.     next_tok
  95.     eval# = evalr#(0)
  97.  
  98. function evalr#(dummy)
  99.     dim n as double
  100.  
  101.     n = eval_eqv#(0)
  102.     do while tok = IMP_T
  103.         next_tok: n = n imp eval_eqv#(0)
  104.     loop
  105.     evalr# = n
  107.  
  108. function eval_eqv#(dummy)
  109.     dim n as double
  110.  
  111.     n = eval_xor#(0)
  112.     do while tok = EQV_T
  113.         next_tok: n = n eqv eval_xor#(0)
  114.     loop
  115.     eval_eqv# = n
  117.  
  118. function eval_xor#(dummy)
  119.     dim n as double
  120.  
  121.     n = eval_or#(0)
  122.     do while tok = XOR_T
  123.         next_tok: n = n xor eval_or#(0)
  124.     loop
  125.     eval_xor# = n
  127.  
  128. function eval_or#(dummy)
  129.     dim n as double
  130.  
  131.     n = eval_and#(0)
  132.     do while tok = OR_T
  133.         next_tok: n = n or eval_and#(0)
  134.     loop
  135.     eval_or# = n
  137.  
  138. function eval_and#(dummy)
  139.     dim n as double
  140.  
  141.     n = eval_relational#(0)
  142.     do while tok = AND_T
  143.         next_tok: n = n and eval_relational#(0)
  144.     loop
  145.     eval_and# = n
  147.  
  148. function eval_relational#(dummy)
  149.     dim n as double
  150.  
  151.     n = eval_add#(0)
  152.     select case tok
  153.         case GTR_T    : next_tok: n = n >  eval_add#(0)
  154.         case GTR_T_EQL: next_tok: n = n >= eval_add#(0)
  155.         case LSS_T_EQL: next_tok: n = n <= eval_add#(0)
  156.         case LSS_T    : next_tok: n = n <  eval_add#(0)
  157.         case NOT_EQUAL: next_tok: n = n <> eval_add#(0)
  158.         case EQUAL    : next_tok: n = n =  eval_add#(0)
  159.     end select
  160.     eval_relational# = n
  162.  
  163. function eval_add#(dummy)
  164.     dim n as double
  165.  
  166.     n = eval_mod#(0)
  167.     do
  168.         select case tok
  169.             case ADD:      next_tok: n = n + eval_mod#(0)
  170.             case SUBTRACT: next_tok: n = n - eval_mod#(0)
  171.             case else: exit do
  172.         end select
  173.     loop
  174.     eval_add# = n
  176.  
  177. function eval_mod#(dummy)
  178.     dim n as double
  179.  
  180.     n = eval_idiv#(0)
  181.     do while tok = MODULUS
  182.         next_tok: n = n mod eval_idiv#(0)
  183.     loop
  184.     eval_mod# = n
  186.  
  187. function eval_idiv#(dummy)
  188.     dim n as double
  189.  
  190.     n = eval_mul#(0)
  191.     do while tok = INT_DIV
  192.         next_tok: n = n \ eval_mul#(0)
  193.     loop
  194.     eval_idiv# = n
  196.  
  197. function eval_mul#(dummy)
  198.     dim n as double
  199.  
  200.     n = eval_pow#(0)
  201.     do
  202.         select case tok
  203.             case MULTIPLY: next_tok:  n = n * eval_pow#(0)
  204.             case DIVIDE:   next_tok:  n = n / eval_pow#(0)
  205.             case else: exit do
  206.         end select
  207.     loop
  208.     eval_mul# = n
  210.  
  211. function eval_pow#(dummy)
  212.     dim n as double
  213.  
  214.     n = factor#(0)
  215.     do while tok = POWER
  216.         next_tok:  n = n ^ factor#(0)
  217.     loop
  218.     eval_pow# = n
  220.  
  221. function factor#(dummy)
  222.     dim n as double
  223.     dim fun as string
  224.  
  225.     select case tok
  226.         case NUMBER:   n = val(id_name): next_tok
  227.         case ADD:      next_tok: n =     factor#(0)
  228.         case SUBTRACT: next_tok: n =    -factor#(0)
  229.         case NOT_T:    next_tok: n = not factor#(0)
  230.         case LPAREN
  231.             next_tok
  232.             n = evalr#(0)
  233.             call expect(RPAREN, ")")
  234.         case ID
  235.             fun = id_name
  236.             next_tok
  237.             call expect(LPAREN, "(")
  238.             n = evalr#(0)
  239.             call expect(RPAREN, ")")
  240.             n = builtin(fun, n)
  241.         case else: print "Expecting a factor": n = 0
  242.     end select
  243.     factor# = n
  245.  
  246. function builtin#(fun as string, arg as double)
  247.     dim n as double
  248.  
  249.     select case lcase$(fun)
  250.         case "abs": n = abs(arg)
  251.         case "atn": n = atn(arg)
  252.         case "cos": n = cos(arg)
  253.         case "exp": n = exp(arg)
  254.         case "fix": n = fix(arg)
  255.         case "int": n = int(arg)
  256.         case "log": n = log(arg)
  257.         case "rnd": n = rnd(arg)
  258.         case "sgn": n = sgn(arg)
  259.         case "sin": n = sin(arg)
  260.         case "sqr": n = sqr(arg)
  261.         case "tan": n = tan(arg)
  262.         case else: n = 0: print "Expecting a function, found: "; fun
  263.     end select
  264.     builtin# = n
  266.  
  267. sub expect(n as integer, s as string)
  268.     if tok = n then next_tok: exit sub
  269.     print "Expecting: "; s
  271.  
  272. sub next_tok
  273.     id_name = ""
  274.     tok = 0
  275.  
  276.     ' skip spaces
  277.     input_st = ltrim$(input_st)
  278.  
  279.     if input_st = "" then exit sub
  280.  
  281.     ' pick off a few multichar operators
  282.     select case lcase$(left$(input_st, 2))
  283.         case ">=": input_st = mid$(input_st, 3): tok = GTR_T_EQL
  284.         case "<=": input_st = mid$(input_st, 3): tok = LSS_T_EQL
  285.         case "<>": input_st = mid$(input_st, 3): tok = NOT_EQUAL
  286.         case else
  287.             ' now do the rest, based on first letter
  288.         select case lcase$(left$(input_st, 1))
  289.             case "0" to "9"
  290.                 do
  291.                     id_name = id_name + left$(input_st, 1)
  292.                     input_st = mid$(input_st, 2)
  293.                 loop while (left$(input_st, 1) >= "0" and left$(input_st, 1) <= "9") or left$(input_st, 1) = "."
  294.                 tok = NUMBER
  295.             case "a" to "z"
  296.                 do
  297.                     id_name = id_name + left$(input_st, 1)
  298.                     input_st = mid$(input_st, 2)
  299.                 loop while left$(input_st, 1) >= "a" and left$(input_st, 1) <= "z"
  300.                 select case lcase$(id_name)
  301.                     case "mod": tok = MODULUS:
  302.                     case "not": tok = NOT_T:
  303.                     case "and": tok = AND_T:
  304.                     case "or" : tok = OR_T:
  305.                     case "eqv": tok = EQV_T:
  306.                     case "imp": tok = IMP_T:
  307.                     case "xor": tok = XOR_T:
  308.                     case else:  tok = ID:
  309.                 end select
  310.  
  311.             case "^": input_st = mid$(input_st, 2): tok = POWER
  312.             case "*": input_st = mid$(input_st, 2): tok = MULTIPLY
  313.             case "/": input_st = mid$(input_st, 2): tok = DIVIDE
  314.             case "\": input_st = mid$(input_st, 2): tok = INT_DIV
  315.             case "+": input_st = mid$(input_st, 2): tok = ADD
  316.             case "-": input_st = mid$(input_st, 2): tok = SUBTRACT
  317.             case "=": input_st = mid$(input_st, 2): tok = EQUAL
  318.             case "(": input_st = mid$(input_st, 2): tok = LPAREN
  319.             case ")": input_st = mid$(input_st, 2): tok = RPAREN
  320.             case ">": input_st = mid$(input_st, 2): tok = GTR_T
  321.             case "<": input_st = mid$(input_st, 2): tok = LSS_T
  322.             case else: print "Unknown token encountered"
  323.         end select
  324.     end select
  326.  
Logged
Pages: 1 2 [3]   Go Up
« previous next »