PEG versus een berg reguliere expressies

Org-mode lijkt eenvoudig totdat je het daadwerkelijk probeert te parsen. Koppen zijn makkelijk. Een paragraaf is makkelijk. Een lijst is makkelijk (wacht, eigenlijk niet; daar ben ik van gaan zweten).

Plotseling heb je te maken met:

• Geneste lijsten
• Geordende, ongeordende en beschrijvingslijsten
• Verschillende inspringingsniveaus
• Inline markup
• Links met beschrijvingen
• Source blocks
• Example blocks
• Quote blocks
• Tabellen
• Escaping
• Constructies die de input op precies het juiste moment moeten stoppen met consumeren

Op dit punt wordt de gebruikelijke aanpak van het toevoegen van nog een reguliere expressie enigszins... avontuurlijk. :-) Je eindigt met logica zoals: match dit, tenzij dat erop volgt, behalve binnen dit blok, tenzij het een beschrijving is, maar consumeer de nieuwe regel niet, tenzij de vorige regel een lijstitem was...

Dat is geen beschrijving meer van een taal. Het is een beschrijving van de geschiedenis van de bugs in je parser.

Daarom gebruikt OrgWebAlchemy Parsing Expression Grammars (PEGs) via de uitstekende (ice-9 peg) module van Guile. Bijvoorbeeld:

(define-peg-pattern element body
  (or empty-line
      heading
      separator
      table
      src-block
      quote-block
      example-block
      export-html-block
      description-list
      unordered-list
      ordered-list
      paragraph))

Dit is erg prettig, omdat de grammatica zelf begint te lijken op documentatie voor de taal. Bovendien stelt Guile ons in staat om PEGs direct uit te drukken als S-expressions (alternatief kun je de traditionele syntax gebruiken), wat de Lisper in mij erg gelukkig maakt.

Wat ik vooral waardeer aan deze aanpak, is de losse koppeling: het detail van het genereren van SXML en het vervolgens renderen van HTML is een kwestie van "presentatie". Dit opent mogelijkheden om later naar Markdown of andere formaten te exporteren.

Bijvoorbeeld:

- name :: Josep
- project :: orgwebalchemy
- language :: Scheme

Kan worden omgezet in een AST in de trant van:

(description-list
  (unordered-item
    (desc-key "name")
    (line-content "Josep"))
  ...)

Ik ben nog bezig met de exacte representatie om alles correct te krijgen, maar versie 1.0 is inmiddels redelijk stabiel. Ik zou erg veel waarde hechten aan feedback op het project.

Natuurlijk is Org-mode een enorm stuk (geweldige) software, dus ik ben nog ver verwijderd van het ondersteunen van alle functies, maar enkele belangrijke kernconstructies zijn aanwezig:

• Koppen (regels beginnend met $n$ *)
• Paragrafen (alle "niet-speciale" tekst)
• Ongeordende, geordende en beschrijvingslijsten (met elk niveau van nesting)
• Cursief, vet, inline code
• Links met en zonder beschrijving (met geneste parsing)
• Horizontale scheidingslijnen (vijf of meer streepjes ---–—)
• Tabellen
• #+begin_src
• #+begin_example
• #+begin_quote (met geneste parsing)
• #+begin_export html: De Org-syntax wordt geparsed door de PEG-grammatica, maar ruwe HTML-exportblokken omzeilen de Org-inline-parser en worden als vertrouwde letterlijke output uitgezonden.

Hoera, recursieve lijsten

Een van de leuke onderdelen was het correct krijgen van geneste Org-lijsten. Iets als:

• Item 1
• Item 1.1
• Item 1.2
• Item 2

zou een quasi-boomstructuur moeten worden. De parser produceert aanvankelijk een platte sequentie van lijstitems, en de fase van AST-verwerking zet de inspringing om in een geneste structuur. De HTML-renderer kan vervolgens natuurlijk het volgende produceren:

<ul>
  <li>
    Item 1
    <ul>
      <li>Item 1.1</li>
      <li>Item 1.2</li>
    </ul>
  </li>
  <li>Item 2</li>
</ul>

Ik heb hier nog een klein probleem met het mengen van verschillende lijsttypes in een geneste manier. Hopelijk is dit een subtiele bug die makkelijk op te lossen is.

Voor de HTML-kant gebruik ik SXML, want als we toch Lisp schrijven, kunnen we onze HTML net zo goed representeren als Lisp-data. :-) Dat helpt enorm en maakt het bouwen van de markup-boom veel aangenamer.

Ik heb ervoor gezorgd dat de output HTML volledig aanpasbaar is (via Guile-parameters), zodat de renderer niet hard-coded is naar het idee van één specifieke website over hoe HTML eruit moet zien. De meeste parameters zijn eenvoudige lijsten van klassen, maar aanpassing per kop-niveau is iets flexibeler:

(heading-classes
  (lambda (level)
    (case level
      ((1) '("text-4xl" "font-bold"))
      ((2) '("text-2xl" "font-semibold"))
      (else '("text-base")))))

Waarom maak ik dit?

Deels omdat ik het wilde, ik hou van een uitdaging, en het is superleuk om te werken met parsing, AST's en dergelijke... Ik zou gewoon Emacs kunnen gebruiken voor dit werk, aangezien er geen betere implementatie van Org bestaat.

Maar zoals het nu vorm krijgt, spreekt het idee me aan om een kleine, hackbare free-software Org-parser in Lisp te hebben die anderen kunnen uitbreiden en aanpassen (bijvoorbeeld door meer renderers of Org-functies toe te voegen).

Vrije software

OrgWebAlchemy is gelicentieerd onder de GNU LGPL v3 of later. Het project is bedoeld om binnenkort beschikbaar te komen voor GNU Guix als guile-orgwebalchemy. Er is ook een test suite in de repository die zich al bewijst als een goed vangnet en een showcase van wat de parser kan.

Slotgedachten

Ik hoor graag jullie gedachten, vooral over de grammatica, het AST-ontwerp, de architectuur van de parser of interessante Org-constructies die ik nog niet heb behandeld.

Happy hacking! ✨