parsetræ

A parsetræ, også kendt som en syntaktisk træstruktur eller parse-træ, er en grafisk repræsentation af den syntaktiske struktur af en sætning eller udtryk i et programmeringssprog, en formal sprog eller en naturligt sprog. Det bruges primært inden for lingvistik, computervidenskab og formel grammatik til at visualisere, hvordan elementer i en sætning eller et udtryk er organiseret og relateret til hinanden i overensstemmelse med reglerne i en given grammatik.

Parse-træer konstrueres ved hjælp af en parser, en algoritme eller et program, der analyserer en inputstreng (f.eks. en sætning eller en kodelinje) og opdeler den i mindre, betydningsfulde dele, der følger grammatikreglerne. Hvert knudepunkt i træet repræsenterer enten et terminalt symbol (f.eks. et ord eller en token) eller et ikke-terminalt symbol (f.eks. en grammatisk kategori som "sætning" eller "subjekt"). Terminaler er bladene i træet, mens ikke-terminaler er indre knudepunkter, der repræsenterer syntaktiske kategorier.

I naturlige sprog bruges parse-træer til at analysere sætninger og forstå deres struktur, hvilket er vigtigt for maskinoversættelse, tekstgenkendelse og sprogforståelse. I programmeringssprog hjælper parse-træer med at validere og analysere koden, så den kan oversættes til maskinkode eller udføres korrekt. Parse-træer kan også bruges til at optimere koden eller generere abstrakt syntaks (AST), der er en forenklet version af parse-træet, der fjerner unødvendige detaljer og fokuserer på den semantiske struktur.

Parse-træer er et centralt koncept inden for teoretisk computervidenskab og lingvistik, da de giver et klart og struktureret værktøj til at undersøge og beskrive syntaktiske relationer i sprog og programmer. Der findes forskellige typer af parse-træer, herunder binære parse-træer, hvor hvert ikke-terminalt knudepunkt har højst to børn, og ikke-binære parse-træer, der tillader flere børn pr. knudepunkt. Valget af parse-træ-type afhænger af den anvendte grammatik og det specifikke formål med analysen.