Laboratorijsko delo št. 3
Razvoj leksikalnega analizatorja je precej preprost, če se uporablja teorija običajnih jezikov in končnih stanj. V okviru te teorije se razredi leksemov iste vrste obravnavajo kot formalni jeziki (jezik identifikatorjev, jezik konstant itd.), Katerih niz stavkov je opisan z ustrezno generativno slovnico. Poleg tega so ti jeziki tako preprosti, da jih ustvarja najpreprostejša slovnica - običajna slovnica.
Definicija 1. generativna slovnica G =
Jezik L (G), ki ga generira avtomatska slovnica, se imenuje avtomatski (regularni) jezik ali jezik s končnim številom stanj.
Primer 1. Razred identifikatorjev, če je identifikator zaporedje, sestavljeno iz črk in številk in je prvi znak identifikatorja lahko le črka, opisuje naslednja generativna regularna slovnica G =
N= (I, K), T = (b, c), S=(I),
P = ( 1. I::= b
Tu sta b, c posplošena končna simbola za označevanje črk oziroma številk.
Postopek generiranja identifikatorja "bbcbc" je opisan z naslednjim zaporedjem zamenjav
I => bbc => bbc => bbcK => bbcbK => bbcbc
Vendar glavna naloga LA ni ustvarjanje leksikalnih enot, temveč njihovo prepoznavanje. Matematični model procesa prepoznavanja navadnega jezika je računalniška naprava, imenovana končni stroj (FA). Izraz "končni" poudarja, da ima računalniška naprava fiksno in končno količino pomnilnika ter obdeluje zaporedje vhodnih simbolov, ki pripadajo neki končni množici. Obstajajo različne vrste KA, če je izhodna funkcija KA (rezultat dela) samo pokazatelj ali je vhodno zaporedje simbolov sprejemljivo ali ne, se tak KA imenuje končni razreševalec.
Definicija 2. Naslednjih pet se imenuje končni avtomat:
A =
Q = (q 0 , q 1 , …, q n -1 ) – abeceda stanj (končna množica simbolov);
δ: Q ×V →Q – prehodna funkcija;
q 0 Є Q – začetno stanje končnega avtomata;
F Є Q – množica končnih stanj.
Shema delovanja vesoljskega plovila.
Obstaja neskončen trak, razdeljen na celice, od katerih lahko vsaka vsebuje en simbol iz V. Na traku je zapisana veriga α Є V*. Celice levo in desno od verige so prazne. Obstaja končna krmilna naprava (FCU) z bralno glavo, ki lahko zaporedno bere znake s traku, ki se premikajo po traku od leve proti desni. V tem primeru je krmilna enota lahko v katerem koli stanju od Q. Krmilna enota vedno začne svoje delo v začetnem stanju q 0 in konča v enem od končnih stanj F. Vsakič, ko se premaknete v novo celico na trak, krmilna enota preide v novo stanje v skladu s funkcijo δ.
Prehodno funkcijo vesoljskega plovila lahko predstavimo na naslednje načine:
· Niz ekip;
· Diagram stanja;
· Prehodna miza.
Ukaz državnega stroja je zapisan takole:
(q i, a j) → q k, kjer je q i, q k Є Q; a j Є V.
Ta ukaz pomeni, da je avtomat stanja v stanju q i, prebere simbol a j s traku in preide v stanje q k.
Grafično je ukaz predstavljen kot lok grafa, ki poteka od točke q i do točke q k in je označen s simbolom a j vhodne abecede:
Grafična predstavitev celotne preslikave δ se imenuje diagram stanja končnega avtomata.
Če se vesoljsko plovilo znajde v situaciji (q i, a j), ki ni leva stran nobenega ukaza, se ustavi. Če krmilna enota prešteje vse simbole verige α, posnete na traku, in hkrati preide v končno stanje q r Є F, potem pravijo, da je veriga α dovoljena s končnim strojem.
Tabela prehodov vesoljskega plovila je sestavljena na naslednji način: stolpci matrike ustrezajo simbolom iz vhodne abecede, vrstice ustrezajo simbolom iz abecede stanja, elementi matrike pa ustrezajo stanjem, v katera preide vesoljsko plovilo za dano kombinacijo vhodnega simbola. in državni simbol.
Naj bo regularna slovnica G =
Potem je končni avtomat A =
2) Q = N U (Z), Z N in Z T, Z je končno stanje vesoljskega plovila;
5) Preslikava δ je zgrajena v obliki:
· Vsako nadomestno pravilo v slovnici G oblike A i::= a j A k je povezano z ukazom (A i, a j) → A k;
· Vsako nadomestno pravilo oblike A i::= a j je povezano z ukazom (A i, a j) → Z;
Primer 2. Konstruirajte CA za slovnico iz primera 1. Imamo A =
1) V = T = (b, c)
2) Q = N U (Z) = (I, R, Z)
3) q 0 = (S) = (I)
5) δ: a) v obliki nabora ukazov:
b) v obliki diagrama stanja
Obstajajo deterministični in nedeterministični končni avtomati. Vesoljsko plovilo se imenuje nedeterministični KA (NKA), če v njenem diagramu stanja izhaja iz enega oglišča več lokov z enakimi oznakami. Na primer, KA iz primera 2 je NKA.
Iz praktičnih razlogov je potrebno, da končni razpoznavalec sam določi trenutek, ko se konča vnosno zaporedje znakov in izda sporočilo o pravilnosti ali napaki vnosnega zaporedja. Za te namene velja, da je vhodna veriga na desni omejena s končnim markerjem ├, interpretirana stanja pa se vnesejo v diagram stanja vesoljskega plovila:
Z – "dovoli vhodno verigo";
O – »v vhodni verigi je bila zapomnila napaka«;
E – "zavrni vhodno verigo."
Stanji Z in E sta končni in vesoljsko plovilo gre vanje, ko bere končni marker ├, po obdelavi pravilne ali napačne vhodne verige. Stanje O je vmesno, vesoljsko plovilo se premakne vanj iz katerega koli veljavnega stanja vesoljskega plovila, ko je zaznana napaka v vhodni verigi in ostane tam, dokler ne prispe končni marker ├, po katerem preide v stanje E - »zavrni vhodno verigo. ”
Običajni jezik
V teoriji jezika navaden niz(ali, v navadnem jeziku) imenujemo formalni jezik, ki izpolnjuje naslednje lastnosti. Te preproste lastnosti so takšne, da je razred pravilnih množic primeren za preučevanje kot celoto, dobljeni rezultati pa so uporabni v številnih pomembnih primerih formalnih jezikov. To pomeni, da je koncept pravilne množice primer matematične strukture.
Definicija pravilne množice
Naj bo Σ končna abeceda. Redni komplet R(Σ) v abecedi Σ definirajo naslednje rekurzivne lastnosti:
| №. | Lastnina | Opis |
| 1 | Prazna množica je pravilna množica v abecedi Σ | |
| 2 | Množica, ki jo sestavlja le en prazen niz, je pravilna množica v abecedi Σ | |
| 3 | Množica, sestavljena iz katerega koli simbola abecede Σ, je pravilna množica v abecedi Σ | |
| 4 | Če sta katerikoli dve množici regularni v abecedi Σ, potem je tudi njuna unija regularna množica v abecedi Σ | |
| 5 | Če sta katerikoli dve množici regularni v abecedi Σ, potem je tudi množica, sestavljena iz vseh možnih kombinacij parov njunih elementov, regularna množica v abecedi Σ | |
| 6 | Če je katera koli množica regularna v abecedi Σ, potem je tudi množica vseh možnih kombinacij njenih elementov regularna množica v abecedi Σ | |
| Nič drugega kot naslednje ni pravilna množica v abecedi Σ |
Poglej tudi
- Gradnja razčlenjevalnika na osnovi pristopa avtomatov
Fundacija Wikimedia. 2010.
Oglejte si, kaj je "običajni jezik" v drugih slovarjih:
običajni jezik- - Telekomunikacijske teme, osnovni pojmi EN običajni jezik... Priročnik za tehnične prevajalce
- (latinsko regularius, iz regula pravilo). Pravilno, pravilno urejeno, narejeno. Redno delovanje stroja. Celo kap. Redno življenje. Korektno, spodobno, monotono življenje. Slovar tujih besed, vključenih v ruski jezik.... ... Slovar tujih besed ruskega jezika
cm … Slovar sinonimov
Starodavni pisni jezik- Jezik z dolgo pisno tradicijo, to je, da je pred več stoletji dobil pisni jezik, prilagojen strukturi danega jezika, delovanje pisne različice jezika pa ni bilo epizodično, ampak redno, z... . .. Slovar sociolingvističnih izrazov
Ta izraz ima druge pomene, glej Quechua. Quechua Samoime: Qhichwa Simi, Runa Simi Države ... Wikipedia
Okvir stavbe z mrežo stebrov ali stebrov, ki temelji na stopnici enake velikosti (Bolgarščina; Български) enoten skelet (Češčina; Čeština) pravidelný skelet (Nemščina; Deutsch) regelmäßiges Skelett (Madžarščina; Magyar) szabályos... ... Gradbeni slovar
- [FRANCOSKI PARK] park, ki ima geometrično pravilen tloris, navadno osno tloris (bolgarščina; Български) frenski park (češčina; čeština) francouzský park (nemščina; nem.) park regelmäßiger; Französischer Park …… Gradbeni slovar
Quechua Samoime: Qhichwa Simi, Runa Simi Države: Argentina, Bolivija, Kolumbija, Peru, Čile, Ekvador Regije: Andi Uradni status: Peru ... Wikipedia
Tagalog jezik- (tagal, tagala, tagalo; tagalog) eden od filipinskih jezikov. Območje začetne razširjenosti je v politično, gospodarsko in kulturno najbolj pomembni regiji Republike Filipinov - osrednjem in južnem delu otoka... ... Jezikoslovni enciklopedični slovar
knjige
- Izpeljani glagoli. Skrivnosti finske slovnice. Učbenik, Safronov V.D.. Priročnik je posvečen enemu najbolj zanimivih in nezadostno predstavljenih razdelkov finske slovnice v izobraževalni literaturi v ruskem jeziku - izpeljanim glagolom. Tvorijo se iz glagolov in iz imen...
Teorija avtomatov - to je del teorije nadzorni sistemi, ki preučuje matematične modele diskretnih pretvornikov informacij, imenovan strojnice. Z določenega vidika so takšni pretvorniki tako resnične naprave (računalniki, avtomati, živi organizmi itd.) Kot abstraktni sistemi (na primer formalni sistem, aksiomatske teorije itd.), kar omogoča uporabo teorije avtomatov v različnih znanstvenih in uporabnih raziskavah. Teorija avtomatov je najtesneje povezana z matematično logiko in teorijo algoritmov. Zlasti je rešljivost nekaterih formalnih računov dokazana s pomočjo teorije avtomatov.
Drug pomemben predmet študija v tem predmetu je formalni jezik 1 – poljuben nabor besed neke abecede. Pomen formalnih jezikov za teoretično računalništvo je posledica dejstva, da je najpreprostejši in najprimernejši podatkovni model, ki se uporablja v računalniških programih, končno zaporedje, katerega vsak element je vzet iz neke vnaprej določene končne množice. Ker je formalnih jezikov, ki se uporabljajo v aplikacijah, običajno neskončno, je potreben način za opis formalnega jezika na končen način. V tem tečaju bomo preučevali 3 klasične načine tega opisa: strojnice, regularni izrazi in generativne slovnice.
Uvod
1. Osnovni koncepti teorije formalnih jezikov
Razmislite o neprazni končni množici A, sestavljen iz znakov ( a 1 , …, a k). Bomo poklicali A abeceda , njeni simboli pa so pisma . Vsako končno zaporedje črk te abecede se imenuje v besedi (veriga oz linija ): w=a 1 a 2 …a n- beseda ( a jaz A), |w| – dolžina besede (število črk, ki sestavljajo besedo, pri čemer se vsak znak pojavi tolikokrat, kot se pojavi v w). Prek | w| b označimo število pojavitev simbola b na besedo w.
Neskončno zaporedje črk abecede A klical superbeseda , - nadbeseda neskončnega števila črk A. Prazno je beseda, ki ne vsebuje niti ene črke. Označena je z . Očitno ||=0.
- veliko besed abecede A dolžina n. Komplet vseh besed abecede A(vključno s superbesedami). A*. Ta množica je števna, ker je unija štetnega števila končnih množic 
. Množica vseh nepraznih besed v abecedi A označen z A+ . če A={a), to A*={a)* bomo označili z A*.
Katera koli podmnožica 
klical jezik
(formalni jezik
) nad abecedo A.
če x in l– besede jezika 
, potem beseda xy(rezultat pripisa besede pri na koncu besede X) je poklican veriženje
(sklopka
,
delo
) besede X in pri.
(n vzemimo enkrat X). Postavimo 
.
Pravijo, da beseda X
– podbeseda
besede pri, Če l=uxv za nekaj besed u in v. Vse podbesede besed v jeziku 
oblika mnogo podbesed
jezik L, ki je označen s Subw( L).
Primeri.
1. ba 3 =baaa,
- ta beseda ima podbesede ab,
aba,
ba in tako naprej.
2. Veliko ( a, abb) - jezik (končni) nad abecedo ( a, b}.
3. Veliko 
je jezik nad abecedo ( a,
b). Ta jezik je neskončen, vsebuje besede b,
ba,
aba,
baa,
abaa,
baaa,
aabaa,
abaaa itd.
Ker je vsak jezik niz, lahko upoštevamo operacije združevanja, presečišča in razlike jezikov, definiranih v isti abecedi. Da, jezik 
, Kje 
, imenovano dopolnilo jezika L glede abecede A. In če je vedno vključen v A*, nato jezik 
lahko vsebuje ali ne vsebuje . V slednjem primeru 
.
Pustiti 
,
. Nato se imenuje jezik veriženje
(sklopka
,
delo
) jezikov
in
. pri čemer 
,
(n krat), če n>0.
Primeri. 1. Če 
,
,to .
2. Če je L=(0, 01), potem 
.
Ponovitev
jezik L imenovan jezik 
(ta operacija se imenuje tudi Kleene zvezdica
). Jezik 
klical pozitivna ponovitev
jezik L.
Primer. če A={a,
b) In L={aa,
ab,
ba,
bb), to 
.
S pritožbo
oz v zrcalni podobi
besede w beseda se imenuje w R, v kateri so črke slov w pojdite v obratnem vrstnem redu. Na primer, če w=bac, To 
Pustiti 
. Nato jezik 
klical pritožba
jezik L.
Poimenovali bomo vsak začetek besede predpono
in vsak konec besede - pripona
. Na primer, če l=xv, To X– besedna predpona pri(oznaka – X[l), A v– besedna pripona pri(oznaka – v]l). Očitno je prazna beseda hkrati predpona in pripona katere koli besede. Vse predpone besed v jeziku 
oblika veliko predpon
tega jezika: Pref( L)
. Podobno Suf( L)
-m
nož končnic
jezik 
.
Če jezik L tak, da ni besede L ni predpona (pripona) nobene druge besede L, potem pravijo, da L ima predpono (pripona) premoženje .
Pustiti A 1 in A 2 – abecede. Če prikaz f:
izpolnjuje pogoj za vse besede 
in 
, nato preslikava f klical homomorfizem
.
Opombe. 1. Lahko se dokaže, da če f je torej homomorfizem 
.
2. Homomorfizmi niso vedno bijekcije, vendar je vsak homomorfizem edinstveno določen s svojimi pomeni enočrkovnih besed.
3. Uporaba homomorfizma v jeziku L, dobimo drug jezik f(L).
če f:
– homomorfizem, 
in 
, nato skozi f(L 1) naveden je jezik 
, in skozi 
jezik je naveden 
, in sam zaslon 
klical inverzija homomorfizma
.
Primeri. 1. Recimo, da želimo vsako pojavitev znaka 0 v nizu zamenjati z znakom A, vsak pojav 1 pa je vklopljen bb. Potem lahko definiramo homomorfizem f torej 
in 
. če 
, To 
.
2. Naj f je homomorfizem, za katerega 
in 
. Potem 
in 
.
V tem poglavju začenjamo predstavljati elemente teorije formalnih jezikov.
Ko rečemo "formalni jezik", mislimo, da se tukaj predstavljeni rezultati uporabljajo predvsem za opisovanje umetnih jezikov, ki so jih izumili ljudje za posebne namene, kot so programski jeziki. Toda med posebej izumljenimi umetnimi (formalnimi) jeziki in spontano nastajajočimi in razvijajočimi se naravnimi jeziki ni nepremostljive ovire. Izkazalo se je, da so za naravne jezike značilna kompleksna slovnična pravila, tj. so precej togo formalizirani in tudi najbolj »znanstveno razvit« programski jezik vsebuje »temne točke«, katerih nedvoumno razumevanje je problem.
Pri učenju jezikov morate upoštevati tri glavne vidike.
Prvi je sintaksa jezika . Jezik je neke vrste niz "besed", kjer je "beseda" določeno končno zaporedje "črk" - simbolov neke vnaprej določene abecede. Izraza "črka" in "beseda" je mogoče razumeti na različne načine (matematična definicija teh izrazov bo podana spodaj). Tako so »črke« dejansko lahko črke abecede nekega naravnega ali formalnega jezika, na primer ruskega jezika ali programskega jezika Pascal. Potem bodo "besede" končna zaporedja "črk": krokodil, " celo število". Takšne besede se imenujejo "leksemi". Toda "črka" je lahko "beseda" ("leksem") kot celota. Potem so "besede" stavki naravnega jezika ali programov v programskem jeziku. Če je neki niz "črke" določene, potem ne bo vsako njihovo zaporedje "beseda", tj. eleksem danega jezika, ampak le zaporedje, ki upošteva določena pravila. Beseda "krykadil" ni leksem v ruščini in beseda "iff" ni leksem v Pascalu. Stavek "ljubim te" ni pravilen stavek v ruskem jeziku, tako kot zapis "x:= =t" ni pravilno zapisan pascalov operator dodelitve. Sintaksa* jezika je sistem pravil, v skladu s katerimi je mogoče zgraditi "pravilna" zaporedja "črk". Za vsako besedo jezika je značilna določena zgradba, značilna za ta določen jezik. Nato je treba na eni strani razviti mehanizme za naštevanje oziroma generiranje besed z dano strukturo, na drugi strani pa mehanizme za preverjanje pripadnosti določene besede danemu jeziku. Najprej te mehanizme preučuje klasična teorija formalnih jezikov.
Drugi vidik - semantika jezika . Semantika** vključuje povezovanje besed jezika z določenim »pomenom«, pomenom.« Na primer, pri pisanju matematične formule moramo upoštevati določena sintaktična pravila (postavitev oklepajev, črkovanje simbolov, vrstni red simbolov itd.). ), poleg tega pa ima formula zelo jasen pomen, nekaj pomeni.
Jezik je sredstvo komunikacije in prenosa informacij. Če hočemo, da nas razumejo, moramo svoj govor ne samo skladenjsko pravilno zgraditi, pri tem pa upoštevati pravilen vrstni red črk v besedi in besed v stavku, ampak tudi skrbeti za njegov pomen, za ideje, ki jih izražamo v govoru. Matematične teorije "pomena" so se pojavile razmeroma nedavno in poleg naslednjega poglavja si bomo zelo na kratko ogledali nekatere pristope k matematičnemu opisu semantike programskih jezikov.
* Beseda "sintaksa" izvira iz starogrške besede "syn" - "skupaj" in "taxis" - "red, struktura". Tako lahko sintakso razumemo kot "sestavo".
** Iz starogrških besed "sema" - "znak, znamenje" in "semanticos" - "označuje".
Končno, tretji vidik - pragmatika jezika . Pragmatika je povezana s cilji, ki si jih zastavi domači govorec: na primer, oseba govori s cilji, ki niso povezani s sintakso, ne s semantiko jezika, v katerem govori ali piše, ampak, recimo, s sprejemanjem določen znesek denarja za svoj govor zneske denarja. Pragmatika je bolj družbeno-filozofska disciplina, ki vpliva na dejavnost posameznika pri postavljanju ciljev. Niti malo se ga ne bomo dotaknili.
V tem poglavju bomo najprej preučili osnovne koncepte matematične teorije formalnih jezikov, med katerimi je najpomembnejši koncept generativne slovnice, nato pa še ti regularne jezike. Teorija regularnih jezikov skupaj s teorijo končnih avtomatov tvori temelj celotne teorije formalnih jezikov.
Abeceda, beseda, jezik
Generativne slovnice
Kot smo že omenili, klasična teorija formalnih jezikov preučuje predvsem sintakso jezika. Predstavlja matematični model sintakse, ki opisuje mehanizme za generiranje in prepoznavanje "dobro oblikovanih" verig. V tem razdelku si bomo ogledali prvega od teh mehanizmov.
Redne slovnice, končni avtomati in regularni nizi (ter regularni izrazi, ki jih predstavljajo) so trije različni načini določanja regularnih jezikov.
Izjava
Jezik je PM, če in samo če je določen z levo-linearno (desno-linearno) slovnico. Jezik je mogoče definirati z levo-linearno (desno-linearno) slovnico, če in samo če je pravilna množica.
Jezik je PM, če in samo če ga določa končni avtomat. Državni stroj prepozna jezik, če in samo če je PM.
Vse te tri metode so enakovredne. Obstajajo algoritmi, ki omogočajo, da se za jezik, definiran na enega od teh načinov, konstruira druga metoda, ki definira isti jezik. Podroben opis teh algoritmov je na voljo v literaturi (glej seznam).
Če želite na primer najti regularni izraz za jezik, ki ga definira desnolinearna slovnica, je treba sestaviti in rešiti sistem enačb z regularnimi koeficienti.
V teoriji programskih jezikov ima najpomembnejšo vlogo enakovrednost CA in običajnih slovnic, saj se s takimi slovnicami definirajo leksikalne strukture programskih jezikov. Ko ustvarimo avtomat, ki temelji na znani slovnici, dobimo razpoznavalec za dani jezik. Na ta način je mogoče rešiti problem razčlenjevanja leksikalnih konstrukcij jezika.
Če želite zgraditi CA na podlagi znane običajne slovnice, ga je treba zmanjšati na avtomatsko obliko. Množica stanj avtomata bo ustrezala množici neterminalnih simbolov slovnice. 2.3.2 Lastnosti navadnih jezikov
Množica se imenuje zaprta glede na neko operacijo, če kot rezultat izvajanja te operacije na katerem koli od njenih elementov dobimo nov element, ki pripada isti množici.
Pravilni nizi so zaprti pod operacijami preseka, združevanja, seštevanja, ponavljanja, veriženja, spreminjanja imen simbolov in zamenjave nizov za simbole.
Za običajne jezike je mogoče rešiti veliko težav, ki so nerešljive za druge vrste jezikov. Naslednje težave so na primer rešljive ne glede na to, na kateri način je naveden jezik:
Problem enakovrednosti: dana sta dva običajna jezika L 1 (V) in L 2 (V). Ugotoviti je treba, ali sta enakovredna.
Problem verižne pripadnosti jeziku. Podan je običajni jezik L(V), niz simbolov V * . Preveriti moramo, ali ta veriga pripada jeziku.
Problem praznine jezika. Glede na običajni jezik L(V). Treba je preveriti, ali je ta jezik prazen, tj. najti vsaj eno verigo, L(V).
Včasih je treba dokazati, ali je določen jezik reden. Če je ta jezik mogoče določiti na enega od obravnavanih načinov, potem je običajen. Če pa takšne metode ni mogoče najti, ni znano, ali jezik ni pravilen ali preprosto ni bilo mogoče najti načina, da bi ga določili. Obstaja preprosta metoda za preverjanje, ali je zadevni jezik pravilen. Dokazano je, da če je za določen jezik t.i razširitvena lema, potem je pravilna. Če ta lema ni izpolnjena, jezik ni pravilen.
Lema rasti je formulirana na naslednji način. Če je dan navaden jezik in dovolj dolga veriga simbolov, ki pripadajo temu jeziku, potem lahko v njem najdemo neprazen podniz, ki se lahko ponovi kolikorkrat želimo, in vse tako dobljene verige bodo prav tako pripadale običajni jezik v vprašanju.
Formalno je lema zapisana takole. Če je podan jezik L, potem je konstanta p>0 takšna, da če sta L in p, lahko verigo zapišemo v obliki, kjer je 0 Primer. Razmislite o jeziku L=(a n b n n>0). Dokažimo, da ni pravilna, z uporabo leme o širjenju jezikov. Naj bo ta jezik pravilen, potem mora zanj veljati razširitvena lema. Vzemimo neko verigo tega jezika = a n b n in jo zapišimo v obliki. Če je a + ali b + , potem niz i ne pripada jeziku za noben i, kar je v nasprotju s pogoji leme. Če je a + b + , tudi veriga 2 ne pripada jeziku L. Dobili smo protislovje, torej jezik ni regularen.