Forskjellen mellom tvetydig og entydig grammatikk
Share
De hovedforskjell mellom tvetydig og utvetydig grammatikk er det tvetydig grammatikk er en kontekstfri grammatikk som det eksisterer en streng som kan ha mer enn en venstremest avledning mens en entydig grammatikk er en kontekstfri grammatikk som alle gyldige strenger har en unik venstreflate avledning.
Grammatikk refererer til de syntaktiske reglene på naturlige språk. I 1956 introduserte datavitenskapere en matematisk modell av grammatikk for å skrive dataspråket. Hvis det er mulig å utlede alle strengene i et språk ved hjelp av en viss grammatikk, så sies det at språket genereres fra den grammatikken. Kontekstfri grammatikk er en type grammatikk. Denne grammatikken genererer kontekstfritt språk. Kontekstfri grammatikk kan være tvetydig eller utvetydig. For en bestemt streng, hvis det er to eller flere derivater, sies den grammatikken som tvetydig. For en bestemt streng, hvis det er en eneste unikt venstre sideavledning, sies den grammatikken utvetydig grammatikk.
Nøkkelområder dekket
1. Hva er tvetydig grammatikk
- Definisjon, eksempel
2. Hva er entydig grammatikk
- Definisjon, eksempel
3. Forskjellen mellom tvetydig og entydig grammatikk
- Sammenligning av nøkkelforskjeller
Nøkkelord
Flertydig grammatikk, entydig grammatikk
Hva er tvetydig grammatikk
En grammatikk sies å være tvetydig hvis det finnes to eller flere derivater for en streng.
Figur 1: Flertydig grammatikk
Anta at det er en grammatikk definert som følger.
G = (S, a + b, +, *, P, S. Produksjonsreglene er som følger. S -> S + S | S | S | a | b. Anta at det er nødvendig å generer streng a + a * b.
Vurder, S -> S + S
Ved å erstatte 'a' for venstre vil S gi følgende.
S-> a + S
Det er som følger å erstatte S * S for S.
S-> a + S * S
Ved å erstatte "a" til venstre vil de fleste S gi den nedre utgangen.
S -> a + a * S
Ved å erstatte 'b' for S vil du gi følgende utgang.
S -> a + a * b
Dette er den påkrevde strengen som skal genereres.
Når du bruker den andre produksjonsregelen, vil den gi
S -> S * S
Bruk S + S til venstre, mest vil S gi følgende.
S -> S + S * S
Erstatning 'a' for venstre mest S,
S -> a + S * S
Bytter 'a' til venstre mest S,
S -> a + a * S
Ved å erstatte 'b' for S vil du gi følgende utgang.
S -> a + a * b
Igjen genererte den den nødvendige strengen. Derfor er det mer enn en avledning for å generere strengen. Derfor er det en tvetydig grammatikk.
Hva er entydig grammatikk
I en tvetydig grammatikk har en viss streng en unik venstreflate. Se følgende produksjonsregler.
S -> L | a, L -> LS | S
Vurder S -> L regelen. Bytt LS istedenfor L.
S -> LS
Suppleant S, for første L.
S -> S S
Ved å erstatte 'a' til venstre S vil du gi den nedre utgangen.
S -> a S
Ved å erstatte 'a' for S vil du gi følgende.
S -> a a
Derfor har en streng en unik venstre side. Så, det er en entydig grammatikk.
Forskjellen mellom tvetydig og entydig grammatikk
Definisjon
En tvetydig grammatikk er en kontekstfri grammatikk som det eksisterer en streng som kan ha mer enn en venstreemstrere avledning eller analysere trær. Uklart grammatikk er en kontekstfri grammatikk, for hvilken hver gyldig streng har en unik venstreflate eller avtrekk.
Antall venstre sideavledninger
I tvetydig grammatikk kan en streng ha to eller flere venstrefulle derivater, men i en entydig grammatikk har en streng en unik venstreflate.
Konklusjon
Kontekstfri grammatikk kan være tvetydig eller utvetydig. Forskjellen mellom tvetydig og utvetydig grammatikk er at den tvetydige grammatikken er en kontekstfri grammatikk som det finnes en streng som kan ha mer enn en venstremest avledning mens en entydig grammatikk er en kontekstfri grammatikk som alle gyldige strenger har en unik venstreflate avledning.
Henvisning:
1. "Flertydig grammatikk." Wikipedia, Wikimedia Foundation, 17. juli 2018, Tilgjengelig her.
2. "Compiler Design | Tvetydig grammatikk. "GeeksforGeeks, 10. februar 2018, Tilgjengelig her.
3. "Flertydig grammatikk", Neso-akademiet, 29. mars 2017, Tilgjengelig her.
Bilde Courtesy:
1. "Leftmostderivations jaredwf" Av Jaredwf på English Wikipedia - Overført fra en.wikipedia til Commons av EdwardHades (Public Domain) via Commons Wikimedia
