Algoritmus na elimináciu ľavostrannej rekurzie. Ľavo-rekurzívne gramatiky
Pri postupe rekurzívnej analýzy zhora nadol môže vzniknúť problém nekonečnej slučky.
V gramatike pre aritmetické operácie aplikácia druhého pravidla spôsobí zacyklenie procedúry analýzy. Takéto gramatiky sa nazývajú ľavo-rekurzívne. O gramatike sa hovorí, že je ľavo-rekurzívna, ak obsahuje neterminálne A, pre ktoré existuje odvodenie A=>+Aa. V jednoduchých prípadoch sa ľavá rekurzia volá podľa pravidiel formulára
V tomto prípade sa zavedie nový neterminál a pôvodné pravidlá sa nahradia nasledujúcimi.
(ak existuje nesvorka A, pre ktorú existuje výstup A→+Aa v 1 alebo viacerých krokoch). Ľavej rekurzii sa dá vyhnúť transformáciou gramatiky.
Napríklad inscenácie A→Aa
Môže byť nahradený ekvivalentom:
Pre takýto prípad existuje algoritmus, ktorý vylučuje ľavú rekurziu:
1) definujte nejaké poradie na množine neterminálov (А 1 , А 2 , …, А n)
2) vezmeme každý neterminál, ak preň existuje produkcia, ktorá berie do úvahy neterminál vľavo, a transformujeme gramatiku:
pre i:=1 až n do
pre j:=1 až i-1 do
ak Ai → Ajγ, potom Ai→δ1γ
│ δkγ, kde
Aj → δ1│ δ2│ …│ δk
3) vylúčiť všetky prípady okamžitej rekurzie doľava (pravidlo 1)
To. Algoritmus pomáha predchádzať zacykleniu.
Vylúčenie rekurzie vľavo z gramatiky aritmetických výrazov a všeobecnej formy pravidla na vylúčenie rekurzie vľavo:
Všeobecný pohľad na pravidlo vylúčenia ľavej rekurzie
Ľavá faktorizácia.
Gramatiky LL(1) sú potrebné na výber správnej produkcie na analýzu zhora nadol, aby nedochádzalo k zacykleniu.
Niekedy je možné previesť gramatiku do formy LL(1) pomocou metódy ľavého faktorizácie.
Napríklad: S → ak B, potom S
│ak B, tak S inak S
Tieto produkcie porušujú podmienku LL(1)-gramatiky. Túto gramatiku je možné previesť do tvaru LL(1).
S → ak B, tak S Chvost
Vo všeobecnosti možno túto transformáciu definovať takto:
zavádzame nový neterminál B, pre ktorý
| βN Ľavá faktorizácia sa môže použiť na B. Tento postup sa opakuje dovtedy, kým výber produktov zostáva neistý (teda kým sa v ňom nedá niečo zmeniť).
Zostavenie PRVEJ SÚPRAVY
Prvá množina pre neterminál definuje množinu terminálov, s ktorými môže tento neterminál začať.
1. Ak x je terminál, potom najprv(x)=(x). Keďže prvým znakom sekvencie z jedného terminálu môže byť len samotný terminál.
2. Ak gramatika obsahuje pravidlo Хà e, potom množina first(х) obsahuje e. To znamená, že X môže začínať prázdnou sekvenciou, to znamená, že nemôže vôbec existovať.
3. Pre všetky produkcie v tvare XàY1 Y2 … Yk robíme nasledovné. Do množiny first(X) pridávame množinu first(Yi), až kým first(Yi-1) neobsahuje e a first(Yi) neobsahuje e. V tomto prípade sa i zmení z 0 na k. Je to potrebné, pretože ak Yi-1 môže chýbať, je potrebné zistiť, kde v tomto prípade začne celá sekvencia.
(Čas: 1 s. Pamäť: 16 MB Obtiažnosť: 20%)V teórii formálnych gramatík a automatov (TFGiA) dôležitú úlohu zohráva tzv bezkontextové gramatiky(CS-gramatiky). CS-gramatika je štvorica pozostávajúca z množiny N nekoncových symbolov, množiny T koncových symbolov, množiny P pravidiel (produkcií) a počiatočného symbolu S patriaceho do množiny N.
Každá produkcia p P má tvar A –> a, kde A je nekoncový znak (A alebo N) a a je reťazec pozostávajúci z koncových a nekoncových znakov. Proces výstupu slova začína reťazcom obsahujúcim iba počiatočný znak S. Potom je v každom kroku jeden z neterminálnych znakov zahrnutých v aktuálnom reťazci nahradený pravou stranou jednej z produkcií, v ktorej je ľavá strana. Ak sa po takejto operácii získa reťazec obsahujúci iba koncové znaky, výstupný proces sa skončí.
Pri mnohých teoretických problémoch je vhodné uvažovať o tzv normálne formy gramatika Proces normalizácie gramatiky často začína elimináciou ľavostrannej rekurzie. V tomto probléme budeme uvažovať iba o jeho špeciálnom prípade, ktorý sa nazýva priama ľavá rekurzia. Odvodzovacie pravidlo A -> R obsahuje okamžitú ľavú rekurziu, ak prvý znak reťazca R je A.
Je daná CS-gramatika. Je potrebné nájsť počet pravidiel obsahujúcich okamžitú ľavú rekurziu.
Vstupné Data
Prvý riadok vstupného súboru INPUT.TXT obsahuje počet n (1 ≤ n ≤ 1000) pravidiel v gramatike. Každý z nasledujúcich n riadkov obsahuje jedno pravidlo. Nekoncové symboly sú označené veľkými písmenami anglickej abecedy, koncové symboly - malé. Ľavá časť produkcie je oddelená od pravej časti symbolmi –>. Pravá časť inscenácie má dĺžku 1 až 30 znakov.
Definícia 10.1 O nejakom neterminálnom symbole A bezkontextovej gramatiky G = (N, P, S) sa hovorí, že je rekurzívny, ak existuje derivácia A + A pre nejaké u. Ak zároveň =, potom sa A nazýva ľavo-rekurzívne. Podobne, ak =, potom A sa nazýva pravý rekurzívny. Gramatika, ktorá má aspoň jeden ľavo-rekurzívny neterminálny symbol, sa považuje za ľavo-rekurzívnu. Gramatika, v ktorej sú všetky neterminálne symboly, snáď okrem počiatočného symbolu, rekurzívne, sa nazýva rekurzívna.
Všimnite si, že pre rekurzívne gramatiky je pri derivácii A + A vždy buď alebo. Ak = a =, potom gramatika G je cyklická gramatika. Príklad Príkladom pravej rekurzívnej gramatiky je gramatika s nasledujúcou schémou: 1 0 Táto gramatika generuje množinu čísel pozostávajúcu z núl a jednotiek.
Príklad Rovnaký jazyk ako v príklade je vygenerovaný ľavo-rekurzívnou gramatikou s nasledujúcou schémou: 1 0
Príklad Príkladom ľavo-rekurzívnej gramatiky je gramatika s nasledujúcou schémou: A 1 0 Táto gramatika generuje množinu identifikátorov začínajúcich na písmeno A.
Príklad Rovnaký jazyk ako v príklade je vygenerovaný pravou rekurzívnou gramatikou s nasledujúcou schémou: A 1 0
Lema 10.1 Nech G = (N, P, S) je CF-gramatika, v ktorej pre nejaký neterminálny symbol A majú všetky A-pravidlá tvar A A 1 | A 2 | … | A m | 1 | 2 | … | n | a žiadny z reťazcov i nezačína na A. Nech G"=(N (A"), P", S), kde A" je nový neterminál a P" sa získa z P nahradením týchto A-pravidiel za tieto pravidlá A 1 | 2 | … | n | 1A" | 2A" | … | nA" | A" 1 | 2 | ... | m | 1A" | 2A" | … | mA" Potom L(G") = L(G). Zvážte algoritmus na konverziu CFG s priamou rekurziou vľavo na CFG bez rekurzie vľavo.
Dôkaz. Reťazce, ktoré možno získať v gramatike G z neterminálu A aplikovaním pravidiel A len na najľavejšiu neterminálnu formu regulárnej množiny (… + n)(… + m)* Toto sú presne tie reťazce, ktoré možno získať v gramatiku G" z A pomocou pravotočivých záverov, pričom raz použijeme A-pravidlo a niekoľkokrát A"- pravidlá (výsledkom je, že záver už nebude ľavotočivý). Všetky inferenčné kroky, ktoré nepoužívajú A-pravidlá, je možné vykonať aj priamo v gramatike G", keďže ne-A-pravidlá v oboch gramatikách sú rovnaké. Z toho môžeme usúdiť, že L(G) L(G") .
Obrátené začlenenie je dokázané podobne. Gramatika G" vyvodzuje správny záver a zvažuje postupnosti krokov pozostávajúce z jednej aplikácie A-pravidla a niekoľkých aplikácií A"-pravidiel. Teda L(G") = L(G). Gramatika príkladu je získaná z gramatiky príkladu pomocou transformácie Lemy 10.1.
Lema 10.2 Nech G = (N, P, S) je CF-gramatika, v ktorej pre nejaký neterminálny symbol A majú všetky A-pravidlá tvar А A 1 | A 2 | … | A m | 1 | 2 | … | m a žiadny z reťazcov i nezačína na A. Nech G"=(N, P", S), kde P" sa získa z P nahradením týchto A-pravidiel nasledujúcimi pravidlami A 1 | 2 | ... | m | 1A | 2A | … | mA Potom L(G") = L(G). Príklad gramatiky je získaný z príkladovej gramatiky pomocou transformácie Lemy 10.2.
Obrázok ukazuje, ako transformácie ovplyvňujú výstupný strom A A i1... i2 A A ik A ik A ik-1... i1
Príklad Nech G0 je obyčajná gramatika s pravidlami E E+T E T T T*F T F F (E) F a Ekvivalentná gramatika G`
E T E TE" E" +T E" +TE" T F T FT " T " *F T " *FT " F (E) F
Algoritmus 10.2 Eliminácia ľavostrannej rekurzie. Vstup: Redukovaný CFG G=(N,P,S) Výstup: Ekvivalent CFG G` bez rekurzie doľava. Metóda. Nech N = (A1,…, An), t.j. všetky neterminálne symboly gramatiky sú usporiadané nejakým ľubovoľným spôsobom. Transformujme G tak, že v pravidle Ai reťazec začína buď od terminálu alebo od takého Aj, že j i. 1) Nech i=1.
2) Nech je množina pravidiel Ai Ai Ai | … | Cieľ | 1 | … | p, kde žiadny z reťazcov j nezačína Ak, ak k i (ak sa tak nestane, môžete zaviesť nový nekoncový symbol, nahradiť prvý symbol pravidla týmto symbolom a pridať do gramatiky ďalšie pravidlo) . Nahraďte pravidlá Ai nasledujúcimi pravidlami: Ai 1 | … | p | 1Ai" | … | pAi" Ai" 1 | … | m | 1Ai" | … | mAi" kde A"i je nový neterminál. Pravé strany všetkých pravidiel Ai teraz začínajú od terminálu alebo od Ak pre niektoré k > i. 3) Ak i=n, považujte výslednú gramatiku G" za výsledok a zastavte sa. V opačnom prípade zadajte i=i+1 a j=1. i. 3) Ak i=n, považujte výslednú gramatiku G" za výsledok a zastavte sa. V opačnom prípade zadajte i=i+1 a j=1."> 
J, potom pravú stranu každého" title="4) Nahraďte každé pravidlo v tvare Ai Aj pravidlami Ai 1 |…| m získané nahradením Aj pravou stranou všetkých Aj-pravidiel v tvare Aj 1|…| m. Keďže pravá strana každého Aj pravidla začína už koncovkou alebo Ak pre k > j, potom pravá strana každého" class="link_thumb"> 16 !} 4) Nahraďte každé pravidlo v tvare Ai Aj pravidlami Ai 1 |…| m získané nahradením Aj pravou stranou všetkých Aj-pravidiel v tvare Aj 1|…| m. Keďže pravá strana každého Aj-pravidla už začína terminálom alebo Ak pre k > j, potom pravá strana každého Ai pravidla bude mať teraz túto vlastnosť. 5) Ak j=i–1, prejdite na krok (2). V opačnom prípade zadajte j=j+1 a prejdite na krok (4). j, potom pravá strana každého> j, potom pravá strana každého pravidla Ai bude mať túto vlastnosť. 5) Ak j=i–1, prejdite na krok (2). V opačnom prípade zadajte j=j+ 1 a prejdite na krok (4)."> j, potom pravú stranu každého" title="4) Nahraďte každé pravidlo v tvare Ai Aj pravidlami Ai 1 |…| m získané nahradením Aj pravou stranou všetkých Aj-pravidiel v tvare Aj 1|…| m. Keďže pravá strana každého Aj pravidla začína už koncovkou alebo Ak pre k > j, potom pravá strana každého"> title="4) Nahraďte každé pravidlo v tvare Ai Aj pravidlami Ai 1 |…| m získané nahradením Aj pravou stranou všetkých Aj-pravidiel v tvare Aj 1|…| m. Keďže pravá strana každého Aj pravidla začína už koncovkou alebo Ak pre k > j, potom pravá strana každého"> !}
Veta 10.1 Pre každý CF-jazyk existuje neľavo-rekurzívna gramatika, ktorá ho generuje. Dôkaz je dôsledkom transformácií uvedených v tejto časti. Príklad Nech G je COP gramatika s pravidlami A BC a B CA Ab C AB CC a
Nech A1=A, A2=B a A3=C Po každej aplikácii kroku (2) alebo (4) algoritmu sa získajú nasledujúce gramatiky (uvádzame len nové pravidlá). Krok (2) pre i=1: G sa nemení Krok (4) pre i=2, j=1: B CA BCb ab Krok (2) pre i=2: B CA ab CAB abB B Cb Krok (4) pre i=3, j=1: C BCB aB CC a Krok (4) pre i=3, j=2: C CACB ab CB CAB CB ab B CB aB CC a Krok (2) pre i=3: C abCB ab B CB aB a abCBC ab B CB C aB C aC C ACB C AB CB C CC ACB AB CB C
Chomského klasifikácia formálnych gramatík
Gramatika typu 0 (všeobecná). Pravidlá sú α→β
Gramatika 1. typu (citlivá na kontext, KZ)
Pravidlá sú v tvare αAβ → αγβ. γ patrí do V +, t.j. gramatika sa neskracuje
α,β sa nazývajú ľavý a pravý kontext
Gramatika typu 2 (bezkontextová, CS)
Pravidlá sú v tvare A → α. α patrí do V*, t.j. gramatika môže byť skrátená => CS jazyky nie sú zahrnuté v životopise
Najbližšie k BNF
Gramatika typu 3 (automatická, bežná)
Pravidlá majú tvar A → aB, A → a, A → ε
Jazyky automatu sú obsiahnuté v jazykoch CS
Príklad. Gramatika, ktorá generuje jazyk výrazov v regulárnych zátvorkách.
S → (S) | SS | ε
Generácia (výstup)
Notový zápis
=>+ (1 alebo viac)
=>* (0 alebo viac)
Vetná forma gramatiky je reťazec, ktorý môže byť vydaný zo začiatočného znaku.
Gramatická veta (maximum) je vetná forma pozostávajúca iba z terminálov.
Gramatika jazyka L(G). je súbor všetkých jeho návrhov.
Označenia:
Ľavý, pravý výstup (výroba).
Ľavý a pravý výstup pre vetu i + i * i
Výstupný strom (strom syntaxe, strom analýzy) reťazca vety. Na rozdiel od generovania sú z neho vylúčené informácie o poradí výstupu.
Koruna parsového stromu - reťaz listových štítkov zľava doprava
Gramatika, ktorá produkuje viac ako jeden strom analýzy pre niektorú vetu, sa nazýva nejednoznačný.
Príklad nejednoznačnej gramatiky. Gramatika aritmetických výrazov.
E → E+E | E*E | i
Dva stromy analýzy pre reťazec i + i * i
Príklad nejednoznačnej gramatiky. Gramatika podmieneného operátora
S → ak b, potom S
| ak b, potom S inak S
Dva stromy analýzy pre ak b, potom ak b, potom reťazec
Prevod na ekvivalentnú jednoznačnú gramatiku:
S → ak b, potom S
| ak b, potom S2 inak S
S2 → ak b potom S2 inak S2
44. Formálne jazyky a gramatiky: neprázdne, konečné a nekonečné jazyky
45. Ekvivalencia a minimalizácia automatov
Ekvivalencia konečných automatov
Nech S je abeceda (konečná množina symbolov) a S* je množina všetkých slov v abecede S. Nech e je prázdne slovo, t.j. ktorý vôbec neobsahuje písmená (symboly od S), ale so znamienkom × - operácia priraďovania (reťazenia) slov.
Takže aav × va = aavva. Znamienko × operácie priradenia sa často vynecháva.
Slová v abecede S budú označované malými gréckymi písmenami a, b, g, .... Je zrejmé, že e je jednotka pre operáciu priraďovania:
Je tiež zrejmé, že operácia priradenia je asociatívna, t.j. (ab)g = a(bg).
Množina S* všetkých slov v abecede S vzhľadom na operáciu priradenia je teda pologrupa s identitou, t.j. monoid;
S* sa nazýva voľný monoid nad abecedou S.
Minimalizácia konečného stroja
Rôzne stavové automaty môžu fungovať rovnakým spôsobom, aj keď majú rôzny počet stavov. Dôležitou úlohou je nájsť minimálny konečný automat, ktorý implementuje dané mapovanie automatu.
Je prirodzené nazývať ekvivalentné dva stavy automatu, ktoré nemožno rozlíšiť žiadnymi vstupnými slovami.
Definícia 1: Dva stavy p a q konečného automatu
А = (S,X,Y,s0,d,l) sa nazývajú ekvivalentné (označené p~q), ak ("aн X*)l*(p,a) =l*(q, a)
46. Ekvivalencia jednopáskových a viacpáskových Turingových strojov
Je zrejmé, že koncept k-páskového MT je širší ako koncept „normálneho“ jednopáskového stroja. DEFINÍCIA 6. (k+1)-páska MT M′ s programom w simuluje k-páskový stroj M, ak sa pre akúkoľvek sadu vstupných slov (x1, x2, …, xk) výsledok práce M′ zhoduje s výsledok práce M na rovnakých vstupných údajoch. Predpokladá sa, že slovo w je najskôr napísané na (k + 1)-tej páske M′. Výsledok je chápaný ako stav prvých k MT pások v momente zastavenia a ak sa M nezastaví na danom vstupe, tak by sa na tomto vstupe nemal zastaviť ani stroj, ktorý ho simuluje.
DEFINÍCIA 7. (k+1)-páska MT M* sa nazýva univerzálny Turingov stroj pre k-páskové stroje, ak pre akýkoľvek k-páskový stroj M existuje program w, na ktorom M* simuluje M. 12 Všimnite si, že v definícia univerzálneho MT ten istý stroj M′ musí simulovať rôzne k-páskové stroje (na rôznych programoch w). Zvážte nasledujúcu vetu. VĚTA 3. Pre každé k≥1 existuje univerzálny (k+1) Turingov páskový stroj. Dôkaz. Dokážme vetu konštruktívne, t.j. ukážme, ako možno skonštruovať požadovaný univerzálny stroj M*. Uvažujme iba o všeobecnej schéme konštrukcie, vynechajme zložité detaily. Hlavnou myšlienkou je umiestniť popis simulovaného Turingovho stroja na dodatočnú (k + 1) pásku a použiť tento popis v procese simulácie.
DEFINÍCIA 8. Hovoríme, že Turingov stroj M vyhodnocuje parciálnu funkciu f:A*→A*, ak pre ľubovoľné x∈A* zaznamenané na prvej páske stroja M: ak je definované f(x), potom sa M zastaví, a v momente, keď sa zastaví na poslednej páske stroja, je napísané slovo f(x); ak f(x) nie je definované, potom sa stroj M nezastaví.
DEFINÍCIA 9. Povieme, že stroje M a M′ sú ekvivalentné, ak počítajú rovnakú funkciu. Pojem ekvivalencie je „slabší“ ako simulácia: ak stroj M simuluje stroj M, potom stroj M je ekvivalentný stroju M; opak vo všeobecnosti neplatí. Na druhej strane, simulácia vyžaduje, aby M mal aspoň rovnaký počet pások ako M, zatiaľ čo ekvivalencia nevyžaduje 15. Práve táto vlastnosť nám umožňuje sformulovať a dokázať nasledujúcu vetu.
VETA 4. Pre každý k-páskový stroj M s časovou zložitosťou T(n) existuje ekvivalentný jednopáskový stroj M′ s časovou zložitosťou T′ (n) = O(T 2 (n)).
48. Ekvivalentné transformácie CS-gramatiky: odstránenie reťazových pravidiel, odstránenie ľubovoľného gramatického pravidla
Definícia. Druhé pravidlo gramatiky , Kde , V A , sa nazýva reťaz.
Vyhlásenie. Pre COP gramatiku Γ obsahujúcu reťazové pravidlá je možné vytvoriť ekvivalentnú gramatiku Γ", ktorá neobsahuje reťazové pravidlá.
Myšlienka dôkazu je nasledovná. Ak je gramatická schéma
R = (..., ,...,
potom je takáto gramatika ekvivalentná gramatike so schémou
R" = (..., a
od derivácie v gramatike so schémou R reťazca a
možno získať v gramatike so schémou R“ pomocou pravidla a
Vo všeobecnom prípade možno posledné tvrdenie dokázať nasledovne. Rozdelili sme R na dve podmnožiny R 1 a R 2 , vrátane všetkých pravidiel formulára v R 1
Pre každé pravidlo z R 1 nájdeme množinu pravidiel S( ), ktoré sú postavené takto:
Ak *a v R 2 existuje pravidlo α, kde α je reťazec slovníka (V t V A)*, potom v S( ) zapnite pravidlo
Zostrojíme nový obvod R" spojením pravidiel R 2 a všetkých zostrojených množín S( ). Získame gramatiku Г" = (V t, V A , I, R"), ktorá je ekvivalentná danej a neobsahuje pravidlá tvaru .
Ako príklad vykonajte odstránenie reťazových pravidiel z gramatiky D 1.9 so schémou:
R=(
Najprv rozdeľme gramatické pravidlá na dve podmnožiny:
R1 = (
R2 = (
Pre každé pravidlo z R 1 zostrojíme zodpovedajúcu podmnožinu.
S(
S(
Výsledkom je, že získame požadovanú gramatickú schému bez reťazových pravidiel vo forme:
R 2 U S(
Posledný typ uvažovaných transformácií je spojený s odstránením pravidiel s prázdnou pravou stranou z gramatiky.
Definícia. Milé pravidlo $ volali anulujúce pravidlo.
49. Ekvivalentné transformácie CS-gramatiky: odstránenie nepotrebných znakov.
Nech je daná ľubovoľná CF-gramatika G . Neterminál A táto gramatika sa nazýva produktívny , ak existuje taký koncový reťazec (vrátane prázdneho), ktorý A Þ * a neproduktívne.
Veta. Každá gramatika COP je ekvivalentná gramatike COP bez neterminálov.
Neterminál A gramatika G volal dosiahnuteľné ak existuje taká reťaz a , Čo S Þ * a . V opačnom prípade sa volá neterminál nedosiahnuteľný.
Veta. Každý CFG je ekvivalentný CFG bez nedostupných neterminálov.
Nekoncový symbol v gramatike CF sa nazýva zbytočné (alebo nadbytočné) ak je buď nedosiahnuteľné alebo neproduktívne.
Veta. Každý CFG je ekvivalentný CFG, ktorý nemá žiadne zbytočné neterminály.
Príklad. Odstráňte zbytočné symboly v gramatike
S® aC | A; A ® taxík; B ® b; C ® a.
Krok 1. Stavba súpravy dosiahnuteľné postavy: {S} ® { S, C, A}® { S, C, A, B}. Všetky neterminály sú dosiahnuteľné. Nedosiahnuteľné žiadne gramatické zmeny.
Krok 2. Stavba súpravy produktívny postavy: {C, B}® { S, C, B}. Chápeme to A - neproduktívny. Vyhadzujeme ho a s ním aj všetky pravidlá z gramatiky. Získajte
S® aC; B ® b; C ® a.
Krok 3. Stavba súpravy dosiahnuteľné symboly novej gramatiky: {S} ® { S, C}. Chápeme to B nedosiahnuteľný. Vyhadzujeme ho a s ním aj všetky pravidlá z gramatiky. Získajte
S® aC; C ® a.
Toto je konečný výsledok.
50. Ekvivalentné transformácie CF-gramatiky: eliminácia ľavostrannej rekurzie, ľavá faktorizácia
Odstraňuje sa ľavá rekurzia
Hlavným problémom pri používaní prediktívnej analýzy je nájdenie gramatiky pre vstupný jazyk, ktorý možno použiť na zostavenie analytickej tabuľky s jedinečne definovanými vstupmi. Niekedy je možné pomocou niektorých jednoduchých transformácií redukovať gramatiku non-LL(1) na ekvivalentnú gramatiku LL(1). Medzi týmito transformáciami sú najúčinnejšie ľavé faktorizácia a odstránenie ľavá rekurzia. Tu treba uviesť dve poznámky. Po prvé, nie každá gramatika sa po týchto transformáciách stane LL(1) a po druhé, po takýchto transformáciách sa výsledná gramatika môže stať menej zrozumiteľnou.
Okamžitú ľavú rekurziu, teda rekurziu formulára , možno odstrániť nasledujúcim spôsobom. Najprv zoskupíme pravidlá A:
kde žiadny z riadkov nezačína na A. Potom túto množinu pravidiel nahradíme
kde A" je nový neterminál. Rovnaké reťazce môžu byť odvodené z neterminálu A ako predtým, ale teraz neexistuje ľavá rekurzia. Tento postup okamžite odstráni všetky ľavé rekurzie, ale ľavá rekurzia zahŕňajúca dva alebo viac krokov sa neodstráni. Nižšie algoritmus 4.8 umožňuje odstrániť všetky ľavé rekurzie z gramatiky.
Ľavá faktorizácia
Hlavnou myšlienkou ľavého faktorizácie je, že keď nie je jasné, ktorá z dvoch alternatív by sa mala použiť na rozvinutie neterminálu A, mali by sa zmeniť pravidlá A tak, aby sa rozhodnutie odložilo, kým nebude dostatok informácií na správne rozhodnutie. .
Ak 
- dve A -pravidlá a vstupný reťazec začína výstupom neprázdneho reťazca z nevieme, či sa má rozšíriť o prvé pravidlo alebo o druhé. Rozhodnutie môžete oddialiť rozšírením súboru . Potom, po analýze toho, čo je odvodené, môžete rozšíriť na alebo na . Ľavé faktorizované pravidlá majú formu
51. Jazyk Turingovho stroja.
Zloženie Turingovho stroja zahŕňa neobmedzené v oboch smeroch stuha(možné Turingove stroje, ktoré majú viacero nekonečných pások) rozdelené na bunky a ovládacie zariadenie(tiež nazývaný čítacia/zapisovacia hlava (GZCH)), schopný byť v jednom z množiny stavov. Počet možných stavov riadiaceho zariadenia je konečný a presne daný.
Ovládacie zariadenie sa môže pohybovať po páske doľava a doprava, čítať a zapisovať do buniek znaky nejakej konečnej abecedy. Špeciálny prázdny symbol, ktorý vyplní všetky bunky pásky, okrem tých z nich (konečný počet), na ktorých sú zaznamenané vstupné dáta.
Riadiace zariadenie funguje podľa pravidlá prechodu, ktoré predstavujú algoritmus, realizovateľné daný Turingov stroj. Každé pravidlo prechodu dáva pokyn stroju, v závislosti od aktuálneho stavu a symbolu pozorovaného v aktuálnej bunke, napísať nový symbol do tejto bunky, prejsť do nového stavu a presunúť jednu bunku doľava alebo doprava. Niektoré stavy Turingovho stroja možno označiť ako terminál a prechod na ktorýkoľvek z nich znamená koniec práce, zastavenie algoritmu.
Turingov stroj je tzv deterministický ak každá kombinácia symbolu štátu a stuhy v tabuľke zodpovedá najviac jednému pravidlu. Ak existuje dvojica "symbol pásky - stav", pre ktorú existujú 2 alebo viac inštrukcií, takýto Turingov stroj sa nazýva nedeterministický.
Gramatika obsahujúca ľavú rekurziu nie je gramatikou LL(1). Zvážte pravidlá
A→ aa(ľavá rekurzia v A)
A→ a
Tu a znak predchodcu pre oba neterminálne varianty A. Podobne gramatika obsahujúca ľavú rekurzívnu slučku nemôže byť napríklad gramatikou LL(1).
A→ BC
B→ CD
C→ AE
Gramatiku obsahujúcu ľavú rekurzívnu slučku možno previesť na gramatiku obsahujúcu iba priamu ľavú rekurziu a ďalej zavedením ďalších neterminálov možno ľavú rekurziu úplne eliminovať (v skutočnosti je nahradená pravou rekurziou, ktorá nie je problém s ohľadom na LL(1) -vlastnosti).
Ako príklad si predstavte gramatiku s generatívnymi pravidlami
S→ aa
A→ bb
B→ CC
C→ Dd
C→ e
D→ Az
ktorý má ľavú rekurzívnu slučku zahŕňajúcu A B C D. Aby sme túto slučku nahradili priamou ľavou rekurziou, zoradíme neterminály takto: S, A, B, C, D.
Zvážte všetky pravidlá generovania formulára
Xi→ Xj γ,
Kde Xi A Xj sú neterminály a γ – reťazec koncových a neterminálnych znakov. S ohľadom na pravidlá, pre ktoré j ≥ i, nevykonáva sa žiadna akcia. Táto nerovnosť však nemôže platiť pre všetky pravidlá, ak existuje ľavá rekurzívna slučka. V poradí, ktoré sme si vybrali, máme do činenia s jediným pravidlom:
D→ Az
pretože A predchádzalo D v tomto poradí. Teraz začnime s výmenou A pomocou všetkých pravidiel, ktoré majú A na ľavej strane. V dôsledku toho dostaneme
D→ bbz
Pretože B predchádzalo D pri objednávaní sa proces opakuje, pričom platí pravidlo:
D→ ccbz
Potom sa opakuje ešte raz a dáva dve pravidlá:
D→ ecbz
D→ Ddcbz
Teraz prevedená gramatika vyzerá takto:
S→ aa
A→ bb
B→ CC
C→ Dd
C→ e
D→ Ddcbz
D→ ecbz
Všetky tieto pravidlá generovania majú požadovanú formu a ľavá rekurzívna slučka je nahradená priamou ľavou rekurziou. Aby sme eliminovali priamu ľavú rekurziu, zavádzame nový neterminálny symbol Z a zmeniť pravidlá
D→ ecbz
D→ Ddcbz
D→ ecbz
D→ ecbzZ
Z→ dcbz
Z→ dcbzZ
Všimnite si, že pred a po transformácii D vygeneruje regulárny výraz
(ecbz) (dcbz)*
Zovšeobecnením možno ukázať, že ak je neterminál A sa zobrazí na ľavej strane r+ s vytváranie pravidiel, r z ktorých využívajú priamu ľavú rekurziu a s- nie, t.j.
A→ Aα 1, A→ Aα 2,..., A→ Aα r
A→ β 1, A→ β 2,..., A→ β s
potom môžu byť tieto pravidlá nahradené nasledujúcimi:
Neformálnym dôkazom je, že pred a po premene A vygeneruje regulárny výraz ( β 1 | β 2 |... | β s) ( α 1 | α 2 |... | α r) *
Treba poznamenať, že odstránením ľavej rekurzie (alebo ľavej rekurzívnej slučky) stále nedostaneme gramatiku LL(1), pretože pre niektoré neterminály sú na ľavej strane pravidiel výsledných gramatík alternatívne pravé časti, ktoré začínajú rovnakými znakmi. Preto po odstránení ľavej rekurzie by sa malo pokračovať v transformácii gramatiky do formy LL(1).
17. Konverzia gramatík do formy LL(1). Faktorizácia.
Faktorizácia
V mnohých situáciách je možné gramatiky, ktoré nemajú funkciu LL(1), konvertovať na gramatiky LL(1) pomocou procesu faktorizácie. Zoberme si príklad takejto situácie.
P→ začať D; S koniec
D→ d, D
D→ d
S→ s; S
S→ s
V procese rozkladu nahrádzame niekoľko pravidiel pre jeden neterminál na ľavej strane, ktorého pravá strana začína rovnakým symbolom (reťazcom symbolov) jedným pravidlom, kde na pravej strane nasleduje spoločný začiatok dodatočne zavedený neterminál. Gramatika je doplnená aj o pravidlá pre doplnkový neterminál, podľa ktorých sa z nej odvodzujú rôzne „pozostatky“ pôvodnej pravej strany pravidla. Pre vyššie uvedenú gramatiku by to poskytlo nasledujúcu gramatiku LL(1):
P→ začať D; S koniec
D→ dX X)
X→ , D(podľa prvého pravidla pre D originálna gramatika pre d nasleduje, D)
X→ ε (podľa druhého pravidla pre D originálna gramatika pre d nič (prázdny reťazec)
S→ s Y(uvádzame ďalší neterminál Y)
Y→ ; S(podľa prvého pravidla pre C originálna gramatika pre s nasleduje; C)
Y→ ε (podľa druhého pravidla pre C originálna gramatika pre s nič (prázdny reťazec)
Podobne aj generovanie pravidiel
S→ aSb
S→ asc
S→ ε
možno konvertovať faktorizáciou na pravidlá
S→ aSX
S→ ε
X→ b
X→ c
a výsledná gramatika bude LL(1). Proces faktorizácie však nemožno automatizovať jeho rozšírením na všeobecný prípad. Nasledujúci príklad ukazuje, čo sa môže stať. Zvážte pravidlá
1. P→ Qx
2. P→ Ry
3. Q→ m2
4. Q→ q
5. R→ sRn
6. R→ r
Obe sady vodiacich znakov pre dve možnosti P obsahujú s, a snaží sa „vydržať s mimo zátvorky“, nahrádzame Q A R v správnych častiach pravidiel 1 a 2:
P→ sQmx
P→ sRny
P→ qx
P→ ry
Tieto pravidlá možno nahradiť nasledujúcimi:
P→ qx
P→ ry
P→ sp 1
P 1 → Qmx
P 1 → Rny
Pravidlá pre P1 podobné pôvodným pravidlám pre P a majú prekrývajúce sa sady vodiacich symbolov. Tieto pravidlá môžeme transformovať rovnakým spôsobom ako pravidlá pre P:
P 1 → sQmmx
P 1 → qmx
P 1 → sRny
P 1 → rny
Faktoring, chápeme
