Tvetydighet (grammatikk)

En tvetydig grammatikk er innenfor informasjonsteknologien betegnelsen på en kontekstfri grammatikk for hvilket der eksisterer en streng som kan ha mer enn én derivering helt til venstre. En entydig grammatikk er en kontekstfri grammatikk der hver gyldig streng har en unik derivasjon helt til venstre. Mange språk tillater både en tvetydig og entydig grammatikk, mens noen språk bare tillater en entydig grammatikk. Det eneste språket uten en tvetydig grammatikk er det tomme språket. Ethvert ikke-tomt språk tillater en tvetydig grammatikk, ved å ta en utvetydig grammatikk og introdusere duplikate regler eller synonymer. Et språk som bare tillater tvetydig grammatikk kalles for et iboende tvetydig språk, og der finnes tvetydige kontekstfrie språk. En deterministisk kontekstfri grammatikk er alltid entydig, og der finnes viktige underklasser av kontekstfrie grammatikker. Der finnes likevel ikke-deterministiske, tvetydige kontekstfrie grammatikker.

For programmeringsspråk i den virkelige verden, er referansen til kontekstfrie grammatikker ofte tvetydig, på grunn av tilfeller som dangling else. Slike tvetydigheter er generelt oppløst ved å tilføye regler av forrang eller andre kontekst-sensitive regler, slik at hele grammatikken blir utvetydig.

Kategori:Grammatikk
Kategori:Kompilatorer