uttrycksparsing

Uttrycksparsing är processen att analysera en sträng som beskriver ett matematiskt eller logiskt uttryck och konvertera den till strukturer som kan användas av datorn. Den används i kompilatorer, tolkar och kalkulatorer för att avgöra vilka operationer som ska utföras och i vilken ordning. Vanligtvis producerar parsningen ett syntaktiskt träd eller ett abstrakt syntaxträd (AST).

Ett uttryck definieras ofta av en kontextfri grammatik som innehåller operatorer, parenteser och literaler. Grammatiken anger hur mindre delar som tal, variabler och funktioner kombineras för att bilda större uttryck, samt hur olika operatorer binds ihop. En viktig aspekt är operatorernas precedens- och associativitetsregler som avgör tolkningen vid sammanlänkning av flera operatorer i samma uttryck.

Vanliga metoder för uttrycksparsing inkluderar rekursiv nedstigning (recursive descent) som bygger parsningen direkt ur grammatiken, samt mer specialiserade tekniker som shunting-yard-algoritmen för att konvertera infixnotation till postfix eller AST. En annan teknik är Pratt-parsning (precedence climbing), som är särskilt effektiv för att hantera operatorernas precedens och vänsterassocierade konstruktioner. Valet av metod påverkar hur väl parsern hanterar komplexa uttryck och vilka typer av språkfunktioner som stöds.

Utvärdering av ett parsat uttryck kan ske direkt genom traversering av AST eller genom en stackbaserad tolkning av postfijo- eller polishnotering. Uttrycksparsing är en central del av språkdesign och programtolkning och används i allt från små kalkulatorer till stora programmeringsspråk och databassökningar.