Potrebné pre nedeterministický stavový automat M = (Q, T, D, q 0 , F) vybudovať deterministický konečný automat M = (Q", T, D", q" 0 , F"). Počiatočný stav pre rozostavaný automat je ε-uzavretie počiatočného stavu počiatočného automatu. ε-uzavretie - množina stavov, ktoré sú z daného dosiahnuteľné prechodmi pozdĺž ε. Ďalej, zatiaľ čo existujú stavy, pre ktoré prechody neboli skonštruované (prechody sú robené symbolmi, prechody cez ktoré sú v pôvodnom automate), pre každý symbol platí ε-uzavretie množiny stavov, ktoré sú dosiahnuteľné z uvažovaného stavu. prechodom cez uvažovaný symbol sa vypočíta. Ak už existuje stav, ktorý zodpovedá nájdenej množine, potom sa tam pridá prechod. Ak nie, pridá sa nový prijatý stav.

Príklad

Inicializácia

Označené sú stavy zodpovedajúce ε-uzavretiu počiatočného stavu. Tieto stavy budú zodpovedať stavu A budúca DKA.

Prvá iterácia

Existujú prechody z ε-uzavretia do NCA stavov 3 a 10 (podľa a a c, respektíve). Pre stav 3 je ε-záver množinou stavov (3, 4, 6), pre stav 10 - (10). Označme nové stavy DFA zodpovedajúce týmto množinám ako B a C.

štát DKA	Súbor stavov NFA
		a	b	c
A	{1, 2, 9}	B	-	C
B	{3, 4, 6}	-	-	-
C	{10}	-	-	-

Druhá iterácia

Z množiny stavov NFA (3, 4, 6) zodpovedajúcich stavu DFA B existujú dva prechody - do stavu 5 (podľa b) a 7 (podľa c). Ich ε-uzávery sa pretínajú, ale samotné množiny sú odlišné, takže sú im priradené dva nové stavy DFA - D a E. Zo stavov NFA zodpovedajúcich stavu DFA C, neexistujú žiadne prechody.

štát DKA	Súbor stavov NFA	Skákateľné postavy
		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}	-	-	-

Tretia iterácia

Z množín stavov NFA zodpovedajúcich stavom DFA D a E sa robia prechody do množín stavov zodpovedajúcich existujúcim stavom (z množiny (2, 5, 8, 9) zodpovedajúcej stavu D, na a prechod do stavu 3 patriaceho do množiny (3, 4, 6) zodpovedajúceho stavu DFA B, na c- prechod do stavu 10 zodpovedajúceho stavu C; podobne pre množinu zodpovedajúcu stavu DFA E). Proces konštrukcie tabuľky stavov a prechodov DFA je dokončený.

štát DKA	Súbor stavov NFA	Skákateľné postavy
		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

výsledok:

Budovanie pravolineárnej gramatiky z konečného automatu

Každý stav je spojený s neterminálom. Ak dôjde k prechodu stavu X do stavu Y na a, pridajte pravidlo X → aY. Pre konečné stavy pridajte pravidlá X→ e. Pre ε-prechody - X → Y.

Príklad 1 (deterministický stavový automat)

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

Príklad 2 (nedeterministický stavový automat)

• 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 → ε

Výstavba DFA pomocou RV

Majme regulárny výraz r. Na základe tohto regulárneho výrazu je potrebné postaviť deterministický konečný automat D také že L(D) = L(r).

Úprava regulárneho výrazu

Pridajme k tomu symbol, znamenajúci koniec RV – „#“. Výsledkom je regulárny výraz ( r)#.

Stavanie stromu

Predstavme si regulárny výraz ako strom, ktorého listy sú koncové znaky a vnútorné uzly sú operácie zreťazenia ".", spojenia "∪" a iterácie "*". Každému listu stromu (okrem ε-listov) priradíme jedinečné číslo a označujeme ho na jednej strane ako pozíciu v strome a na druhej strane ako pozíciu symbolu zodpovedajúceho list.

Výpočet funkcií s nulovou hodnotou, firstpos, lastpos

Teraz, prechádzajúc stromom T zdola nahor zľava doprava, vypočítame tri funkcie: s možnosťou nulovania, firstpos a lastpos. Funkcie s možnosťou nulovania, firstpos a lastpos definované v uzloch stromu. Hodnota všetkých funkcií okrem s možnosťou nulovania, je súbor pozícií. Funkcia firstpos(n) pre každý uzol n stromu syntaxe regulárneho výrazu poskytuje množinu pozícií, ktoré sa zhodujú s prvými znakmi v podreťazcoch vygenerovaných podvýrazom končiacim na n. podobne, lastpos(n) udáva množinu pozícií, ktoré zodpovedajú posledným znakom v podreťazcoch vygenerovaných podvýrazmi s top n. Pre uzly n, ktorého podstromy (teda strom, ktorého uzol n je koreň) dokáže vygenerovať prázdne slovo, ktoré definujeme s možnosťou nulovania(n) = pravda a pre ostatné uzly falošné. Tabuľka na výpočet s možnosťou nulovania, firstpos, lastpos:

uzol n	s možnosťou nulovania(n)	firstpos(n)	lastpos(n)
ε	pravda	∅	∅
i ≠ ε	falošné	{i}	{i}
u ∪ v	s možnosťou nulovania(u) alebo s možnosťou nulovania(v)	firstpos(u) ∪ firstpos(v)	lastpos(u) ∪ lastpos(v)
u . v	s možnosťou nulovania(u) a s možnosťou nulovania(v)	ak s možnosťou nulovania(u) potom firstpos(u) ∪ firstpos(v) inak firstpos(u)	ak s možnosťou nulovania(v) potom lastpos(u) ∪ lastpos(v) inak lastpos(v)
v*	pravda	firstpos(v)	lastpos(v)

Budova followpos

Funkcia followpos vypočítané cez s možnosťou nulovania, firstpos a lastpos. Funkcia followpos definované na viacerých pozíciách. Význam followpos je súbor pozícií. Ak i- poloha teda followpos(i) je veľa pozícií j tak, aby tam bol nejaký reťazec... cd... zahrnuté v jazyku opísanom RW tak, že i sa zhoduje s týmto záznamom c, a j- vstup d. Funkcia followpos možno vypočítať aj pri jednom prechode stromom podľa nasledujúcich dvoch pravidiel

1. Nechať byť n- vnútorný uzol s "." (reťazenie); a, b- jeho potomkovia. Potom pre každú pozíciu i zahrnuté v lastpos(a followpos(i) kopa firstpos(b).
2. Nechať byť n- interný uzol s operáciou "*" (iterácia), a- jeho potomok. Potom pre každú pozíciu i zahrnuté v lastpos(a), pridajte k množine hodnôt followpos(i) kopa firstpos(a).

Príklad

Vypočítajte hodnotu funkcie followpos pre regulárny výraz ( a(b|c))*c.

pozícia	Význam 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}

Vytvorenie DFA

DFA je množina stavov a množina prechodov medzi nimi. Stav DFA je súbor pozícií. Konštrukcia DFA spočíva v postupnom pridávaní potrebných stavov k nemu a výstavbe prechodov pre ne. Spočiatku existuje jeden štát firstpos(koreň) (koreň- koreň stromu), ktorý nemá žiadne prechody. Prechod vykonávajú znaky z regulárneho výrazu. Každý znak zodpovedá množine pozícií ( p i). Zjednotenie všetkých followpos(x) je stav, do ktorého je potrebné prejsť, kde x je pozícia, ktorá je prítomná tak medzi pozíciami stavu, ako aj medzi pozíciami symbolu z RE, na ktorom sa prechod uskutočňuje. Ak taký stav neexistuje, treba ho doplniť. Proces sa musí opakovať, kým sa nevytvoria všetky prechody pre všetky stavy. Všetky stavy obsahujúce polohu symbolu # pridaného na koniec RE sú vyhlásené za konečné.

DFA získané z RV ( a(b|c))*c

Príklad

Zostavte DFA pomocou regulárneho výrazu ( a(b|c))*c.

štát DKA	Symbol
	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)	-	-	-

Budovanie DFA s minimálnym počtom štátov

DFA s minimálnym počtom stavov je skonštruovaná pre všade definovanú DFA, t.j. také že . Pre každú DFA existuje všade definovaný ekvivalent DFA.

Konštrukcia všade definovanej DFA

Zaveďte nový stav a definujte nový súbor stavov .

Definujme novú prechodovú funkciu takto:

Vytvorenie oddielu (formálne)

Poďme zostaviť počiatočný oddiel P množiny stavov do dvoch skupín: konečné stavy F a ďalšie S/F, t.j. P = {F, Q\F}.

Použiť na každú skupinu G ∈ P nasledujúci postup. rozbiť G do podskupín tak, aby štáty s a t od G skončili v rovnakej skupine vtedy a len vtedy, ak pre každý vstupný symbol aštátov s a t mať prechody a do štátov z rovnakej skupiny v P.

Výsledné podskupiny sa pridajú do nového oddielu P Nový.

súhlasiť P = P nový a stavbu priečky opakujte až do ustálenia, t.j. kým sa priečka neprestane meniť.

Vytvorenie oddielu (algoritmus)

Na vytvorenie oddielu existuje nasledujúci algoritmus. Zostavíme tabuľku prechodov pre pôvodný automat, zostavíme počiatočný oddiel.

Každej skupine z partície priradíme identifikátor (pre úvodnú partíciu napr. 0 a 1).

Každý štát (každý riadok tabuľky) má priradený reťazec v tvare „a.bcd…xyz“, kde je identifikátor skupiny, do ktorej štát patrí [prvý stĺpec (odkiaľ ideme), druhý stĺpec stĺpec (kam ideme prvým znakom), …, posledný stĺpec (kam prechádzame posledným znakom)].

Nové skupiny budujeme podľa zhody reťazcov, teda tak, aby stavy s rovnako priradenými reťazcami spadali do jednej skupiny.

Potom nová iterácia. Výsledným skupinám priradíme nové identifikátory, napríklad (0, 1, ..., n). A opakujeme stavbu priečky až do ustálenia.

Všimnite si, že keď v skupine zostane iba jeden stav, v nasledujúcich fázach vytvárania oddielu už nemôžete zapísať reťazec identifikátorov pre tento stav, pretože tento reťazec bude v každom prípade jedinečný kvôli prvému znaku reťazec. Inými slovami, pri rozdelení sa skupine z jedného štátu nič nestane – prenesie sa do nového rozdelenia tak, ako je.

Konštrukcia redukovaného automatu

Každá z výsledných skupín sa stáva stavom nového DFA. Ak skupina obsahuje počiatočný (konečný) stav pôvodného automatu, táto skupina sa stáva počiatočným (resp. konečným) stavom nového DFA. Prechody sú konštruované zrejmým spôsobom: prechod do stavu zo skupiny sa považuje za prechod do skupiny.

Prinášame stroj. Najprv odstránime negenerujúce (sterilné, „mŕtve“), potom nedosiahnuteľné stavy (definície sú uvedené pre symboly, ale očividným spôsobom sa prenášajú do stavov automatu).

Vo všeobecnosti sa odstránením mŕtvych stavov zmení DFA na NFA, pretože v DFA musia byť definované všetky prechody. V Dračej knihe sa však takáto odchýlka od formálnej definície stále považuje za prijateľnú.

Príklad

Vytvorenie DFA s minimálnym počtom stavov pre DFA nasledujúceho tvaru:

• Počiatočné rozdelenie: (C) ( konečný stav), (A, B, D, E) ( všetky ostatné štáty).
• (C)( bez zmien), (A, D, E), (B), ( keďže prechádzame z A, D, E pozdĺž a, c do B a C, v tomto poradí).
• Nemôžeme robiť ďalšie rozchody.

Nech skupina (C) zodpovedá stavu C, skupina (A, D, E) stavu A a skupina (B) stavu B. Potom dostaneme DFA s minimálnym počtom stavov:

Príklad (algoritmus na zostavenie oddielu)

Tabuľka prechodov pre všade definovanú (pridaný stav Z) DFA zodpovedajúcu RV (ab|ε)a*|abb|b*a. Zo skúšobných otázok z roku 2012.

	a	b	ja 0	ja 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
F*	Z	Z	0.11
Z	Z	Z	1.11

Iterácie:

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

Výsledok: stroj už mal minimálny počet stavov :-)

DFA, ktorá umožňuje dokončenie jazyka

Algoritmus na zostavenie DFA, ktorý akceptuje doplnok jazyka L (L̅), pozostáva z dvoch krokov:

• Vytvorenie kompletnej DFA
• Konštrukcia požadovaného automatu z neho

V skutočnosti neexistuje nič také ako úplná DFA. Pod plnou DKA niektoré učitelia rozumejú automatu, v ktorého prechodovej tabuľke nie sú žiadne prázdne bunky. Podľa definície DFA - δ: Q × Σ → Q - však v žiadnom prípade nemôžu byť prázdne bunky. Automat „s prázdnymi bunkami“ však spĺňa definíciu NFA. V priebehu riešenia nie je nezvyčajné získať práve taký NFA, ktorému chýbajú len prechody pred DFA.

Na jeho doplnenie stačí pridať nový stav X a „namiesto“ neexistujúcich prechodov pridávajú prechody do tohto nového stavu. Nezabudnite pridať prechody z X v X. Je ľahké vidieť, že tam, kde pôvodný automat neakceptoval nejaký reťazec z dôvodu absencie prechodu, prejde nový automat do stavu X a zavesiť sa na to. Keďže nový stav nie je akceptujúcim (konečným) stavom, nový automat nebude akceptovať ani tento reťazec.

Teraz je na zostrojenie želaného automatu potrebné už len zmeniť roly prijímajúcich a neakceptujúcich stavov. Inými slovami, F" = Q \ F.

Zostrojenie LL(k) analyzátora

Gramatická transformácia

Nie každá gramatika je LL(k)-parsovateľná. Bezkontextová gramatika patrí do triedy LL(1), ak nemá konflikty FIRST-FIRST (ľavá rekurzia je špeciálnym prípadom takéhoto konfliktu) a FIRST-FOLLOW.

Niekedy je možné transformovať ne-LL(1) gramatiky tak, aby sa stali LL(1). Niektoré (presnejšie tie, ktoré boli zvažované v kurze) transformácie sú uvedené nižšie.

Odstraňuje sa ľavá rekurzia

Predpokladajme, že máme pravidlo formulára (ďalej v tejto časti veľké písmená - nekoncové symboly, malými písmenami - reťazce ľubovoľných znakov):

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

Nie je prístupný jednoznačnej analýze, preto by sa mal previesť.

Je ľahké ukázať, že toto pravidlo je ekvivalentné nasledujúcemu páru pravidiel:

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

Ľavá faktorizácia

Podstatou tohto postupu je odstránenie nejednoznačnosti pri výbere pravidiel pre ľavú postavu. Na tento účel sa nájde spoločná ľavá predpona a to, čo po nej môže nasledovať, sa odstráni v novom pravidle (malé písmená - reťazce ľubovoľných znakov)

Príklad

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

Prevedené na

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

ktorý sa zase stáva

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

Príklad gramatickej konverzie

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

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

Odstránenie ľavej rekurzie pre S:

• S → ako 1
• S 1 → AbBS 1 | ε

Ľavá faktorizácia pre A:

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

Záverečná gramatika:

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

Stavať PRVÝ a NASLEDOVAŤ

FIRST(α), kde α ∈ (N ∪ T)* je množina terminálov, z ktorých môže α začínať. Ak α ⇒ ε, potom ε ∈ PRVÝ(α). Preto hodnota FOLLOW( A) pre neterminál A- veľa terminálov, ktoré sa môžu objaviť hneď potom A v nejakej sentimentálnej forme. Ak A môže byť znak úplne vpravo v nejakej vetnej forme, potom posledný token $ tiež patrí FOLLOW( A)

PRVÝ výpočet

Pre terminály

• Pre akýkoľvek terminál X, X ∈ T, NAJPRV( X) = {X}

Pre neterminály

• Ak X je neterminál, potom dáme FIRST( X) = {∅}
• Ak má gramatika pravidlo X→ ε, potom pridajte ε k FIRST( X)
• Pre každý neterminál X a pre každé vyvodzovacie pravidlo X → Y 1 …Y k pridať do FIRST( X) množina PRVÝ zo všetkých symbolov na pravej strane pravidla až po prvý, od ktorého ε nie je odvodené, vrátane jeho

Pre reťaze

• Pre reťazec znakov X 1 …X k FIRST je spojenie FIRST znakov zahrnutých v reťazci až po prvý, ktorý má ε ∉ FIRST, vrátane neho.

Príklad

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

PRVÉ neterminály v poradí riešenia závislostí:

• FIRST(S) = (a)
• PRVÝ (A) = (a, ε)
• PRVÝ (A 1) = (b, a)
• PRVÝ (B) = (c, ε)
• FIRST(S 1) = (a, b, ε)

PRVÝ pre pravidlá odvodzovania:

• FIRST(aS 1) = (a)
• FIRST(AbBS 1) = (a, b)
• PRVÝ (ε) = (ε)
• FIRST(aA 1) = (a)
• PRVÝ (a) = (a)
• FIRST (b) = (b)
• FIRST (c) = (c)

SLEDUJTE výpočet

Výpočet funkcie FOLLOW pre znak X:

• Nech FOLLOW(X) = (∅)
• Ak X je gramatická axióma, pridajte značku $ do položky FOLLOW
• Pre všetky pravidlá tvaru A → αXβ pridajte FIRST(β)\(ε) k FOLLOW(X) (X môžu nasledovať tie znaky, ktoré začínajú β)
• Pre všetky pravidlá tvaru A → αX a A → αXβ, ε ∈ FIRST(β) pridajte FOLLOW(A) k FOLLOW(X) (to znamená, že X môžu nasledovať všetky znaky, ktoré môžu nasledovať po A, ak je v pravidlo odvodenia, X môže byť úplne vpravo)
• Opakujte predchádzajúce dva odseky, pokiaľ je možné pridať znaky do sady

Príklad

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

výsledok:

• FOLLOW(S) = ($)
• FOLLOW(S 1) = ($) (S 1 je znak úplne vpravo v pravidle S → aS 1)
• FOLLOW(A) = (b) (A v pravidle S 1 → AbBS 1 nasleduje b)
• FOLLOW(A 1) = (b) (A 1 je znak úplne vpravo v pravidle A → aA 1 , preto sa k FOLLOW(A 1) pridáva FOLLOW(A))
• FOLLOW(B) = (a, b, $) (sčítajte PRVÉ (S 1)\(ε) (vyplýva z pravidla S 1 → AbBS 1), FOLLOW(S 1) (keďže existuje S 1 → ε))

Zostavenie tabuľky

Tabuľka M pre pár, ktorý nie je koncový-koncový (v bunke M[A, a]) určuje pravidlo, podľa ktorého sa musí vstupné slovo zmenšiť. Tabuľka sa vypĺňa takto: pre každé odvodzovacie pravidlo danej gramatiky A → α (kde α sa rozumie reťazec na pravej strane pravidla) sa vykonajú tieto akcie:

1. Pre každý terminál a∈ FIRST(α) pridajte pravidlo A → α do M[A, a]
2. Ak ε ∈ FIRST(α), potom pre každú b∈ SLEDOVAŤ( A) pridať A → α do M[A, b]
3. ε ∈ FIRST(α) a $ ∈ FOLLOW( A), pridajte A → α do M[A, $]
4. Všetky prázdne bunky sú chybou vo vstupnom slove

Príklad

Vytvorte tabuľku pre gramatiku

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

výsledok:

	a	b	c	$
S	S → ako 1 (Prvé pravidlo, odvodenie S → aS 1 , a ∈ FIRST(aS 1))	chyba (štvrté pravidlo)	chyba (štvrté pravidlo)	chyba (štvrté pravidlo)
S1	S1 → AbBS 1 (Prvé pravidlo, výstup S 1 → AbBS 1 , a ∈ FIRST(AbBS 1))	S1 → AbBS 1 (Prvé pravidlo, výstup S 1 → AbBS 1 , b ∈ FIRST(AbBS 1))	chyba (štvrté pravidlo)	S1 → ε (Tretie pravidlo, odvodenie S 1 → ε, ε ∈ FIRST(ε), $ ∈ FOLLOW(S 1))
A	A → aA 1 (Prvé pravidlo, výstup A → aA 1 , a ∈ FIRST(aA 1))	A→ε (Druhé pravidlo, výstup A 1 → ε, b ∈ FOLLOW(A 1))	chyba (štvrté pravidlo)	chyba (štvrté pravidlo)
A 1	A 1 → a (Prvé pravidlo, výstup A 1 → a, a ∈ FIRST(a))	A 1 → b (Prvé pravidlo, výstup A 1 → b, b ∈ FIRST(b))	chyba (štvrté pravidlo)	chyba (štvrté pravidlo)
B	B→e	B→e (Druhé pravidlo, záver B → ε, a ∈ FOLLOW(B))	B → c (Prvé pravidlo, výstup B → c, c ∈ FIRST(c))	B→e (Tretie pravidlo, odvodenie B → ε, $ ∈ FOLLOW(B))

Analýza reťazca

Proces analýzy reťazca je pomerne jednoduchý. Jeho podstata je nasledovná: pri každom kroku sa číta horný symbol v c vstupný reťazec.

• Ak v- symbol terminálu
  • Ak v sa zhoduje s s, potom sú obe zničené, nastáva posun
  • Ak v nezhoduje sa s s, potom je signalizovaná chyba analýzy
• Ak v- nekoncový symbol, c vráti sa na začiatok riadku namiesto v pravá strana pravidla, ktorá sa vyberie z bunky tabuľky, sa vráti do zásobníka M[v, c]

Proces končí, keď reťazec aj zásobník dosiahnu koncovú značku (#).

Príklad

Poďme analyzovať reťazec "aabbaabcb":

stoh	riadok	akcie
S#	a abbaabcb$	S → ako 1
a S1#	a abbaabcb$	posun
S1#	a bbaabcb$	S1 → AbBS 1
A bbs 1#	a bbaabcb$	A → aA 1
a A 1 BBS 1 #	a bbaabcb$	posun
A 1 bbs 1#	b baabcb$	A 1 → b
b bbs 1#	b baabcb$	posun
b B.S. 1#	b aabcb$	posun
B S1#	a abcb$	B→e
S1#	a abcb$	S1 → 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$	posun
A 1 bbs 1#	a bcb$	A 1 → a
a bbs 1#	a bcb$	posun
b B.S. 1#	b cb$	posun
B S1#	c b$	B → c
c S1#	c b$	posun
S1#	b$	S1 → AbBS 1
A bbs 1#	b$	A→ε
b B.S. 1#	b$	posun
B S1#	$	B→e
S1#	$	S1 → ε
#	$	pripravený

Zostavenie LR(k) analyzátora

Výpočet k v LR(k)

Neexistuje žiadny algoritmus, ktorý by vo všeobecnom prípade umožňoval vypočítať k pre ľubovoľnú gramatiku. Zvyčajne sa oplatí pokúsiť sa zostaviť analyzátor LR(1). Ak má najviac jednu operáciu na sadu (Shift, Reduce alebo Accept), potom je gramatika LR(0). Ak však pri zostavovaní syntaktického analyzátora LR(1) dôjde ku konfliktu a kolízii, potom táto gramatika nie je LR(1) a oplatí sa pokúsiť zostaviť LR(2). Ak sa to nepodarí postaviť, potom LR(3) atď.

Dokončenie gramatiky

Pridajme nové pravidlo S" → S a urobme zo S" axiómu gramatiky. Toto dodatočné pravidlo je potrebné na určenie, kedy sa analyzátor ukončí a vstupný reťazec je povolený. Prijatie sa uskutoční vtedy a len vtedy, ak je možné vykonať konvolúciu podľa pravidla S → S".

Konštrukcia kanonického systému množín prípustných LR(1)-situácií

Na začiatku je množina I 0 s konfiguráciou analyzátora S" → .S, $. Potom sa na túto konfiguráciu aplikuje operácia zatvárania, až kým v dôsledku jej aplikácie nie sú pridané žiadne nové konfigurácie. Ďalej , prechody do nových množín sú konštruované posunutím bodu o jeden znak doprava (skoky robí znak, ktorý bol za bodkou pred skokom a pred ním po skoku), a tie konfigurácie, ktoré boli získané z existujúcich týmto spôsobom sa pridajú k týmto množinám, pričom sa na ne aplikuje aj operácia uzavretia a celý proces sa opakuje, kým sa neobjavia ďalšie nové množiny.

Príklad

Zostrojte kanonický systém množín prípustných LR(1)-situácií pre špecifikovanú gramatiku:

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

rozhodnutie:

• Vytvárame uzáver pre konfiguráciu S" → .S, $:
  • S → .ABA,$
• Pre výsledné konfigurácie (S → .ABA, $) vytvoríme aj uzáver:
  • A → .Aa, c
  • A → .Aa, d
  • A → .,c
  • A → ., d
• Pre výsledné konfigurácie (A → .Aa, c; A → .Aa, d) zostrojíme aj uzáver:
  • A → .Aa, a
  • A → ., a
• V stave I 0 sa už nedajú postaviť žiadne ďalšie konfigurácie - uzáver je vybudovaný

• Od I 0 môžete robiť prechody pozdĺž S a A a získať súbor konfigurácií I 1 a I 2, ktorý pozostáva z nasledujúcich prvkov:
  • I 1 = (S" → S., $)
  • I2 = (S → A.BA, $; A → A.a, c; A → A.a, d; A → A.a, a)
• I 1 nevyžaduje uzavretie
• Zostrojme uzáver I 2:
  • B → .cBc, a
  • B → .cBc, $
  • B → .d, a
  • B → .d, $
• Všetky ostatné súpravy sú konštruované podobne.

Vytvorenie tabuľky syntaktického analyzátora

Posledným krokom pri vytváraní syntaktického analyzátora LR(1) je zostavenie tabuliek akcie a ísť do. Tabuľka akcie vytvorený pre vstupné reťazcové znaky, t. j. pre terminály a koncovú značku $, tabuľku ísť do je zostavený pre gramatické symboly, t.j. pre terminály a neterminály.

Vytvorenie tabuľky Goto

Tabuľka Prejsť ukazuje, do ktorého stavu prejsť, keď sa objaví ďalší gramatický symbol. Ak teda v kanonickom systéme množín dochádza k prechodu z ja i v Ij symbolom A, potom v Goto( ja i, A) dáme stav ja j. Po vyplnení tabuľky predpokladáme, že vo všetkých prázdnych bunkách Goto( ja i, A) = chyba

Vytvorenie tabuľky Akcie

• Ak na termináli a dôjde k prechodu zo stavu I i do stavu I j , potom Action(I i, a) = Shift(I j)
• Ak A ≠ S" a existuje konfigurácia A → α., a, potom Akcia(I i, a) = Zníženie(A → α)
• Pre stav I i, ktorý má konfiguráciu S" → S., $, Akcia(I i, $) = Prijať
• Pre všetky prázdne bunky Akcia(I i, a) = Chyba

Príklad

Zostavte tabuľky Action a Goto pre gramatiku

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

rozhodnutie:

	akcie				ísť do
	a	c	d	$	S	S"	A	B	a	c	d
ja 0	Znížiť (A → ε)	Znížiť (A → ε)	Znížiť (A → ε)		ja 1		ja 2
ja 1				súhlasiť
ja 2	Shift(I 6)	Shift(I 4)	Shift(I 5)					ja 3	ja 6	ja 4	ja 5
ja 3	Znížiť (A → ε)			Znížiť (A → ε)			ja 13
ja 4		Shift(I 8)	Shift(I 9)					ja 7		ja 8	ja 9
ja 5	Znížiť (B → d)			Znížiť (B → d)
ja 6	Znížiť (A → Aa)	Znížiť (A → Aa)	Znížiť (A → Aa)
ja 7		Shift(I 10)								ja 10
ja 8		Shift(I 8)	Shift(I 9)					ja 11		ja 8	ja 9
ja 9		Znížiť (B → d)
ja 10	Znížiť (B → cBc)			Znížiť (B → cBc)
ja 11		Shift(I 12)								ja 12
ja 12		Znížiť (B → cBc)
ja 13	Shift(I 14)			Znížiť (S → ABA)					ja 14
ja 14	Znížiť (A → Aa)			Znížiť (A → Aa)

Analýza reťazca

V každom kroku sa prečíta horný znak v zo zásobníka analyzátora a zoberte posledný znak c vstupný reťazec.

Ak je v tabuľke akcií na križovatke v a c Nachádza:

• Shift( Ja k), potom položte na stoh s a potom Ja k. V čom c odstránené z reťazca.
• Znížiť ( A → u), potom sa všetky terminálové a neterminálne symboly, ktoré tvoria reťazec, vymažú z hornej časti zásobníka u, po ktorých sa štát stará ja m zostávajúce na vrchole. Podľa prechodovej tabuľky na križovatke ja m a A nájsť ďalší stav Je. Potom sa A zatlačí na stoh a potom Je. Linka zostáva nezmenená.
• Prijmite, potom je analýza dokončená
• prázdnota je chyba

Príklad

Poďme zostaviť analýzu reťazca aaaccdcc:

Stoh	Linka	Akcia
ja 0	a aaccdcc$	Znížiť (A → ε), prejsť na I 2
Ja 0 A ja 2	a aaccdcc$	Shift(I 6)
I 0 A I 2 a ja 6	a accdcc$	Znížiť (A → Aa), prejsť na I 2
Ja 0 A ja 2	a accdcc$	Shift(I 6)
I 0 A I 2 a ja 6	a ccdcc$	Znížiť (A → Aa), prejsť na I 2
Ja 0 A ja 2	a ccdcc$	Shift(I 6)
I 0 A I 2 a ja 6	c cdcc$	Znížiť (A → Aa), prejsť na I 2
Ja 0 A ja 2	c cdcc$	Shift(I 4)
I 0 A I 2 s ja 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$	Znížiť (B → d), prejsť na I 11
I 0 A I 2 c I 4 c I 8 B ja 11	c c$	Shift(I 12)
I 0 A I 2 c I 4 c I 8 B I 11 c ja 12	c$	Znížiť (B → cBc), prejsť 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 ja 10	$	Znížiť (B → cBc), prejsť na I 3
I 0 A I 2 B ja 3	$	Znížiť (A → ε), prejsť na I 13
I 0 A I 2 B I 3 A ja 13	$	Znížiť (S → ABA), prejsť na I 1
ja 0 S ja 1	$	súhlasiť

Preklad aritmetických výrazov (Seti-Ullmanov algoritmus)

Poznámka. Kód je generovaný psím štýlom podobným Motorole, t.j.

Op Arg1, Arg2

znamenať

Arg2 = Arg1 Op Arg2

Stavanie stromu

Strom je zostavený ako obvykle pre aritmetický výraz: V koreni operácia s najnižšou prioritou, za ňou operácie s mierne vyššou prioritou atď. Zátvorky majú najvyššiu prioritu. Ak existuje niekoľko operácií s rovnakou prioritou - a op b op c, potom sa strom zostaví ako pre výraz (a op b) op c.

Príklad

Zostavte strom pre výraz a + b / (d + a − b × c / d − e) + c × d

rozhodnutie: Výraz píšeme v tvare

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

Potom v koreni každého podstromu bude operácia a výrazy v zátvorkách naľavo a napravo od neho budú jeho podstromy. Napríklad pre podvýraz ((b) × (c)) / (d) bude koreňom zodpovedajúceho podstromu operácia „/“ a jeho podstromy budú podvýrazy ((b) × (c)) a (d).

Rozloženie stromu (výpočet počtu registrov)

• Ak je vrcholom ľavý list (teda premenná), tak ho označíme nulou.
• Ak je vrchol pravý list, tak ho označíme jedným
• Ak označíme oba jeho podstromy pre nejaký vrchol, potom ho označíme takto:
  • Ak sú ľavý a pravý podstrom označené rôznymi číslami, vyberte najväčší z nich
  • Ak sú ľavý a pravý podstrom označené rovnakými číslami, tomuto podstromu je priradené číslo, ktoré je o jednu väčšie ako číslo, ktoré označuje podstromy

označenie listov	Rozloženie stromu s identickými podstromami	Ľavý podstrom je označený veľkým číslom	Pravý podstrom je označený veľkým číslom

správny - rovnaký ako predok.

Ak štítok vľavo potomok viacštítky správny, potom správny dieťa má pridelený register ešte jeden než predok, a vľavo - rovnaký ako predok.

Kód je tvorený prechádzaním stromu zdola nahor takto:

1. Pre vrchol s označením 0 sa nevygeneruje žiadny kód

2. Ak je navrchu list X so štítkom 1 a registrom R i, potom kód

MOVE X, Ri

3. Ak je horná časť vnútorná s registrom R i a jeho ľavým potomkom je list X s označením 0, potom zodpovedá kódu

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

4. Ak podstromy vrcholu s registrom R i- nelistuje a označenie pravého vrcholu je väčšie alebo rovnaké ako označenie ľavého (ktorý má register Rj, j = i + 1), potom kód zodpovedá vrcholu

<Код správny podstrom><Код vľavo podstromy > Op Rj, Ri

5. Ak podstromy vrcholu s registrom R i- nie listy a označenie pravého vrcholu (pre ktorý register Rj, j = i + 1) je menšie ako označenie ľavého, potom kód zodpovedá vrcholu

Rozloženie registrov je znázornené v grafe vpravo. Vygenerovaný kód:

POHYB d, R0 ;R0 = d POHYB c, R1 ;R1 = c MUL b, R1 ;R1 = (b × c) DIV R1, R0 ;R0 = (b × c) / d POHYB a, R1 ;R1 = a ADD d, R1 ;R1 = a + d SUB R1, R0 ;R0 = (a + d) − ((b × c) / d) POHYB 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) ADD a, R0 ;R0 = a + (b / (((a + d) − ((b × c) / d )) − e)) POHYB d, R1 ;R1 = d MUL c, R1 ;R1 = c × d PRIDAŤ R0, R1 ;R1 = (a + (b / (((a + d) − ((b × c) ) / d)) − e))) + (c × d) POHYB R1, R0;R0 = (a + (b / (((a + d) − ((b × c) / d)) − e) )) + (c × d)

Preklad logických výrazov

Táto časť ukazuje, ako generovať kód na pomalé vyhodnocovanie boolovských výrazov. V dôsledku algoritmu sa získa časť kódu, ktorá pomocou operácií TST, BNE, BEQ vypočíta logický výraz prepnutím na jedno z označení: TRUELAB alebo FALSELAB.

Stavanie stromu

Strom logického výrazu odráža poradie, v akom sa vyhodnocuje podľa poradia operácií, teda na vyhodnotenie hodnoty uzla stromu (čo je operácia dvoch operandov, ktoré sú podstrommi uzla), musíme najprv vypočítajte hodnoty jeho podstromov.

Priorita prevádzky: Operátor NOT má najvyššiu prioritu, nasleduje AND a potom OR. Ak sú vo výraze použité iné logické operácie, musia byť vyjadrené prostredníctvom týchto troch určitým spôsobom (zvyčajne neexistujú žiadne ďalšie operácie a konverzia výrazu nie je potrebná). Asociativita operácií s rovnakou prioritou je zľava doprava, t.j. A a B a C sa považujú za (A a B) a C

Príklad

Zostrojte strom pre logický výraz nie A alebo B a C a (B alebo nie C).

rozhodnutie: pozri diagram vpravo.

Pre každý vrchol stromu sa vypočítajú 4 atribúty:

• Číslo uzla
• Označenie, na ktoré sa má prejsť, ak je výraz v uzle nepravdivý (false label, fl)
• Označenie, na ktoré sa má prejsť, ak je výraz v uzle pravdivý (true label, tl)
• Štítok (znak) (ďalšie podrobnosti nájdete nižšie)

Vrcholy sú číslované v náhodnom poradí, jedinou podmienkou je jedinečnosť čísiel uzlov.

Rozloženie stromu sa robí takto:

• fl určuje číslo vrcholu, na ktorý sa prechod uskutoční, alebo falselab, ak je tento vrchol nepravdivý
• tl označuje číslo vrcholu, na ktorý sa prechod uskutoční, alebo truelab, ak je tento vrchol pravdivý

Znak určuje, v akom prípade môže byť vyhodnocovanie aktuálneho podstromu ukončené.

Pre koreň stromu fl=falselab, tl=truelab, sign=false.

takto:

Príklad

Označte strom vytvorený pre logický výraz nie A alebo B a C a (B alebo nie C).

Generovanie kódu

Strojové príkazy použité vo vygenerovanom kóde:

• TST - kontrola pravdivosti argumentu a nastavenie príznaku, ak je argument nepravdivý
• BNE - skok na štítok, ak príznak nie je nastavený, t. j. stav skontrolovaný pomocou TST pravda
• BEQ - skok na štítok, ak je nastavený príznak, t.j. stav kontrolovaný pomocou TST falošné

Kód je zostavený takto:

• strom sa prechádza od koreňa, pre AND a OR sa najprv prechádza ľavým podstromom a potom pravým
• pre každý prejdený vrchol sa vytlačí jeho číslo (označenie).
• pre list A (číslo, tl, fl, znak) sa vytlačí TST A
  • ak znamienko == true, vytlačí sa BNE tl
  • ak znak == nepravda, vytlačí sa BEQ fl

Príklad

Pre vyššie uvedený výraz sa vygeneruje nasledujúci kód:

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:

Metóda porovnávania vzoriek

Myšlienka metódy spočíva v tom, že pre tú istú časť programu možno kód generovať rôznymi spôsobmi a v dôsledku toho je možné dosiahnuť optimalizáciu pre jeden alebo iný parameter.

Formulácia problému

Existuje mnoho vzoriek, z ktorých každá je definovaná časťou prechodnej reprezentácie, pre ktorú je použiteľná, hmotnosťou a vygenerovaným kódom. Existuje strom strednej reprezentácie, čo je fragment programu, pre ktorý je potrebné vygenerovať kód. Cieľom je vybudovať také pokrytie stredného reprezentačného stromu vzorkami, aby celková hmotnosť vzoriek bola minimálna.

Vzory sú montážne pokyny a im zodpovedajúce stromy analýzy. Pre každú vzorku je známy čas jej vykonávania (v cykloch). S ich pomocou vygenerujeme optimálny (z hľadiska času vykonávania) kód.

Vzorové príklady

Budovanie strednej reprezentácie

Najprv vytvoríme strom analýzy pre celý výraz.

Budovanie pokrytia

Teraz pre každý vrchol (prejdeme ich v poradí od listov po koreň) vygenerujeme optimálny kód pre jeho podstrom. Aby sme to urobili, jednoducho prejdeme všetky vzorky, ktoré sú použiteľné v danom vrchole. Čas vykonania pri použití konkrétneho vzoru bude súčtom času potrebného na vyhodnotenie jeho argumentov (a vďaka poradiu prechodu cez strom už poznáme optimálny kód na ich výpočet) a času vykonania samotného vzoru. Zo všetkých získaných možností vyberieme tú najlepšiu - bude to optimálny kód pre podstrom tohto vrcholu. V koreni stromu získame optimálny kód pre celý výraz.

Generovanie kódu

Nie je potrebné vypisovať kód pre všetky vrcholy - stačí si zapísať minimálny požadovaný čas a vzorku, ktorú potrebujete použiť. Všetko ostatné z toho sa dá ľahko obnoviť.

V týchto problémoch máme nekonečné množstvo registrov, takže zakaždým môžete použiť nový.

Stavba RV podľa DFA

Konštrukcia NFA podľa pravolineárnej gramatiky

Gramatický casting

Ak chcete previesť ľubovoľnú gramatiku COP do zmenšenej formy, musíte vykonať nasledujúce kroky:

• odstráňte všetky neplodné postavy;
• odstrániť všetky nedostupné znaky;

Odstránenie nepotrebných znakov

Vstup: COP-gramatika G = (T, N, P, S).

Výkon: COP-gramatika G' = (T, N', P', S) neobsahujúca žiadne neplodné symboly, pre ktoré L(G) = L(G').

metóda:

Rekurzívne zostavte množiny N 0 , N 1 , ...

1. N° = ∅, i = 1.
2. Ni = (A | (A → α) ∈ P a α ∈ (N i - 1 ∪ T)*) ∪ N i-1.
3. Ak Ni ≠ Ni - 1, potom i = i + 1 a prejdite na krok 2, inak N' = Ni; P' pozostáva z pravidiel množiny P obsahujúcich iba symboly z N' ∪ T; G' = (T, N', P', S).

Definícia: symbol x ∈ (T ∪ N) sa považuje za nedosiahnuteľný v gramatike G = (T, N, P, S), ak sa nevyskytuje v žiadnej vetnej forme tejto gramatiky.

Príklad

Odstráňte zbytočné znaky z gramatiky G((A, B, C, D, E, F, S), (a, b, c, d, e, f, g), P, S)

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

rozhodnutie

• N° = ∅
• N1 = (B (B → bfg) , D (D → ac) , E (E → aec) )
• N2 = (B, D, E, C (C → Ebd) )
• N3 = (B, D, E, C, S (S → aCb) )
• N 4 \u003d (B, D, E, C, S) \u003d N 3

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

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

Odstraňovanie nedostupných postáv

Vstup: COP gramatika G = (T, N, P, S)

Výkon: COP-gramatika G' = (T', N', P', S) neobsahujúca žiadne nedostupné symboly, pre ktoré L(G) = L(G').

metóda:

1. V° = (S); i = 1.
2. V i = (x | x ∈ (T ∪ N), (A → αxβ) ∈ P a A ∈ V i-1) ∪ V i-1.
3. Ak Vi ≠ Vi-1, potom i = i + 1 a prejdite na krok 2, inak N' = V i ∩ N; T' = Vj°T; P' pozostáva z pravidiel množiny P obsahujúcich iba symboly z Vi; G' = (T', N', P', S).

Definícia: COP-gramatika G je redukovaná, ak neobsahuje nedosiahnuteľné a sterilné symboly.

Príklad

Odstráňte nedostupné znaky z gramatiky G"((B, C, D, E, S), (a, b, c, d, e, f, g), P", S)

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

rozhodnutie

• V 0 = (S)
• V1 = (S, C (S → CaDbCe), D (S → CaDbCe), a (S → CaDbCe), b (S → CaDbCe), e (S → CaDbCe) )
• V2 = (S, C, D, a, b, e, E (C → Ebd) , d (C → Ebd), f (D → fCE) )
• V3 = (S, C, D, E, a, b, d, e, f, c (E → ESacD) )
• V 4 \u003d (S, C, D, E, a, b, d, e, f, c) \u003d V 3

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

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

celkovým počtom znakov abecedy symbolov a znakov operácií a zátvoriek v zázname r .

Základ. Automaty pre výrazy dĺžky 1: a sú zobrazené na nasledujúcom obrázku.

Ryža. 5.1.

Všimnite si, že každý z týchto troch automatov má súbor konečných stavov pozostáva z jedného štátu.

indukčný krok. Predpokladajme teraz, že pre každého regulárny výraz dĺžka<= k построен соответствующий НКА, причем у него единственное заключительное состояние. Рассмотрим произвольное regulárny výraz r dĺžky k+1. V závislosti od poslednej operácie môže mať jednu z troch foriem: (r 1 + r 2), (r 1 r 2) alebo (r 1) * . Dovoľte a buďte NFA, ktoré rozpoznávajú jazyky L r1 a L r2 . Bez straty všeobecnosti budeme predpokladať, že majú rôzne stavy: .

Potom NFA, ktorého diagram je znázornený na obr. 5.2, rozpozná jazyk.

Ryža. 5.2.

Tento stroj má súbor štátov, kde q 0 je nový počiatočný stav, q f je nový (jedinečný!) konečný stav a program obsahuje programy automatov M 1 a M 2 a štyri nové prechodové príkazy: . Je zrejmé, že jazyk rozpoznávaný NFA M zahŕňa všetky slová z L (M 1 ) az L ( M 2 ). Na druhej strane každé slovo trvá q 0 až q f a po prvom kroku cesta, ktorá ho vedie, prechádza cez q 0 1 alebo q 0 2 . Keďže sa stavy M 1 a M 2 nepretínajú, tak v prvom prípade sa táto cesta môže dostať do q f len -prechodom z q f 1 a potom . Podobne aj v druhom prípade.

Pre výraz je na nasledujúcom obrázku znázornený diagram NFA, ktorý rozpoznáva jazyk L r.

Ryža. 5.3.

Tento stroj má súbor štátov , počiatočný stav q 0 = q 0 1 , konečný stav q f = q f 2 a súčasťou programu sú programy automatov M 1 a M 2 a jeden nový príkaz - prechod z konečného stavu M 1 do počiatočného stavu M 2, t.j. . Tu je tiež zrejmé, že akákoľvek cesta z q 0 = q 0 1 do q f = q f 2 prechádza cez prechod z q f 1 do q 0 2 . Preto každé slovo povolené M je zreťazením nejakého slova z L M1 ) s nejakým slovom z L M2 ) a akékoľvek zreťazenie takýchto slov je povolené. Preto NFA M rozpoznáva jazyk .

Nech r = r 1 * . Diagram NFA, ktorý rozpoznáva jazyk L r =L r1* = L M1 * je znázornený na obr. 5.3.

Ryža. 5.3.

Tento stroj má súbor štátov, kde q 0 je nový počiatočný stav, q f je nový (jedinečný!) konečný stav a program obsahuje program automatu M 1 a štyri nové prechodové príkazy: . Samozrejme, . Pre neprázdne slovo w podľa definície iterácie pre niektoré k >= 1 možno slovo w rozdeliť na k podslov: w=w 1 w 2 ... w k a je to. Pre každé i= 1,... ,k slovo w i zobrazuje q 0 1 až q f 1 . Potom pre slovo w v diagrame M existuje cesta

Preto, . Naopak, ak nejaké slovo preloží q 0 na q f , tak buď existuje, alebo je vedené cestou q 0 1 -prechodom, prípadne z q f 1 -prechodom končí na q f . Preto také slovo.

Z viet 4.2 a 5.1 priamo získame

Dôsledok 5.1. Pre každého regulárny výraz je možné efektívne skonštruovať deterministický konečný automat, ktorý rozpoznáva jazyk reprezentovaný týmto výrazom.

Toto vyhlásenie je jedným z príkladov teorémy syntézy: podľa popisu úlohy (jazyk ako regulárny výraz) efektívne skonštruovaný program (DFA), ktorý ho vykonáva. Opak je tiež pravdou - teorém analýzy.

Veta 5.2. Pre každý deterministický (alebo nedeterministický) konečný automat možno skonštruovať regulárny výraz, ktorý predstavuje jazyk rozpoznaný týmto automatom.

Dôkaz tejto vety je dosť technický a presahuje rámec nášho kurzu.

Môžeme teda dospieť k záveru, že trieda jazykov konečných automatov sa zhoduje s triedou regulárne jazyky. Ďalej to budeme nazývať jednoducho trieda automatových jazykov.

Automat M r, ktorý je zostrojený v dôkaze vety 5.1

Základné definície Regulárne výrazy v abecede Σ a regulárne množiny, ktoré označujú, sú definované rekurzívne takto: 1) regulárny výraz, ktorý označuje regulárnu množinu; 2) e je regulárny výraz označujúci regulárnu množinu (e); 3) ak a Σ, potom a je regulárny výraz označujúci regulárnu množinu (a); 4) ak p a q sú regulárne výrazy označujúce regulárne množiny P a Q, potom a) (p+q) je regulárny výraz označujúci P Q; b) pq je regulárny výraz označujúci PQ; c) p* je regulárny výraz označujúci P*; 5) nič iné nie je regulárny výraz.

Základné definície Prioritizácia: * (iterácia) – najvyššia priorita; zreťazenie; + (únia). Takže 0 + 10* = (0 + (1 (0*))). Príklady: 1.01 znamená (01); 2,0* - (0*); 3. (0+1)* - (0,1)*; 4. (0+1)* 011 - znamená množinu všetkých reťazcov zložených z 0 a 1 a končiacich reťazcom 011; 5. (a+b) (a+b+0+1)* znamená množinu všetkých reťazcov (0, 1, a, b)* počnúc a alebo b.

Hlavné definície lemmy: 1) α + β = β + α 2) * = e 3) α + (β + γ) = (α + β) + γ 4) α(βγ) = (αβ)γ 5 ) α( β + γ) = αβ + αγ 6) (α + β)γ = αγ + βγ 7) αe = eα = α 8) α = 9) α+α* = α* 10) (α*)* = α* 11) α+α = α 12) α+ = α

Komunikácia RT a RM RM sú jazyky generované RT. Napríklad: x = a+b, y = c+d, x X = (a, b), y Y = (c, d), x + y X Y = (a, b, c, d). Reťazenie: xy XY = (ac, ad, bc, bd). k(u+o)t (k)(u, o)(t) = (veľryba, mačka) alebo lemami č. 5 a č. 6 k(u+o)m = veľryba + mačka (veľryba, mačka) . Iterácia: x = a, x* X* = (e, a, aaa, ...), t.j. x* = e + xxx + ...

Vzťah RT a RM Iterácia zreťazenia a spojenia: (xy)* = e + xyxyxy + ... (x + y)* = e + (x + y) (x + y) + ... = = e + xx + xy + yx + yy + xxx + … Príklad: 0 + 1(0+1)* (0) ((1) (0, 1)*) = (0, 1, 10, 11, 100, 101, 110, 111...). Zjednotenie je komutatívne: x + y = y + x Zreťazenie nie je: xy ≠ yx

Vzťah medzi RT a PM Príklady priority: x + yz (x, yz), (x + y)z (xz, yz), x + y* (e, x, y, yyy, yyyy, …), (x + y)* (e, x, y, xx, xy, yx, yy, xxx, ...), (xy)* (e, xyxy, ...), xy* (x, xyy, xyyy, ...). Nové lemmy: a* + e = a*; (a + e)* = a*; a*a* = a*; e* = e; atď.

Regulárne sústavy rovníc Rovnica s regulárnymi koeficientmi X = a. X + b má riešenie (najmenší pevný bod) a*b: aa*b + b = (aa* + e)b = a*b Sústava rovníc s regulárnymi koeficientmi: X 1 = α 10 + α 11 X 1 + α 12 X 2 + … + α 1 n. Xn X 2 \u003d α 20 + α 21 X 1 + α 22 X 2 + ... + α 2 n. Xn …………………………. . Xn = αn 0 + αn 1 X 1 + αn 2 X 2 + … + αnn. Xn Neznáme – Δ = (X 1, X 2, …, Xn).

Regulárne sústavy rovníc Algoritmus riešenia (Gaussova metóda): Krok 1. Nastavte i = 1. Krok 2. Ak i = n, prejdite na krok 4. V opačnom prípade napíšte rovnice pre Xi v tvare Xi = αXi + β (β = β0 + βi +1 Xi+1 + … + βn.Xn). Potom na pravej strane pre rovnice Xi+1, …, Xn nahradíme Xi regulárnym výrazom α*β. Krok 3. Zvýšte i o 1 a vráťte sa ku kroku 2. Krok 4. Napíšte rovnicu pre Xn ako Xn = αXn + β. Prejdite na krok 5 (s i = n). Krok 5. Rovnica pre Xi je Xi = αXi + β. Napíšte na výstup Xi = α*β, do rovníc pre Xi– 1, …, X 1 dosaďte α*β namiesto Xi. Krok 6. Ak i = 1, zastavte, inak znížte hodnotu i o 1 a vráťte sa na krok 5.

Transformácia DFA na RW Pre DFA M = (Q, Σ, δ, q 0, F) zostavíme sústavu s regulárnymi koeficientmi, kde Δ = Q: 1. nastavíme αij: = ; 2. ak δ(Xi, a) = Xj, a Σ, potom αij: = αij + a; 3. ak Xi F alebo δ(Xi,) = HALT, potom αi 0: = e. Po vyriešení požadovaného RV bude X 1 = q 0.

Prevod DFA na RW Príklad: pre číslo s pevnou bodkou dostaneme sústavu q 0 = + q 0 + sq 1 + pq 2 + dq 3 + q 4 q 1 = + q 0 + q 1 + pq 2 + dq 3 + q 4 q 2 = + q 0 + q 1 + q 2 + q 3 + dq 4 q 3 = e + q 0 + q 1 + q 2 + dq 3 + pq 4 = e + q 0 + q 1 + q 2 + q 3 + dq 4 Tu: s je znamienko čísla, s = "+" + "-"; p – desatinná čiarka, p = "."; d - čísla, d = "0" + "1" + ... + "9".

Konverzia DFA na RW Riešenie: q 0 = *(sq 1 + pq 2 + dq 3 + q 4 +) = sq 1 + pq 2 + dq 3 q 1 = + q 0 + q 1 + pq 2 + dq 3 + q 4 = pq 2 + dq 3, q ​​​​2 = + q 0 + q 1 + q 2 + q 3 + dq 4 = dq 4, q 3 = e + q 0 + q 1 + q 2 + dq 3 + pq 4 = dq 3 + pq 4 + e, q 4 = e + q 0 + q 1 + q 2 + q 3 + dq 4 = dq 4 + e. Z tretej rovnice: q 3 \u003d dq 3 + pq 4 + e \u003d d * (pq 4 + e). Zo štvrtej rovnice: q 4 = dq 4 + e = d*.

Prevod DFA na RW Obrátený: q 3 = d*(pq 4 + e) ​​​​= d*(pd* + e), q 2 = dq 4 = dd*, q 1 = pq 2 + dq 3 = pdd* + dd *(pd* + e), q0 = sq 1 + pq 2 + dq 3 = s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). Táto DFA teda zodpovedá RE s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). Pre zjednodušenie: s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e) ​​​​= = spdd* + sdd*(pd* + e) ​​​​+ pdd* + dd*(pd* + e) ​​= (s + e)(pdd* + dd*(pd* + e)) Pre kratší zápis môžete použiť kladnú iteráciu aa* = a*a = a+: (s + e )(pdd* + dd* (pd* + e)) = (s + e)(pd+ + d+pd* + d+)

Transformácia DFA na RT Mapovanie grafu prechodovej funkcie DFA na základné operácie s regulárnym výrazom: q 0 a b a q 1 q 2 q 1 q 0 a+b a b ab q 2 a*

Prevod DFA na RT Zložitejšie kombinácie operácií: q 0 a q 1 b b b q 0 a q 2 q 1 (a + e)b c b q 0 q 2 ab(cab)* q 0 (a + b)* q 0 a q 1 aa* = a+ q 0 a q 1 a b a a a (ab)+ q 2 b q 1 c e + (a + b)c*

Konverzia DFA na RW Pre RW (s + e)(pd+ + d+(pd* + e)): q 0 p q 2 d s p q 1 d d q 3 d p q 4 d q 5 d

Regulárne výrazy programovania v reálnom čase: Zabudované do mnohých programovacích jazykov (PHP, Java. Script, …); Implementované ako zásuvné moduly (napríklad trieda Regex pre platformu .NET). Rozdiely v písaní: x? = x + e x(1, 3) = x + xxx atď.

Konštrukty triedy regulárneho výrazu programovania RT (System.Text.Regular.Expressions): Interpretácia sekvencie úniku znakov b Pri použití v hranatých zátvorkách sa zhoduje so znakom "←" (u 0008) t, r, n, a, f, v Tab (u 0009), návrat vozíka (u 000 D), nový riadok (u 000 A) atď. c. X Riadiaci znak (napr. c. C je Ctrl+C, u 0003) e Escape (u 001 B) ooo Osmičkový znak ASCII xhh Hexadecimálny znak ASCII uhhhh Znak Unicode Nasledujúci znak nie je špeciálny znak PB. Všetky špeciálne znaky musia byť označené týmto znakom. Príklad (v príklade je uvedený vzor a hľadaný reťazec, nájdené zhody v reťazci sú podčiarknuté): @"rnw+" – "rn. Je tu n dvoch reťazcov" .

Programovanie RT Podmnožiny znakov. Akýkoľvek znak okrem konca reťazca (n) Akýkoľvek znak z množiny [^xxx] Akýkoľvek znak iný ako znaky z množiny Akýkoľvek znak z rozsahu ] Odčítanie jednej množiny alebo rozsahu od inej p(meno) Akýkoľvek zadaný znak podľa kategórie Unicode pomenované meno P (názov) Akýkoľvek znak okrem tých, ktoré špecifikuje názov kategórie Unicode w Sada znakov použitých pri zadávaní identifikátorov W Sada znakov, ktoré sa nepoužívajú pri zadávaní identifikátorov s Medzery S Všetko okrem medzier d Číslice D Nie číslice Príklady : @". +" – "rn. Je tu n dvoch riadkov"; @"+" - "0xabcfx"; @"[^fx]+" – "0 xabcfx"; @"+" - "0xabcfx"; @"[^a-f]+" – "0 xabcfx"; @"]+" – "0xabcfx"; @"p(Lu)" - "Svetlá mesta"; // Lu - veľké písmená @"P(Lu)" - "Mesto"; @"p(je. azbuka)" - "ha. OS"; // Je. Cyrilika - ruské písmená

PB Programming Anchor ^, A Na začiatku reťazca $, Z Na konci reťazca alebo po „n“ na konci reťazca z Na konci reťazca G Kde skončila predchádzajúca zhoda b Hranica slova B Akákoľvek pozícia, ktorá nie je na hranici slova Príklady: @ "G(d)" - "(1)(3)(5)(9)"; // tri zhody (1), (2) a (3) @"bnS*ionb" – "darovanie národa"; @"Bendw*b" – "koniec posiela vydržať veriteľa".

Programovanie operácií RT (kvantifikátory) *, *? Iterácia +, +? Pozitívna iterácia? , ? ? Nula alebo jedna zhoda (n), (n)? Zhoduje sa presne n (n, ), (n, )? Aspoň n sa zhoduje (n, m), (n, m)? Od n do m sa zhodujú Príklady (prvé kvantifikátory sú chamtivé, hľadajú čo najviac prvkov, druhé sú lenivé, hľadajú čo najmenej prvkov): @"d(3, )" – "888 -5555"; @"^d(3)" - "913 -913"; @"-d(3)$" - "913 -913"; @"5+? 5" - "888 -5555"; // tri zhody - 55, 55 a 55 @"5+5" - "888 -5555".

Zoskupenie programovania RT () Skupine sa automaticky priradilo číslo (?:) Neukladať skupinu (?) alebo (? "meno") Ak sa nájde zhoda, vytvorte pomenovanú skupinu (?) alebo odstráňte predtým definovanú skupinu a (? "name-name") uložiť do novej skupiny podreťazec medzi predtým definovanou skupinou a novou skupinou (? imnsx:) Zapne alebo vypne ktorúkoľvek z piatich (? -imnsx:) možných možností v skupine: i - case necitlivý; s je jeden riadok (potom "." je ľubovoľný znak); m – viacriadkový režim („^“ , „$“ – začiatok a koniec každého riadku); n - nezachytávať nepomenované skupiny; x - vylúčiť zo vzoru medzery bez špeciálnych znakov a za znak čísla (#) (?=) zahrnúť komentáre

RE Programovanie (? !) Negatívne dopredné tvrdenie nulovej dĺžky (?) Nevracajúca sa (nenásytná) časť výrazu Príklady: @"(an)+" – "bananas annals"; @"an+" – "ananály banánov"; // porovnaj, tri zhody - an, an a ann @"(? i: an)+" - "ba. NAnas annals"; @"+(? =d)" – "abc xyz 12 555 w"; @"(?

Src="https://website/presentation/-112203859_437213351/image-24.jpg" alt="(!LANG:Programovanie RT Referenčné číslo Odkaz na skupinu k Odkaz na pomenovanú skupinu Príklady: @"> Программирование РВ Ссылки число Ссылка на группу k Ссылка на именованную группу Примеры: @"(w)1" – "deep"; @"(? w)k " – "deep". Конструкции изменения | Альтернатива (соответствует операции объединения) (? (выражение)да|нет) Сопоставляется с частью «да» , если выражение соответствует; в противном случае сопоставляется с необязательной частью «нет» (? (имя)да|нет), Сопоставляется с частью «да» , если названное имя (? (число)да|нет) захвата имеет соответствие; в противном случае сопоставляется с необязательной частью «нет» Пример: @"th(e|is|at)" – "this is the day";!}

Programovanie RT Substitúcie $číslo Nahradí časť reťazca zodpovedajúcu skupine zadaným číslom $(meno) Nahradí časť reťazca zodpovedajúcu skupine zadaným názvom $$ Nahradí $ $& Nahradí kópiou celého reťazca match $` Nahradiť text vstupného reťazca, kým sa nezhoduje $" Nahradiť text vstupného riadku po zhode $+ Nahradiť poslednú zachytenú skupinu $_ Nahradiť celý riadok Komentáre (? #) Vložený komentár # Komentár na koniec riadku

Výsledky programovania RT pre Regex: Regex Matches() Match. Zbierka Match Groups() Group. Collection Group Captures() Capture. Zbierka zachytáva ()

Príklad programovania RT v C++ CLI (Aplikácia konzoly Visual C++/CLR/CLR): int main() ( Regex ^r = gcnew Regex(L"((\d)+)+"); Zhoda ^m = r-> Zhoda (L"123 456"); int match. Count = 0; while (m->Success) ( Console: : Write. Line(L"Match(0)", ++match. Count); for (int i = 1; i Skupiny->Počet; i++) ( Skupina ^g = m->Skupiny[i]; Konzola: : Zápis. Riadok(L" Skupina (0) = "(1)"", i, g-> Hodnota ); for (int j = 0; j Zachytenie->Počet; j++) ( Zachytenie ^c = g->Zachytenie[j]; Konzola: : Write.Line(L" Zachytenie(0) = "(1)" , pozícia = (2), dĺžka = (3)", j, c, c->Index, c->Dĺžka); ) ) m = m->Ďalšia. Zhoda(); ) návrat 0; ) Systém: : Text ::Pravidelne. výrazov

Zahrnutie akcií a hľadanie chýb Obmedzenie počtu platných číslic v čísle: (s + e)(pd+ + d+(pd* + e)) s = +|p = . d = ds + e = s? = (+|-)? pd* + e = (pd*)? =(.d*)? @"(+|-)? (. d+|d+(. d*)?)" alebo @"^(+|-)? (. d+|d+(. d*)?)$" Regulárny výraz r = nový regulárny výraz (@"^(+|-)? (. (? "číslica"d)+|(? "číslica"d)+(. (? "číslica"d)*)?)$"); Zhoda m = r. Match("+1. 23456789"); if (m. Úspech) ( Skupina g = m. Skupiny["číslica"]; if (g. Zachytí. Počet

Povolenie akcií a hľadanie chýb pri určovaní polohy chyby: Regulárny výraz r = nový regulárny výraz(@"(+|-)? (. (? "číslica"d)+|(? "číslica"d)+(. (? " číslica "d )*)?)"); string str = "+1,2345!678"; Zhoda m = r. Match(str); if (m. Úspech) ( Skupina g = m. Skupiny["číslica"]; if (g. Zachytí. Počet 0) Konzola. Zápis. Riadok("Chyba na pozícii 1: neočakávaný znak "(0)"", str ); inak, ak (m.Dĺžka

Povolenie akcií a vyhľadávanie chýb Určenie polohy chyby: 1. prvá pozícia vstupného reťazca (1), ak prvá zhoda nezačína od pozície Index = 0; 2. pozícia po poslednej zhode (zhoda. Dĺžka + 1), ak sa nezhoduje s poslednou pozíciou vstupného reťazca; 3. pozícia prvej prestávky medzi zhodami (zhoda[i]. Index + zhoda[i]. Dĺžka + 1), ak znak nasledujúci po predchádzajúcej zhode nie je prvým znakom nasledujúcej zhody.

index) zlom; index = m[i]. Index + m[i]. dĺžka; ) Konzola. písať. Riadok("Chyba na pozícii (0) "(1)"", index + 1, str); ) "abc. xyz. pqr" je správne; + abc. xyz. pqr" - chyba na pozícii 1 ("+"); "abc. xyz. pqr!" – chyba na pozícii 12 („!“); "abc. xyz!. pqr" - chyba na pozícii 8 ("!").

Zahrnutie akcií a hľadanie chýb Ale! "abc. xyz. +pqr" - chyba na pozícii 8 (."). Nový variant vzoru: @"w+(. w+)*(. (? !$))?" Overenie: "abc. xyz. +pqr" - chyba na pozícii 9 ("+"); "abc. xyz. pqr. "- chyba na pozícii 12 (.").

Vyvážené definície: "(? "x")" pridáva jeden prvok do kolekcie s názvom "x"; "(? "-x")" odstráni jeden prvok z kolekcie "x"; "(? (x)(? !))" skontroluje, či v kolekcii "x" nezostali žiadne prvky. Jazyk L, popisujúci vnorené príkazy jazyka Pascal „začiatok konca; ': @"^s*((? "začína+)+(? "-začína" končí*; s*)+)*(? (začína)(? !))$".

DFA je špeciálny prípad NFA. V ňom:

neexistuje stav s ε-prechodmi;

pre každý stav S a vstupný symbol a existuje najviac jeden oblúk vychádzajúci zo S a označený a.

DFA má maximálne jeden prechod pre akýkoľvek vstupný symbol z každého štátu. Ak sa na znázornenie funkcie prechodu DFA použije tabuľka, každá položka bude obsahovať iba jeden stav. Je teda ľahké skontrolovať, či daná DFA povoľuje určitý riadok, pretože existuje iba jedna cesta z počiatočného stavu, ktorá je označená týmto riadkom.

Obrázok 3 zobrazuje graf prechodu DFA, ktorý umožňuje rovnaký jazyk (a|b) * a(a|b)(a|b) ako NFA na obrázku 1.

Obrázok 3. DFA, ktorá umožňuje reťazec (a|b) * a(a|b)(a|b).

Deterministický konečný automat M, ktorý akceptuje daný jazyk:

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

Prechodová funkcia D je definovaná takto:

Budovanie nc z regulárneho výrazu

1. Pre ε má NFA nasledujúci tvar (0 je počiatočný stav, 1 je konečný stav):

2. Pre jazyk zahrnutý v danom jazyku NFA:

3. Nech N(s) a N(t) sú NFA pre regulárne výrazy s a t.

Pre regulárny výraz s|t má zložený NFA nasledujúci tvar:

b. Pre regulárny výraz st NFA:

s Pre výraz s* má NFA tvar:

d. Pre výraz v zátvorkách (s) sa používa NFA N(s) ako v odseku a.

Každý nový štát dostane individuálny názov. Konštrukcia NFA N(r) má nasledujúce vlastnosti:

N(r) má taký počet stavov, ktorý nepresahuje počet symbolov viac ako 2-krát.

N(r) má práve jeden počiatočný a jeden konečný stav. Konečný stav nemá žiadne odchádzajúce prechody.

Každý stav N(r) má buď 1 prechod pre symbol z abecedy (), alebo nie viac ako 2 odchádzajúce ε-prechody.

Konverzia na na dka.

NFA na obrázku 1 má 2 prechody zo stavu 0 pre symbol a: stavy 0 a 1. Takýto prechod je nejednoznačný, rovnako ako prechod v ε. Modelovanie takýchto NSC pomocou počítačového programu je oveľa náročnejšie. Definícia prípustnosti uvádza, že musí existovať určitá cesta z počiatočného stavu do konečného stavu, ale ak existuje viacero ciest pre rovnaký vstupný reťazec, musia sa zvážiť všetky, aby sa našla cesta do konečného stavu alebo aby sa zistilo, že taká cesta neexistuje.

V tabuľke prechodu NFA každý záznam zodpovedá množine stavov a v tabuľke prechodu DFA iba jednému. Podstatou transformácie je, že každý stav DFA zodpovedá množine stavov NFA. DFA používa svoje stavy na sledovanie všetkých možných stavov, v ktorých môže byť NFA po prečítaní ďalšieho vstupného symbolu. To znamená, že po načítaní vstupného toku je DFA v stave, ktorý predstavuje určitú množinu stavov NFA, ktoré sú dosiahnuteľné z počiatočného po ceste zodpovedajúcej vstupnému reťazcu. Počet takýchto stavov DFA môže výrazne prevyšovať počet stavov NFA (exponenciálna závislosť), ale v praxi je to extrémne zriedkavé a niekedy je v DFA ešte menej štátov ako v NFA.

Uvažujme o takejto transformácii na konkrétnom príklade. Obrázok 4 zobrazuje ďalší NFA, ktorý umožňuje jazyk (a|b) * a(a|b)(a|b) (ako na obrázkoch 1 a 3).

Obrázok 4. NFA, ktorý umožňuje jazyk (a|b) * a(a|b)(a|b)

Prechod zo stavu 13 do stavu 14 znázornený na obrázku môže byť znázornený podobne ako prechod zo stavu 8 do stavu 13.

Postavme DFA pre daný jazyk. Východiskovým stavom ekvivalentnej DFA je stav A =(0, 1, 2, 4, 7), teda také stavy, ktoré je možné dosiahnuť od 0 do ε.

Vstupná abeceda znakov je (a, b). Z počiatočného stavu A možno vypočítať dosiahnuteľný stav vzhľadom na a. Nazvime tento stav B = (1, 2, 3, 4, 6, 7, 8, 9, 11, 13, 14).

Spomedzi stavov v A má iba stav 4 prechod na b do stavu 5, takže DFA má prechod na b zo stavu A do stavu C = (1, 2, 4, 5, 6, 7).

Ak budeme pokračovať v tomto procese so stavmi B a C, označia sa všetky súbory stavov NFA. Budeme mať teda množiny stavov:

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)

Stav A je počiatočný a stavy B, D, E sú konečné.

Kompletná tabuľka prechodu je uvedená nižšie.

Obrázok 5 nižšie zobrazuje samotnú DFA pre tento jazyk.

Obrázok 5. DFA, ktorá akceptuje jazyk (a|b) * a(a|b)(a|b)

Zoznam použitej literatúry:

Pentus A. E., Pentus M. R. – Teória formálnych jazykov

A. Aho, R. Seti, D. Ullman - Kompilátory: princípy, technológie, nástroje.

Zostavenie deterministického konečného automatu z regulárneho výrazu

Predstavme si teraz algoritmus na zostrojenie deterministického konečného automatu z regulárneho výrazu, ktorý umožňuje rovnaký jazyk [?].

Nech je regulárny výraz r daný v abecede T. Pridajte koncovú značku k regulárnemu výrazu r: (r)#. Takýto regulárny výraz sa bude nazývať dokončený. Algoritmus bude v priebehu svojej práce používať hotový regulárny výraz.

Algoritmus bude pracovať so stromom syntaxe pre dokončený regulárny výraz (r)#, ktorého každý list je označený symbolom a vnútorný vrch je označený znakom jednej z operácií: (reťazenie),| (spojenie), * (iterácia).

Každému listu stromu (okrem e-listov) bude pridelené jedinečné číslo, nazývané pozícia, a budeme ho používať na jednej strane na označenie listu v strome a na druhej strane na označenie na symbol zodpovedajúci tomuto listu. Všimnite si, že ak sa znak v regulárnom výraze použije viackrát, má viacero pozícií.

Prejdeme stromom T zdola nahor zľava doprava a vypočítame štyri funkcie: nullable, firstpos, lastpos a followpos. Prvé tri funkcie – nullable, firstpos a lastpos – sú definované na uzloch stromu a followpos je definované na množine pozícií. Hodnota všetkých funkcií okrem nullable je množina pozícií. Funkcia followpos je vypočítaná prostredníctvom ostatných troch funkcií.

Funkcia firstpos(n) pre každý uzol n stromu syntaxe regulárneho výrazu dáva množinu pozícií, ktoré zodpovedajú prvým znakom v podreťazce, generovaný podvýrazom s vrcholom na n. Podobne lastpos(n) dáva množinu pozícií, ktoré zodpovedajú posledným znakom v podreťazce generované podvýrazmi s vrcholom n. Pre uzol n, ktorého podstromy (t. j. stromy, ktorých koreňový uzol n je) môžu vytvárať nulové slovo, definujte nullable(n)=true a pre ostatné uzly nullable(n)=false.

Tabuľka na výpočet funkcií s nulovou hodnotou, firstpos a lastpos je znázornená na obr. 3.11.

Príklad 3.7.Na obr. 3.12 ukazuje strom syntaxe pre dokončený regulárny výraz (a|b) * abb# s výsledkom vyhodnotenia funkcií firstpos a lastpos. Naľavo od každého uzla je hodnota firstpos, napravo od uzla je hodnota lastpos. Všimnite si, že tieto funkcie možno vypočítať v rámci jedného prechodu cez strom.

Ak i je pozícia, potom followpos(i) je množina pozícií j takých, že existuje nejaký reťazec... cd ... vyskytujúci sa v jazyku opísanom regulárnym výrazom tak, že pozícia i zodpovedá tomuto výskytu c a pozícii j je záznam d.

Ryža. 3.11.

Ryža. 3.12.

Funkciu followpos je možné vypočítať aj pri jednom prechode stromom zdola nahor podľa týchto dvoch pravidiel.

1. Nech n je vnútorný uzol s operáciou (reťazením), u a v sú jeho potomkovia. Potom pre každú pozíciu, ktorú som zahrnul do lastpos(u), pridáme k množine hodnôt followpos(i) množinu firstpos(v).

2. Nech n je vnútorný uzol s operáciou * (iterácia), u - jeho potomok. Potom pre každú pozíciu, ktorú som zahrnul do lastpos(u), pridáme k množine hodnôt followpos(i) množinu firstpos(u).

Príklad 3.8. Výsledok vyhodnotenia funkcie followpos pre regulárny výraz z predchádzajúceho príkladu je na obr. 3.13.

Algoritmus 3.3. Priama konštrukcia DFA z regulárneho výrazu.

Vchod. Regulárny výraz r v abecede T.

Výkon. DFA M = (Q, T, D, q°, F) tak, že L(M) = L(r).

Metóda. Stavy DFA zodpovedajú množinám pozícií.

Na začiatku sú Q a D prázdne. Postupujte podľa krokov 1-6:

(1) Vytvorte syntaktický strom pre rozšírený regulárny výraz (r)#.