> For the complete documentation index, see [llms.txt](https://quarkdown.com/wiki/llms.txt).

# Pipeline - Parsing

> Main packages: [`core.parser`](https://github.com/iamgio/quarkdown/tree/main/quarkdown-core/src/main/kotlin/com/quarkdown/core/parser), [`core.ast`](https://github.com/iamgio/quarkdown/tree/main/quarkdown-core/src/main/kotlin/com/quarkdown/core/ast)

Continuing with the metaphor introduced in [Lexing](pipeline---lexing.md), once the nouns, verbs, and adjectives are extracted from a sentence, our brain is responsible for linking them together to build information out of them.

The parser takes the sequence of tokens and organizes them into a tree structure called an *Abstract Syntax Tree* (AST), which defines the relationships between different parts of the document. Each element of the tree is called a *Node*.

---

Example Markdown input:

```markdown
## Title

This is **bold** and _italic_ text.

- Item 1
- Item 2
```

Output AST:

- `AstRoot`

  - `Heading(depth=1)`

    - `Text("Title")`
  - `Paragraph`

    - `Text("This is ")`
    - `Strong("bold")`
    - `Text(" and ")`
    - `Emphasis("italic")`
    - `Text(" text")`
  - `UnorderedList`

    - `ListItem`

      - `Paragraph`

        - `Text("Item 1")`
    - `ListItem`

      - `Paragraph`

        - `Text("Item 2")`

---

The *lexing* stage produces just the outer blocks, which in this example are a `HeadingToken`, a `ParagraphToken`, and an `UnorderedListToken`.

To gain nested information, the parser analyzes each token and starts searching in depth for nested blocks and inlines.

- For each block token, the parser triggers the lexing stage on its inner content (*lexeme*)
- Once the inner tokens are extracted, they undergo the parsing stage again
- This process continues until no more nested tokens remain. This is called **recursive parsing**, visualized in the following figure:

<img src="media/recursive-parsing@1016067414.svg" alt="Recursive parsing" width="200.0px" />