QB64.org Forum

Active Forums => Programs => Topic started by: Ed Davis on April 17, 2021, 10:18:34 am

Title: Compiler/lexical analyzer (Rosetta Code Task)
Post by: Ed Davis on April 17, 2021, 10:18:34 am

http://rosettacode.org/wiki/Compiler/lexical_analyzer#QB64 (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.  
4. declare function isalnum&(s as string)
5. declare function isalpha&(s as string)
6. declare function isdigit&(s as string)
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
22. open command$(1) for binary as #1
23. source = space$(lof(1))
24. get #1, 1, source
25. close #1
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.  
31. do
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
44. end
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
86. end sub
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
98. end sub
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
112. end sub
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
139. end sub
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
162. end sub
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
178. end sub
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
191. end sub
192.  
193. function isalpha&(s as string)
194.   dim c as string
195.   c = left$(s, 1)
196.   isalpha& = c <> "" and instr("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_", c) > 0
197. end function
198.  
199. function isdigit&(s as string)
200.   dim c as string
201.   c = left$(s, 1)
202.   isdigit& = c <> "" and instr("0123456789", c) > 0
203. end function
204.  
205. function isalnum&(s as string)
206.   dim c as string
207.   c = left$(s, 1)
208.   isalnum& = c <> "" and instr("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789_", c) > 0
209. end function
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.  
234. end sub
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
240. end sub
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.  

Text Only | Text with Attachments