====== Transformace a normální formy bezkontextových gramatik ====== ===== Derivace a derivační stromy ===== Gramatika (//N//, //Σ//, //P//, //S//) * **[[wp>Parse tree|Derivační strom]]** * Uzly jsou prvky z //N// ∪ //Σ// * Kořen stromu je //S// * Uzly označené prvky z //Σ// jsou koncové uzly stromu * Hrany odpovídají přepisovacím pravidlům gramatiky //P// * Označení koncových uzlů zleva doprava tvoří větnou formu * Každé derivaci přísluší jeden derivační strom, ale jednomu stromu může příslušet více derivací (více způsobů jak sestavit stejný strom). * **Levá/pravá derivace** * Při sestavování je vždy přepsán nejlevější/nejpravější nonterminál * **Fráze větné formy** * Řada symbolů na koncových uzlech některého podstromu derivačního stromu (řada symbolů, které lze získat derivacemi z jednoho nonterminálu) * //β// je frází větné formy pokud //S// =>* //αAγ// ∧ //A// =>⁺ //β// * **Jednoduchá fráze větné formy** * Řada sybmolů na koncových uzlech jednopatrového podstormu derivačního stromu * //β// je jednoduchou frází větné formy pokud //S// =>* //αAγ// ∧ //A// => //β// * **Nejlevější jednoduchá fráze (l-fráze)** * Fráze větné formy, která se nachází nejvíce vlevo * **Víceznačnost** * Věta je víceznačná pokud existuje více derivačních stromů tvořících tuto větu * Existují jazyky, které nelze generovat bez víceznačnosti * Gramatika, která obsahuje cykly je vždy víceznačná * **//ε//-pravidlo** * //A// -> //ε// (přepisují nonterminál na prázdný řetezec) * **//A//-pravidla** * Všechna pravidla, která mají //A// na levé straně * **Jednoduchá pravidlo** * //A// -> //B// (přepisují nonterminál na jiný nonterminál) * **Zbytečné symboly** * Nedostupné symboly (nelze jich dosáhnout žádným přepisem) a symboly negenerující terminální řetězce (nikdy nevytvoří větnou formu) * **Cyklus** * //A// ->⁺ //A// * **Vlastní gramatika** * Gramatika bez zbytečných symbolů, bez cyklů a bez //ε//-pravidel * **Rekurzivní pravidla** * Rekurzivní zleva: //A// -> //Aα// * Rekurzivní zprava: //A// -> //αA// * Rekurzivní: //A// -> //αAβ// * Každý bezkontextový jazyk lze generovat gramatikou bez levé rekurze * Všechna pravidla s levou rekurzí lze nahradit pravidly s pravou rekurzí ===== Transformace ===== [[pitel:tin:ukoly:2010:2#priklad_3|Úkol z TINu 2010]], [[pitel:tin:ukoly:2011:2#priklad_5|Úkol z TINu 2011]] ==== Odstranění nedostupných symbolů ==== Převod gramatiky (//N//, //Σ//, //P//, //S//) na gramatiku bez nedostupných stavů (//N//′, //Σ//′, //P//′, //S//) - Najdeme všechny dostupné terminály a nonterminály - //i// = 0 - //V//₀ = {//S//} (tj. v nultém kroku je dostupný pouze počáteční stav) - ''repeat'' - //Vᵢ//₊₁ = //Vᵢ// ∪ {//X// | //A// -> //αXβ// ∈ //P// ∧ //A// ∈ //Vᵢ//} (tj. do množiny dostupných přidáme všechny terminály a nonterminály, kterlé lze získat přepisem z některého nonterminálu z množiny dostupných z předchozího kroku) - //i//++ (tj. přejdeme k dalšímu kroku) - ''until'' //Vᵢ//₊₁ = //Vᵢ//₋₁ (tj. končíme pokud se nám v posledním kroku množina dostupných nezměnila) - Novou gramatiku sestavíme jako: * //N//′ = //Vᵢ// ∩ //N// (tj. použijeme pouze dosažitelené nonterminály) * //Σ//′ = //Vᵢ// ∩ //Σ// (tj. použijeme pouze dosažitelené terminály) * //P//′ ⊂ //P// obsahuje pouze pravidla používající pouze symboly z //Vᵢ// ==== Odstranění zbytečných symbolů ==== Převod gramatiky (//N//, //Σ//, //P//, //S//) na gramatiku bez nedostupných stavů (//N//′, //Σ//, //P//′, //S//) - Nalezení nonterminálů, které produkují terminální řetězce - //i// = 0 - //N//₀ = ∅ (tj. v nultém kroku začínáme s prázdnou množinou nonterminálů generujících terminální řetězce) - ''repeat'' - //Nᵢ//₊₁ = //Nᵢ// ∪ {//A// | //A// -> //α// ∈ //P// ∧ α ∈ (//Nᵢ// ∪ //Σ//)*} (tj. do množiny všechny terminály, které lze přepsat na řetězce skladádající se pouze z terminálů nebo nonterminálů, které jsou již v množině nonterminálů generujících terminální řetězce) - //i//++ (tj. přejdeme k dalšímu kroku) - until //Nᵢ//₊₁ = //Nᵢ//₋₁ (tj. končíme pokud se nám v posledním kroku množina nezměnila) - Vytvoříme gramatiku bez nonterminálů, které neprodukují terminální řetězce: * //N//′ = //Nᵢ// * //P//′ ⊂ //P// obsahuje pouze pravidla používající pouze symboly z //Nᵢ// - Odstraníme nedostupné symboly z gramatiky ==== Odstranění ε-pravidel ==== Převod gramatiky (//N//, //Σ//, //P//, //S//) na gramatiku bez //ε//-pravidel (//N//′, //Σ//′, //P//′, //S//′) - Sestavení množiny nonterminálů, které mohou generovat //ε// //Nε// * Postup je obdobný jako krok 1 algoritmu odstranění zbytečných symbolů pouze //Nᵢ//₊₁ = //Nᵢ// ∪ {//A// | //A// -> //α// ∈ //P// ∧ //α// ∈ (//Nᵢ// ∪ {//ε//})*}, //Nε// = //Nᵢ// - Sestavíme novou množinu přepisovacích pravidel //P//′ * Jestliže //A// -> //α//₀//B//₁//α//₁...//Bₖαₖ// ∈ //P//, //k// ≥ 0 a všechna //Bᵢ// jsou v //Nε// a žádný symbol //αᵢ// není v //Nε// pak k //P//′ přidej všechny prvidla tvaru //A// -> //α//₀//X//₁//α//₂//X//₂...//Xₖαₖ// kde //Xᵢ// je buď //Bᵢ// nebo //ε//. Nepřidává se pravidlo A -> //ε//. * Tj. od každého pravidla sestavíme všechny možné kombinace, kde jsou jednotlivé částí přepsatelné na //ε// vynechány - Zavedeme nový počáteční nonterminál //S//′ - Jestliže je //S// v //Nε// pak přidáme do //P//′ pravidla //S//′ -> //ε// a //S//′ -> //S// ==== Odstranění jednoduchých pravidel ==== Převod gramatiky bez //ε//-pravidel (//N//, //Σ//, //P//, //S//) na gramatiku bez jednoduchých pravidel (//N//, //Σ//, //P//′, //S//) - Pro každé //A// ∈ //N// sestrojíme množinu //NA// = {//B// | //A// =>* //B//} - //i// = 0 - //N//₀ = {//A//} - ''repeat'' - //Nᵢ//₊₁ = //Nᵢ// ∪ {//C// | //B// -> //C// ∈ //P// ∧ //B// ∈ //Nᵢ//} - //i//++ - ''until'' //Nᵢ// = //Nᵢ//₋₁ (tj. končíme pokud se nám v posledním kroku množina nezměnila) - //NA// = //Nᵢ// - Sestavíme novou množinu //P//′ * Pro všechna nejednoduchá pravidla //B// -> //α// přidáme do //P//′ pravidla //A// -> //α// pro všechna //A// pro něž platí //B// ∈ //NA//, tj. pro každého nejednoduché pravidlo najdeme všechny nonterminály //A//, které jdou jednoduchými pravidly přepsat na //B//, a vytvoříme všechny varianty pravidla, kde levou stranu nahradíme za //A//. ==== Odstranění levé rekurze ==== Převod vlastní gramatiky (//N//, //Σ//, //P//, //S//) na gramatiku bez levé rekurze (//N//′, //Σ//, //P//′, //S//). Nonterminály vyjádříme jako //N// = {//A//₁, //A//₂, ..., //Aₙ//} tj. zvolíme pořadí jednotlivých nonterminálů. Gramatiku budeme transformovat tak, že je-li //Aᵢ// -> //α// pravidlo pak //α// začíná buď terminálem nebo nonterminálem //Aj//, který je v pořadí až za //Aᵢ// (//j// > //i//). - //i// = 1 (tj. začneme prvním nonterminálem v pořadí) - Vezmeme všechna //Aᵢ//-pravidla, která jsou buď ve tvaru //Aᵢ// -> //Aᵢαₓ// nebo //Aᵢ// -> //βₓ//, kde //β// nezačíná nonterminálem, který je v pořadí před //Aᵢ// - Přidáme nový nonterminál //Aᵢ//′ do //N//′ - Všechna //Aᵢ//-pravidla nahradíme za: * //Aᵢ// -> //β//₁ | //β//₂ | ... | //βₓ// (tj. přepisy na //β// zachováme) * //Aᵢ// -> //β//₁//Aᵢ//′ | //β//₂//Aᵢ//′ | ... | //βₓAᵢ//′ (tj. pro všechny přepisy na //β// vytvoříme pravidla s vpravo přidaným //Aᵢ//′) * //Aᵢ//′ -> //α//₁ | //α//₂ | ... | //αₓ// (tj. u přepisů na //Aᵢα// vytvoříme pravidla pouze s //α//) * //Aᵢ//′ -> //α//₁//Aᵢ//′ | //α//₂//Aᵢ//′ | ... | //αₓAᵢ//′ (tj. u přepisů na //Aᵢα// vytvoříme pravidla s odstraněným //Aᵢ// a vpravo přidaným //Aᵢ//′ * Tím dosáhneme toho, že všechna //Aᵢ//-pravidla začínají buď terminálem nebo nonterminálem, který je v pořadí až za //Aᵢ//) - Pokud jsme již prošli všechny nontermínály (//i// = //n//) končíme - //i//++ - Pro všechny dosud procházené nonterminály //Aj// (1 < //j// < //i//) - Pravidlo //Aᵢ// -> //Ajα// odstraníme - Pro každé //Aj//-pravidlo (//Aj// -> //β//) vytvoříme //Aᵢ// -> //βα//, tj. vezmeme všechna //Aᵢ//-pravidla, jejichž pravá strana začíná nonterminálem //Aj//, který je v pořadí před //Aᵢ//, a nahradíme je za pravidla ve kterých je //Aj// nahrazeno všemi řetězci na které jej lze přepsat. - Jdeme na krok 2 ===== Normální formy ===== ==== Chomského normální forma (CNF) ==== [[wp>Chomsky normal form]] Přepisovací pravidla jsou pouze ve tvaru: * //A// -> //BC// * //A// -> //a// * Případně //S// -> //ε// pokud //ε// ∈ //L//(//G//) a //S// nesmí být na pravé straně žádného přepisovacího pravidla. Převod vlastní gramatiky bez jednoduchých pravidel (//N//, //Σ//, //P//, //S//) na gramatiku v CNF (//N//′, //Σ//, //P//′, //S//′) - Množina //P//′ obsahuje všechny pravidla z //P// ve tvaru //A// -> //BC// a //A// -> //a//, případně //S// -> //ε//. - Každé pravidlo tvaru //A// -> //X//₁//X//₂...//Xₖ// (//k// > //2//) přepíšeme do //P//′ jako sérii pravidel: - //A// -> //X//₁//X//₂′ - //X//₂′ -> //X//₂//X//₃′ - ... - //Xₖ//₋₁′ -> //Xₖ//₋₁//Xₖ// - Zavedeme nové non-terminální symboly //A// -> //X//₂′...//Xₖ//₋₁′ (tj. pravidla mající pravou stranu delší než dva prvky rozdělíme na navazující sérii pravidel majících napravo jen dva prvky) - Ve všech pravidlech v //P//′ které nejsou ve tvaru //A// -> //a//, kde se vyskytují na pravé straně terminály, nahradíme tyto terminály a za nové non-terminály //A//′ a přidáme pravidlo //A//′ -> //a// (tj. nepovolená pravidla s terminály na pravé straně upravíme tak, že terminál nahradíme nonterminálem, který se přepisuje na původní terminál) ==== Greibachové normální forma (GNF) ==== [[wp>Greibach normal form]] * Nejsou žádná //ε// pravidla * Přepisovací pravidla ve tvaru //A// -> //aα// kde //aα// ∈ //N//* * Případně //S// -> //ε// pokud //ε// ∈ //L//(//G//) a //S// nesmí být na pravé straně žádného přepisovacího pravidla Převod vlastní gramatiky bez levé rekurze (//N//, //Σ//, //P//, //S//) na gramatiku v GNF (//N//′, //Σ//, //P//′, //S//′): - Seřadíme všechny nonterminály tak, aby pravá strana žádného přepisovacího pravidla nezačínala nonterminálem, který je v pořadí před přepisovaným nonterminálem. (v podstatě stejná pořadí v jakém máme nonterminály během algoritmu odstranění levé rekurze): //N// = {//A//₁, //A//₂, ..., //Aₙ//} - Postupně pro všechny nonterminály //Aᵢ// od //Aₙ//₋₁ sestupně po //A//₁: - Pro každé pravidlo //Aᵢ// -> //Ajα//: - Odstraň toto pravidlo - Pro všechna //Aj//-pravidla (//Ajα// -> //β//) vytvoř nová pravidla ve tvaru //Aᵢ// -> //βα// (tj. všechna pravidla jejichž pravé strana začíná nonterminálem rozepíšeme tento nonterminál na všechny možnosti na jaké jej lze přepsat) - Po dokončení tohoto kroku všechny pravidla mají pravou stranu začínající terminálem. - Ve všech pravidlech v //P//′ ve kterých se na pravé straně vyskytují terminály na jiné než první pozici nahradíme tyto terminály a za nové non-terminály //A//′ a přidáme pravidlo //A//′ -> //a// (tj. nepovolená pravidla s terminály na pravé straně upravíme tak, že terminál nahradíme nonterminálem, který se přepisuje na původní terminál)