"Ak gramatika produkuje aspoň 2 odlišné strom analýzy alebo odvodenia, potom je gramatika nejednoznačná." Ďalšie pravidlo: všetky CFG (bez zbytočných symbolov) s ľavou rekurzivitou a pravou rekurzivitou pre rovnaký neterminál sú tiež nejednoznačné.
Ako zistíte, či je gramatika nejednoznačná?
Gramatika sa považuje za nejednoznačnú, ak existuje viac ako jedna derivácia úplne vľavo alebo viac ako jedna derivácia najviac vpravo alebo viac ako jeden strom analýzy pre daný vstupný reťazec. Ak gramatika nie je nejednoznačná, potom sa nazýva jednoznačná. Ak je gramatika nejednoznačná, potom nie je vhodná na konštrukciu kompilátora.
Aký príklad je nejednoznačná gramatika?
V informatike je nejednoznačná gramatika bezkontextová gramatika, pre ktorú existuje reťazec, ktorý môže mať viac než jednu deriváciu úplne vľavo alebo strom analýzy, zatiaľ čo jednoznačná gramatika je bezkontextová gramatika, pre ktorú má každý platný reťazec jedinečnú deriváciu najviac vľavo alebo strom analýzy.
Ako dokážete, že bezkontextová gramatika je nejednoznačná?
3 odpovede
- Všetky CFG bez zbytočných symbolov a s ľavou a pravou rekurziou pre rovnaký symbol sú nejednoznačné. Všeobecne: …
- Ak chcete zistiť nejednoznačnosť, musíte nájsť 2 derivácie najviac vľavo pre rovnaký reťazec (alebo 2 derivácie najviac vpravo, alebo 2 stromy odvodzovania).
Ako riešite nejednoznačnú gramatiku?
Metódy na odstránenie nejednoznačnosti-
- Opravou gramatiky.
- Pridaním pravidiel zoskupovania.
- Pomocou sémantiky a výberom analýzy, ktorá dáva najväčší zmysel.
- Pridaním pravidiel priority alebo iných pravidiel analýzy citlivých na kontext.