scratch/brainfuck/src/gbf/internal/parser.gleam (view raw)
| 1 | import gbf/internal/lexer.{type Position, Position} |
| 2 | import gbf/internal/token.{type Token} |
| 3 | import gleam/list |
| 4 | import gleam/pair |
| 5 | import gleam/result |
| 6 | |
| 7 | pub type AST { |
| 8 | /// A single command |
| 9 | /// |
| 10 | Leaf(Command) |
| 11 | |
| 12 | /// A block with nested children (used for loops) |
| 13 | /// |
| 14 | Node(Block) |
| 15 | } |
| 16 | |
| 17 | pub type Command = |
| 18 | #(Token, Position) |
| 19 | |
| 20 | pub type Block { |
| 21 | Block(children: List(AST), position: Position) |
| 22 | } |
| 23 | |
| 24 | pub type Error { |
| 25 | FinishedTooEarly |
| 26 | UnexpectedCommand |
| 27 | UnexpectedBlock |
| 28 | } |
| 29 | |
| 30 | /// Parses a list of tokens into an Abstract Syntax Tree. |
| 31 | /// |
| 32 | /// Takes a flat list of tokens with their positions and constructs |
| 33 | /// a hierarchical tree structure where loop blocks become nested nodes. |
| 34 | /// All tokens must be consumed for successful parsing. |
| 35 | /// |
| 36 | pub fn parse(tokens: List(#(Token, Position))) -> Result(AST, Error) { |
| 37 | let root = Node(Block(children: [], position: Position(0))) |
| 38 | use #(ast, remaining_tokens) <- result.try(parse_tokens(tokens, root)) |
| 39 | |
| 40 | case remaining_tokens { |
| 41 | [] -> Ok(ast) |
| 42 | _ -> Error(FinishedTooEarly) |
| 43 | } |
| 44 | } |
| 45 | |
| 46 | fn parse_tokens(tokens: List(#(Token, Position)), node: AST) { |
| 47 | case tokens { |
| 48 | [] -> Ok(#(node, [])) |
| 49 | [token, ..rest] -> { |
| 50 | case token { |
| 51 | #(token.StartBlock, _) -> parse_block(token, rest, node) |
| 52 | #(token.EndBlock, _) -> parse_block_end(rest, node) |
| 53 | _ -> parse_command(token, rest, node) |
| 54 | } |
| 55 | } |
| 56 | } |
| 57 | } |
| 58 | |
| 59 | fn parse_block_end(tokens: List(#(Token, Position)), node: AST) { |
| 60 | Ok(#(node, tokens)) |
| 61 | } |
| 62 | |
| 63 | fn parse_block(token, tokens, node) { |
| 64 | case node { |
| 65 | Leaf(_) -> Error(UnexpectedCommand) |
| 66 | Node(block) -> { |
| 67 | let child_block = Node(Block(children: [], position: pair.second(token))) |
| 68 | use #(parsed_child_block, remaining_tokens) <- result.try(parse_tokens( |
| 69 | tokens, |
| 70 | child_block, |
| 71 | )) |
| 72 | |
| 73 | let children = list.append(block.children, [parsed_child_block]) |
| 74 | let node = Node(Block(children: children, position: block.position)) |
| 75 | |
| 76 | parse_tokens(remaining_tokens, node) |
| 77 | } |
| 78 | } |
| 79 | } |
| 80 | |
| 81 | fn parse_command( |
| 82 | token: #(Token, Position), |
| 83 | tokens: List(#(Token, Position)), |
| 84 | node: AST, |
| 85 | ) { |
| 86 | case node { |
| 87 | Leaf(_) -> Error(UnexpectedBlock) |
| 88 | Node(block) -> { |
| 89 | let command = Leaf(token) |
| 90 | let node = |
| 91 | Node(Block( |
| 92 | children: list.append(block.children, [command]), |
| 93 | position: block.position, |
| 94 | )) |
| 95 | |
| 96 | parse_tokens(tokens, node) |
| 97 | } |
| 98 | } |
| 99 | } |