« previous next »
Pages: [1]   Go Down

Author Topic: Compiler/lexical analyzer (Rosetta Code Task)  (Read 2964 times)

0 Members and 1 Guest are viewing this topic.

Offline Ed Davis

  • Newbie
  • Posts: 40
    • View Profile
Compiler/lexical analyzer (Rosetta Code Task)
« on: April 17, 2021, 10:18:34 am »
http://rosettacode.org/wiki/Compiler/lexical_analyzer#QB64

Lexical Analyzer
Definition from Wikipedia:

Lexical analysis is the process of converting a sequence of characters (such as in a computer program or web page) into a sequence of tokens (strings with an identified "meaning"). A program that performs lexical analysis may be called a lexer, tokenizer, or scanner (though "scanner" is also used to refer to the first stage of a lexer).

Task
Create a lexical analyzer for the simple programming language specified below. The program should read input from a file and/or stdin, and write output to a file and/or stdout. If the language being used has a lexer module/library/class, it would be great if two versions of the solution are provided: One without the lexer module, and one with.

This is lex.bas:

Code: QB64: [Select]
  1. dim shared source as string, the_ch as string, tok as string, toktyp as string
  2. dim shared line_n as integer, col_n as integer, text_p as integer, err_line as integer, err_col as integer, errors as integer
  3.  
  7. declare sub divide_or_comment
  8. declare sub error_exit(line_n as integer, col_n as integer, msg as string)
  9. declare sub follow(c as string, typ2 as string, typ1 as string)
  10. declare sub nextch
  11. declare sub nexttok
  12. declare sub read_char_lit
  13. declare sub read_ident
  14. declare sub read_number
  15. declare sub read_string
  16.  
  17. const c_integer = "Integer", c_ident = "Identifier", c_string = "String"
  18.  
  19. dim out_fn as string, out_tok as string
  20.  
  21. if command$(1) = "" then print "Expecting a filename": end
  23. source = space$(lof(1))
  24. get #1, 1, source
  26.  
  27. out_fn = command$(2): if out_fn <> "" then open out_fn for output as #1
  28.  
  29. line_n = 1: col_n = 0: text_p = 1: the_ch = " "
  30.  
  32.     call nexttok
  33.     select case toktyp
  34.         case c_integer, c_ident, c_string: out_tok = tok
  35.         case else:                         out_tok = ""
  36.     end select
  37.     if out_fn = "" then
  38.         print err_line, err_col, toktyp, out_tok
  39.     else
  40.         print #1, err_line, err_col, toktyp, out_tok
  41.     end if
  42. loop until errors or tok = ""
  43. if out_fn <> "" then close #1
  45.  
  46. ' get next tok, toktyp
  47. sub nexttok
  48.     toktyp = ""
  49.     restart: err_line = line_n: err_col = col_n: tok = the_ch
  50.     select case the_ch
  51.         case " ", chr$(9), chr$(10): call nextch:          goto restart
  52.         case "/": call divide_or_comment: if tok = "" then goto restart
  53.  
  54.         case "%": call nextch: toktyp = "Op_mod"
  55.         case "(": call nextch: toktyp = "LeftParen"
  56.         case ")": call nextch: toktyp = "RightParen"
  57.         case "*": call nextch: toktyp = "Op_multiply"
  58.         case "+": call nextch: toktyp = "Op_add"
  59.         case ",": call nextch: toktyp = "Comma"
  60.         case "-": call nextch: toktyp = "Op_subtract"
  61.         case ";": call nextch: toktyp = "Semicolon"
  62.         case "{": call nextch: toktyp = "LeftBrace"
  63.         case "}": call nextch: toktyp = "RightBrace"
  64.  
  65.         case "&": call follow("&", "Op_and",          "")
  66.         case "|": call follow("|", "Op_or",           "")
  67.         case "!": call follow("=", "Op_notequal",     "Op_not")
  68.         case "<": call follow("=", "Op_lessequal",    "Op_less")
  69.         case "=": call follow("=", "Op_equal",        "Op_assign")
  70.         case ">": call follow("=", "Op_greaterequal", "Op_greater")
  71.  
  72.         case chr$(34): call read_string
  73.         case chr$(39): call read_char_lit
  74.  
  75.         case "": toktyp = "End_of_input"
  76.  
  77.         case else
  78.             if isdigit&(the_ch) then
  79.                 call read_number
  80.             elseif isalpha&(the_ch) then
  81.                 call read_ident
  82.             else
  83.                 call nextch
  84.             end if
  85.     end select
  87.  
  88. sub follow(c as string, if_both as string, if_one as string)
  89.     call nextch
  90.     if the_ch = c then
  91.         tok = tok + the_ch
  92.         call nextch
  93.         toktyp = if_both
  94.     else
  95.         if if_one = "" then call error_exit(line_n, col_n, "Expecting " + c): exit sub
  96.         toktyp = if_one
  97.     end if
  99.  
  100. sub read_string
  101.     toktyp = c_string
  102.     call nextch
  103.     do
  104.         tok = tok + the_ch
  105.         select case the_ch
  106.             case chr$(10): call error_exit(line_n, col_n, "EOL in string"): exit sub
  107.             case "":       call error_exit(line_n, col_n, "EOF in string"): exit sub
  108.             case chr$(34): call nextch: exit sub
  109.             case else:     call nextch
  110.         end select
  111.     loop
  113.  
  114. sub read_char_lit
  115.     toktyp = c_integer
  116.     call nextch
  117.     if the_ch = chr$(39) then
  118.         call error_exit(err_line, err_col, "Empty character constant"): exit sub
  119.     end if
  120.  
  121.     if the_ch = "\" then
  122.         call nextch
  123.         if the_ch = "n" then
  124.             tok = "10"
  125.         elseif the_ch = "\" then
  126.             tok = "92"
  127.         else
  128.             call error_exit(line_n, col_n, "Unknown escape sequence:" + the_ch): exit sub
  129.         end if
  130.     else
  131.         tok = ltrim$(str$(asc(the_ch)))
  132.     end if
  133.  
  134.     call nextch
  135.     if the_ch <> chr$(39) then
  136.         call error_exit(line_n, col_n, "Multi-character constant"): exit sub
  137.     end if
  138.     call nextch
  140.  
  141. sub divide_or_comment
  142.     call nextch
  143.     if the_ch <> "*" then
  144.         toktyp = "Op_divide"
  145.     else  ' skip comments
  146.         tok = ""
  147.         call nextch
  148.         do
  149.             if the_ch = "*" then
  150.                 call nextch
  151.                 if the_ch = "/" then
  152.                     call nextch
  153.                     exit sub
  154.                 end if
  155.             elseif the_ch = "" then
  156.                 call error_exit(line_n, col_n, "EOF in comment"): exit sub
  157.             else
  158.                 call nextch
  159.             end if
  160.         loop
  161.     end if
  163.  
  164. sub read_ident
  165.     do
  166.         call nextch
  167.         if not isalnum&(the_ch) then exit do
  168.         tok = tok + the_ch
  169.     loop
  170.     select case tok
  171.         case "else":  toktyp = "keyword_else"
  172.         case "if":    toktyp = "keyword_if"
  173.         case "print": toktyp = "keyword_print"
  174.         case "putc":: toktyp = "keyword_putc"
  175.         case "while": toktyp = "keyword_while"
  176.         case else:    toktyp = c_ident
  177.     end select
  179.  
  180. sub read_number
  181.     toktyp = c_integer
  182.     do
  183.         call nextch
  184.         if not isdigit&(the_ch) then exit do
  185.         tok = tok + the_ch
  186.     loop
  187.  
  188.     if isalpha&(the_ch) then
  189.         call error_exit(err_line, err_col, "Bogus number: " + tok + the_ch): exit sub
  190.     end if
  192.  
  193. function isalpha&(s as string)
  195.   c = left$(s, 1)
  196.   isalpha& = c <> "" and instr("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_", c) > 0
  198.  
  199. function isdigit&(s as string)
  201.   c = left$(s, 1)
  202.   isdigit& = c <> "" and instr("0123456789", c) > 0
  204.  
  205. function isalnum&(s as string)
  207.   c = left$(s, 1)
  208.   isalnum& = c <> "" and instr("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789_", c) > 0
  210.  
  211. ' get next char - fold cr/lf into just lf
  212. sub nextch
  213.     the_ch = ""
  214.     col_n = col_n + 1
  215.     if text_p > len(source) then exit sub
  216.  
  217.     the_ch = mid$(source, text_p, 1)
  218.     text_p = text_p + 1
  219.  
  220.     if the_ch = chr$(13) then
  221.         the_ch = chr$(10)
  222.         if text_p <= len(source) then
  223.             if mid$(source, text_p, 1) = chr$(10) then
  224.                 text_p = text_p + 1
  225.             end if
  226.         end if
  227.     end if
  228.  
  229.     if the_ch = chr$(10) then
  230.         line_n = line_n + 1
  231.         col_n = 0
  232.     end if
  233.  
  235.  
  236. sub error_exit(line_n as integer, col_n as integer, msg as string)
  237.     errors = -1
  238.     print line_n, col_n, msg
  239.     end
  241.  

One of the samples provided, mandelp.t

Code: QB64: [Select]
  1. {
  2. /*
  3.  This is an integer ascii Mandelbrot generator
  4.  */
  5.     left_edge   = -420;
  6.     right_edge  =  300;
  7.     top_edge    =  300;
  8.     bottom_edge = -300;
  9.     x_step      =    7;
  10.     y_step      =   15;
  11.  
  12.     max_iter    =  200;
  13.  
  14.     y0 = top_edge;
  15.     while (y0 > bottom_edge) {
  16.         x0 = left_edge;
  17.         while (x0 < right_edge) {
  18.             y = 0;
  19.             x = 0;
  20.             the_char = ' ';
  21.             i = 0;
  22.             while (i < max_iter) {
  23.                 x_x = (x * x) / 200;
  24.                 y_y = (y * y) / 200;
  25.                 if (x_x + y_y > 800 ) {
  26.                     the_char = '0' + i;
  27.                     if (i > 9) {
  28.                         the_char = '@';
  29.                     }
  30.                     i = max_iter;
  31.                 }
  32.                 y = x * y / 100 + y0;
  33.                 x = x_x - y_y + x0;
  34.                 i = i + 1;
  35.             }
  36.             putc(the_char);
  37.             x0 = x0 + x_step;
  38.         }
  39.         putc('\n');
  40.         y0 = y0 - y_step;
  41.     }
  42. }
  43.  

And here is the output, from:  lex mandelp.t

Code: QB64: [Select]
  1. 1             1            LeftBrace
  2. 5             5            Identifier    left_edge
  3. 5             17           Op_assign
  4. 5             19           Op_subtract
  5. 5             20           Integer       420
  6. 5             23           Semicolon
  7. 6             5            Identifier    right_edge
  8. 6             17           Op_assign
  9. 6             20           Integer       300
  10. 6             23           Semicolon
  11. 7             5            Identifier    top_edge
  12. 7             17           Op_assign
  13. 7             20           Integer       300
  14. 7             23           Semicolon
  15. 8             5            Identifier    bottom_edge
  16. 8             17           Op_assign
  17. 8             19           Op_subtract
  18. 8             20           Integer       300
  19. 8             23           Semicolon
  20. 9             5            Identifier    x_step
  21. 9             17           Op_assign
  22. 9             22           Integer       7
  23. 9             23           Semicolon
  24. 10            5            Identifier    y_step
  25. 10            17           Op_assign
  26. 10            21           Integer       15
  27. 10            23           Semicolon
  28. 12            5            Identifier    max_iter
  29. 12            17           Op_assign
  30. 12            20           Integer       200
  31. 12            23           Semicolon
  32. 14            5            Identifier    y0
  33. 14            8            Op_assign
  34. 14            10           Identifier    top_edge
  35. 14            18           Semicolon
  36. 15            5            keyword_while
  37. 15            11           LeftParen
  38. 15            12           Identifier    y0
  39. 15            15           Op_greater
  40. 15            17           Identifier    bottom_edge
  41. 15            28           RightParen
  42. 15            30           LeftBrace
  43. 16            9            Identifier    x0
  44. 16            12           Op_assign
  45. 16            14           Identifier    left_edge
  46. 16            23           Semicolon
  47. 17            9            keyword_while
  48. 17            15           LeftParen
  49. 17            16           Identifier    x0
  50. 17            19           Op_less
  51. 17            21           Identifier    right_edge
  52. 17            31           RightParen
  53. 17            33           LeftBrace
  54. 18            13           Identifier    y
  55. 18            15           Op_assign
  56. 18            17           Integer       0
  57. 18            18           Semicolon
  58. 19            13           Identifier    x
  59. 19            15           Op_assign
  60. 19            17           Integer       0
  61. 19            18           Semicolon
  62. 20            13           Identifier    the_char
  63. 20            22           Op_assign
  64. 20            24           Integer       32
  65. 20            27           Semicolon
  66. 21            13           Identifier    i
  67. 21            15           Op_assign
  68. 21            17           Integer       0
  69. 21            18           Semicolon
  70. 22            13           keyword_while
  71. 22            19           LeftParen
  72. 22            20           Identifier    i
  73. 22            22           Op_less
  74. 22            24           Identifier    max_iter
  75. 22            32           RightParen
  76. 22            34           LeftBrace
  77. 23            17           Identifier    x_x
  78. 23            21           Op_assign
  79. 23            23           LeftParen
  80. 23            24           Identifier    x
  81. 23            26           Op_multiply
  82. 23            28           Identifier    x
  83. 23            29           RightParen
  84. 23            31           Op_divide
  85. 23            33           Integer       200
  86. 23            36           Semicolon
  87. 24            17           Identifier    y_y
  88. 24            21           Op_assign
  89. 24            23           LeftParen
  90. 24            24           Identifier    y
  91. 24            26           Op_multiply
  92. 24            28           Identifier    y
  93. 24            29           RightParen
  94. 24            31           Op_divide
  95. 24            33           Integer       200
  96. 24            36           Semicolon
  97. 25            17           keyword_if
  98. 25            20           LeftParen
  99. 25            21           Identifier    x_x
  100. 25            25           Op_add
  101. 25            27           Identifier    y_y
  102. 25            31           Op_greater
  103. 25            33           Integer       800
  104. 25            37           RightParen
  105. 25            39           LeftBrace
  106. 26            21           Identifier    the_char
  107. 26            30           Op_assign
  108. 26            32           Integer       48
  109. 26            36           Op_add
  110. 26            38           Identifier    i
  111. 26            39           Semicolon
  112. 27            21           keyword_if
  113. 27            24           LeftParen
  114. 27            25           Identifier    i
  115. 27            27           Op_greater
  116. 27            29           Integer       9
  117. 27            30           RightParen
  118. 27            32           LeftBrace
  119. 28            25           Identifier    the_char
  120. 28            34           Op_assign
  121. 28            36           Integer       64
  122. 28            39           Semicolon
  123. 29            21           RightBrace
  124. 30            21           Identifier    i
  125. 30            23           Op_assign
  126. 30            25           Identifier    max_iter
  127. 30            33           Semicolon
  128. 31            17           RightBrace
  129. 32            17           Identifier    y
  130. 32            19           Op_assign
  131. 32            21           Identifier    x
  132. 32            23           Op_multiply
  133. 32            25           Identifier    y
  134. 32            27           Op_divide
  135. 32            29           Integer       100
  136. 32            33           Op_add
  137. 32            35           Identifier    y0
  138. 32            37           Semicolon
  139. 33            17           Identifier    x
  140. 33            19           Op_assign
  141. 33            21           Identifier    x_x
  142. 33            25           Op_subtract
  143. 33            27           Identifier    y_y
  144. 33            31           Op_add
  145. 33            33           Identifier    x0
  146. 33            35           Semicolon
  147. 34            17           Identifier    i
  148. 34            19           Op_assign
  149. 34            21           Identifier    i
  150. 34            23           Op_add
  151. 34            25           Integer       1
  152. 34            26           Semicolon
  153. 35            13           RightBrace
  154. 36            13           keyword_putc
  155. 36            17           LeftParen
  156. 36            18           Identifier    the_char
  157. 36            26           RightParen
  158. 36            27           Semicolon
  159. 37            13           Identifier    x0
  160. 37            16           Op_assign
  161. 37            18           Identifier    x0
  162. 37            21           Op_add
  163. 37            23           Identifier    x_step
  164. 37            29           Semicolon
  165. 38            9            RightBrace
  166. 39            9            keyword_putc
  167. 39            13           LeftParen
  168. 39            14           Integer       10
  169. 39            18           RightParen
  170. 39            19           Semicolon
  171. 40            9            Identifier    y0
  172. 40            12           Op_assign
  173. 40            14           Identifier    y0
  174. 40            17           Op_subtract
  175. 40            19           Identifier    y_step
  176. 40            25           Semicolon
  177. 41            5            RightBrace
  178. 42            1            RightBrace
  179. 43            1            End_of_input
  180.  
Logged
Pages: [1]   Go Up
« previous next »