nx_nparse.nx source
↩ module page · 450 lines · 15010 B
1// nx_nparse.nx -- NishiLang parser in pure NishiLang.
2//
3// SECOND CONCRETE STEP of the nxc2 self-hosting trajectory. Consumes
4// the NxToken stream emitted by nx_nlex.nx and produces an AST.
5//
6// Minimum viable subset:
7// - Function declarations: `func name(...) -> type { body }`
8// (empty parameter list for now)
9// - Block: { stmts ... }
10// - Statements: return <expr> ;? | <expr> ;?
11// - Expressions: integer literal, identifier, binary +/-/*//,
12// parenthesized
13//
14// Future: parameter lists, let/var bindings, if/while, struct, etc.
15
16import "syscalls.nx"
17import "nx_nlex.nx"
18import "nx_loop.nx"
19
20// === AST node kinds ================================================
21
22const NX_AST_FUNC: i64 = 1
23const NX_AST_BLOCK: i64 = 2
24const NX_AST_RETURN: i64 = 3
25const NX_AST_INT: i64 = 4
26const NX_AST_IDENT: i64 = 5
27const NX_AST_BINOP: i64 = 6
28const NX_AST_TYPE_REF: i64 = 7 // simple type identifier (e.g., i64)
29const NX_AST_LET: i64 = 8 // a=value expr idx; c=slot index
30const NX_AST_IF: i64 = 9 // a=cond expr idx; b=then-block idx
31
32// BINOP node payload: a=left ast idx, b=right ast idx, c=op-kind
33const NX_BIN_ADD: i64 = 1
34const NX_BIN_SUB: i64 = 2
35const NX_BIN_MUL: i64 = 3
36const NX_BIN_DIV: i64 = 4
37
38// Symbol table for locals (linear scan; up to 8 per function scope).
39const NX_NPARSE_MAX_LOCALS: i64 = 8
40
41// === AST node struct ===============================================
42//
43// Unified 64-byte node: kind + 6 child/data slots. Each AST node
44// occupies one slot in a flat array (no malloc per node).
45
46struct NxAst {
47 kind: i64,
48 a: i64, // kind-dependent: child ptr / int / ident-token-idx
49 b: i64,
50 c: i64,
51 d: i64,
52 e: i64,
53 parent: i64, // index of parent node (0 = root)
54 span: i64, // source span (start | (len << 32))
55}
56
57struct NxNParser {
58 lex: *NxNLexer,
59 pos: i64, // current token index
60 nodes: *NxAst,
61 n_nodes: i64,
62 cap: i64,
63 // Symbol table: parallel arrays of (name_start, name_len, slot).
64 // n_locals is the count of bindings in the current function scope.
65 sym_starts: *i64,
66 sym_lens: *i64,
67 n_locals: i64,
68}
69
70// === construction ==================================================
71
72func nx_nparse_new(lex: *NxNLexer, cap: i64) -> *NxNParser {
73 let raw: *u8 = sys_mmap(80)
74 let p: *NxNParser = raw as *NxNParser
75 p.lex = lex
76 p.pos = 0
77 p.nodes = sys_mmap(cap * 64) as *NxAst
78 p.n_nodes = 0
79 p.cap = cap
80 p.sym_starts = sys_mmap(NX_NPARSE_MAX_LOCALS * 8) as *i64
81 p.sym_lens = sys_mmap(NX_NPARSE_MAX_LOCALS * 8) as *i64
82 p.n_locals = 0
83 return p
84}
85
86// Symbol table: lookup name in current scope. Returns slot (>=0) or -1.
87func nx_nparse_sym_lookup(p: *NxNParser, start: i64, len: i64) -> i64 {
88 var i: i64 = 0
89 while i < p.n_locals {
90 if p.sym_lens[i] == len {
91 var matched: i64 = 1
92 var j: i64 = 0
93 while j < len {
94 if p.lex.src[p.sym_starts[i] + j] as i64 != p.lex.src[start + j] as i64 {
95 matched = 0
96 j = len
97 }
98 j = j + 1
99 }
100 if matched == 1 { return i }
101 }
102 i = i + 1
103 }
104 return -1
105}
106
107// Bind a new local; returns its slot index.
108func nx_nparse_sym_bind(p: *NxNParser, start: i64, len: i64) -> i64 {
109 if p.n_locals >= NX_NPARSE_MAX_LOCALS { return -1 }
110 let slot: i64 = p.n_locals
111 p.sym_starts[slot] = start
112 p.sym_lens[slot] = len
113 p.n_locals = p.n_locals + 1
114 return slot
115}
116
117func nx_nparse_node_at(p: *NxNParser, i: i64) -> *NxAst {
118 return (p.nodes as i64 + i * 64) as *NxAst
119}
120
121func nx_nparse_alloc(p: *NxNParser, kind: i64) -> i64 {
122 if p.n_nodes >= p.cap { return -1 }
123 let idx: i64 = p.n_nodes
124 let n: *NxAst = nx_nparse_node_at(p, idx)
125 n.kind = kind
126 n.a = 0
127 n.b = 0
128 n.c = 0
129 n.d = 0
130 n.e = 0
131 n.parent = -1
132 n.span = 0
133 p.n_nodes = p.n_nodes + 1
134 return idx
135}
136
137// === token cursor ===================================================
138
139func nx_nparse_peek(p: *NxNParser) -> *NxToken {
140 return nx_nlex_token_at(p.lex, p.pos)
141}
142
143func nx_nparse_peek_kind(p: *NxNParser) -> i64 {
144 let t: *NxToken = nx_nparse_peek(p)
145 return t.kind
146}
147
148func nx_nparse_advance(p: *NxNParser) -> *NxToken {
149 let t: *NxToken = nx_nparse_peek(p)
150 if t.kind != NX_TOK_EOF { p.pos = p.pos + 1 }
151 return t
152}
153
154// Expect a kind; returns 1 if matched and consumed, 0 otherwise.
155func nx_nparse_match(p: *NxNParser, kind: i64) -> i64 {
156 let k: i64 = nx_nparse_peek_kind(p)
157 if k == kind {
158 nx_nparse_advance(p)
159 return 1
160 }
161 return 0
162}
163
164// === expression parser =============================================
165//
166// Precedence-climbing. Levels:
167// 2: * /
168// 1: + -
169// 0: primary (INT | IDENT | ( expr ))
170
171func nx_nparse_primary(p: *NxNParser) -> i64 {
172 let t: *NxToken = nx_nparse_peek(p)
173 if t.kind == NX_TOK_INT {
174 nx_nparse_advance(p)
175 let idx: i64 = nx_nparse_alloc(p, NX_AST_INT)
176 let n: *NxAst = nx_nparse_node_at(p, idx)
177 n.a = t.int_val
178 n.span = t.start | (t.len << 32)
179 return idx
180 }
181 if t.kind == NX_TOK_IDENT {
182 nx_nparse_advance(p)
183 let idx: i64 = nx_nparse_alloc(p, NX_AST_IDENT)
184 let n: *NxAst = nx_nparse_node_at(p, idx)
185 n.a = t.start
186 n.b = t.len
187 // Resolve to local slot (-1 if not a known local; emitter handles).
188 n.c = nx_nparse_sym_lookup(p, t.start, t.len)
189 n.span = t.start | (t.len << 32)
190 return idx
191 }
192 // NB: parens handling lives in nx_nparse_expr (NishiLang forbids
193 // forward refs, so primary can't call expr).
194 return -1
195}
196
197func nx_nparse_mul(p: *NxNParser) -> i64 {
198 var lhs: i64 = nx_nparse_primary(p)
199 // Bound: parser cannot consume more tokens than the lex emitted.
200 let lp: *NxLoopFrame = nx_loop_begin(p.lex.n_tokens + 1)
201 while nx_loop_step(lp) == 1 {
202 let k: i64 = nx_nparse_peek_kind(p)
203 var op: i64 = 0
204 if k == NX_TOK_STAR { op = NX_BIN_MUL }
205 if k == NX_TOK_SLASH { op = NX_BIN_DIV }
206 if op == 0 {
207 nx_loop_break(lp)
208 } else {
209 nx_nparse_advance(p)
210 let rhs: i64 = nx_nparse_primary(p)
211 let idx: i64 = nx_nparse_alloc(p, NX_AST_BINOP)
212 let n: *NxAst = nx_nparse_node_at(p, idx)
213 n.a = lhs
214 n.b = rhs
215 n.c = op
216 lhs = idx
217 }
218 }
219 return lhs
220}
221
222func nx_nparse_expr(p: *NxNParser) -> i64 {
223 // Handle parens here (self-recursion is allowed; mutual is not).
224 if nx_nparse_peek_kind(p) == NX_TOK_LPAREN {
225 nx_nparse_advance(p)
226 let inner: i64 = nx_nparse_expr(p)
227 nx_nparse_match(p, NX_TOK_RPAREN)
228 // Then continue with binop chain at this level
229 var lhs: i64 = inner
230 let lp1: *NxLoopFrame = nx_loop_begin(p.lex.n_tokens + 1)
231 while nx_loop_step(lp1) == 1 {
232 let k: i64 = nx_nparse_peek_kind(p)
233 var op: i64 = 0
234 if k == NX_TOK_PLUS { op = NX_BIN_ADD }
235 if k == NX_TOK_MINUS { op = NX_BIN_SUB }
236 if k == NX_TOK_STAR { op = NX_BIN_MUL }
237 if k == NX_TOK_SLASH { op = NX_BIN_DIV }
238 if op == 0 {
239 nx_loop_break(lp1)
240 } else {
241 nx_nparse_advance(p)
242 let rhs: i64 = nx_nparse_mul(p)
243 let idx: i64 = nx_nparse_alloc(p, NX_AST_BINOP)
244 let n: *NxAst = nx_nparse_node_at(p, idx)
245 n.a = lhs
246 n.b = rhs
247 n.c = op
248 lhs = idx
249 }
250 }
251 return lhs
252 }
253 var lhs: i64 = nx_nparse_mul(p)
254 let lp2: *NxLoopFrame = nx_loop_begin(p.lex.n_tokens + 1)
255 while nx_loop_step(lp2) == 1 {
256 let k: i64 = nx_nparse_peek_kind(p)
257 var op: i64 = 0
258 if k == NX_TOK_PLUS { op = NX_BIN_ADD }
259 if k == NX_TOK_MINUS { op = NX_BIN_SUB }
260 if op == 0 {
261 nx_loop_break(lp2)
262 } else {
263 nx_nparse_advance(p)
264 let rhs: i64 = nx_nparse_mul(p)
265 let idx: i64 = nx_nparse_alloc(p, NX_AST_BINOP)
266 let n: *NxAst = nx_nparse_node_at(p, idx)
267 n.a = lhs
268 n.b = rhs
269 n.c = op
270 lhs = idx
271 }
272 }
273 return lhs
274}
275
276// === statement parser ==============================================
277
278func nx_nparse_stmt(p: *NxNParser) -> i64 {
279 let k: i64 = nx_nparse_peek_kind(p)
280 if k == NX_TOK_RETURN {
281 nx_nparse_advance(p)
282 let idx: i64 = nx_nparse_alloc(p, NX_AST_RETURN)
283 let n: *NxAst = nx_nparse_node_at(p, idx)
284 let next_kind: i64 = nx_nparse_peek_kind(p)
285 if next_kind != NX_TOK_SEMI {
286 if next_kind != NX_TOK_RBRACE {
287 let expr_idx: i64 = nx_nparse_expr(p)
288 let nn: *NxAst = nx_nparse_node_at(p, idx)
289 nn.a = expr_idx
290 }
291 }
292 nx_nparse_match(p, NX_TOK_SEMI)
293 return idx
294 }
295 if k == NX_TOK_IF {
296 // `if EXPR { THEN_BLOCK }` -- single-arm, no else. Block-
297 // parsing is inlined here because NishiLang forbids forward
298 // function references and stmt is defined before block.
299 nx_nparse_advance(p)
300 let cond_idx: i64 = nx_nparse_expr(p)
301 let then_idx: i64 = nx_nparse_alloc(p, NX_AST_BLOCK)
302 var blk_n_stmts: i64 = 0
303 if nx_nparse_match(p, NX_TOK_LBRACE) == 1 {
304 // Bound: AST_BLOCK has 4 slots (a,b,c,d) -- max 4 stmts.
305 let blp: *NxLoopFrame = nx_loop_begin(5)
306 while nx_loop_step(blp) == 1 {
307 let bk: i64 = nx_nparse_peek_kind(p)
308 if bk == NX_TOK_RBRACE { nx_loop_break(blp) }
309 if bk == NX_TOK_EOF { nx_loop_break(blp) }
310 let bk2: i64 = nx_nparse_peek_kind(p)
311 if bk2 != NX_TOK_RBRACE {
312 if bk2 != NX_TOK_EOF {
313 let s: i64 = nx_nparse_stmt(p)
314 if s < 0 {
315 nx_loop_break(blp)
316 } else {
317 let bb: *NxAst = nx_nparse_node_at(p, then_idx)
318 if blk_n_stmts == 0 { bb.a = s }
319 if blk_n_stmts == 1 { bb.b = s }
320 if blk_n_stmts == 2 { bb.c = s }
321 if blk_n_stmts == 3 { bb.d = s }
322 blk_n_stmts = blk_n_stmts + 1
323 }
324 }
325 }
326 }
327 let bb2: *NxAst = nx_nparse_node_at(p, then_idx)
328 bb2.e = blk_n_stmts
329 nx_nparse_match(p, NX_TOK_RBRACE)
330 }
331 let if_idx: i64 = nx_nparse_alloc(p, NX_AST_IF)
332 let n: *NxAst = nx_nparse_node_at(p, if_idx)
333 n.a = cond_idx
334 n.b = then_idx
335 return if_idx
336 }
337 if k == NX_TOK_LET {
338 // `let NAME [: TYPE] = EXPR ;`
339 nx_nparse_advance(p)
340 let nm: *NxToken = nx_nparse_peek(p)
341 if nm.kind != NX_TOK_IDENT { return -1 }
342 let name_start: i64 = nm.start
343 let name_len: i64 = nm.len
344 nx_nparse_advance(p)
345 // Optional `: type` — skip past it (we ignore the type for now)
346 if nx_nparse_match(p, NX_TOK_COLON) == 1 {
347 let tt: *NxToken = nx_nparse_peek(p)
348 if tt.kind == NX_TOK_IDENT { nx_nparse_advance(p) }
349 }
350 // `= expr`
351 nx_nparse_match(p, NX_TOK_ASSIGN)
352 let val_idx: i64 = nx_nparse_expr(p)
353 nx_nparse_match(p, NX_TOK_SEMI)
354 // Bind the symbol (lookup-able for later IDENT refs).
355 let slot: i64 = nx_nparse_sym_bind(p, name_start, name_len)
356 // Build AST_LET node
357 let let_idx: i64 = nx_nparse_alloc(p, NX_AST_LET)
358 let ln: *NxAst = nx_nparse_node_at(p, let_idx)
359 ln.a = val_idx
360 ln.b = name_start
361 ln.c = slot
362 ln.d = name_len
363 return let_idx
364 }
365 // Expression statement
366 let expr_idx: i64 = nx_nparse_expr(p)
367 nx_nparse_match(p, NX_TOK_SEMI)
368 return expr_idx
369}
370
371// === block parser ==================================================
372
373func nx_nparse_block(p: *NxNParser) -> i64 {
374 let block_idx: i64 = nx_nparse_alloc(p, NX_AST_BLOCK)
375 let block: *NxAst = nx_nparse_node_at(p, block_idx)
376 if nx_nparse_match(p, NX_TOK_LBRACE) == 0 { return block_idx }
377 // Track up to 4 stmt children in slots a..d, count in e.
378 // Bound: 4 slots + RBRACE iteration.
379 var n_stmts: i64 = 0
380 let blp: *NxLoopFrame = nx_loop_begin(5)
381 while nx_loop_step(blp) == 1 {
382 let k: i64 = nx_nparse_peek_kind(p)
383 if k == NX_TOK_RBRACE { nx_loop_break(blp) }
384 if k == NX_TOK_EOF { nx_loop_break(blp) }
385 let k2: i64 = nx_nparse_peek_kind(p)
386 if k2 != NX_TOK_RBRACE {
387 if k2 != NX_TOK_EOF {
388 let s: i64 = nx_nparse_stmt(p)
389 if s < 0 {
390 nx_loop_break(blp)
391 } else {
392 let b: *NxAst = nx_nparse_node_at(p, block_idx)
393 if n_stmts == 0 { b.a = s }
394 if n_stmts == 1 { b.b = s }
395 if n_stmts == 2 { b.c = s }
396 if n_stmts == 3 { b.d = s }
397 n_stmts = n_stmts + 1
398 }
399 }
400 }
401 }
402 let bb: *NxAst = nx_nparse_node_at(p, block_idx)
403 bb.e = n_stmts
404 nx_nparse_match(p, NX_TOK_RBRACE)
405 return block_idx
406}
407
408// === function decl parser ==========================================
409
410func nx_nparse_func(p: *NxNParser) -> i64 {
411 if nx_nparse_match(p, NX_TOK_FUNC) == 0 { return -1 }
412 // name
413 let name_tok: *NxToken = nx_nparse_peek(p)
414 if name_tok.kind != NX_TOK_IDENT { return -1 }
415 let name_start: i64 = name_tok.start
416 let name_len: i64 = name_tok.len
417 nx_nparse_advance(p)
418 // parens (empty for now)
419 nx_nparse_match(p, NX_TOK_LPAREN)
420 nx_nparse_match(p, NX_TOK_RPAREN)
421 // -> type
422 var ret_idx: i64 = -1
423 if nx_nparse_match(p, NX_TOK_ARROW) == 1 {
424 let tt: *NxToken = nx_nparse_peek(p)
425 if tt.kind == NX_TOK_IDENT {
426 nx_nparse_advance(p)
427 ret_idx = nx_nparse_alloc(p, NX_AST_TYPE_REF)
428 let rn: *NxAst = nx_nparse_node_at(p, ret_idx)
429 rn.a = tt.start
430 rn.b = tt.len
431 }
432 }
433 // body
434 let body_idx: i64 = nx_nparse_block(p)
435 // Build the FUNC node
436 let func_idx: i64 = nx_nparse_alloc(p, NX_AST_FUNC)
437 let f: *NxAst = nx_nparse_node_at(p, func_idx)
438 f.a = name_start
439 f.b = name_len
440 f.c = ret_idx
441 f.d = body_idx
442 return func_idx
443}
444
445// === top-level entry ===============================================
446
447func nx_nparse_run(p: *NxNParser) -> i64 {
448 // For now, parse a single function declaration.
449 return nx_nparse_func(p)
450}