De auteur bespreekt een alternatieve benadering voor het schrijven van parsers door gebruik te maken van Tree-sitter, een parser-generator die concrete syntax trees produceert. In plaats van traditionele parsing, hanteert de auteur een proces gebaseerd op vier specifieke constraints: check-queries, parse-corpus, extract-golden en highlight-golden. Door deze constraints te combineren met diffs en ondersteuning van coding agents, kan de parser iteratief worden verbeterd. Dit proces leidde tot de creatie van tree-sitter-haskell-contrib, met grammatica's voor onder andere .cabal-bestanden, cabal.project en GHC dumps.
Hoe je géén parsers schrijft
Deze tekst is gebaseerd op een presentatie die ik heb gegeven; de dia's hiervan zijn online te vinden.
Ik gebruik Helix als mijn favoriete editor. Deze maakt gebruik van tree-sitter als mechanisme voor syntaxhighlighting. Ik ben erg enthousiast over Haskell, maar helaas was de tree-sitter grammatica voor .cabal-bestanden verwijderd uit de Helix-repository omdat deze nog in een vroeg stadium van ontwikkeling (WIP) verkeerde.
Er bestond al een grammatica van Magnus Therning en een pull request van Ananda Umamil om segmentatiefouten (segfaults) te herstellen; dit is wat ik een tijd lang heb gebruikt. Toen ik echter ook ondersteuning wilde voor cabal.project, was dat voldoende motivatie om alles volledig te vernieuwen.
Hoe je in bomen zit
Tree-sitter is een parser-generator DSL. Je schrijft een grammatica in JavaScript, deze genereert een incrementele parser in C, en het resultaat is een concrete syntax tree.
readFields :: ByteString -> Either ParseError [Field] -- Cabal
parse :: Text -> Tree -- tree-sitter
Het eerste mooie aan tree-sitter parsers is dat ze 'totaal' zijn. Ze falen niet als er parsing-fouten optreden. In plaats daarvan versiert de parser de parse-tree met ERROR- of MISSING-nodes.
Voorbeeld: library (library build-depends base >= 4.9 ~> type: (sectiontype)) → ^ geen dubbele punt (ERROR (fieldname) (identifier) ...)
Het tweede sterke punt is hoe eenvoudig het is om semantiek aan deze parse-trees te koppelen. Dit gebeurt via tree-sitter queries die via pattern matching op de parse-tree specifieke nodes annoteren en vastleggen (captures). Deze captures kunnen vervolgens door downstream-applicaties worden gebruikt voor functies zoals 'go-to-symbol', waarbij alle symbolen in een bestand worden geïsoleerd.
match :: Query -> Tree -> [Match]
Deze matching van queries en trees vormt een relatie. Eén patroon kan op meerdere plaatsen iets vastleggen, en één node kan betrokken zijn bij verschillende query-captures. De punt in hs-source-dirs: . kan bijvoorbeeld zowel een pad-capture als een gewone string-capture matchen in een enkel token.
De volledige tree-sitter pipeline kan dus worden opgesplitst in:
- Een totale parse.
- Een relationele match.
- Een fold die captures omzet in willekeurig gedrag, wat uiteindelijk de actie van de gebruiker bepaalt.
Grammatica en query's in een boom
Een grammatica en de bijbehorende queries vormen een punt in een oplossingsruimte van mogelijke nuttige parsers. Aan de ene kant hebben we een parser die de lege taal parseert, en aan de andere kant één die alle mogelijke strings accepteert. De cabal-parser die we willen, bevindt zich ergens tussen deze twee uitersten.
Ik kan dit formuleren als een zoektocht. Gegeven constraints $C1, \ldots, Cn$, waarbij elke constraint een fold is van de Tree naar een monoid $Mi$, en verwachte waarden $ei$ over een vaste set $X$, zoeken we $g$ zodanig dat:
$Ci(\mathrm{parse}g\; x) = e_i(x) \qquad \forall i,\; \forall x \in X$
De vrije variabele $g$ is het paar (grammatica, queries), aangezien hun definities aan elkaar gekoppeld zijn.
De verwachte waarden $e_i$ verschuiven technisch gezien ook wanneer de constraints veranderen. Ik kan dit echter handmatig in balans houden via diffs. Telkens wanneer de grammatica of query verandert en aan alle constraints is voldaan, hebben we een geldige parser uit de oplossingsruimte in handen. De volgende stap is het zorgvuldig kiezen van de constraints, zodat deze precies overeenkomen met de functies die we van de parser verwachten.
Mijn boom kiezen
Ik heb de volgende vier constraints (die in dit geval uitwisselbaar zijn met tests) gebruikt:
- check-queries: Deze controleert of de patronen in elke query compatibel zijn met de gegenereerde parser. Een patroon als
(librari ...) is bijvoorbeeld een ongeldig nodetype, omdat dit library moet zijn.
- parse-corpus: Hoewel tree-sitter niet faalt bij ongeldige parses, weten we zeker dat de parse-trees uit onze tests geen foutnodes mogen bevatten. Deze constraint stelt vast dat er over een groot corpus geen
ERROR- of MISSING-nodes voorkomen. Voor dit corpus heb ik 968 bestanden verzameld uit de cabal en haskell-language-server repositories, met een mediane lengte van 14 regels.
- extract-golden: Wat er precies wordt vastgelegd (captured) is vrij ondoorzichtig. Een 'golden testsuite' legt dit vast door de aanwezigheid van bepaalde captures, inclusief hun locatie en inhoud, af te dwingen op basis van een kleine testset. Deze set is bewust klein gehouden om reviews gemakkelijk te maken.
- highlight-golden: Aangezien syntaxhighlighting mijn oorspronkelijke use-case was, is het logisch om dit als test vast te leggen. We dwingen af dat symbolen die we verwachten te highlighten, ook daadwerkelijk worden gematcht. Per token wint er slechts één capture, omdat er uiteindelijk maar één kleur kan worden getoond. Omdat de query-file hier de daadwerkelijke highlighting uitvoert, is dit een betere representatie dan de versie gebruikt in
extract-golden.
Zoeken door het bos
Dankzij deze constraints kunnen wijzigingen in de grammatica of queries worden gerenderd en vergeleken via diffs. Dit maakt het eenvoudig om hier een feedbackloop van te maken die bruikbaar is voor een coding agent.
De output van zo'n agent is gebonden om fouten te bevatten, maar een deel is nuttig. De agent stelt een wijziging in de grammatica of query voor en controleert vervolgens alle vier de constraints. Groen betekent dat het klaar is; rood geeft aan waar er een regressie is opgetreden.
Dit vereist nog steeds menselijke interventie. Er zijn een oneindig aantal geldige parsers die aan alle tests voldoen, maar die niet per se de parser- of query-opstelling zijn die ik zoek. De ideale opstelling is subjectief.
Men zou kunnen proberen dit te formuleren als een meetbare metric om het objectief te maken, maar de keuze van die metric zal waarschijnlijk ook subjectief blijven. De menselijke stap — het lezen van de diff en het testen van de grammatica in een echt bestand — blijft noodzakelijk. Gelukkig zijn diffs makkelijker te reviewen dan complexe reguliere expressies.
Het resultaat van dit experiment is tree-sitter-haskell-contrib, dat grammatica's bevat voor .cabal, cabal.project en de Core, STG en Cmm dumps van GHC.
Hoe je géén parsers schrijft
Deze tekst is gebaseerd op een presentatie die ik heb gegeven; de dia's hiervan zijn online te vinden.
Ik gebruik Helix als mijn favoriete editor. Deze maakt gebruik van tree-sitter als mechanisme voor syntaxhighlighting. Ik ben erg enthousiast over Haskell, maar helaas was de tree-sitter grammatica voor .cabal-bestanden verwijderd uit de Helix-repository omdat deze nog in een vroeg stadium van ontwikkeling (WIP) verkeerde.
Er bestond al een grammatica van Magnus Therning en een pull request van Ananda Umamil om segmentatiefouten (segfaults) te herstellen; dit is wat ik een tijd lang heb gebruikt. Toen ik echter ook ondersteuning wilde voor cabal.project, was dat voldoende motivatie om alles volledig te vernieuwen.
Hoe je in bomen zit
Tree-sitter is een parser-generator DSL. Je schrijft een grammatica in JavaScript, deze genereert een incrementele parser in C, en het resultaat is een concrete syntax tree.
readFields :: ByteString -> Either ParseError [Field] -- Cabal
parse :: Text -> Tree -- tree-sitter
Het eerste mooie aan tree-sitter parsers is dat ze 'totaal' zijn. Ze falen niet als er parsing-fouten optreden. In plaats daarvan versiert de parser de parse-tree met ERROR- of MISSING-nodes.
Voorbeeld: library (library build-depends base >= 4.9 ~> type: (sectiontype)) → ^ geen dubbele punt (ERROR (fieldname) (identifier) ...)
Het tweede sterke punt is hoe eenvoudig het is om semantiek aan deze parse-trees te koppelen. Dit gebeurt via tree-sitter queries die via pattern matching op de parse-tree specifieke nodes annoteren en vastleggen (captures). Deze captures kunnen vervolgens door downstream-applicaties worden gebruikt voor functies zoals 'go-to-symbol', waarbij alle symbolen in een bestand worden geïsoleerd.
match :: Query -> Tree -> [Match]
Deze matching van queries en trees vormt een relatie. Eén patroon kan op meerdere plaatsen iets vastleggen, en één node kan betrokken zijn bij verschillende query-captures. De punt in hs-source-dirs: . kan bijvoorbeeld zowel een pad-capture als een gewone string-capture matchen in een enkel token.
De volledige tree-sitter pipeline kan dus worden opgesplitst in:
- Een totale parse.
- Een relationele match.
- Een fold die captures omzet in willekeurig gedrag, wat uiteindelijk de actie van de gebruiker bepaalt.
Grammatica en query's in een boom
Een grammatica en de bijbehorende queries vormen een punt in een oplossingsruimte van mogelijke nuttige parsers. Aan de ene kant hebben we een parser die de lege taal parseert, en aan de andere kant één die alle mogelijke strings accepteert. De cabal-parser die we willen, bevindt zich ergens tussen deze twee uitersten.
Ik kan dit formuleren als een zoektocht. Gegeven constraints $C1, \ldots, Cn$, waarbij elke constraint een fold is van de Tree naar een monoid $Mi$, en verwachte waarden $ei$ over een vaste set $X$, zoeken we $g$ zodanig dat:
$Ci(\mathrm{parse}g\; x) = e_i(x) \qquad \forall i,\; \forall x \in X$
De vrije variabele $g$ is het paar (grammatica, queries), aangezien hun definities aan elkaar gekoppeld zijn.
De verwachte waarden $e_i$ verschuiven technisch gezien ook wanneer de constraints veranderen. Ik kan dit echter handmatig in balans houden via diffs. Telkens wanneer de grammatica of query verandert en aan alle constraints is voldaan, hebben we een geldige parser uit de oplossingsruimte in handen. De volgende stap is het zorgvuldig kiezen van de constraints, zodat deze precies overeenkomen met de functies die we van de parser verwachten.
Mijn boom kiezen
Ik heb de volgende vier constraints (die in dit geval uitwisselbaar zijn met tests) gebruikt:
- check-queries: Deze controleert of de patronen in elke query compatibel zijn met de gegenereerde parser. Een patroon als
(librari ...) is bijvoorbeeld een ongeldig nodetype, omdat dit library moet zijn.
- parse-corpus: Hoewel tree-sitter niet faalt bij ongeldige parses, weten we zeker dat de parse-trees uit onze tests geen foutnodes mogen bevatten. Deze constraint stelt vast dat er over een groot corpus geen
ERROR- of MISSING-nodes voorkomen. Voor dit corpus heb ik 968 bestanden verzameld uit de cabal en haskell-language-server repositories, met een mediane lengte van 14 regels.
- extract-golden: Wat er precies wordt vastgelegd (captured) is vrij ondoorzichtig. Een 'golden testsuite' legt dit vast door de aanwezigheid van bepaalde captures, inclusief hun locatie en inhoud, af te dwingen op basis van een kleine testset. Deze set is bewust klein gehouden om reviews gemakkelijk te maken.
- highlight-golden: Aangezien syntaxhighlighting mijn oorspronkelijke use-case was, is het logisch om dit als test vast te leggen. We dwingen af dat symbolen die we verwachten te highlighten, ook daadwerkelijk worden gematcht. Per token wint er slechts één capture, omdat er uiteindelijk maar één kleur kan worden getoond. Omdat de query-file hier de daadwerkelijke highlighting uitvoert, is dit een betere representatie dan de versie gebruikt in
extract-golden.
Zoeken door het bos
Dankzij deze constraints kunnen wijzigingen in de grammatica of queries worden gerenderd en vergeleken via diffs. Dit maakt het eenvoudig om hier een feedbackloop van te maken die bruikbaar is voor een coding agent.
De output van zo'n agent is gebonden om fouten te bevatten, maar een deel is nuttig. De agent stelt een wijziging in de grammatica of query voor en controleert vervolgens alle vier de constraints. Groen betekent dat het klaar is; rood geeft aan waar er een regressie is opgetreden.
Dit vereist nog steeds menselijke interventie. Er zijn een oneindig aantal geldige parsers die aan alle tests voldoen, maar die niet per se de parser- of query-opstelling zijn die ik zoek. De ideale opstelling is subjectief.
Men zou kunnen proberen dit te formuleren als een meetbare metric om het objectief te maken, maar de keuze van die metric zal waarschijnlijk ook subjectief blijven. De menselijke stap — het lezen van de diff en het testen van de grammatica in een echt bestand — blijft noodzakelijk. Gelukkig zijn diffs makkelijker te reviewen dan complexe reguliere expressies.
Het resultaat van dit experiment is tree-sitter-haskell-contrib, dat grammatica's bevat voor .cabal, cabal.project en de Core, STG en Cmm dumps van GHC.
Groetjes,