Dizajn kompajlera, algoritmi za rješavanje problema. Regex konačne mašine

Regularni izrazi (RE) su vrlo zgodan oblik pisanja takozvanih regularnih ili automatskih jezika. Stoga se RV-ovi koriste kao ulazni jezik u mnogim sistemima lančane obrade. Razmotrimo primjere takvih sistema:

• Grep komanda operativni sistem Unix ili slične komande za pretraživanje stringova, koje se nalaze u web pretraživačima ili sistemima za formatiranje teksta. U takvim sistemima, RT se koriste za opisivanje obrazaca koje korisnik pretražuje u datoteci. Različiti pretraživači pretvaraju RT ili u deterministički konačni automat (DFA) ili nedeterministički konačni automat (NFA) i primjenjuju ovaj automat na datoteku koja se traži.
• Generatori leksičkih analizatora. Leksički analizatori su komponenta kompajlera; oni razbijaju izvorni program u logičke jedinice (tokene), koje se mogu sastojati od jednog ili više znakova i imati određeno značenje. Generator leksičkog analizatora prima formalne opise tokena, koji su u suštini RV, i kreira DFA koji prepoznaje koji se od tokena pojavljuje na njegovom ulazu.
• RV u programskim jezicima.

U ovom članku ćemo se prvo upoznati sa mašinama konačnih stanja i njihovim tipovima (DFA i NFA), a zatim ćemo razmotriti primjer konstruiranja minimalnog DFA pomoću regularnog izraza.

Konačne mašine

Konačni automat (KA) je pretvarač koji vam omogućava da povežete ulaz sa odgovarajućim izlazom, a ovaj izlaz može zavisiti ne samo od trenutnog ulaza, već i od onoga što se dogodilo ranije, od istorije državnog stroja. Čak se i ljudsko ponašanje, a ne samo umjetni sistemi, može opisati korištenjem CA. Na primjer, vaša reakcija na komšiju koji noću sluša glasnu muziku bit će ista nakon prvog takvog incidenta i potpuno drugačija nakon nekoliko takvih puta. Takvih praistorija može biti beskonačan broj, postavlja se pitanje: koju memoriju CA treba da ima da bi se ponašao drugačije za svaku praistoriju? Jasno je da je nemoguće pohraniti beskonačan broj pozadinskih priča. Prema tome, automat, takoreći, dijeli sve moguće praistorije u klase ekvivalencije. Dvije priče su ekvivalentne ako imaju isti učinak na ponašanje mašine u budućnosti. Poziva se i klasa ekvivalentnosti kojoj je automat dodijelio svoju trenutnu historiju unutrašnje stanje mašina.

Razmotrimo primjer rada primitivnog CA:

Ova svemirska letjelica se sastoji od:

• traka predstavljena ulaznim lancem.
• čitalac.
• kontrolni blok koji sadrži listu pravila prijelaza.

Čitač se može kretati u jednom smjeru, obično s lijeva na desno, čitajući tako znakove ulaznog niza. Za svaki takav pokret može računati jedan simbol. Nadalje, očitani znak se prenosi na upravljačku jedinicu. Upravljačka jedinica mijenja stanje mašine na osnovu pravila tranzicije. Ako lista prijelaznih pravila ne sadrži pravilo za pročitani znak, tada automat "umre".

Hajde sada da razmotrimo na koje načine se CA može specificirati. Mogu se specificirati u obliku grafikona ili u obliku kontrolnih tabela. U obliku grafikona letjelica je specificirana na sljedeći način:

• vrhovi grafa odgovaraju stanjima letjelice.
• usmjerene ivice odgovaraju prijelaznim funkcijama (pored svake takve ivice je označen simbol duž kojeg se vrši prijelaz).
• vrh sa ivicom koja ulazi u njega, koji ne napušta više od jednog stanja, odgovara početnom stanju.
• konačna stanja svemirske letjelice su označena podebljanim obrisima.

U obliku kontrolne tablice, ovako:

• CA stanja se nalaze u redovima tabele.
• znakova prepoznatog jezika - u kolonama.
• na raskrsnici je ovim simbolom označeno stanje u koje se iz tog stanja može doći.

Primjer CA u obliku grafikona iu obliku kontrolne tablice bit će predstavljen u nastavku.

DKA i NKA

Glavna razlika između DFA i NFA je u tome što DFA tokom rada može biti u samo jednom stanju, a NFA u nekoliko država istovremeno. Kao primjer rada NCA možemo navesti ideju američkog fizičara Hugha Everetta da bilo koji događaj razbija svijet na nekoliko svjetova, u svakom od kojih je ovaj događaj završio na svoj način. Na primjer, u jednom svijetu Hitler je pobijedio u drugom svjetski rat, u drugom - Njutn je umesto fizike krenuo u posao i otkriće zakona klasične mehanike je moralo biti odloženo za 50 godina. Za izvođenje bilo kakvih zaključaka iz rada automata treba proučiti sve "svetove". Nakon što je čitav ulazni lanac pročitan, pretpostavljamo da NFA prihvata dati lanac ako je završio svoj rad u stanju prihvatanja u barem jednom od skupa "svjetova". Shodno tome, automat odbacuje prečku ako se završi u neprihvatljivom stanju u svakom "svijetu". DFA prihvata string, to je očigledno ako se, nakon čitanja celog ulaznog niza, pokaže da je u stanju prihvatanja.

U većini slučajeva, mnogo je lakše izgraditi NCA nego DCA. No, unatoč tome, korištenje NCA za modeliranje nije najviše dobra ideja... Na sreću, za svaki NFA moguće je konstruisati DFA koji prihvata isti jezik unosa. U ovom članku nećemo predstavljati algoritam za konstruisanje DFA koristeći NFA, već ćemo ovaj algoritam razmotriti na osnovu ilustrativni primjer ispod.

Izgradnja minimalnog DFA koristeći regularni izraz

Za početak, predstavljamo listu RT operacija korištenih u ovom članku, po prioritetu:

• iteracija (Kleene zatvaranje), koristeći "*"
• konkatenacija je navedena pomoću razmaka ili praznog niza (npr. ab)
• konkatenacija pomoću "|"

Razmotrimo primjer, s obzirom na regularni izraz:

Xy * (x | y *) | ab (x | y *) | (x | a *) (x | y *)

Potrebno je konstruisati minimalni DFA koristeći regularni izraz i demonstrirati prepoznavanje ispravnih i netačnih lanaca.

Za početak, pojednostavljujemo dati RV, koristeći desni distributivni zakon konkatenacije u odnosu na uniju, dobijamo sljedeće RV:

(xy * | ab | (x | a *)) (x | y *)

Sada pravimo automat za ovaj PB:

Prema pravilu za pretvaranje konkatenacije (nećemo davati pravila za pretvaranje PB u CA, jer su sasvim očigledna), dobijamo sljedeći automat:

Po pravilu transformacije sindikata:

Prema pravilu transformacije konkatenacije:

I na kraju primjenjujemo pravilo transformacije zatvaranja i dobijamo εNKA. Ovdje treba napomenuti da je εNKA NFA koja sadrži ε-prijelaze. Zauzvrat, ε-prijelaz je prijelaz u kojem automat ne uzima u obzir ulazni niz ili, drugim riječima, prijelaz praznim simbolom.

Riješimo se ε-prijelaza (konačna stanja su označena zvjezdicom):

U ovom NSA, stanja s3 i s5 su ekvivalentna, jer je δ (s3, x) = δ (s5, x) = s1 i δ (s3, y) = δ (s5, y) = s5, s7. Preimenujte stanja s6 -> s5 i s7 -> s6:

Gradimo DCA za NCA:

U ovom DFA, stanja p1 i p5 su ekvivalentna, jer
δ (p1, x) = δ (p5, x) = p4 i δ (p1, y) = δ (p5, y) = p5. Preimenujte stanja p6 -> p5 i p7 -> p6:

Ovaj automat je minimalni DFA.

Neka je δ prijelazna funkcija, tada će proširena prijelazna funkcija izgrađena na δ biti označena sa δ ’, a ω je ulazni lanac.

Pretpostavimo da je lanac ω = aaax naveden na ulaz, očekujemo da će automat biti u jednom od prihvatljivih stanja.

δ ’(p0, ε) = p0
δ ’(p0, a) = δ (δ’ (p0, ε), a) = δ (p0, a) = p3
δ ’(p0, aa) = δ (δ’ (p0, a), a) = δ (p3, a) = p5
δ ’(p0, aaa) = δ (δ’ (p0, aa), a) = δ (p5, a) = p5
δ ’(p0, aaax) = δ (δ’ (p0, aaa), x) = δ (p5, x) = p4

P4 je važeće konačno stanje, tako da je aaax lanac ispravan za ovaj automat.

Sada pretpostavimo da je ω = xyyb:

δ ’(p0, ε) = p0
δ ’(p0, x) = δ (δ’ (p0, ε), x) = δ (p0, x) = p1
δ ’(p0, xy) = δ (δ’ (p0, x), y) = δ (p1, y) = p1
δ ’(p0, xyy) = δ (δ’ (p0, xy), y) = δ (p1, y) = p1
δ ’(p0, xyyb) = δ (δ’ (p0, xyy), b) = δ (p1, b) = ∅

Ovdje vidimo da ako se simbol b unese u automat kada je u stanju p1, onda će ovaj automat umrijeti, stoga je lanac xyyb netačan.

P. S. U ovom članku je razmatran algoritam za izgradnju DFA iz PB-a, ali postoje zgodniji algoritmi, posebno za programiranje, ali to je već tema za drugi članak ...

DKA je poseban slučaj NKA. u njemu:

ne postoji stanje sa ε-prijelazima;

za svako stanje S i ulazni simbol a, postoji najviše jedan luk koji izlazi iz S i označen sa a.

DFA ima samo jedan prijelaz za bilo koji ulazni simbol iz svakog stanja. Ako se tablica koristi za predstavljanje funkcije DFA prijelaza, tada će svaki zapis sadržavati samo jedno stanje. Tako je lako provjeriti da li dati DFA prihvata određenu liniju, jer postoji samo jedna putanja od početnog stanja koja je označena ovom linijom.

Slika 3 prikazuje prelazni graf DFA koji dozvoljava isti jezik (a | b) * a (a | b) (a | b) kao NFA na slici 1.

Slika 3. DFA koji prihvata niz (a | b) * a (a | b) (a | b).

Deterministički konačni stroj M koji prihvata dati jezik:

M = ((1, 2, 3, 4, 5, 6, 7, 8), (a, b), D, 1, (3, 5, 6, 8))

Prijelazna funkcija D definirana je na sljedeći način:

Izgradnja nka pomoću regularnog izraza

1. Za ε, NSA ima sljedeći oblik (0 je početno stanje, 1 je konačno stanje):

2. Za a, uključeno na datom jeziku NCA:

3. Neka su N (s) i N (t) NFA za regularni izrazi s i t.

Za regularni izraz s | t, kompozitni NFA ima sljedeći oblik:

b. Za regularni izraz st NFA:

With. Za izraz s *, NCA ima oblik:

d. Za izraz u zagradama (s), NFA N (s) se koristi kao u paragrafu a.

Svaka nova država dobija individualno ime. Izgradnja NSA N (r) ima sljedeća svojstva:

N (r) ima broj stanja koji ne prelazi broj simbola za više od 2 puta.

N (r) ima tačno jedno početno i jedno konačno stanje. Završno stanje nema izlaznih prijelaza.

Svako stanje N (r) ima ili 1 prijelaz za simbol iz abecede (), ili najviše 2 izlazna ε-prijelaza.

Pretvaranje nka u dka.

NFA na slici 1 ima 2 prijelaza iz stanja 0 za simbol a: stanja 0 i 1. Ovaj prijelaz je dvosmislen, kao i prijelaz u ε. Modeliranje takvih NSV-ova pomoću kompjuterskog programa je mnogo teže. Definicija valjanosti kaže da mora postojati neki put od početnog stanja do konačnog stanja, ali kada postoji više putanja za isti ulazni niz, sve se moraju uzeti u obzir da bi se pronašao put do konačnog stanja ili da bi se saznalo da takav put ne postoji.

U NFA prelaznoj tabeli, svaki zapis odgovara skupu stanja, au DFA prelaznoj tabeli - samo jednom. Suština transformacije je da svako DFA stanje odgovara skupu NFA stanja. DFA koristi svoja stanja da prati sva moguća stanja u kojima NFA može biti nakon čitanja sljedećeg ulaznog simbola. To jest, nakon čitanja ulaznog toka, DFA je u stanju koje predstavlja skup stanja NFA koji se može doseći od početnog duž putanje koja odgovara ulaznoj liniji. Broj takvih stanja DFA može značajno premašiti broj stanja NFA (eksponencijalna zavisnost), ali u praksi je to izuzetno rijetko, a ponekad je čak i manje stanja u DFA nego u NFA.

Razmotrimo sličnu transformaciju koristeći poseban primjer. Slika 4 prikazuje drugi NFA koji dozvoljava jezik (a | b) * a (a | b) (a | b) (kao na slikama 1 i 3).

Slika 4. NFA koji dozvoljava jezik (a | b) * a (a | b) (a | b)

Prijelaz iz stanja 13 u stanje 14 prikazan na slici može se predstaviti slično prijelazu iz 8. u 13. stanje.

Hajde da napravimo DFA za dati jezik. Početno stanje ekvivalentnog DFA je stanje A = (0, 1, 2, 4, 7), odnosno ona stanja koja se mogu doseći od 0 pomoću ε.

Abeceda ulaznih znakova je (a, b). Iz početnog stanja A može se izračunati stanje koje se može postići u odnosu na a. Nazovimo ovo stanje B = (1, 2, 3, 4, 6, 7, 8, 9, 11, 13, 14).

Među stanjima u A, samo stanje 4 ima prijelaz duž b u stanje 5, tako da DFA ima prijelaz duž b iz A u stanje C = (1, 2, 4, 5, 6, 7).

Ako nastavimo ovaj proces sa stanjima B i C, svi skupovi NFA stanja će biti označeni. Dakle, imaćemo mnogo stanja:

A = (0, 1, 2, 4, 7)

B = (1, 2, 3, 4, 6, 7, 8, 9, 11, 13, 14)

C = (1, 2, 4, 5, 6, 7)

D = (10, 12, 13, 14)

Stanje A je početno, a stanja B, D, E su konačna.

Kompletna prelazna tabela je prikazana ispod.

Slika 5 ispod prikazuje sam DFA za ovaj jezik.

Slika 5. Jezik koji prihvata DFA (a | b) * a (a | b) (a | b)

Spisak korišćene literature:

Pentus A.E., Pentus M.R. - Teorija formalnih jezika

A. Aho, R. Seti, D, Ullman - Prevodioci: principi, tehnologije, alati.

Pogodnije je opisati vokabular jezika u obliku regularnih izraza, a jezik prepoznati pomoću CA. Stoga je važno biti u stanju transformirati jezične definicije u obliku regularnih izraza u definiciju u obliku CA. Ovu transformaciju je predložio Kennet Thompson.

Konačni automat je pet (S, S, d, S 0, F)

S je konačan skup stanja.

S je konačan skup dopuštenih ulaznih signala.

d - prelazna funkcija. On odražava skup Sh (SÈ (e)) u skup stanja nedeterminističkog konačnog automata. Za deterministički automat, funkcija tranzicije odražava skup SxS u skup stanja automata. Drugim riječima, ovisno o stanju i ulaznom simbolu, d određuje novo stanje automata.

S 0 - početno stanje konačnog automata, S 0 Î S.

F je skup konačnih stanja automata, F Î S.

Rad državnog stroja je niz koraka. Korak je određen stanjem mašine i ulaznim simbolom. Sam korak se sastoji u promeni stanja mašine i čitanju sledećeg karaktera ulazne sekvence.

Postoji slijedeći pravila pretvaranje regularnih izraza u državni stroj.

1 Regularni izraz "e" se pretvara u automat dva stanja i e-prijelaza između njih (slika 1).

Slika 1. - Automatska mašina za e-prijelaz

2 Regularni izraz iz jednog znaka "a" se konvertuje u mašinu stanja dva stanja i prelaz između njih na ulaznom signalu a (slika 2).

Slika 2. - Automatska mašina za prelaz simbolom a

3 Pretpostavimo da postoji regularni izraz rs i da su mašine stanja za izraz r i izraz s već izgrađene. Zatim se dvije mašine povezuju u seriju. Slika 3 prikazuje originalne automate za r i s jezike. Na slici je prikazan automat za prepoznavanje konkatenacije ovih jezika.

Automat za r Automat za s

Slika 3. - Početni automati

Slika 4. - Mašina za spajanje jezika

4 Neka postoji regularni izraz r | s i automati stanja za izraz r i izraz s su već izgrađeni (slika 3). Tada rezultirajući automat mora imati alternativu izvršavanju jednog od dva automata. To jest, automat za izražavanje r | s za automate za r i s sa slike 3 ima oblik prikazan na slici 5.

Slika 5. - Mašina za kombinovanje jezika

5 Neka postoji regularni izraz r * sa konstruisanim konačnim strojem r. U ovom slučaju uvode se dva nova stanja za mogućnost zaobilaženja automata izraza r, a e-prijelaz između konačnog i početnog stanja uvodi se za mogućnost višestrukog ponavljanja automata r. Ako se konstruiše automat sličan slici 3 za regularni izraz r, tada državni stroj prikazan na slici 6 odgovara regularnom izrazu r *.

U ovom dijelu ćemo formirati važna pitanja vezana za obične jezike. Prvo morate shvatiti šta znači postaviti pitanje o određenom jeziku. Tipičan jezik je beskonačan, tako da nema smisla nekome pokazati lance ovog jezika i postaviti pitanje koje zahtijeva provjeru beskonačnog broja lanaca. Mnogo je razumnije koristiti jednu od konačnih reprezentacija jezika, naime: DFA, NFA, ε-NFA ili regularni izraz.

Očigledno je da će jezici predstavljeni na ovaj način biti redovni. Zaista ne postoji način da se predstavljaju potpuno proizvoljni jezici. U narednim poglavljima predlažu se konačne metode opisivanja klasa širih od klase regularnih jezika, a mogu se razmatrati i pitanja o jezicima iz njih. Međutim, algoritmi za rješavanje mnogih pitanja o jezicima postoje samo za klasu regularnih jezika. Ova ista pitanja postaju “nerješiva” (ne postoje algoritmi za odgovore na ova pitanja) ako se postavljaju korištenjem više “izražajnijih” notacija (koje se koriste za izražavanje šireg spektra jezika) od reprezentacija razvijenih za obične jezike.

Započnimo naše proučavanje algoritama za pitanja o regularnim jezicima gledajući načine na koje se jedna reprezentacija jezika transformiše u drugu. Posebno razmotrite vremensku složenost algoritama koji izvode transformacije. Zatim ćemo pogledati tri glavna pitanja o jezicima.

1. Da li je opisani jezik prazan skup?

2. Da li neki niz w pripada predstavljenom jeziku?

3. Da li zaista postoje dva različiti opisi predstavljaju isti jezik? (Ovo pitanje se često naziva "ekvivalentnošću" jezika.)

2.1 Konverzije različitih reprezentacija jezika

Svaki od četiri prikaza regularnih jezika može se konvertovati u bilo koji od ostala tri. Na sl. 3.1 prikazuje prelaze iz jednog pogleda u drugi. Iako postoje algoritmi za bilo koju od ovih transformacija, ponekad nas zanima ne samo izvodljivost neke transformacije, već i vrijeme potrebno da se ona završi. Posebno je važno razlikovati algoritme koji uzimaju eksponencijalno vrijeme (vrijeme kao funkcija veličine ulaznih podataka) i stoga se mogu izvršiti samo za relativno male ulazne podatke, od onih algoritama čije je vrijeme izvršenja linearno, kvadratno , ili polinom s malim kao funkcija veličine ulaznih podataka. Potonji algoritmi su „realistični“ po tome što se mogu izvršiti za mnogo širu klasu instanci problema. Razmotrite vremensku složenost svake transformacije o kojoj se raspravlja.

Konverzija NCA u DCA

Vrijeme izvršenja transformacije NFA ili ε-NFA u DFA može biti eksponencijalna funkcija broja stanja NFA. Za početak, izračunavanje ε-zatvaranja n stanja traje O (n3) vremena. Potrebno je pronaći sve lukove sa oznakom ε koji vode iz svakog od n stanja. Ako postoji n stanja, onda ne može biti više od n2 luka. Razumna upotreba sistemski resursi i dobro dizajnirane strukture podataka osiguravaju da vrijeme istraživanja za svako stanje ne prelazi O (n2). U stvari, algoritam tranzitivnog zatvaranja kao što je Warshall algoritam 5 može se koristiti za izračunavanje cijelog ε-zatvaranja jednom.

Nakon izračunavanja ε-zatvaranja, možemo nastaviti sa sintezom DFA koristeći konstrukciju podskupova. Glavni uticaj na potrošnju vremena ima broj DFA stanja, koji može biti jednak 2n. Za svako stanje, moguće je izračunati prelaze u O (n3) vremenu koristeći ε-zatvaranje i NFA tablicu prijelaza za svaki ulazni simbol. Pretpostavimo da trebate izračunati δ ((q1, q2,…, qk), a) za DFA. Svako stanje qi može doseći najviše n stanja duž putanja označenih ε, a svako od ovih stanja može imati najviše n lukova označenih a. Nakon što smo kreirali niz indeksiran po stanjima, možemo izračunati uniju od najviše n skupova koji se sastoje od najviše n stanja u vremenu proporcionalnom n2.

Na ovaj način, za svako stanje qi, može se izračunati skup stanja dostupnih iz qi duž putanje označene a (moguće uključujući i lukove označene ε). Kako je k ≤ n, postoji najviše n takvih stanja qi, a za svako od njih izračunavanje dostupnih stanja traje O (n2) vremena. Na ovaj način, ukupno vrijeme izračunavanje dostižnih stanja je O (n3). Kombinovanje skupova dostupnih stanja će zahtevati samo O (n2) dodatnog vremena; stoga, izračunavanje jedne DFA tranzicije traje O (n3) vremena.

Imajte na umu da se broj ulaznih znakova smatra konstantnim i ne zavisi od n. Dakle, i u ovoj i u drugim procjenama vremena rada, broj ulaznih znakova se ne uzima u obzir. Veličina ulazne abecede utiče samo na konstantni faktor skriven u Velikom O notaciji.

Dakle, vrijeme transformacije NFA u DFA, uključujući situaciju kada NFA sadrži ε-prijelaze, je O (n32n). Naravno, u praksi je obično broj izgrađenih država mnogo manji od 2n. Ponekad postoje samo n. Stoga je moguće utvrditi procjenu radnog vremena jednako O (n3s), gdje je s broj stanja koje DFA stvarno ima.

Pretvaranje DKA u NKA

Ovo je jednostavna transformacija za koju je potrebno O (n) vremena za DFA u n-stanje. Sve što treba da se uradi je da promenite prelaznu tabelu za DFA, stavljajući stanja u zagrade (), i takođe dodate kolonu za ε ako je potrebno da se dobije ε-NFA. Budući da se broj ulaznih znakova (tj. širina tablice za skok) smatra konstantnim, kopiranje i obrada tabele traje O (n) vremena.

Pretvorite automat u regularni izraz

U svakoj od n faza (gdje je n broj DFA stanja), veličina konstruiranog regularnog izraza može se učetvorostručiti, budući da je svaki izraz konstruiran iz četiri izraza prethodnog ciklusa. Na ovaj način, jednostavan unos n3 izraza može potrajati O (n34n) vremena. Poboljšana konstrukcija iz Odjeljka 3.2.2 smanjuje konstantni faktor, ali ne utiče na eksponencijalnost ovog problema (u najgorem slučaju).

Sličan dizajn zahtijeva isto vrijeme rada ako se transformira NFA, ili čak ε-NFA, ali to ovdje nije dokazano. Međutim, korištenje dizajna za NSA ima veliki značaj... Ako prvo pretvorite NFA u DFA, a zatim DFA u regularni izraz, tada će za ovo trebati O (n34n32n) vremena, što je dvostruko eksponencijalno.

Pretvorite regularni izraz u automat

Potrebno je linearno vrijeme da se regularni izraz pretvori u ε-NFA. Morate efikasno raščlaniti regex koristeći metodu kojoj je potrebno O (n) vremena za regularni izraz dužine n6. Kao rezultat, dobijamo stablo sa jednim čvorom za svaki znak regularnog izraza (iako se zagrade ne pojavljuju u ovom stablu, jer kontrolišu samo raščlanjivanje izraza).

Rezultirajuće stablo datog regularnog izraza može se obraditi konstruiranjem ε-NFA za svaki čvor. Pravila transformacije regularnog izraza uvedena u Odjeljku 3.2.3 nikada ne dodaju više od dva stanja i četiri luka svakom čvoru u stablu izraza. Dakle, i broj stanja i broj lukova rezultirajućeg ε-NCA jednaki su O (n). Osim toga, rad na kreiranju ovih elemenata u svakom čvoru stabla analize je konstantan, pod uslovom da funkcija koja obrađuje svako podstablo vraća pokazivače na početna i prihvatljiva stanja ovog automata.

Dolazimo do zaključka da je za konstrukciju ε-NFA pomoću regularnog izraza potrebno vrijeme koje je linearno ovisno o veličini izraza. Moguće je isključiti ε-prijelaze iz ε-NCA sa n stanja transformacijom u običan NCA u vremenu O (n3) i bez povećanja broja stanja. Međutim, konverzija u DFA može potrajati eksponencijalno.

Potreban nedeterminističkom stroju konačnog stanja M = (Q, T, D, q 0 , F) izgraditi deterministički konačni stroj M = (Q ", T, D ", q " 0 , F "). Početno stanje za automat u izgradnji je ε-zatvaranje početnog stanja inicijalnog automata. ε-zatvaranje je skup stanja do kojih se iz datog može doći prijelazima duž ε. Nadalje, dok postoje stanja za koja nisu konstruirani prijelazi (prijelazi se vrše simbolima, prijelazi duž kojih su u originalnom automatu), za svaki simbol se izračunava ε-zatvaranje skupa stanja koja su dostupna iz stanje koje se razmatra prelaskom duž razmatranog simbola. Ako stanje koje odgovara pronađenom skupu već postoji, tada se tu dodaje prijelaz. Ako nije, dodaje se novo primljeno stanje.

Primjer

Inicijalizacija

Označena su stanja koja odgovaraju ε-zatvaranju početnog. Ova stanja će odgovarati državi A budući DKA.

Prva iteracija

Postoje prijelazi iz ε-zatvaranja u NFA stanja 3 i 10 (prema a i c, odnosno). Za stanje 3, ε-zatvaranje je skup stanja (3, 4, 6), za stanje 10 - (10). Nova DFA stanja koja odgovaraju ovim skupovima označavamo kao B i C.

DKA stanje	Skup država NCA
		a	b	c
A	{1, 2, 9}	B	-	C
B	{3, 4, 6}	-	-	-
C	{10}	-	-	-

Druga iteracija

Iz skupa NFA stanja (3, 4, 6), što odgovara DFA stanju B postoje dva prijelaza - u stanje 5 (po b) i 7 (od c). Njihova ε-zatvaranja se sijeku, ali sami skupovi su različiti; stoga im se dodeljuju dva nova stanja DFA - D i E... Od država NFA koje odgovaraju stanju DFA C, nema prijelaza.

DKA stanje	Skup država NCA	Simboli za navigaciju
		a	b	c
A	{1, 2, 9}	B	-	C
B	{3, 4, 6}	-	D	E
C	{10}	-	-	-
D	{2, 5, 8, 9}	-	-	-
E	{2, 7, 8, 9}	-	-	-

Treća iteracija

Iz skupova stanja NFA koji odgovaraju državama NFA D i E prelaze se vrše na skupove stanja koji odgovaraju postojećim stanjima (iz skupa (2, 5, 8, 9), koji odgovaraju stanju D, na a prelazak u stanje 3 koje pripada skupu (3, 4, 6) koji odgovara stanju DFA B, na c- prijelaz u stanje 10, koje odgovara stanju C; slično za skup koji odgovara stanju DFA E). Proces izgradnje tabele stanja i prelaza DFA je završen.

DKA stanje	Skup država NCA	Simboli za navigaciju
		a	b	c
A	{1, 2, 9}	B	-	C
B	{3, 4, 6}	-	D	E
C	{10}	-	-	-
D	{2, 5, 8, 9}	B	-	C
E	{2, 7, 8, 9}	B	-	C

rezultat:

Izgradnja pravolinearne gramatike iz konačnog stroja

Svakom stanju dodjeljujemo neterminal. Ako dođe do prijelaza iz stanja X u državi Y on a, dodajte pravilo X → aY... Dodajte pravila za konačna stanja X→ ε. Za ε-prijelaze - X → Y.

Primjer 1 (deterministički državni stroj)

• A → a B | c C
• B → b D | c E
• C → ε
• D → a B | c C
• E → a B | c C

Primjer 2 (nedeterministički državni stroj)

• 1 → 2 | 9
• 2 → a 3
• 3 → 4 | 6
• 4 → b 5
• 5 → 8
• 6 → c 7
• 7 → 8
• 8 → 2 | 9
• 9 → c 10
• 10 → ε

Izgradnja DFA zasnovanog na PB

Neka postoji regularni izraz r... Za ovaj regularni izraz, potrebno je izgraditi deterministički konačni stroj D takav da L(D) = L(r).

Modifikacija regularnog izraza

Dodajmo mu simbol koji označava kraj PB - "#". Kao rezultat, dobijamo regularni izraz ( r)#.

Izgradnja drveta

Predstavimo regularni izraz u obliku stabla, čiji su listovi terminalni simboli, a unutrašnji vrhovi su operacije spajanja ".", unije "∪" i iteracije "*". Svakom listu stabla (osim ε-lišća) će biti dodijeljen jedinstveni broj i na njega ćemo, s jedne strane, gledati kao na poziciju u stablu, a s druge kao na poziciju odgovarajućeg simbola na list.

Evaluacija funkcija nullable, firstpos, lastpos

Sada, prelazeći stablo T odozdo prema gore s lijeva na desno, izračunavamo tri funkcije: nullable, firstpos, i lastpos... Funkcije nullable, firstpos i lastpos definisani su na čvorovima stabla. Vrijednost svih funkcija osim nullable, je niz pozicija. Funkcija firstpos(n) za svaki čvor n stabla sintakse regexp daje skup pozicija koje odgovaraju prvim znakovima u podlancima generiranim podizrazom s vrhom na n... Isto tako, lastpos(n) daje skup pozicija koje odgovaraju zadnjim znakovima u podlancima generiranim podizrazima sa vrhom n... Za čvorove nčija podstabla (tj. stablo čiji čvor n je korijen) može generirati praznu riječ, definiramo nullable(n) = tačno, i za ostale čvorove false... Tablica proračuna nullable, firstpos, lastpos:

čvor n	nullable(n)	firstpos(n)	lastpos(n)
ε	tačno	∅	∅
i ≠ ε	false	{i}	{i}
u ∪ v	nullable(u) ili nullable(v)	firstpos(u) ∪ firstpos(v)	lastpos(u) ∪ lastpos(v)
u. v	nullable(u) i nullable(v)	ako nullable(u) onda firstpos(u) ∪ firstpos(v) drugo firstpos(u)	ako nullable(v) onda lastpos(u) ∪ lastpos(v) drugo lastpos(v)
v *	tačno	firstpos(v)	lastpos(v)

Building followpos

Funkcija followpos izračunato kroz nullable, firstpos i lastpos... Funkcija followpos definisano na različitim pozicijama. Vrijednost followpos je niz pozicija. Ako i- pozicija, onda followpos(i) ima mnogo pozicija j tako da postoji neki niz... cd... uključeno u jezik koji je opisao PB, tako da i odgovara ovom unosu c, a j- ulaz d... Funkcija followpos također se može izračunati u jednom obilasku stabla prema sljedeća dva pravila

1. Neka n- interni čvor sa operacijom "." (konkatenacija); a, b- njegovi potomci. Zatim za svaku poziciju i uključeno u lastpos(a followpos(i) gomila firstpos(b).
2. Neka n- interni čvor sa operacijom "*" (iteracija), a- njegov potomak. Zatim za svaku poziciju i uključeno u lastpos(a), dodati skupu vrijednosti followpos(i) gomila firstpos(a).

Primjer

Izračunajte vrijednost funkcije followpos za regex ( a(b|c))*c.

Pozicija	Značenje followpos
1: (a (b|c))*c	{2, 3}
2: (a(b |c))*c	{1, 4}
3: (a(b|c ))*c	{1, 4}
4: (a(b|c))*c	{5}

Izgradnja DFA

DCA je skup stanja i skup prijelaza između njih. DFA stanje je skup pozicija. Izgradnja DFA se sastoji u postepenom dodavanju potrebnih stanja u njega i konstrukciji prijelaza za njih. U početku postoji jedna država, firstpos(root) (root- korijen stabla), koji nema prijelaza. Prijelaz se vrši pomoću znakova iz regularnog izraza. Svaki znak odgovara skupu pozicija ( str i). Ujedinjujući sve followpos(x) je stanje u koje je potrebno ići, gdje je x pozicija koja je prisutna i među pozicijama stanja i među pozicijama simbola iz PB-a, duž koje se vrši prijelaz. Ako takvo stanje ne postoji, onda se mora dodati. Proces se mora ponavljati dok se ne izgrade svi prijelazi za sva stanja. Sva stanja koja sadrže položaj simbola # dodanog na kraj PB-a proglašavaju se konačnim.

DFA dobijen od PB ( a(b|c))*c

Primjer

Konstruirajte DFA koristeći regularni izraz ( a(b|c))*c.

DKA stanje	Simbol
	a (1)	b (2)	c (3, 4)
A (1, 4)	B (2, 3)	-	C (5)
B (2, 3)	-	A (1, 4)	A (1, 4)
C (5)	-	-	-

Izgradnja DFA sa minimalnim brojem stanja

DFA sa minimalnim brojem stanja se konstruiše za svuda definisanu DFA, tj. takav da. Za bilo koji DFA postoji svugdje definiran DFA ekvivalent njemu.

Izgradnja svuda definisanog DFA

Hajde da uvedemo novo stanje i definišemo novi skup stanja .

Definirajmo novu prijelaznu funkciju ovako:

Izgradnja pregrada (formalno)

Napravimo početnu particiju P skupove stanja u dvije grupe: konačna stanja F i ostalo S \ F, tj. P = {F, Q \ F}.

Prijavite se za svaku grupu G ∈ P sledeća procedura. Raskid G u podgrupe tako da države s i t od G završio u istoj grupi ako i samo ako za svaki ulazni simbol a bogatstva s i t imati uključene prelaze a državama iz iste grupe do P.

Rezultirajuće podgrupe se dodaju novoj particiji. P novo.

Prihvatamo P = P novi i ponavljajte konstrukciju particije dok se ne stabilizuje, odnosno dok se particija ne prestane mijenjati.

Particioniranje (algoritam)

Postoji sljedeći algoritam za konstruiranje particije. Gradimo prelaznu tabelu za originalni automat, gradimo početnu particiju.

Svakoj grupi iz particije je dodijeljen identifikator (za početnu particiju, na primjer, 0 i 1).

Svakom stanju (svakom redu tabele) je dodijeljena linija oblika “a.bcd ... xyz”, gdje je identifikator grupe kojoj pripada stanje iz [prve kolone (odakle idemo), druga kolona (gdje idemo po prvom znaku), ..., posljednja kolona (gdje idemo po zadnjem znaku)].

Nove grupe gradimo slučajnošću linija, odnosno tako da države sa istim zadatim linijama spadaju u jednu grupu.

Zatim, nova iteracija. Rezultirajućim grupama dodjeljujemo nove identifikatore, na primjer (0, 1, ..., n). I ponavljamo konstrukciju pregrade do stabilizacije.

Imajte na umu da kada u grupi ostane samo jedno stanje, u narednim fazama izgradnje particije, više ne možete ispisati niz identifikatora za ovo stanje, jer će ovaj niz u svakom slučaju biti jedinstven zbog prvog znaka niza. Drugim riječima, tokom particije se ništa ne dešava grupi iz jednog stanja - ona se prenosi na novu particiju kakva jeste.

Konstrukcija redukovanog automata

Svaka od rezultirajućih grupa postaje stanje novog DCA. Ako grupa sadrži početno (konačno) stanje originalnog automata, ova grupa postaje početno (odnosno, konačno) stanje novog DFA. Tranzicije se grade na očigledan način: prijelaz u stanje iz grupe smatra se prijelazom u grupu.

Dajemo mašinu. Prvo uklanjamo negenerativne (sterilne, "mrtve"), onda nedostižna stanja (definicije su date za simbole, ali se očito prenose na stanja automata).

Uopšteno govoreći, uklanjanje mrtvih stanja pretvara DFA u NFA, pošto u DFA svi prijelazi moraju biti definirani. Međutim, u Knjizi zmajeva takvo se odstupanje od formalne definicije smatra prihvatljivim.

Primjer

Jer, konstruišemo DFA sa minimalnim brojem stanja za DFA sledećeg oblika:

• Početna particija: (C) ( konačno stanje), (A, B, D, E) ( sve druge države).
• (C) ( bez promjena), (A, D, E), (B), ( pošto od A, D, E duž a, c idemo do B i C, redom).
• Ne možemo više praviti particije.

Neka stanje C odgovara grupi (C), stanje A grupi (A, D, E), a stanje B grupi (B). Tada dobijamo DFA sa minimalnim brojem stanja:

Primjer (algoritam izgradnje particija)

Prijelazna tablica za svuda definiranu (dodatno stanje Z) DFA koja odgovara PB (ab | ε) a * | abb | b * a. Od ispitnih zadataka 2012.

	a	b	I 0	I 1
→ A *	B	C	0.01	0.12
B *	D	E	0.00	1.01
C	F	C	1.01
D *	D	Z	0.01	0.04
E *	D	Z	0.00	1.03
Ž *	Z	Z	0.11
Z	Z	Z	1.11

Iteracije:

• I 0: ABCDEF (0), CZ (1).
• I 1: AD (0), BE (1), C (2), F (3), Z (4).
• I 2: A, B, C, D, E, F, Z.

Rezultat: mašina je ionako imala minimalan broj stanja :-)

DFA omogućava proširenje jezika

Algoritam za konstruisanje DFA uzimajući dopunu jezika L (L̅) sastoji se od dva koraka:

• Izgradnja kompletnog DFA
• Konstruisanje potrebnog automata od njega

U stvari, ne postoji takva stvar kao potpuni DFA. Pod punim DKA neki nastavnici razumeju automat, u čijoj prelaznoj tabeli nema praznih ćelija. Međutim, u skladu sa definicijom DFA - δ: Q × Σ → Q - u svakom slučaju ne može biti praznih ćelija. Međutim, automat sa praznim ćelijama zadovoljava definiciju NFA. U toku rješenja često se dobije upravo takav NSC, kojem nedostaju samo prijelazi u DSC.

Da biste ga nadopunili, dovoljno je dodati novo stanje X, i "umjesto" nepostojećih prijelaza dodajte prijelaze u ovo novo stanje. U ovom slučaju, ne zaboravite dodati prijelaze iz X v X... Lako je vidjeti da tamo gdje originalni automat nije prihvatio određeni lanac zbog odsustva tranzicije, nova mašina ići će u državu X i "zakači" se u njemu. Pošto novo stanje ne prihvata (konačno), novi automat neće prihvatiti ni ovaj lanac.

Sada, da bi se konstruisao traženi automat, potrebno je samo promeniti uloge prihvatajućih i neprihvatajućih stanja. Drugim riječima, F "= Q \ F.

Izgradnja LL (k) analizatora

Pretvaranje gramatike

Nije svaka gramatika LL (k) raščlanjena. Gramatika bez konteksta pripada klasi LL (1) ako u njoj nema sukoba tipa FIRST-FIRST (lijeva rekurzija - poseban slučaj takav sukob) i FIRST-FOLLOW.

Ponekad je moguće transformisati ne-LL (1) gramatike tako da postanu LL (1). Neke (tačnije one o kojima je bilo riječi u kursu) date su u nastavku.

Uklanjanje lijeve rekurzije

Pretpostavimo da imamo pravilo oblika (u daljem tekstu u ovom odeljku, velika slova - neterminalnih simbola, mala slova - nizovi bilo kojih znakova):

• A → A a| A b| … | A k | m | n | … | z

Ne podliježe jednoznačnoj analizi, pa ga treba transformisati.

Lako je pokazati da je ovo pravilo ekvivalentno sljedećem paru pravila:

• A → m B | n B | … | z B
• B → a B | b B | … | k B | ε

Lijeva faktorizacija

Suština ovog postupka je otklanjanje nejasnoća u izboru pravila za lijevi simbol. Da biste to učinili, pronalazi se zajednički lijevi prefiks i ono što može uslijediti stavlja se u novo pravilo (mala slova - nizovi bilo kojih znakova)

Primjer

• A → a c | a df | a dg | b

Pretvoreno u

• A → a B | b
• B → c | d f | d g

Što će se zauzvrat pretvoriti u

• A → a B | b
• B → c | d WITH
• C → f | g

Primjer konverzije gramatike

G= ((S, A, B), (a, b, c), P, S)

• S → SAbB | a
• A → ab | aa | ε
• B → c | ε

Uklanjanje lijeve rekurzije za S:

• S → asS 1
• S 1 → AbBS 1 | ε

Lijeva faktorizacija za A:

• A → aA 1 | ε
• A 1 → b | a

Završna gramatika:

• S → asS 1
• S 1 → AbBS 1 | ε
• A → aA 1 | ε
• A 1 → b | a
• B → c | ε

Zgrada PRVO i PRVO

PRVI (α), gdje je α ∈ (N ∪ T) * skup terminala od kojih α može početi. Ako je α ⇒ ε, onda je ε ∈ PRVI (α). Shodno tome, vrijednost FOLLOW ( A) za neterminalnu A- mnogi terminali koji se mogu pojaviti odmah nakon toga A u bilo kom obliku rečenice. Ako A može biti krajnji desni znak u nekom obliku rečenice, tada konačni $ marker također pripada FOLLOW ( A)

Izračunavanje PRVO

Za terminale

• Za bilo koji terminal x, x ∈ T, PRVI ( x) = {x}

Za ne-terminale

• Ako X je neterminal, onda stavljamo PRVI ( X) = {∅}
• Ako postoji pravilo u gramatici X→ ε, zatim dodamo ε na PRVO ( X)
• Za svaki neterminal X i za svako pravilo zaključivanja X → Y 1 …Y k dodaj u PRVO ( X) skupa PRVI od svih simbola na desnoj strani pravila do prvog iz kojeg se ε ne izvodi, uključujući i njega

Za lance

• Za niz znakova X 1 …X k FIRST je konkatenacija FIRST karaktera u lancu do prvog sa ε ∉ FIRST, uključujući i njega.

Primjer

• S → asS 1
• S 1 → AbBS 1 | ε
• A → aA 1 | ε
• A 1 → b | a
• B → c | ε

PRVI neterminali po redoslijedu rješavanja ovisnosti:

• PRVI (S) = (a)
• PRVI (A) = (a, ε)
• PRVI (A 1) = (b, a)
• PRVI (B) = (c, ε)
• PRVI (S 1) = (a, b, ε)

PRVO za pravila povlačenja:

• PRVI (aS 1) = (a)
• PRVI (AbBS 1) = (a, b)
• PRVI (ε) = (ε)
• PRVI (aA 1) = (a)
• PRVI (a) = (a)
• PRVI (b) = (b)
• PRVI (c) = (c)

Izračunavanje FOLLOW

Procjena funkcije FOLLOW za znak X:

• Neka FOLLOW (X) = (∅)
• Ako je X aksiom gramatike, dodajte token $ u FOLLOW
• Za sva pravila oblika A → αXβ dodajte PRVI (β) \ (ε) u FOLLOW (X) (X može biti praćen onim simbolima sa kojima β počinje)
• Za sva pravila oblika A → αX i A → αXβ, ε ∈ FIRST (β), dodajte FOLLOW (A) u FOLLOW (X) (to jest, X mogu biti praćeni svim simbolima koji mogu pratiti A ako su na izlazu pravilo, X može biti na desnoj strani)
• Ponavljajte prethodne dvije tačke što je duže moguće da dodate znakove u skup

Primjer

• S → asS 1
• S 1 → AbBS 1 | ε
• A → aA 1 | ε
• A 1 → b | a
• B → c | ε

rezultat:

• PRATI (S) = ($)
• FOLLOW (S 1) = ($) (S 1 je krajnji desni znak u pravilu S → aS 1)
• PRATI (A) = (b) (nakon A u pravilu S 1 → AbBS 1, slijedi b)
• FOLLOW (A 1) = (b) (A 1 je krajnji desni znak u pravilu A → aA 1, stoga dodajte FOLLOW (A) u FOLLOW (A 1))
• PRATI (B) = (a, b, $) (dodati PRVO (S 1) \ (ε) (slijedi iz pravila S 1 → AbBS 1), PRATI (S 1) (pošto postoji S 1 → ε))

Sastavljanje tabele

U tabeli M za par koji nije terminal-terminal (u ćeliji M[A, a]) specificira pravilo prema kojem je potrebno izvršiti preklapanje ulazne riječi. Tabela se popunjava na sljedeći način: za svako pravilo zaključivanja za datu gramatiku A → α (gdje α označava lanac na desnoj strani pravila), izvode se sljedeće radnje:

1. Za svaki terminal a∈ FIRST (α) dodati pravilo A → α To M[A, a]
2. Ako je ε ∈ FIRST (α), onda za svaki b∈ PRATI ( A) dodati A → α To M[A, b]
3. ε ∈ PRVI (α) i $ ∈ PRVI ( A), dodati A → α To M[A, $]
4. Sve prazne ćelije su greška u ulaznoj riječi

Primjer

Napravite tabelu za gramatiku

• S → asS 1
• S 1 → AbBS 1 | ε
• A → aA 1 | ε
• A 1 → b | a
• B → c | ε

rezultat:

	a	b	c	$
S	S → asS 1 (Prvo pravilo, zaključak S → aS 1, a ∈ FIRST (aS 1))	Greška (četvrto pravilo)	Greška (četvrto pravilo)	Greška (četvrto pravilo)
S 1	S 1 → AbBS 1 (Prvo pravilo, izlaz S 1 → AbBS 1, a ∈ FIRST (AbBS 1))	S 1 → AbBS 1 (Prvo pravilo, izlaz S 1 → AbBS 1, b ∈ FIRST (AbBS 1))	Greška (četvrto pravilo)	S 1 → ε (Treće pravilo, zaključak S 1 → ε, ε ∈ PRVI (ε), $ ∈ FOLLOW (S 1))
A	A → aA 1 (Prvo pravilo, zaključak A → aA 1, a ∈ FIRST (aA 1))	A → ε (Drugo pravilo, zaključak A 1 → ε, b ∈ PRATI (A 1))	Greška (četvrto pravilo)	Greška (četvrto pravilo)
A 1	A 1 → a (Prvo pravilo, zaključak A 1 → a, a ∈ FIRST (a))	A 1 → b (Prvo pravilo, zaključak A 1 → b, b ∈ FIRST (b))	Greška (četvrto pravilo)	Greška (četvrto pravilo)
B	B → ε	B → ε (Drugo pravilo, zaključak B → ε, a ∈ PRATI (B))	B → c (Prvo pravilo, zaključak B → c, c ∈ FIRST (c))	B → ε (Treće pravilo, zaključak B → ε, $ ∈ PRATI (B))

Parsiranje niza

Proces raščlanjivanja niza je prilično jednostavan. Njegova suština je sljedeća: na svakom koraku se čita gornji znak v c ulazni lanac.

• Ako v- simbol terminala
  • Ako v poklapa se sa With tada su oba uništena, dolazi do pomaka
  • Ako v ne odgovara With, tada se signalizira greška raščlanjivanja
• Ako v- neterminalni simbol, c vraća se na početak reda, umjesto v vraća se u stog desni dio pravilo koje je preuzeto iz ćelije tabele M[v, c]

Proces se završava kada i linija i snop dođu do zadnjeg markera (#).

Primjer

hajde da raščlanimo red "aabbaabcb":

stog	linija	akcija
S#	a abbaabcb $	S → asS 1
a S 1 #	a abbaabcb $	smjena
S 1#	a bbaabcb $	S 1 → AbBS 1
A bBS 1 #	a bbaabcb $	A → aA 1
a A 1 bBS 1 #	a bbaabcb $	smjena
A 1 bBS 1 #	b baabcb $	A 1 → b
b bBS 1 #	b baabcb $	smjena
b BS 1 #	b aabcb $	smjena
B S 1 #	a abcb $	B → ε
S 1#	a abcb $	S 1 → AbBS 1
A bBS 1 #	a abcb $	A → aA 1
A bBS 1 #	a abcb $	A → aA 1
a A 1 bBS 1 #	a abcb $	smjena
A 1 bBS 1 #	a bcb $	A 1 → a
a bBS 1 #	a bcb $	smjena
b BS 1 #	b cb $	smjena
B S 1 #	c b $	B → c
c S 1 #	c b $	smjena
S 1#	b$	S 1 → AbBS 1
A bBS 1 #	b$	A → ε
b BS 1 #	b$	smjena
B S 1 #	$	B → ε
S 1#	$	S 1 → ε
#	$	spreman

Izgradnja LR (k) analizatora

Izračun k u LR (k)

Ne postoji algoritam koji bi omogućio, u opštem slučaju, izračunavanje k za proizvoljnu gramatiku. Obično je vrijedno pokušati napraviti LR (1) parser. Ako ima najviše jednu operaciju za svaki skup (Shift, Reduce ili Accept), onda je gramatika LR (0). Ako pri konstruisanju LR (1) -analizatora dođe do sukoba i kolizije, onda ova gramatika nije LR (1) i vredi pokušati konstruisati LR (2). Ako ga ne uspije konstruirati, onda LR (3) i tako dalje.

Dovršavanje gramatike

Dodajmo novo pravilo S "→ S, i učinimo S" aksiomom gramatike. Ovo dodatno pravilo je potrebno da bi se odredilo kada je analizator isključen i tolerancija ulazne prečke. Prijem se vrši ako i samo ako je moguće izvršiti konvoluciju prema pravilu S → S".

Konstrukcija kanonskog sistema skupova dozvoljenih LR (1) -situacija

Na početku se nalazi skup I 0 sa konfiguracijom analizatora S "→ .S, $. Zatim se operacija zatvaranja primjenjuje na ovu konfiguraciju sve dok se nove konfiguracije više ne dodaju kao rezultat njene primjene. Zatim se prelazi na novu skupovi se konstruiraju pomicanjem tačke za jedan znak udesno (prijelazi se vrše prema karakteru koji je stajao iza tačke prije prijelaza i prije nje nakon prijelaza), a one konfiguracije koje su dobijene od postojećih na ovaj način Za njih se takođe primenjuje operacija zatvaranja i ceo proces se ponavlja sve dok novi setovi ne prestanu da se pojavljuju.

Primjer

Konstruisati kanonski sistem skupova dozvoljenih LR (1) -situacija za navedenu gramatiku:

• S "→ S
• S → ABA
• A → Aa | ε
• B → cBc | d

Rješenje:

• Napravite zatvaranje za konfiguraciju S "→ .S, $:
  • S → .ABA, $
• Za rezultirajuće konfiguracije (S → .ABA, $), također konstruiramo zatvaranje:
  • A → .Aa, c
  • A → .Aa, d
  • A →., C
  • A →., D
• Za rezultirajuće konfiguracije (A → .Aa, c; A → .Aa, d) također konstruiramo zatvaranje:
  • A → .Aa, a
  • A →., A
• Više konfiguracija u I 0 stanju se ne može izgraditi - zatvaranje je izgrađeno

• Od I 0 možete napraviti prijelaze duž S i A i dobiti skup konfiguracija I 1 i I 2, koji se sastoji od sljedećih elemenata:
  • I 1 = (S "→ S., $)
  • I 2 = (S → A.BA, $; A → A.a, c; A → A.a, d; A → A.a, a)
• I 1 ne zahtijeva zatvaranje
• Konstruirajmo zatvaranje I 2:
  • B → .cBc, a
  • B → .cBc, $
  • B → .d, a
  • B → .d, $
• Svi ostali skupovi su konstruisani slično.

Izrada tabele parsera

Završna faza u konstrukciji LR (1) analizatora je izrada tablica Akcija i Idi... sto Akcija je izgrađen za znakove ulaznog reda, odnosno za terminale i marker kraja reda $, tabela Idi je izgrađen za gramatičke simbole, odnosno za terminale i neterminale.

Pravljenje Goto stola

Tabela Goto prikazuje stanje u koje treba ići kada se naiđe na sljedeći gramatički simbol. Stoga, ako u sistemu kanonskog skupa postoji prijelaz iz I i v I j znakom A, zatim u Goto ( I i, A) stavljamo stanje I j... Nakon popunjavanja tabele, pretpostavljamo da u svim praznim ćelijama Idi na ( I i, A) = Greška

Izgradnja tabele akcija

• Ako postoji prijelaz preko terminala a iz stanja I i u stanje I j, tada je Akcija (I i, a) = Shift (I j)
• Ako je A ≠ S" konfiguracija A → α., A, tada Akcija (I i, a) = Reduciranje (A → α)
• Za stanje I i, u kojem postoji konfiguracija S "→ S., $, Akcija (I i, $) = Prihvati
• Za sve prazne ćelije Akcija (I i, a) = Greška

Primjer

Izgradite Akcije i Goto tabele za gramatiku

• S "→ S
• S → ABA
• A → Aa | ε
• B → cBc | d

Rješenje:

	Akcija				Idi
	a	c	d	$	S	S "	A	B	a	c	d
I 0	Smanjiti (A → ε)	Smanjiti (A → ε)	Smanjiti (A → ε)		I 1		I 2
I 1				Prihvati
I 2	Shift (I 6)	Shift (I 4)	Shift (I 5)					I 3	ja 6	I 4	ja 5
I 3	Smanjiti (A → ε)			Smanjiti (A → ε)			I 13
I 4		Shift (I 8)	Shift (I 9)					ja 7		ja 8	ja 9
ja 5	Smanjiti (B → d)			Smanjiti (B → d)
ja 6	Smanjiti (A → Aa)	Smanjiti (A → Aa)	Smanjiti (A → Aa)
ja 7		Shift (I 10)								I 10
ja 8		Shift (I 8)	Shift (I 9)					I 11		ja 8	ja 9
ja 9		Smanjiti (B → d)
I 10	Smanji (B → cBc)			Smanji (B → cBc)
I 11		Shift (I 12)								I 12
I 12		Smanji (B → cBc)
I 13	Shift (I 14)			Smanji (S → ABA)					I 14
I 14	Smanjiti (A → Aa)			Smanjiti (A → Aa)

Raščlanjivanje lanca

Glavni znak se čita na svakom koraku v iz steka parsera i uzmite ekstremni karakter c ulazni lanac.

Ako je tabela akcija na raskrsnici v i c nalazi se:

• Shift ( I k), zatim With i onda I k... Gde c je uklonjen iz niza.
• Smanjiti ( A → u), tada se svi terminalni i neterminalni simboli koji čine lanac brišu sa vrha steka u, nakon čega država gleda ja sam ostajući na vrhu. Prema prelaznom stolu na raskrsnici ja sam i A sljedeće stanje je pronađeno I s... Zatim se A gura na stek, a zatim I s... Linija ostaje nepromijenjena.
• Prihvatite, tada je raščlanjivanje završeno
• praznina je greška

Primjer

Hajde da raščlanimo niz aaaccdcc:

Stack	Linija	Akcija
I 0	a aaccdcc $	Smanjite (A → ε), idite na I 2
I 0 A I 2	a aaccdcc $	Shift (I 6)
I 0 A I 2 a ja 6	a accdcc $	Smanjite (A → Aa), idite na I 2
I 0 A I 2	a accdcc $	Shift (I 6)
I 0 A I 2 a ja 6	a ccdcc $	Smanjite (A → Aa), idite na I 2
I 0 A I 2	a ccdcc $	Shift (I 6)
I 0 A I 2 a ja 6	c cdcc $	Smanjite (A → Aa), idite na I 2
I 0 A I 2	c cdcc $	Shift (I 4)
I 0 A I 2 c I 4	c dcc $	Shift (I 8)
I 0 A I 2 c I 4 c ja 8	d cc $	Shift (I 9)
I 0 A I 2 c I 4 c I 8 d ja 9	c c $	Smanjite (B → d), idite na I 11
I 0 A I 2 c I 4 c I 8 B I 11	c c $	Shift (I 12)
I 0 A I 2 c I 4 c I 8 B I 11 c I 12	c$	Smanjite (B → cBc), idite na I 7
I 0 A I 2 c I 4 B ja 7	c$	Shift (I 10)
I 0 A I 2 c I 4 B I 7 c I 10	$	Smanjite (B → cBc), idite na I 3
I 0 A I 2 B I 3	$	Smanjite (A → ε), idite na I 13
I 0 A I 2 B I 3 A I 13	$	Smanjite (S → ABA), idite na I 1
I 0 S I 1	$	Prihvati

Prijevod aritmetičkih izraza (Seti-Ullman algoritam)

Bilješka. Kod je generisan doggy style kao Motorola, tj.

Op Arg1, Arg2

označava

Arg2 = Arg1 Op Arg2

Izgradnja drveta

Stablo je izgrađeno kao i obično za aritmetički izraz: u korijenu, operacija s najnižim prioritetom, nakon čega slijede operacije sa nešto višim prioritetom, i tako dalje. Zagrade imaju najveći prioritet. Ako postoji više operacija sa istim prioritetom - a op b op c, tada se stablo konstruiše kao za izraz (a op b) op c.

Primjer

Napravite stablo za izraz a + b / (d + a - b × c / d - e) + c × d

Rješenje: Zapišimo izraz u formu

((a) + ((b) / ((((d) + (a)) - ((b) × (c)) / (d)) - (e)))) + ((c) × ( d))

Zatim će u korijenu svakog podstabla biti operacija, a izrazi u zagradama lijevo i desno od njega će biti njegova podstabla. Na primjer, za podizraz ((b) × (c)) / (d) u ​​korijenu odgovarajućeg podstabla bit će operacija “/”, a njegova podstabla će biti podizrazi ((b) × (c)) i (d).

Izgled stabla (izračunavanje broja registara)

• Ako je vrh lijevi list (tj. varijabla), onda ga označavamo nulom.
• Ako je vrh desni list, onda ga označavamo jednim
• Ako smo označili oba njegova podstabla za neki vrh, onda ćemo ga označiti na sljedeći način:
  • Ako su lijevo i desno podstablo označeno različiti brojevi, zatim biramo najveći od njih
  • Ako su lijevo i desno podstablo označeno isti brojevi, onda je ovo podstablo povezano s brojem za jedan većim od onog kojim su označena podstabla

Oznake na listovima	Izgled stabla sa istim podstablima	Lijevo podstablo je označeno velikim brojem	Desno podstablo je označeno velikim brojem

desno - isto kao predak.

Ako etiketa lijevo potomak više oznake u pravu, onda u pravu djetetu se dodjeljuje registar još jedan nego predak, i lijevo - isto kao predak.

Kod se formira prelaskom stabla odozdo prema gore na sljedeći način:

1. Za vrh sa oznakom 0, kod se ne generiše

2. Ako je vrh list X sa oznakom 1 i registrom R i, tada se kod slaže s njim

MOVE X, Ri

3. Ako je vrh interni sa registrom R i a njegovo lijevo dijete je list X sa oznakom 0, tada odgovara kodu

<Код правого поддерева>Op X, Ri

4. Ako podstabla vrha sa registrom R i- ne ostavlja i oznaka desnog vrha je veća ili jednaka oznaci lijevog (u kojem je registar Rj, j = i + 1), tada vrh odgovara kodu

<Код u pravu podstablo><Код lijevo podstablo> Op Rj, Ri

5. Ako podstabla vrha sa registrom R i- ne ostavlja i oznaka desnog vrha (za koji je registar Rj, j = i + 1) manja od oznake lijevog, tada vrh odgovara kodu

Distribucija registara je prikazana na grafikonu desno. Generirani kod:

MOVE d, R0; R0 = d MOVE c, R1; R1 = c MUL b, R1; R1 = (b × c) DIV R1, R0; R0 = (b × c) / d MOVE a, R1; R1 = a DODATI d, R1; R1 = a + d SUB R1, R0; R0 = (a + d) - ((b × c) / d) MOVE e, R1; R1 = e SUB R0, R1; R1 = ((a + d) - ((b × c) / d)) - e MOVE R1, R0; R0 = ((a + d) - ((b × c) / d)) - e DIV b, R0; R0 = b / (((a + d) - ((b × c) / d)) - e) DODATI a, R0; R0 = a + (b / (((a + d) - ((b × c) / d )) - e)) MOVE d, R1; R1 = d MUL c, R1; R1 = c × d DODAJ R0, R1; R1 = (a + (b / (((a + d) - ((b × c) ) / d)) - e))) + (c × d) MOVE R1, R0; R0 = (a + (b / (((a + d) - ((b × c) / d)) - e) )) + (c × d)

Prijevod logičkog izraza

Ovaj odjeljak vam pokazuje kako generirati kod za lijenu evaluaciju Bulovih izraza. Kao rezultat rada algoritma, dobije se dio koda koji, koristeći TST, BNE, BEQ operacije, izračunava logički izraz skokom na jednu od oznaka: TRUELAB ili FALSELAB.

Izgradnja drveta

Stablo logičkog izraza odražava redosled njegovog izračunavanja u skladu sa prioritetom operacija, odnosno da bismo izračunali vrednost određenog čvora stabla (što je operacija iz dva operanda koja su podstabla čvora), moramo prvo izračunajte vrijednosti njegovih podstabala.

Prioritet operacija: NOT ima najveći prioritet, nakon čega slijedi AND i zatim OR. Ako izraz koristi drugi logičke operacije onda se moraju izraziti u terminima ova tri na određeni način (obično, nema drugih operacija i nije potrebna konverzija izraza). Asocijativnost operacija istog prioriteta je s lijeva na desno, odnosno A i B i C se tretiraju kao (A i B) i C

Primjer

Napravite stablo za logički izraz ne A ili B i C i (B ili ne C).

Rješenje: vidi dijagram sa desne strane.

Za svaki čvor stabla izračunavaju se 4 atributa:

• Broj čvora
• Oznaka na koju treba ići ako je izraz u čvoru lažan (lažna oznaka, fl)
• Oznaka kamo ići ako je izraz u čvoru istinit (true label, tl)
• Potpišite (pogledajte dolje za detalje)

Vrhovi su numerisani bilo kojim redom, jedini uslov je jedinstvenost brojeva čvorova.

Drvo je označeno na sledeći način:

• Fl označava broj vrha na koji je napravljen prijelaz ili falselab, ako je ovaj vrh lažan
• tl označava broj vrha na koji je napravljen prijelaz ili truelab, ako je ovaj vrh istinit

Znak označava kada treba prekinuti računanje trenutnog podstabla.

Za korijen stabla fl = falselab, tl = truelab, sign = false.

Na ovaj način:

Primjer

Označite stablo izgrađeno za logički izraz ne A ili B i C i (B ili ne C).

Generisanje koda

Strojne komande korištene u generiranom kodu:

• TST - provjera argumenta za istinitost i postavljanje zastave ako je argument lažan
• BNE - skočiti na etiketu ako zastavica nije postavljena, odnosno stanje provjereno pomoću TST-a zaista
• BEQ - skočiti na etiketu ako je postavljena zastavica, odnosno stanje provjereno pomoću TST-a lažno

Kod je napravljen na sljedeći način:

• stablo se prelazi iz korijena, za AND i OR, prvo se prelazi lijevo podstablo, zatim desno
• za svaki prođeni vrh ispisuje se njegov broj (oznaka).
• za list A (broj, tl, fl, znak) ispisuje se TST A
  • ako je znak == istina, ispisuje se BNE tl
  • ako je znak == netačan, ispisuje se BEQ fl

Primjer

Za gornji izraz, generirat će se sljedeći kod:

1: 2: 4: TST A BEQ TRUELAB 3: 5: 7: TST B BEQ FALSELAB 8: TST C BEQ FALSELAB 6: 9: TST B BNE TRUELAB 10:11: TST C BNE FALSELAB TRUELAB: FALSELAB:

Metoda podudaranja uzorka

Ideja iza metode je da se kod može generirati za isti dio programa. Različiti putevi, i, kao posljedica toga, moguće je postići optimizaciju za jedan ili drugi parametar.

Formulacija problema

Postoji mnogo uzoraka, za svaki od njih postoji definiran dio međureprezentacije za koji je primjenjiv, težina i generirani kod. Postoji srednje stablo predstavljanja, koje je fragment programa za koji trebate generirati kod. Cilj je konstruisati takav obuhvat stabla srednjeg predstavljanja uzorcima tako da ukupna težina uzoraka bude minimalna.

Obrasci su upute za sklapanje i raščlanjivanje stabala koja im odgovaraju. Za svaki uzorak poznato je njegovo vrijeme izvršenja (u tikovima). Uz njihovu pomoć ćemo generisati optimalan (u smislu vremena izvršenja) kod.

Uzorci uzoraka

Izgradnja posredne reprezentacije

Prvo, gradimo stablo raščlanjivanja za cijeli izraz.

Izgradnja pokrivenosti

Sada, za svaki vrh (prelazimo ih po redu od listova do korijena), generirat ćemo optimalni kod za njegovo podstablo. Da biste to učinili, jednostavno ponovite sve obrasce primjenjive na ovom vrhu. Vrijeme izvršenja kada se koristi određeni uzorak bit će zbir vremena potrebnog za izračunavanje njegovih argumenata (a već znamo optimalni kod za njihovo izračunavanje zbog redoslijeda obilaženja stabla) i vremena izvršavanja samog uzorka. Od svih dobijenih opcija biramo najbolju - to će biti optimalni kod za podstablo ovog vrha. U korenu stabla dobijamo optimalni kod za ceo izraz.

Generisanje koda

Nije potrebno pisati kod za sve vrhove - dovoljno je napisati minimum potrebno vrijeme i uzorak za korištenje. Ostatak ovoga je lako nadoknadiv.

U ovim zadacima imamo beskonačan broj registara, tako da svaki put možete koristiti novi.

Izgradnja RT iz DFA

Izgradnja NFA koristeći pravolinearnu gramatiku

Redukcija gramatike

Da biste proizvoljnu CS gramatiku pretvorili u njen redukovani oblik, morate izvršiti sljedeće korake:

• ukloniti sve jalove simbole;
• ukloniti sve nedostižne znakove;

Uklanjanje beskorisnih simbola

ulaz: KS-gramatika G = (T, N, P, S).

Izlaz: KS-gramatika G '= (T, N', P', S), koja ne sadrži sterilne simbole, za koje je L (G) = L (G').

Metoda:

Rekurzivno konstruirajte skupove N 0, N 1, ...

1. N 0 = ∅, i = 1.
2. N i = (A | (A → α) ∈ P i α ∈ (N i - 1 ∪ T) *) ∪ N i-1.
3. Ako je N i ≠ N i - 1, tada je i = i + 1 i idite na korak 2, inače N ’= N i; P ’sastoji se od pravila skupa P koja sadrže samo simbole iz N’ ∪ T; G '= (T, N', P', S).

definicija: simbol x ∈ (T ∪ N) naziva se nedostižnim u gramatici G = (T, N, P, S) ako se ne pojavljuje ni u jednom od rečeničnih oblika ove gramatike.

Primjer

Uklonite beskorisne znakove iz gramatike G ((A, B, C, D, E, F, S), (a, b, c, d, e, f, g), P, S)

• S → AcDe | CaDbCe | SaCa | aCb | dFg
• A → SeAd | cSA
• B → CaBd | aDBc | BSCf | bfg
• C → Ebd | Seb | aAc | cfF
• D → fCE | ac | dEdAS | ε
• E → ESacD | aec | eFf

Rješenje

• N 0 = ∅
• N 1 = (B (B → bfg), D (D → ac), E (E → aec))
• N 2 = (B, D, E, C (C → Ebd))
• N 3 = (B, D, E, C, S (S → aCb))
• N 4 = (B, D, E, C, S) = N 3

G "((B, C, D, E, S), (a, b, c, d, e, f, g), P", S)

• S → CaDbCe | SaCa | aCb
• B → CaBd | aDBc | BSCf | bfg
• C → Ebd | Seb
• D → fCE | ac | ε
• E → ESacD | aec

Uklanjanje nedostupnih znakova

ulaz: KS-gramatika G = (T, N, P, S)

Izlaz: CS-gramatika G '= (T', N ', P', S), koja ne sadrži nedostižne znakove, za koje je L (G) = L (G ').

Metoda:

1. V 0 = (S); i = 1.
2. V i = (x | x ∈ (T ∪ N), (A → αxβ) ∈ P i A ∈ V i - 1) ∪ V i-1.
3. Ako je V i ≠ V i - 1, tada je i = i + 1 i idite na korak 2, inače N ’= V i ∩ N; T '= V i ∩ T; P 'sastoji se od pravila skupa P koja sadrži samo simbole iz V i; G '= (T', N ', P', S).

definicija: Za CS gramatiku G se kaže da je redukovana ako ne sadrži nedostižne i sterilne simbole.

Primjer

Uklonite nedostupne znakove iz gramatike G"((B, C, D, E, S), (a, b, c, d, e, f, g), P", S)

• S → CaDbCe | SaCa | aCb
• B → CaBd | aDBc | BSCf | bfg
• C → Ebd | Seb
• D → fCE | ac | ε
• E → ESacD | aec

Rješenje

• V 0 = (S)
• V 1 = (S, C (S → CaDbCe), D (S → CaDbCe), a (S → CaDbCe), b (S → CaDbCe), e (S → CaDbCe))
• V 2 = (S, C, D, a, b, e, E (C → Ebd), d (C → Ebd), f (D → fCE))
• V 3 = (S, C, D, E, a, b, d, e, f, c (E → ESacD))
• V 4 = (S, C, D, E, a, b, d, e, f, c) = V 3

G "" ((C, D, E, S), (a, b, c, d, e, f), P "", S)

• S → CaDbCe | SaCa | aCb
• C → Ebd | Seb
• D → fCE | ac | ε
• E → ESacD | aec

Povratak