Excerpt
- 97 - turi atlikti, Pereisime prie gramatikos. Teš kalba yra baigtinė, tešo Ėslnai priklauso tik baigtinis žodžių kiekis, tai pa- | kanka išvardinti tuos žodžius. Tada gramatika trivialiai Ru- stato, kurie žodžiai priklauso kalbai, o kubie - ne. Būtent, …
Excerpt
Sr ga < Simbolis (identirikatosius? pažymi visus identi- fikatorius - raidžių ir skaitmenų sekas, praaidedasnčias rai- de. Identifikatoriams pažymėti galima buvo pasirinkti kitą simbolį, pavyzdžiui, I, kuris neįeina į alfabetą Va Tačiau mes naudosime …
Excerpt
ggs i kur Vai V, Va 62 V. 4 tiesioginio išvedimo savybė iš. Vuaš žymima |. R Ni Išvada. Jai Šikai r I Ks, R, tai "+ išveda- mas iš X. 4 arai Taikome A kai W ir V tušti žodžiai. ; e STD išvedamas iš (EL egzisuoja seka Ų= Yo RS an 2 Vi Gai 2, ki Išvedimo …
Excerpt
E 100 S tuojs jo išvedimas. Iš visų gramatikos elementų (o jų yra keturi) sunkiausia yra apibrėžti elementą R, +.y. gramatines taisykles. 2. Gramatikų pavyzdžiai ia Vas fa». Trys ž Alfabetai Vr ir V„ turi būti netušti. Minimalus alfa- betas Vr - yra …
Excerpt
- 101 — Pa js — AS, 8 —> A, A a A —> 82 200404 +404 Na ; Taisyklių kiekis n į A. Ši gramatika irgi apibrėžia uni- versalią kalbą, tik taisyklių kiekis lygus n 4 2. Pirmame pa- vyzdyje taisyklių kiekis. lygus 2n. Paimkime žodį a3252123 s Žas Sp ms Ip ais …
Excerpt
- 102 - B -=—* bb, S A, B —9). Pirmosios 2 taisyklės Eeneruoja reikiamą simbolių kirkį, paskutinės 4 < užbaigia tą generavimo procesą. sbbbba 6 Lj, nes S =5 abbbba, 5 AS aSa i abSba > abbbba.“ Tuo tarpu abbb € Li, nes iš 5 negalima lšvesti abbb, 4. Kalba …
Excerpt
103 — apibrėžimas. Į 1-os taisyklės dešini4ją pusę vžl įeina apibrė-| žiamoji sąvoka A. Tokie apibrėžimai yra vadinami rekursyviniais apibrėžin imais (rekursyvinėmis taisyklėmis). Rekursyviniai sąvo- "kų apibrėžimai jau bus 1- 3 pavyzdžiuose. '" …
Excerpt
10 , < natūrinis skaičius > —> (natūrinis skaičius > > , € sveikas skačius» > + < natūrinis skaičius), < Sveikas škaičius> — — 4, 2 Aa, A—> 0$ Paimkime žodį ab. Rasimę jo išvedirą. 2 s. Žž as 2, as 5 Aa '€ a) Gali buti ir kitas išvedimas. ės 50 isl m 3 …
Excerpt
BTOB < Išvedimai (1) ir (2) turi tą patį išvedimo medį (3). Medis (3) atspindi žodžio ab struktūrą. Jei Madia vienas, B “galime vienareikšmiškai nustatyti žodžio struktūrą. Išvedimo medį zelime Susieti su Isiekvienu Žodžiu, pri- klausančiu kalbai. at …
Excerpt
- 106 - P-= įs —a86 ; s 280, 8£> 2; B> —> b Į Paimkime žodį ab, š . Išvedimai; B Ly a8 Arap 8-5 82, ap Atitinkamį medžiai: BE ui Isila : Medžiai skiriasi tuo, jog atitinkamai 2 ir 3 elementai skirtingi, Jie lygūs atitinkamai aS,b ir Sb,a. Paprastai …
Excerpt
aOo7 = Terminaliniai simboliai vadinami pagrindiniais simbo- liais, neterminaliniai - metakintamaisisis, gramatinės tai- syklės - metalingvistinėmis formulėmis (Bekuso metalingvis- tinėmis formulėmis). Gramatinėse taisyklėse "ženklas o, pakeistas ženklu …
Excerpt
- 108 - :1> 4syeikas skaičius be žęnkl0? | + | ž -(aveikas skaičius be ženklo> < sveikas skaičius be ženklo?:;=4 skaitmuo? | 4 sveikas skai- čius be ženklo> £ skaitmuo 7? Daugelio sąvokų apibrėžimams naudojamos rekursyvinės taisyklės, Tai yra todėl, kad …
Excerpt
109 pagrindinių simbolių seka, kurioje nėra „simbolio “ arba ?> < pagrindinis : simbolis, išskyrus simbolius S < tuščia> ::= š Čia simbolis " tn yra atidaraiti kabutė, o simbolis “2 — uždaranti kabutė. Vienareikšmiškumas pažeidžiamas naudojant taisyklę £ …
Excerpt
- 116 - ; € eilutė? “5 "až | 4 E Ak Į 4 N B E“. E "+ : t I PB a B / N 454 a P P P ų ži 1 b a b Vadinasi, eilutės struktūra gali būti nustatyta nevis- nareikšmiškai, Bendru atveju tai yra negalima, res nuo prog- ramos (arba jos dalies) struktūros priklauso …
Excerpt
- 111 = X— ž5 Bukonatžuosis kaišyae V Piy SD prijungsime prie gramatikos gramatiką „ Gramatikos „ ir J, buš ekvivalenčios £ "taisyklių. Gausime Raują (reiškia mūsų gramatikos 4 transformacija yra ekvivalenti). LO Saras „ Norint įrodyti dviejų gramatikų …
Excerpt
a kuriamę nors išvedimo žingsnyje. Tegul tai bus Pi AE Šį ži žingsaį pakeisimei Asp hy K > Ap šs Gauaime išvedimą, kuris yra išvedimas gramatikoje A a 2. Išorinės taisyklės pašalinimas. Turine taisykles; ; Ip y Xų - išorinė taisyklė; Xx-— Tą 3 PE - …
Excerpt
=.113-> R J k Šį fragmentą pakeisime fragmentu Po visų tokio tipo fragmentų pakeitimo gausime « Ašvedi- ' mo Aedį naujoje gramatikoje. Iaujoje gronetikoje e baik pri tuoja et išvėdimas 2. Tegul SL išvedama naujoje gėidatlisjos "Bsaut || reikalui, …
Excerpt
- Mk - Gausims ekvivalenčių granetiką. 4, Zaigyklių dekompezicija. Tegul turime taisykles; Ši, > „f 2. k £ 4099,00990> 940064414:44 000444 04644 74 44Ą096006400664444046444444 44444 ik, os Yk šas ins pakeisti taisyklėmig; — 4 = 2 V XV I Žs Sakykime turimę …
Excerpt
5 4 —2b keičiamos į. B —> 68, 4 8 —> 68, o taisyklėš : „B254 058 AŠ> 06 keišiamos į B > a 5 —b. Ekvivalenčios gramgtikų transformacijos naudojamos tuo atveju, kei norima suvesti gramatiką į tan tikrą pavį- čalą. Mūsų pavyzdyje buvo gauta grametiks, kuri …
Excerpt
E V. ALGORITMINĖ KAIBA L I 8 P Algoritminė kalba LISP naudojama simbolinės informaci- jos apdorojimui. Tipiški uždavinisi, kurie gali bžti išspręs- ti, naudojant LISP'0 kalbą, - tai formulių transformacija, teksto apdorojimas, mąstymo procesų …
Excerpt
- 117 - Pavyzdžiai. (4.11 B) i (au (BL 0) LD) Pirmajame pavyzdyje sąrašas susideda iš dviejų elementų - atomų A ir B, antrajame - iš trijų elementų - atonio 4, dąrašė (Bi; C) ir atomo D. Tarpas tarp sąrašo elementų būtinas tik tada, kai abu gratimi …
Excerpt
- 218 — Galimas :oks sąrašo pavyzdys < ( 23 Tai sąrašas, susidedz:ntis iš vieno elenrnto, kuris yra tuščias sąrašas. 2. Bazinės funkcijos LiSP'0 kalboje yra 5 bazinės funkcijos, taikomos Lk šamg. 1. car [x] Funkcijos argumentes parašyta: kvadrstiniuose …
Excerpt
- 119 = cdr [1] = 7 aax I6C 22 0) Galimos šių funkcijų kombinacijos: car [car [a 8)]] = car [65] = B car [car [car [a B c)111 =.C ; Funkcijomis car ir cd2 galima išskinti bet kurį * sąrašo elementą. Jų kombinacijoms pažymėti įvesti sutrumpinį- mai. …
Excerpt
- 120 - car [eons [x 3 7]] = cons [car[3]; cd-[7]] zyz. Apibrėšime du specialaus pavidalo atomus - T ir F. Tai dvi loginės Baiškiūtos - tiesa ir netiesa, Funkcijos, ku- “ rių reikšmės zra T arba FP, vadinamos loginėnis fžunkcijomis arba predikatais. 4. …
Excerpt
- 121 - 3. Sąlyginės išraiškos Sąlyginės išraiškos LISP'o kalboje turi pavidalą [m - 815 Po —> 62 +++š Bn—? “I , kur Pi - predikatai, £ S bazinė arba programinė (-iūr.žemiau) funkcija, vėl sąlyginė išraiška arba atomas. Sąlyginės iš- raiškos rcikšmė …
Excerpt
- 122 — 4. Programinės funkcijos 5 bazinių funkcijų ir sąlyginių išraiškų nepakanka sp- rašyti sudėtingiems apdorojimo algoritmams. Todėl kalbojs ga- lims įvesti (apibrėžti) naujas funkcijas, kurias pavadinsime programinėmis funkcijomis. Programinės …
Excerpt
- 123 - tripis[a ; (86) ; (0)] = CA B 6) G)). 3. Tolimesniuoše pavyzdžiuose naudosime funkciją null, kuri E ar argumentas yra tuščias sąrašas. nuli [x] = ca [x į NIL]. 5. Rekursyvinės funkcijos Funkcija vadinama rekursyvine, jei jos apibrėžimo iš- …
Excerpt
ABA rezultatas turi būti F (elemento x sąrašas y neturi). Prie- šingu atveju tikriname, ar x nesutanps su 1-ju y elementu. Jei taip, tai rezultatas T, Jei ne, — rėiria patikrinti, ar nėra elemento x likusioje (be 1-jo elemento) 7 dalyje. Tam tikslui …
Excerpt
“125 3. Bazinė funkcija - predikatas 64 apibrėžta tik tada, ksi ben vienss iš srgimientų yra stomas. 45i0=ė8ize funkciją ais kuri „GLA bet kokius sąrašus. egua1|x į 7| = Li — cafx 5 315 aton[y] —> P; ' egual [car[x] 3 caz[z.lJ > geg [+]; i vel) 1— PĮ …