File size: 1,811 Bytes
ce25ab4 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 | ; Assembly Bite: Tree Pattern Matcher — DFS path matching
; Adjacency list: [id, first_child, next_sibling] per node
; Standard DFS with explicit stack — no invented tools
; Author: Ahmad Ali Parr · Trust: Bel Esprit D'Accord Irrevocable Trust
.DATA
MAX_NODES: .word 100
PATTERN_LEN: .word 3
NODES: .repl 0, MAX_NODES*3 ; [id, first_child, next_sibling]
PATTERN: .repl 0, PATTERN_LEN ; e.g. [1,5,9] root→child→grandchild
MATCH_FLAG: .word 0
STACK: .repl 0, 100 ; DFS stack (node_id, pattern_index)
SP: .word 0
.CODE
MAIN:
LOAD R0, #0
STORE SP, R0
LOAD R0, #0
STORE MATCH_FLAG, R0
LOAD R0, #1 ; push root (ID=1)
STORE STACK+0, R0
LOAD R0, #0
STORE STACK+1, R0 ; pattern_idx=0
LOAD R0, #2
STORE SP, R0
CALL DFS_MATCH
RET
DFS_MATCH:
LOAD R0, SP
CMP R0, #0
JEQ DFS_END
LOAD R1, SP
SUB R1, #2
STORE SP, R1
LOAD R2, STACK+R1 ; node_id
LOAD R3, STACK+R1+1 ; pattern_idx
LOAD R4, PATTERN_LEN
CMP R3, R4
JGE MATCH_FOUND
MUL R5, R2, #3
LOAD R6, NODES+R5
CMP R6, R2
JNE DFS_MATCH
LOAD R7, PATTERN+R3
CMP R6, R7
JNE CHECK_SIBLINGS
LOAD R8, R3
ADD R8, #1
LOAD R9, PATTERN_LEN
CMP R8, R9
JGE MATCH_FOUND
LOAD R10, NODES+R5+1
CMP R10, #0
JEQ CHECK_SIBLINGS
LOAD R11, SP
STORE STACK+R11, R10
LOAD STACK+R11+1, R8
LOAD R12, #2
ADD R11, R11, R12
STORE SP, R11
JMP DFS_MATCH
CHECK_SIBLINGS:
LOAD R13, NODES+R5+2
CMP R13, #0
JEQ DFS_MATCH
LOAD R14, SP
STORE STACK+R14, R13
LOAD STACK+R14+1, R3
LOAD R15, #2
ADD R14, R14, R15
STORE SP, R14
JMP DFS_MATCH
MATCH_FOUND:
LOAD R0, #1
STORE MATCH_FLAG, R0
RET
DFS_END:
RET
|