Nyckelbegrepp inom syntax

Här är en lista med begrepp på svenska och engelska som berör syntaxdelen i kursen, med korta förklaringar.

- Alfabet - eng. alphabet - En ändlig icketom mängd av symboler/tecken som går att särskilja.

- Ord - eng. word - En ändlig sekvens av symboler/tecken, som kan vara tom.

- Sträng - eng. string - Synonym till ord.

- Språk - eng. language - En mängd av ord vars symboler/tecken kommer från ett och samma alfabet.

- Känna igen ett språk - eng. recognize a language - Avgöra med en algoritm om en viss sträng i ett givet alfabet är i ett givet språk eller inte. Kräver att (1) för varje ord över språkets alfabet som är i språket ska det avgöras vara i språket och (2) för varje ord över språkets alfabet som inte är i språket ska det avgöras inte vara språket. Algoritmen måste terminera för alla strängar över alfabetet.

- Ändlig automat / DFA - eng. Deterministic Finite Automaton - en enkel typ av automat med ändligt antal tillstånd där övergångsrelationen är en funktion, dvs det är alltid entydigt givet ett tecken från indata och nuvarande tillstånd vad nästa tillstånd ska vara.

- Stackautomat / DPDA - eng. Deterministic Push-Down Automaton - en typ av automat med ändligt antal tillstånd och en obegränsad stack som minne, där övergångar mellan tillstånd kan ta bort och lägga till tecken på stacken.

- Språkklass - eng. language class - Samling av språk med speciella egenskaper, t ex klassen av språk som känns igen av en DFA.

- Grammatik - eng. grammar - Samling av regler i form av slutsymboler och ickeslutsymboler som kan användas för att konstruera strängar i ett språk.

- Härledning - eng. derivation - kedja av ersättningar av enstaka ickeslutsymbol från en grammatik.

- Syntaxträd - eng. syntax tree - trädstruktur som byggs upp av härledningar i en grammatik.

- LL-parser - eng. Left-to-right, Leftmost derivation parser - Grammatikdriven parser som läser indata från vänster till höger och väljer ickeslutsymbolen i grammatiken längst till vänster.

- LR-parser - eng. Left-to-right, Rightmost derivation parser - Grammatikdriven parser som läser indata från vänster till höger och väljer ickeslutsymbolen i grammatiken längst till höger.

- LALR-parser - eng. Look Ahead Left-to-right, Rightmost derivation parser - Mindre kraftfull variant av LR-parser som ibland kan leda till mer effektiva parserimplementationer.

- Rekursiv medåkning - eng. recursive descent - Metod för att konstruera en parser för ett språk genom att definiera rekursiva procedurer baserade på språkets grammatik.

- LL-språk - eng. LL languages - klass av språk som kan kännas igen genom att utföra rekursiv medåkning baserat på en grammatik.