parsetræer

Parsetræer er træstrukturer, der viser den syntaktiske struktur af en streng i henhold til et regelsæt. I lingvistik kaldes de ofte sætningstræer eller sætningsstrukturer og illustrerer, hvordan en sætning er afledt gennem produktionsregler i en kontekstfri grammatik. Roden er start-symbolet (typisk S); indre noder bærer syntaktiske kategorier som NP, VP og PP; bladene er terminale symboler (ordene i sætningen). Parsetræet viser hele afledningen fra start til ordene og hjælper med at identificere relationer som subjekt, predikat og modifikationer.

I computer science anvendes parsetræer ved parsing af programmeringssprog. Her repræsenterer de kildekoden ud fra sproggrensningen og bruges til syntaktisk analyse under kompilering eller tolning. Ofte fører parse-træet til et abstrakt syntaks-træ (AST), som fjerner detaljer som enkelte syntaktiske operationer og fokuserer på semantisk struktur, der er relevant for videre behandling.

Forskelle: Et parsetræ bevarer alle produktioners anvendelser, mens et AST forenkler strukturen til videre brug. Ambigøse grammatikker kan give mere end ét parse-træ for samme streng.

Anvendelser omfatter sprogteknologi som syntaksanalyse, maskinoversættelse og informationsudtræk, samt udvikling af kompilatorer, hvor parse-træer giver en oversigt over, hvordan en sætning eller kode er konstrueret ud fra grammatikkens regler.