Abstracte syntaxis

Abstracte syntaxis is een representatie van gegevens, vaak een bericht dat over een communicatiekanaal wordt verstuurd of een computerprogramma dat wordt gecompileerd, die onafhankelijk is van de datastructuur en coderingen, die zelf wel van de gebruikte computer afhangen, en ook van de werkelijke representatie van de gegevens, in het geval van compileren de concrete syntaxis genoemd en bij communicatie de transfersyntaxis.

Een compiler dat een computerprogramma naar machinetaal omzet, geeft onder andere aan hoe de variabelen en identifiers die in het programma voorkomen, moeten worden behandeld. Variabelen en identifiers worden dus ergens vastgelegd. Hun representatie is onafhankelijk van de syntaxis van de broncode, de concrete syntaxis, van het programma dat wordt gecompileerd, ook al kunnen de representatie in de broncode en de machinetaal vaak goed met elkaar worden vergeleken. Een syntaxisboom lijkt veel op een abstracte syntaxisboom, maar er kunnen bijvoorbeeld haakjes in voorkomen, die voor de syntaxis van de machinetaal wel van belang zijn. Dit soort zaken worden in de abstracte syntaxisboom impliciet gelaten.

De abstracte syntaxis in functionele programmeertalen kan vaak rechtstreeks aan de hand van de formele grammatica worden geconstrueerd. Stel we hebben een formele grammatica met de volgende productieregels:

${\displaystyle S\rightarrow aS}$

${\displaystyle S\rightarrow bSS}$

${\displaystyle S\rightarrow c}$

In de programmeertaal Haskell kan dit gerepresenteerd worden met:

data S = CaseA S | CaseB S S | CaseC

De string abac, de concrete syntaxis kan met de volgende abstracte syntaxis worden weergegeven:

CaseA (CaseB (CaseA CaseC) CaseC)

Deze representatie kan ook als een boomstructuur worden gezien, waarbij CaseA de wortel is met CaseB als kind, en hetzelfde voor de andere componenten. Dit wordt de abstracte syntaxisboom genoemd.

De conversie tussen de abstracte syntaxis en de concrete syntaxis is vrij eenvoudig:

toConcrete :: S -> String toConcrete (CaseA x) = "a" ++ toConcrete x toConcrete (CaseB x y) = "b" ++ toConcrete x ++ toConcrete y toConcrete CaseC = "c" 

Voor het omzetten van de concrete syntaxis naar abstracte syntaxis wordt een parser gebruikt.