produceringsregler

Produceringsregler, ofte kalt produksjonsregler, er regler i formelle grammatikker som bestemmer hvordan symboler kan erstattes i en derivasjon. De utgjør kjernen i en grammatikk G = (V, Σ, R, S), der V er ikke-terminaler, Σ er terminaler, R er regler og S er start-symbolet.

En regel har formen α → β, der venstre side α vanligvis er et enkelt ikke-terminal i kontekstfrie grammatikker, og høyre side β er en streng av terminaler og/eller ikke-terminaler. Regler brukes i trinnvise erstatninger, for eksempel S → NP VP, NP → Det N, Det → 'en' | 'den', N → 'hund' | 'katt'. Resultatet er strenger som til sammen utgjør språket grammatikkens regler beskriver.

Grammatikkens typer bestemmer hvilke former regler kan ha. Type-3 (regulære) regler har formen A → a eller A → aB; Type-2 (kontekstfrie) lar venstre side være et enkelt ikke-terminal; Type-1 (kontekst-sensitive) og Type-0 (ufravgrensede) tillater bredere former. Mange språk beskrives med kontekstfrie regler, særlig i språkteknologi og kompilatordesign.

Derivasjon og parse-tre: En sekvens av regelapplikasjoner kalles en derivasjon. Når alle ikke-terminaler er erstattet av terminaler, oppstår avkastningen. Parse-treet viser hvordan reglene ble anvendt og hjelper i syntaksanalyse og kompilatordesign.

Anvendelser: Produceringsregler beskriver syntaksen i programmeringsspråk og i naturlig språkbehandling. De noteres ofte i BNF eller EBNF, og reglene kan inkludere alternativer og repeterende konstruksjoner. Tvetydighet kan oppstå hvis reglene tillater flere tolkninger.

Merknad: I andre sammenhenger kan «produceringsregler» også referere til regler som styrer produksjonsprosesser i industriell sammenheng, planlegging eller kvalitetskontroll.