flash-attention-rtl / src /hybrid_parser.nim

October 2026 main drop: mirror from GitHub

2166d7e verified 19 days ago

18.4 kB

# Hybrid Parser: Build AST from tokens, trace control flow, allocate memory
#
# Deterministic parsing of Befunge 2D grids, Brainfuck sequences, and BCPL
# variable declarations. Produces a unified AST and memory layout.
#
# Invariants:
# - All variables have unique names
# - All memory addresses are assigned deterministically
# - All jumps and loops are resolved (no forward references)
# - Control flow is acyclic for Brainfuck (loops are recognized)

import hybrid_ast
import hybrid_lexer
import sequtils
import strutils

# ─────────────────────────────────────────────────────────────────────────────
# Parser initialization
# ─────────────────────────────────────────────────────────────────────────────

proc initParser*(tokens: seq[Token]): Parser =
  Parser(
    tokens: tokens,
    pos: 0,
    symbols: @[],
    memCounter: 9,  # Start after SUBLEQ overhead
    error: "",
    errors: @[]
  )

# ─────────────────────────────────────────────────────────────────────────────
# Token stream navigation
# ─────────────────────────────────────────────────────────────────────────────

proc peek*(p: Parser; offset: int = 0): Token =
  let idx = p.pos + offset
  if idx >= 0 and idx < p.tokens.len: p.tokens[idx] else: Token(kind: tokEOF)

proc advance*(p: var Parser): Token =
  let tok = p.peek()
  if p.pos < p.tokens.len:
    inc p.pos
  tok

proc expect*(p: var Parser; kind: TokenKind): bool =
  if p.peek().kind == kind:
    discard p.advance()
    true
  else:
    false

proc errorAt*(p: var Parser; msg: string) =
  let tok = p.peek()
  let err = "line " & $tok.line & " col " & $tok.col & ": " & msg
  p.errors.add err
  p.error = err

proc addSymbol*(p: var Parser; v: VarDecl): bool =
  # Check for duplicate
  for item in p.symbols:
    if item[0] == v.name:
      p.errorAt("duplicate variable: " & v.name)
      return false
  p.symbols.add (v.name, v)
  true

proc lookupSymbol*(p: Parser; name: string): VarDecl =
  for item in p.symbols:
    if item[0] == name:
      return item[1]
  VarDecl()  # null/zero value for not found

# ─────────────────────────────────────────────────────────────────────────────
# Brainfuck bracket matching (pre-pass)
# ─────────────────────────────────────────────────────────────────────────────

proc matchBrackets*(tokens: seq[Token]): (seq[int], string) =
  # Build a jump map: bracket position → matching bracket position
  var jumpMap = newSeq[int](tokens.len)
  var stack: seq[int]
  var errorMsg = ""

  for i, tok in tokens:
    if tok.kind == tokLBracket:
      stack.add i
    elif tok.kind == tokRBracket:
      if stack.len == 0:
        errorMsg = "unmatched ']' at token " & $i
        break
      let j = stack.pop()
      jumpMap[i] = j
      jumpMap[j] = i

  if stack.len > 0 and errorMsg == "":
    errorMsg = "unmatched '['"

  (jumpMap, errorMsg)

# ─────────────────────────────────────────────────────────────────────────────
# Parse variable declarations (BCPL-style)
# ─────────────────────────────────────────────────────────────────────────────

proc parseVarDecl*(p: var Parser): VarDecl =
  var v = VarDecl(cellAddr: p.memCounter, initialValue: 0, isArray: false)

  # Expect: int name [= initialValue] [;]
  if not p.expect(tokVarDecl):
    p.errorAt("expected 'int'")
    return v

  let nameTok = p.peek()
  if nameTok.kind != tokIdent:
    p.errorAt("expected identifier after 'int'")
    return v
  v.name = nameTok.lexeme
  discard p.advance()

  # Optional array size: [N]
  if p.peek().kind == tokLBracket:
    discard p.advance()
    let sizeTok = p.peek()
    if sizeTok.kind != tokNumber:
      p.errorAt("expected array size")
      return v
    v.arraySize = sizeTok.value
    v.isArray = true
    discard p.advance()
    if not p.expect(tokRBracket):
      p.errorAt("expected ']'")
      return v

  # Optional initializer: = value
  if p.peek().kind == tokAssign:
    discard p.advance()
    let valTok = p.peek()
    if valTok.kind != tokNumber:
      p.errorAt("expected number in initializer")
      return v
    v.initialValue = valTok.value
    discard p.advance()

  # Consume semicolon
  if not p.expect(tokSemicolon):
    p.errorAt("expected ';' after variable declaration")

  # Allocate memory
  v.cellAddr = p.memCounter
  if v.isArray:
    p.memCounter += v.arraySize
  else:
    p.memCounter += 1

  v

# ─────────────────────────────────────────────────────────────────────────────
# Parse Brainfuck sequence
# ─────────────────────────────────────────────────────────────────────────────

proc parseBrainfuckSeq*(p: var Parser): ASTNode =
  var children: seq[ASTNode]
  let bracketResult = matchBrackets(p.tokens[p.pos ..< p.tokens.len])
  let jumpMap = bracketResult[0]
  let errMsg = bracketResult[1]
  if errMsg != "":
    p.errorAt(errMsg)
    return newSeqNode(@[])

  while p.peek().kind != tokEOF:
    let tok = p.peek()
    case tok.kind
    of tokBefungeOp:
      # Brainfuck-specific operations (>, <, +, -, ., ,, [, ])
      let op = case tok.lexeme
        of ">": BfcPtrInc
        of "<": BfcPtrDec
        of "+": BfcCellInc
        of "-": BfcCellDec
        of ".": BfcOutput
        of ",": BfcInput
        else:
          p.errorAt("invalid brainfuck op: " & tok.lexeme)
          discard p.advance()
          continue
      children.add newBrainfuckNode(op)
      discard p.advance()

    of tokLBracket:
      # Match and parse loop body
      let openIdx = p.pos
      discard p.advance()
      let closeIdx = jumpMap[openIdx]

      # Parse loop body
      var bodyChildren: seq[ASTNode]
      while p.pos < closeIdx and p.peek().kind != tokEOF:
        let bodyTok = p.peek()
        case bodyTok.kind
        of tokBefungeOp:
          let op = case bodyTok.lexeme
            of ">": BfcPtrInc
            of "<": BfcPtrDec
            of "+": BfcCellInc
            of "-": BfcCellDec
            of ".": BfcOutput
            of ",": BfcInput
            else:
              p.errorAt("invalid brainfuck op: " & bodyTok.lexeme)
              discard p.advance()
              continue
          bodyChildren.add newBrainfuckNode(op)
          discard p.advance()
        of tokRBracket:
          break
        else:
          discard p.advance()

      if not p.expect(tokRBracket):
        p.errorAt("expected matching ']'")

      # Loop condition: test if tape[ptr] == 0
      let cond = newBrainfuckNode(BfcCellDec)  # dummy; real test is runtime
      let body = if bodyChildren.len == 0:
        newSeqNode(@[])
      elif bodyChildren.len == 1:
        bodyChildren[0]
      else:
        newSeqNode(bodyChildren)
      children.add newLoopNode(cond, body)

    of tokRBracket:
      p.errorAt("unmatched ']'")
      discard p.advance()

    else:
      discard p.advance()

  if children.len == 0:
    newSeqNode(@[])
  elif children.len == 1:
    children[0]
  else:
    newSeqNode(children)

# ─────────────────────────────────────────────────────────────────────────────
# Parse 2D Befunge grid
# ─────────────────────────────────────────────────────────────────────────────

proc parse2DBerungeGrid*(grid: BefungeGrid): ASTNode =
  # Build a linear AST from the 2D grid (row-major traversal)
  var children: seq[ASTNode]

  for row in 0 ..< grid.height:
    for col in 0 ..< grid.width:
      if col < grid.ops[row].len:
        let op = grid.ops[row][col]
        case op
        of BfNop:
          discard
        of BfPush:
          # Push needs a digit argument; we'll use 0 as placeholder
          children.add newBefungeNode(BfPush, 0)
        of BfRight, BfLeft, BfDown, BfUp:
          children.add newBefungeNode(op)
        of BfAdd, BfSub, BfMul, BfDiv, BfMod:
          children.add newBefungeNode(op)
        of BfNot, BfCmpGt:
          children.add newBefungeNode(op)
        of BfHRotate, BfHRotateL:
          children.add newBefungeNode(op)
        of BfDup, BfPop, BfSwap:
          children.add newBefungeNode(op)
        of BfMGet, BfMPut:
          children.add newBefungeNode(op)
        of BfInput, BfOutput, BfOutputAscii:
          children.add newBefungeNode(op)
        of BfExit:
          children.add newBefungeNode(BfExit)
          break

  if children.len == 0:
    newSeqNode(@[])
  elif children.len == 1:
    children[0]
  else:
    newSeqNode(children)

# ─────────────────────────────────────────────────────────────────────────────
# Parse primary expression
# ─────────────────────────────────────────────────────────────────────────────

proc parseExpr*(p: var Parser): ASTNode =
  let tok = p.peek()
  case tok.kind
  of tokNumber:
    let val = tok.value
    discard p.advance()
    return newLitNode(val)
  of tokIdent:
    let name = tok.lexeme
    discard p.advance()
    return newVarRefNode(name)
  of tokAmpersand:
    discard p.advance()
    let name = p.peek().lexeme
    if p.peek().kind != tokIdent:
      p.errorAt("expected identifier after '&'")
      return newLitNode(0)
    discard p.advance()
    return newVarRefNode(name, false)
  of tokStar:
    discard p.advance()
    let name = p.peek().lexeme
    if p.peek().kind != tokIdent:
      p.errorAt("expected identifier after '*'")
      return newLitNode(0)
    discard p.advance()
    return newVarRefNode(name, true)
  else:
    p.errorAt("unexpected token in expression: " & tok.lexeme)
    discard p.advance()
    return newLitNode(0)

# ─────────────────────────────────────────────────────────────────────────────
# Parse statement (top-level production)
# ─────────────────────────────────────────────────────────────────────────────

proc parseStatement*(p: var Parser): ASTNode =
  let tok = p.peek()
  case tok.kind
  of tokVarDecl:
    let v = p.parseVarDecl()
    if p.addSymbol(v):
      # Successful declaration; return comment node (no code generation)
      return newCommentNode("declare " & v.name)
    else:
      return newSeqNode(@[])

  of tokIf:
    discard p.advance()
    if not p.expect(tokLParen):
      p.errorAt("expected '(' after 'if'")
      return newSeqNode(@[])
    let cond = p.parseExpr()
    if not p.expect(tokRParen):
      p.errorAt("expected ')' after condition")
    if not p.expect(tokLBrace):
      p.errorAt("expected '{' before then-branch")
      return newSeqNode(@[])
    var thenChildren: seq[ASTNode]
    while p.peek().kind != tokRBrace and p.peek().kind != tokEOF:
      thenChildren.add p.parseStatement()
    if not p.expect(tokRBrace):
      p.errorAt("expected '}'")
    let thenBranch = if thenChildren.len == 0:
      newSeqNode(@[])
    elif thenChildren.len == 1:
      thenChildren[0]
    else:
      newSeqNode(thenChildren)

    var elseBranch = newSeqNode(@[])
    if p.peek().kind == tokElse:
      discard p.advance()
      if not p.expect(tokLBrace):
        p.errorAt("expected '{'")
        return newSeqNode(@[])
      var elseChildren: seq[ASTNode]
      while p.peek().kind != tokRBrace and p.peek().kind != tokEOF:
        elseChildren.add p.parseStatement()
      if not p.expect(tokRBrace):
        p.errorAt("expected '}'")
      elseBranch = if elseChildren.len == 0:
        newSeqNode(@[])
      elif elseChildren.len == 1:
        elseChildren[0]
      else:
        newSeqNode(elseChildren)

    return newIfNode(cond, thenBranch, elseBranch)

  of tokWhile:
    discard p.advance()
    if not p.expect(tokLParen):
      p.errorAt("expected '(' after 'while'")
      return newSeqNode(@[])
    let cond = p.parseExpr()
    if not p.expect(tokRParen):
      p.errorAt("expected ')' after condition")
    if not p.expect(tokLBrace):
      p.errorAt("expected '{' before loop body")
      return newSeqNode(@[])
    var bodyChildren: seq[ASTNode]
    while p.peek().kind != tokRBrace and p.peek().kind != tokEOF:
      bodyChildren.add p.parseStatement()
    if not p.expect(tokRBrace):
      p.errorAt("expected '}'")
    let body = if bodyChildren.len == 0:
      newSeqNode(@[])
    elif bodyChildren.len == 1:
      bodyChildren[0]
    else:
      newSeqNode(bodyChildren)
    return newLoopNode(cond, body)

  of tokBefungeOp:
    let op = case tok.lexeme
      of ">": BfRight
      of "<": BfLeft
      of "v": BfDown
      of "^": BfUp
      of "+": BfAdd
      of "-": BfSub
      of "*": BfMul
      of "/": BfDiv
      of "%": BfMod
      of "!": BfNot
      of "`": BfCmpGt
      of ":": BfDup
      of "$": BfPop
      of "g": BfMGet
      of "p": BfMPut
      of ".": BfOutput
      of ",": BfOutputAscii
      of "&": BfInput
      of "@": BfExit
      else:
        p.errorAt("unknown befunge op: " & tok.lexeme)
        discard p.advance()
        return newSeqNode(@[])
    discard p.advance()
    return newBefungeNode(op)

  of tokFATrap:
    discard p.advance()
    if not p.expect(tokLParen):
      p.errorAt("expected '(' after __fa_trap")
      return newSeqNode(@[])
    let descTok = p.peek()
    if descTok.kind != tokNumber:
      p.errorAt("expected address in __fa_trap")
      return newSeqNode(@[])
    let desc = descTok.value
    discard p.advance()
    if not p.expect(tokRParen):
      p.errorAt("expected ')'")
    return newFATrapNode(desc, 0)  # nextPc will be assigned during code gen

  else:
    p.errorAt("unexpected token: " & tok.lexeme)
    discard p.advance()
    return newSeqNode(@[])

# ─────────────────────────────────────────────────────────────────────────────
# Compute memory layout
# ─────────────────────────────────────────────────────────────────────────────

proc computeMemoryLayout*(p: Parser; befungeCodeSize: int = 0; brainfuckTapeCells: int = 256): MemoryLayout =
  var layout = MemoryLayout(
    subleqOverhead: 9,
    variables: p.symbols.mapIt(it[1]),
    varMap: p.symbols.mapIt((it[0], it[1].cellAddr)),
    befungeCodeBase: p.memCounter,
    befungeCodeSize: befungeCodeSize,
    brainfuckTapeBase: p.memCounter + befungeCodeSize,
    brainfuckTapeCells: brainfuckTapeCells,
    totalCells: p.memCounter + befungeCodeSize + brainfuckTapeCells
  )
  layout

# ─────────────────────────────────────────────────────────────────────────────
# Main parsing function: build HybridProgram from input
# ─────────────────────────────────────────────────────────────────────────────

proc parseHybrid*(input: string): HybridProgram =
  var prog = HybridProgram(
    ast: newSeqNode(@[]),
    befungeGrid: BefungeGrid(),
    brainfuckProg: BrainfuckProg(tapeCells: 256),
    variables: @[],
    memoryLayout: MemoryLayout(),
    entryPoint: 9,
    error: ""
  )

  # Try 2D Befunge grid first
  let gridResult = tokenize2DGrid(input)
  let grid = gridResult[0]
  let gridErr = gridResult[1]
  if gridErr == "" and grid.height > 0:
    prog.befungeGrid = grid
    prog.ast = parse2DBerungeGrid(grid)
    prog.memoryLayout = computeMemoryLayout(Parser(), grid.width * grid.height, 256)
    return prog

  # Otherwise, tokenize as BCPL + Brainfuck
  let tokResult = tokenize(input)
  let tokens = tokResult[0]
  let lexErr = tokResult[1]
  if lexErr != "":
    prog.error = lexErr
    return prog

  var p = initParser(tokens)

  # Parse declarations and statements
  while p.peek().kind != tokEOF:
    discard p.parseStatement()
    # (comment nodes are just for declarations; skip them)

  if p.errors.len > 0:
    prog.error = p.errors.join("; ")
    return prog

  prog.variables = p.symbols.mapIt(it[1])
  prog.memoryLayout = p.computeMemoryLayout()
  prog.entryPoint = 9

  prog

	# Hybrid Parser: Build AST from tokens, trace control flow, allocate memory
	#
	# Deterministic parsing of Befunge 2D grids, Brainfuck sequences, and BCPL
	# variable declarations. Produces a unified AST and memory layout.
	#
	# Invariants:
	# - All variables have unique names
	# - All memory addresses are assigned deterministically
	# - All jumps and loops are resolved (no forward references)
	# - Control flow is acyclic for Brainfuck (loops are recognized)

	import hybrid_ast
	import hybrid_lexer
	import sequtils
	import strutils

	# ─────────────────────────────────────────────────────────────────────────────
	# Parser initialization
	# ─────────────────────────────────────────────────────────────────────────────

	proc initParser*(tokens: seq[Token]): Parser =
	Parser(
	tokens: tokens,
	pos: 0,
	symbols: @[],
	memCounter: 9, # Start after SUBLEQ overhead
	error: "",
	errors: @[]
	)

	# ─────────────────────────────────────────────────────────────────────────────
	# Token stream navigation
	# ─────────────────────────────────────────────────────────────────────────────

	proc peek*(p: Parser; offset: int = 0): Token =
	let idx = p.pos + offset
	if idx >= 0 and idx < p.tokens.len: p.tokens[idx] else: Token(kind: tokEOF)

	proc advance*(p: var Parser): Token =
	let tok = p.peek()
	if p.pos < p.tokens.len:
	inc p.pos
	tok

	proc expect*(p: var Parser; kind: TokenKind): bool =
	if p.peek().kind == kind:
	discard p.advance()
	true
	else:
	false

	proc errorAt*(p: var Parser; msg: string) =
	let tok = p.peek()
	let err = "line " & $tok.line & " col " & $tok.col & ": " & msg
	p.errors.add err
	p.error = err

	proc addSymbol*(p: var Parser; v: VarDecl): bool =
	# Check for duplicate
	for item in p.symbols:
	if item[0] == v.name:
	p.errorAt("duplicate variable: " & v.name)
	return false
	p.symbols.add (v.name, v)
	true

	proc lookupSymbol*(p: Parser; name: string): VarDecl =
	for item in p.symbols:
	if item[0] == name:
	return item[1]
	VarDecl() # null/zero value for not found

	# ─────────────────────────────────────────────────────────────────────────────
	# Brainfuck bracket matching (pre-pass)
	# ─────────────────────────────────────────────────────────────────────────────

	proc matchBrackets*(tokens: seq[Token]): (seq[int], string) =
	# Build a jump map: bracket position → matching bracket position
	var jumpMap = newSeq[int](tokens.len)
	var stack: seq[int]
	var errorMsg = ""

	for i, tok in tokens:
	if tok.kind == tokLBracket:
	stack.add i
	elif tok.kind == tokRBracket:
	if stack.len == 0:
	errorMsg = "unmatched ']' at token " & $i
	break
	let j = stack.pop()
	jumpMap[i] = j
	jumpMap[j] = i

	if stack.len > 0 and errorMsg == "":
	errorMsg = "unmatched '['"

	(jumpMap, errorMsg)

	# ─────────────────────────────────────────────────────────────────────────────
	# Parse variable declarations (BCPL-style)
	# ─────────────────────────────────────────────────────────────────────────────

	proc parseVarDecl*(p: var Parser): VarDecl =
	var v = VarDecl(cellAddr: p.memCounter, initialValue: 0, isArray: false)

	# Expect: int name [= initialValue] [;]
	if not p.expect(tokVarDecl):
	p.errorAt("expected 'int'")
	return v

	let nameTok = p.peek()
	if nameTok.kind != tokIdent:
	p.errorAt("expected identifier after 'int'")
	return v
	v.name = nameTok.lexeme
	discard p.advance()

	# Optional array size: [N]
	if p.peek().kind == tokLBracket:
	discard p.advance()
	let sizeTok = p.peek()
	if sizeTok.kind != tokNumber:
	p.errorAt("expected array size")
	return v
	v.arraySize = sizeTok.value
	v.isArray = true
	discard p.advance()
	if not p.expect(tokRBracket):
	p.errorAt("expected ']'")
	return v

	# Optional initializer: = value
	if p.peek().kind == tokAssign:
	discard p.advance()
	let valTok = p.peek()
	if valTok.kind != tokNumber:
	p.errorAt("expected number in initializer")
	return v
	v.initialValue = valTok.value
	discard p.advance()

	# Consume semicolon
	if not p.expect(tokSemicolon):
	p.errorAt("expected ';' after variable declaration")

	# Allocate memory
	v.cellAddr = p.memCounter
	if v.isArray:
	p.memCounter += v.arraySize
	else:
	p.memCounter += 1

	v

	# ─────────────────────────────────────────────────────────────────────────────
	# Parse Brainfuck sequence
	# ─────────────────────────────────────────────────────────────────────────────

	proc parseBrainfuckSeq*(p: var Parser): ASTNode =
	var children: seq[ASTNode]
	let bracketResult = matchBrackets(p.tokens[p.pos ..< p.tokens.len])
	let jumpMap = bracketResult[0]
	let errMsg = bracketResult[1]
	if errMsg != "":
	p.errorAt(errMsg)
	return newSeqNode(@[])

	while p.peek().kind != tokEOF:
	let tok = p.peek()
	case tok.kind
	of tokBefungeOp:
	# Brainfuck-specific operations (>, <, +, -, ., ,, [, ])
	let op = case tok.lexeme
	of ">": BfcPtrInc
	of "<": BfcPtrDec
	of "+": BfcCellInc
	of "-": BfcCellDec
	of ".": BfcOutput
	of ",": BfcInput
	else:
	p.errorAt("invalid brainfuck op: " & tok.lexeme)
	discard p.advance()
	continue
	children.add newBrainfuckNode(op)
	discard p.advance()

	of tokLBracket:
	# Match and parse loop body
	let openIdx = p.pos
	discard p.advance()
	let closeIdx = jumpMap[openIdx]

	# Parse loop body
	var bodyChildren: seq[ASTNode]
	while p.pos < closeIdx and p.peek().kind != tokEOF:
	let bodyTok = p.peek()
	case bodyTok.kind
	of tokBefungeOp:
	let op = case bodyTok.lexeme
	of ">": BfcPtrInc
	of "<": BfcPtrDec
	of "+": BfcCellInc
	of "-": BfcCellDec
	of ".": BfcOutput
	of ",": BfcInput
	else:
	p.errorAt("invalid brainfuck op: " & bodyTok.lexeme)
	discard p.advance()
	continue
	bodyChildren.add newBrainfuckNode(op)
	discard p.advance()
	of tokRBracket:
	break
	else:
	discard p.advance()

	if not p.expect(tokRBracket):
	p.errorAt("expected matching ']'")

	# Loop condition: test if tape[ptr] == 0
	let cond = newBrainfuckNode(BfcCellDec) # dummy; real test is runtime
	let body = if bodyChildren.len == 0:
	newSeqNode(@[])
	elif bodyChildren.len == 1:
	bodyChildren[0]
	else:
	newSeqNode(bodyChildren)
	children.add newLoopNode(cond, body)

	of tokRBracket:
	p.errorAt("unmatched ']'")
	discard p.advance()

	else:
	discard p.advance()

	if children.len == 0:
	newSeqNode(@[])
	elif children.len == 1:
	children[0]
	else:
	newSeqNode(children)

	# ─────────────────────────────────────────────────────────────────────────────
	# Parse 2D Befunge grid
	# ─────────────────────────────────────────────────────────────────────────────

	proc parse2DBerungeGrid*(grid: BefungeGrid): ASTNode =
	# Build a linear AST from the 2D grid (row-major traversal)
	var children: seq[ASTNode]

	for row in 0 ..< grid.height:
	for col in 0 ..< grid.width:
	if col < grid.ops[row].len:
	let op = grid.ops[row][col]
	case op
	of BfNop:
	discard
	of BfPush:
	# Push needs a digit argument; we'll use 0 as placeholder
	children.add newBefungeNode(BfPush, 0)
	of BfRight, BfLeft, BfDown, BfUp:
	children.add newBefungeNode(op)
	of BfAdd, BfSub, BfMul, BfDiv, BfMod:
	children.add newBefungeNode(op)
	of BfNot, BfCmpGt:
	children.add newBefungeNode(op)
	of BfHRotate, BfHRotateL:
	children.add newBefungeNode(op)
	of BfDup, BfPop, BfSwap:
	children.add newBefungeNode(op)
	of BfMGet, BfMPut:
	children.add newBefungeNode(op)
	of BfInput, BfOutput, BfOutputAscii:
	children.add newBefungeNode(op)
	of BfExit:
	children.add newBefungeNode(BfExit)
	break

	if children.len == 0:
	newSeqNode(@[])
	elif children.len == 1:
	children[0]
	else:
	newSeqNode(children)

	# ─────────────────────────────────────────────────────────────────────────────
	# Parse primary expression
	# ─────────────────────────────────────────────────────────────────────────────

	proc parseExpr*(p: var Parser): ASTNode =
	let tok = p.peek()
	case tok.kind
	of tokNumber:
	let val = tok.value
	discard p.advance()
	return newLitNode(val)
	of tokIdent:
	let name = tok.lexeme
	discard p.advance()
	return newVarRefNode(name)
	of tokAmpersand:
	discard p.advance()
	let name = p.peek().lexeme
	if p.peek().kind != tokIdent:
	p.errorAt("expected identifier after '&'")
	return newLitNode(0)
	discard p.advance()
	return newVarRefNode(name, false)
	of tokStar:
	discard p.advance()
	let name = p.peek().lexeme
	if p.peek().kind != tokIdent:
	p.errorAt("expected identifier after '*'")
	return newLitNode(0)
	discard p.advance()
	return newVarRefNode(name, true)
	else:
	p.errorAt("unexpected token in expression: " & tok.lexeme)
	discard p.advance()
	return newLitNode(0)

	# ─────────────────────────────────────────────────────────────────────────────
	# Parse statement (top-level production)
	# ─────────────────────────────────────────────────────────────────────────────

	proc parseStatement*(p: var Parser): ASTNode =
	let tok = p.peek()
	case tok.kind
	of tokVarDecl:
	let v = p.parseVarDecl()
	if p.addSymbol(v):
	# Successful declaration; return comment node (no code generation)
	return newCommentNode("declare " & v.name)
	else:
	return newSeqNode(@[])

	of tokIf:
	discard p.advance()
	if not p.expect(tokLParen):
	p.errorAt("expected '(' after 'if'")
	return newSeqNode(@[])
	let cond = p.parseExpr()
	if not p.expect(tokRParen):
	p.errorAt("expected ')' after condition")
	if not p.expect(tokLBrace):
	p.errorAt("expected '{' before then-branch")
	return newSeqNode(@[])
	var thenChildren: seq[ASTNode]
	while p.peek().kind != tokRBrace and p.peek().kind != tokEOF:
	thenChildren.add p.parseStatement()
	if not p.expect(tokRBrace):
	p.errorAt("expected '}'")
	let thenBranch = if thenChildren.len == 0:
	newSeqNode(@[])
	elif thenChildren.len == 1:
	thenChildren[0]
	else:
	newSeqNode(thenChildren)

	var elseBranch = newSeqNode(@[])
	if p.peek().kind == tokElse:
	discard p.advance()
	if not p.expect(tokLBrace):
	p.errorAt("expected '{'")
	return newSeqNode(@[])
	var elseChildren: seq[ASTNode]
	while p.peek().kind != tokRBrace and p.peek().kind != tokEOF:
	elseChildren.add p.parseStatement()
	if not p.expect(tokRBrace):
	p.errorAt("expected '}'")
	elseBranch = if elseChildren.len == 0:
	newSeqNode(@[])
	elif elseChildren.len == 1:
	elseChildren[0]
	else:
	newSeqNode(elseChildren)

	return newIfNode(cond, thenBranch, elseBranch)

	of tokWhile:
	discard p.advance()
	if not p.expect(tokLParen):
	p.errorAt("expected '(' after 'while'")
	return newSeqNode(@[])
	let cond = p.parseExpr()
	if not p.expect(tokRParen):
	p.errorAt("expected ')' after condition")
	if not p.expect(tokLBrace):
	p.errorAt("expected '{' before loop body")
	return newSeqNode(@[])
	var bodyChildren: seq[ASTNode]
	while p.peek().kind != tokRBrace and p.peek().kind != tokEOF:
	bodyChildren.add p.parseStatement()
	if not p.expect(tokRBrace):
	p.errorAt("expected '}'")
	let body = if bodyChildren.len == 0:
	newSeqNode(@[])
	elif bodyChildren.len == 1:
	bodyChildren[0]
	else:
	newSeqNode(bodyChildren)
	return newLoopNode(cond, body)

	of tokBefungeOp:
	let op = case tok.lexeme
	of ">": BfRight
	of "<": BfLeft
	of "v": BfDown
	of "^": BfUp
	of "+": BfAdd
	of "-": BfSub
	of "*": BfMul
	of "/": BfDiv
	of "%": BfMod
	of "!": BfNot
	of "`": BfCmpGt
	of ":": BfDup
	of "$": BfPop
	of "g": BfMGet
	of "p": BfMPut
	of ".": BfOutput
	of ",": BfOutputAscii
	of "&": BfInput
	of "@": BfExit
	else:
	p.errorAt("unknown befunge op: " & tok.lexeme)
	discard p.advance()
	return newSeqNode(@[])
	discard p.advance()
	return newBefungeNode(op)

	of tokFATrap:
	discard p.advance()
	if not p.expect(tokLParen):
	p.errorAt("expected '(' after __fa_trap")
	return newSeqNode(@[])
	let descTok = p.peek()
	if descTok.kind != tokNumber:
	p.errorAt("expected address in __fa_trap")
	return newSeqNode(@[])
	let desc = descTok.value
	discard p.advance()
	if not p.expect(tokRParen):
	p.errorAt("expected ')'")
	return newFATrapNode(desc, 0) # nextPc will be assigned during code gen

	else:
	p.errorAt("unexpected token: " & tok.lexeme)
	discard p.advance()
	return newSeqNode(@[])

	# ─────────────────────────────────────────────────────────────────────────────
	# Compute memory layout
	# ─────────────────────────────────────────────────────────────────────────────

	proc computeMemoryLayout*(p: Parser; befungeCodeSize: int = 0; brainfuckTapeCells: int = 256): MemoryLayout =
	var layout = MemoryLayout(
	subleqOverhead: 9,
	variables: p.symbols.mapIt(it[1]),
	varMap: p.symbols.mapIt((it[0], it[1].cellAddr)),
	befungeCodeBase: p.memCounter,
	befungeCodeSize: befungeCodeSize,
	brainfuckTapeBase: p.memCounter + befungeCodeSize,
	brainfuckTapeCells: brainfuckTapeCells,
	totalCells: p.memCounter + befungeCodeSize + brainfuckTapeCells
	)
	layout

	# ─────────────────────────────────────────────────────────────────────────────
	# Main parsing function: build HybridProgram from input
	# ─────────────────────────────────────────────────────────────────────────────

	proc parseHybrid*(input: string): HybridProgram =
	var prog = HybridProgram(
	ast: newSeqNode(@[]),
	befungeGrid: BefungeGrid(),
	brainfuckProg: BrainfuckProg(tapeCells: 256),
	variables: @[],
	memoryLayout: MemoryLayout(),
	entryPoint: 9,
	error: ""
	)

	# Try 2D Befunge grid first
	let gridResult = tokenize2DGrid(input)
	let grid = gridResult[0]
	let gridErr = gridResult[1]
	if gridErr == "" and grid.height > 0:
	prog.befungeGrid = grid
	prog.ast = parse2DBerungeGrid(grid)
	prog.memoryLayout = computeMemoryLayout(Parser(), grid.width * grid.height, 256)
	return prog

	# Otherwise, tokenize as BCPL + Brainfuck
	let tokResult = tokenize(input)
	let tokens = tokResult[0]
	let lexErr = tokResult[1]
	if lexErr != "":
	prog.error = lexErr
	return prog

	var p = initParser(tokens)

	# Parse declarations and statements
	while p.peek().kind != tokEOF:
	discard p.parseStatement()
	# (comment nodes are just for declarations; skip them)

	if p.errors.len > 0:
	prog.error = p.errors.join("; ")
	return prog

	prog.variables = p.symbols.mapIt(it[1])
	prog.memoryLayout = p.computeMemoryLayout()
	prog.entryPoint = 9

	prog