Abstrakt semantisk graf - Abstract semantic graph

Semantik
Computing
Typer
Teori
Analyse
Ansøgninger

I datalogi er en abstrakt semantisk graf ( ASG ) eller termgraf en form for abstrakt syntaks , hvor et udtryk for et formelt eller programmeringssprog er repræsenteret af en graf, hvis hjørner er udtrykets underordninger . En ASG er på et højere abstraktionsniveau end et abstrakt syntaks-træ (eller AST), som bruges til at udtrykke den syntaktiske struktur for et udtryk eller et program .

ASG'er er mere komplekse og koncise end AST'er, fordi de kan indeholde delte underordninger (også kendt som "almindelige underudtryk"). Abstrakte semantiske grafer bruges ofte som en mellemrepræsentation af kompilatorer for at gemme resultaterne af udførelse af almindelig eliminering af subekspression på abstrakte syntaks-træer . AST'er er træer og er således ikke i stand til at repræsentere fælles vilkår. ASG'er er normalt rettet acykliske grafer (DAG) , selvom grafer indeholdende cyklusser i nogle applikationer kan være tilladt. For eksempel kan en graf indeholdende en cyklus bruges til at repræsentere de rekursive udtryk, der almindeligvis bruges i funktionelle programmeringssprog som ikke- loopende iterationskonstruktioner . Mutabiliteten af ​​disse typer grafer undersøges inden for grafomskrivning .

Nomenklaturen sigt graf er forbundet med området for udtrykket graf omskrivning , der involverer omdannelse og forarbejdning af udtryk ved specifikationen af omskrivning regler, hvorimod abstrakt semantisk graf bruges, når vi diskuterer lingvistik , programmeringssprog , typesystemer og kompilering .

Abstrakte syntaks-træer er ikke i stand til at dele subekspressionsnoder, fordi det ikke er muligt for en node i et korrekt træ at have mere end en forælder. Selvom denne konceptuelle enkelhed er tiltalende, kan det koste prisen for overflødig repræsentation og til gengæld muligvis ineffektiv kopiering af beregningen af ​​identiske termer. Af denne grund bruges ASG'er ofte som et mellemliggende sprog på et efterfølgende kompileringstrin til abstrakt syntaks- trækonstruktion via parsing.

En abstrakt semantisk graf er typisk konstrueret af et abstrakt syntaks-træ ved en proces med berigelse og abstraktion. Berigelsen kan for eksempel være tilføjelse af back-pointers , kanter fra en identifikationsknude (hvor en variabel bruges) til en node, der repræsenterer erklæringen for den variabel. Abstraktionen kan medføre fjernelse af detaljer, der kun er relevante i parsing , ikke for semantik.

Eksempel: Refactoring af kode

Overvej f.eks. Tilfældet med kodefakturering . For at repræsentere implementeringen af ​​en funktion, der tager et inputargument, får den modtagne parameter traditionelt et vilkårligt, særskilt navn i kildekoden, så den kan henvises til. Den abstrakte repræsentation af denne begrebsmæssige enhed, en "funktionsargument" -forekomst, vil sandsynligvis blive nævnt i funktionssignaturen og også en eller flere gange inden for implementeringskodet. Da funktionen som helhed er overordnet til både dens overskrift eller "signatur" -oplysninger såvel som dens implementeringsorgan, ville en AST ikke være i stand til at bruge den samme node til at identificere de forskellige anvendelser eller udseender af argumentenheden. Dette løses af DAG-karakteren af ​​en ASG. En nøglefordel ved at have en enkelt, tydelig knudepunktsidentitet for et givet kodeelement er, at hvert elements egenskaber pr. Definition er unikt lagret. Dette forenkler refactoring-operationer, fordi der er nøjagtigt en eksistentiel forbindelse til en given ejendomsinstinktiering. Hvis udvikleren beslutter at ændre en egenskabsværdi såsom "navnet" på et hvilket som helst kodeelement ("funktionsargumentet" i dette eksempel), eksponerer ASG iboende denne værdi nøjagtigt ét sted, og det følger, at sådanne egenskabsændringer er implicit, trivielt og straks propageret globalt.

Se også

Referencer

eksterne links