Astăzi vom vorbi despre mitraliere, dar în niciun caz despre cele care sunt ținute în mâinile soldaților armatei ruse. Va fi vorba despre un stil atât de interesant de programare a microcontrolerelor precum programarea automată. Mai exact, acesta nu este nici măcar un stil de programare, ci un întreg concept, datorită căruia un programator de microcontrolere își poate simplifica foarte mult viața. Datorită cărora, multe sarcini prezentate programatorului sunt rezolvate mult mai ușor și mai ușor, salvându-l pe programator de dureri de cap. Apropo, programarea automatelor este adesea numită Tehnologia SWITCH.

Vreau să observ că stimulentul pentru scrierea acestei postări a fost o serie de articole despre tehnologia SWITCH Vladimir Tatarchevsky. Seria de articole se numește „Aplicarea tehnologiei SWITCH în dezvoltarea aplicațiilor software pentru microcontrolere „Deci, în acest articol, voi încerca în cea mai mare parte să dau un exemplu de cod de lucru și descrierea acestuia.

Apropo, am planificat o serie de articole despre programare, în care voi lua în considerare în detaliu tehnicile de programare pentru microcontrolere ATS, nu ratați…. Ei bine, hai să mergem!

Programul execută secvenţial comenzile stabilite de programator. Pentru cele obișnuite program de calculator este perfect normal când programul s-a finalizat și a oprit execuția acestuia, în timp ce afișează rezultatele muncii sale pe monitor.

Un program pentru un microcontroler nu poate să-și încheie pur și simplu execuția. Imaginați-vă că porniți playerul sau casetofonul. Ați apăsat butonul de pornire, ați selectat melodia dorită și vă bucurați de muzică. Totuși, când muzica a încetat să mai fluture timpanul urechii tale, jucătorul a înghețat și nu a reacționat în niciun fel la apăsarea butoanelor și cu atât mai mult la dansurile tale cu tamburin.

Ce e în neregulă cu asta? Totul este în regulă - controlerul, cel din măruntaiele playerului tău, tocmai și-a terminat de executat programul. Vedeți, se dovedește cumva stânjenitor.

Deci de aici concluzionăm că programul pentru microcontroler pur și simplu nu ar trebui să se oprească. În esență, ar trebui să fie ciclu nesfârșit- doar în acest caz jucătorul nostru ar funcționa corect. În continuare vă voi arăta care sunt construcțiile codului de program pentru microcontrolere, acestea nu sunt nici măcar construcții, ci niște stiluri de programare.

Stiluri de programare.

„Stiluri de programare” - sună ca ceva de neînțeles, dar ei bine. Ce vreau să spun prin asta Să ne imaginăm că o persoană nu a mai fost niciodată implicată în programare, adică, în general, un ibric plin.

Această persoană a citit multe cărți despre programare, a studiat toate construcțiile de bază ale limbajului.El a colectat informații bit cu bit, deoarece acum accesul la informații este nelimitat. Toate acestea sunt bine și bune, dar cum vor arăta primele sale programe? Mi se pare că nu va filozofa, ci va urma calea de la simplu la complex.

Deci aceste stiluri sunt pașii care duc de la un nivel simplu la unul mai complex, dar în același timp mai eficient.

La început, nu m-am gândit la niciuna caracteristici de proiectare programe. Tocmai am format logica programului - am desenat o diagramă și am scris codul. Din care am dat mereu peste o grebla. Dar aceasta a fost prima dată când nu m-am deranjat și am folosit stilul „simple looping”, apoi am început să folosesc întreruperi, apoi au apărut automate și am plecat...

1. Buclă simplă. În acest caz, programul circulă fără subtilități, iar acest lucru are avantajele și dezavantajele sale. În plus, doar în simplitatea abordării, nu trebuie să inventezi modele viclene, scrii așa cum crezi (săpându-ți treptat propriul mormânt).

Void main (void) (inițial_AL (); // inițializarea periferiei în timp ce (1) (Leds_BLINK (); // funcție intermitent led semnal_on (); // funcția de activare a semnalului signal_off (); // functie de oprire a semnalului l = butonul (); // variabila responsabilă cu apăsarea butoanelor comutator (l) // În funcție de valoarea variabilei, se realizează cutare sau cutare acțiune (cazul 1: (Deistvie1 (); // În locul unei funcții, poate exista operator condițional Deistvie2 (); // sau mai multe ramuri comută cazul Deistvie3 (); Deistvie4 (); Deistvie5 (); ); cazul 2: (Deistvie6 (); Deistvie7 (); Deistvie8 (); Deistvie9 (); Deistvie10 ();); ... ... ... ... ... ... ... ... )))

Punctul de operare al programului se deplasează în ordine. În acest caz, toate acțiunile, condițiile și ciclurile sunt executate secvenţial. Codul începe să încetinească, trebuie să introduceți o mulțime de condiții inutile, complicând astfel percepția.

Toate acestea încurcă foarte mult programul, făcând o încurcătură de condiții din cod. Ca urmare, nu puteți adăuga sau scădea la acest cod, el devine ca o piesă monolitică. Desigur, atunci când volumul nu este mare, codul se pretează la modificări, dar cu cât este mai departe, cu atât mai complicat.

Cu această abordare, am scris mai multe programe, nu erau mari și destul de funcționale, dar claritatea lăsa de dorit. Pentru a adăuga o condiție nouă, a trebuit să trec cu lopata prin întregul cod, pentru că totul era legat. Acest lucru a provocat o mulțime de greșeli și dureri de cap. Compilatorul a înjurat cât a putut, depanarea unui astfel de program s-a transformat în iad.

2. Buclă + întreruperi.

Puteți rezolva parțial un ciclu de frânare fără sfârșit folosind întreruperi. Întreruperile ajută la ieșirea din cercul vicios, ajută la nu rata un eveniment important, adaugă funcționalități suplimentare (întreruperi de la temporizatoare, întreruperi externe).

Să presupunem că puteți închide procesarea butoanelor la o întrerupere sau urmărirea unui eveniment important. Ca urmare, programul devine mai intuitiv, dar nu mai puțin confuz.

Din păcate, întreruperea nu vă va salva de mizeria în care se transformă programul. Nu se va putea împărți în părți ceea ce constituie un singur întreg.

3. Programare automată.

Aici ajungem la subiectul principal al acestui articol. Programarea în mașini cu stări finite elimină dezavantajele inerente primelor două exemple. Programul devine mai simplu și ușor de modificat.

Un program scris într-un stil automat este ca un comutator care comută într-o stare sau alta în funcție de condiții. Programatorul știe inițial numărul de stări.

Într-un mod grosier, este ca un întrerupător de lumină. Există două stări pornit și oprit și două condiții pornit și oprit. Ei bine, primul lucru.

Implementarea multitasking-ului în tehnologia switch-ului.

Microcontrolerul este capabil să controleze sarcina, să clipească LED-urile, să monitorizeze tastele și multe altele. Dar cum să faci toate acestea în același timp? Există multe soluții pentru a rezolva această problemă. Cel mai simplu pe care l-am menționat deja este utilizarea întreruperilor.

În timp ce programul rulează, atunci când are loc o întrerupere, controlerul este distras de la executarea codului programului și execută pentru scurt timp o altă bucată de program pentru care întreruperea este responsabilă. Întreruperea va funcționa, apoi punctul de funcționare al programului va continua din punctul din care controlerul a fost întrerupt de întrerupere (cuvântul însuși indică faptul că controlerul este întrerupt).

O altă modalitate de a implementa multitasking este utilizarea sisteme de operare... Da, într-adevăr, au început deja să apară sisteme de operare mici, care pot fi aplicate pe un controler de putere redusă. Dar adesea această metodă se dovedește a fi oarecum redundantă. La urma urmei, de ce să risipești resursele controlerului cu muncă inutilă, când este foarte posibil să te descurci cu puțin sânge.

În programele scrise folosind tehnologia switch, o „iluzie” similară a multitasking-ului se obține datorită sistemului de mesagerie. Am scris „o iluzie” pentru că este într-adevăr, deoarece un program nu poate executa fizic diferite părți ale codului în același timp. Voi vorbi puțin mai departe despre sistemul de mesagerie.

Sistem de mesagerie.

Puteți rezolva numeroase procese și puteți crea iluzia de multitasking folosind sistemul de mesagerie.

Să presupunem că avem nevoie de un program în care LED-ul este comutat. Aici avem două mașini, să le numim LEDON - mașina responsabilă cu aprinderea LED-ului și mașina LEDOFF - mașina responsabilă cu stingerea LED-ului.

Fiecare dintre mașini are două stări, adică mașina poate fi într-o stare activă sau într-o stare inactivă, deoarece comutatorul este fie pornit, fie oprit.

Când o mașină este activată, LED-ul este aprins, când cealaltă este activată, LED-ul este stins. Să ne uităm la un mic exemplu:

Int main (void) (INIT_PEREF (); // inițializarea perifericelor (LED-uri) InitGTimers (); // inițializarea temporizatoarelor InitMessages (); // inițializarea mecanismului de procesare a mesajelor InitLEDON (); // inițializarea mașinii LEDON InitLEDOFF (); // inițializarea automatului LEDOFF SendMessage (MSG_LEDON_ACTIVATE); // activarea automatului LEDON sei (); // Activarea întreruperilor // Ciclul principal al programului în timp ce (1) (ProcessLEDON (); // iterația automatului LEDON ProcessLEDOFF (); // repetarea automatului LEDOFF ProcessMessages (); // procesarea mesajelor);)

În rândurile 3-7 au loc diverse inițializări, așa că nu ne interesează în mod deosebit acest lucru acum. Dar apoi se întâmplă următoarele: înainte de a începe bucla principală (în timp ce (1)), trimitem un mesaj mașinii

Trimite mesaj (MSG_LEDON_ACTIVATE)

responsabil de aprinderea LED-ului. Fără acest mic pas, organul nostru nu va funcționa. În continuare, bucla principală fără sfârșit realizează cea mai mare parte a muncii.

Mică digresiune:

Mesajul are trei stări. Și anume, starea mesajului poate fi inactivă, setată, dar starea inactivă și activă.

Se dovedește că inițial mesajul a fost inactiv, când am trimis mesajul, a primit starea „instalat dar inactiv”. Și asta ne dă următoarele. Când programul este executat secvenţial, automatul LEDON nu primeşte mesajul. Există o iterație inactivă a automatului LEDON în care mesajul pur și simplu nu poate fi primit. Deoarece mesajul are starea „instalat dar inactiv”, programul își continuă execuția.

După ce toate automatele sunt inactive, coada vine la funcția ProcessMessages (). Această funcție este întotdeauna plasată la sfârșitul buclei, după ce toate iterațiile automatelor au fost finalizate. Funcția ProcessMessages () schimbă pur și simplu mesajul din starea „setat, dar inactiv” în starea „activ”.

Când bucla fără sfârșit completează al doilea cerc, imaginea este deja complet diferită. Iterația automatului ProcessLEDON nu va mai fi inactiv. Distribuitorul automat va putea primi mesajul, trece în starea aprinsă și, la rândul său, va trimite și mesajul. Acesta va fi adresat aparatului LEDOFF și ciclu de viață mesajele vor fi repetate.

Vreau să observ că mesajele care au starea „activă” sunt distruse atunci când întâlnesc funcția ProcessMessages. Prin urmare, un mesaj poate fi primit de un singur aparat. Mai există un tip de mesaje - acestea sunt mesaje difuzate, dar nu le voi lua în considerare, sunt bine acoperite și în articolele lui Tatarchevsky.

Cronometre

Cu organizarea corectă a mesajelor, putem controla ordinea mașinilor de stat, dar nu ne putem descurca doar cu mesaje.

Este posibil să fi observat că fragmentul de cod de exemplu anterior nu va funcționa așa cum a fost prevăzut. Aparatele vor schimba mesaje, LED-urile se vor comuta, dar nu o vom vedea. Vom vedea doar un LED slab aprins.

Acest lucru se datorează faptului că nu ne-am gândit la procesarea competentă a întârzierilor. La urma urmei, pornirea alternantă a LED-urilor nu este suficientă pentru noi, LED-ul ar trebui să fie întârziat în fiecare stare, să spunem pentru o secundă.

Algoritmul va fi după cum urmează:

Puteți face clic pentru a mări

Am uitat să adaug pe această diagramă bloc că, atunci când cronometrul este activ, desigur, se efectuează o acțiune - pornirea LED-ului sau oprirea acestuia.

1. Intrăm în stare acceptând mesajul.

2. Verificăm citirile cronometrului/contorului, dacă este punctat, atunci executăm acțiunea, altfel pur și simplu ne trimitem un mesaj.

3. Trimitem mesajul la următoarea mașină.

4. Ieșire

La următoarea intrare, totul se repetă.

Program de tehnologie SWITCH. Trei pasi.

Să scriem un program în mașinile de stat și pentru aceasta trebuie să facem doar trei pași simpli... Programul va fi simplu, dar merită să începeți cu lucruri simple. Un program cu LED de comutare este potrivit pentru noi. Acesta este un exemplu foarte bun, așa că să nu inventăm nimic nou.

Voi scrie programul în limbajul C, dar asta nu înseamnă deloc că în mașinile cu stări finite trebuie să scrieți doar în C, este foarte posibil să folosiți orice alt limbaj de programare.

Programul nostru va fi modular și, prin urmare, va fi împărțit în mai multe fișiere. Vom avea următoarele module:

• Modulul buclei principale de program conține fișierele leds_blink.c, HAL.c, HAL.h
• Modulul cronometre conține fișierele timers.c, timers.h
• Modul de procesare a mesajelor conține fișierele messages.c, messages.h
  
• Modulul mașinii 1 conține fișierele ledon.c, ledon.h
• Modulul mașinii 2 conţine fişierele ledoff.c, ledoff .h

Pasul 1.

Creăm un proiect și conectăm imediat fișierele modulelor noastre statice la acesta: timers.c, timers.h, messages.c, messages.h.

Fișierul leds_blink.c al modulului de buclă principală al programului.

#include "hal.h" #include "messages.h" // modul de procesare a mesajelor #include "timers.h" // modul timer // Timer întreruperi // ############# # ############################################### ############################ ISR (TIMER0_OVF_vect) // sare de-a lungul vectorului de întrerupere (contor timer T0 overflow) (ProcessTimers (); // Gestionar întreruperea temporizatorului) // ##################################################################### ############################################ int main (void ) (INIT_PEREF (); // inițializarea periferiei (LED-uri) InitGTimers (); // inițializarea temporizatoarelor InitMessages (); // inițializarea mecanismului de procesare a mesajelor InitLEDON (); // inițializarea mașinii LEDON InitLEDOFF () ; StartGTimer ( TIMER_SEK); // Porniți temporizatorul SendMessage (MSG_LEDON_ACTIVATE); // activează automatul FSM1 sei (); // Activează întreruperi // Bucla principală a programului în timp ce (1) (ProcessLEDON (); // repetă automatul LEDON ProcessLEDOFF (); ProcessMessages ( ); // procesează mesaje);)

În primele rânduri, modulele rămase sunt conectate la programul principal. Aici vedem că modulul cronometru și modulul de procesare a mesajelor sunt conectate. Mai departe în text programul merge vector de întrerupere de debordare.

Din linia int main (void), putem spune că începe programul principal. Și începe cu inițializarea tuturor și a tuturor. Aici inițializam perifericele, adică setăm valorile inițiale pentru porturile de intrare/ieșire ale comparatorului și restul conținutului controlerului. Toate acestea sunt realizate de funcția INIT_PEREF, aici o rulăm, deși corpul său principal se află în fișierul hal.c.

În continuare, vedem inițializarea temporizatoarelor, modulul de procesare a mesajelor și inițializarea mașinilor. Aici, aceste funcții sunt, de asemenea, ușor de rulat, deși funcțiile în sine sunt scrise în fișierele modulelor lor. Vezi cât de convenabil este. Textul principal al programului rămâne ușor de citit și nu este aglomerat cu cod redundant din care diavolul îți rupe piciorul.

Inițializările principale s-au terminat acum trebuie să începem bucla principală. Pentru a face acest lucru, trimitem un mesaj de pornire și, în plus, pornim ceasul - pornim cronometrul.

StartGTimer (TIMER_SEK); // Porniți temporizatorul SendMessage (MSG_LEDON_ACTIVATE); // activează mașina FSM1

Și bucla principală, așa cum am spus, pare foarte simplă. Notăm funcțiile tuturor mașinilor, doar le notăm într-o coloană, fără a respecta ordinea. Aceste funcții sunt manipulatoare de automate și sunt situate în modulele automate. Această piramidă automată este completată de funcția modulului de procesare a mesajelor. Desigur, am vorbit deja despre asta mai devreme când ne-am ocupat de sistemul de trimitere a mesajelor. Acum puteți vedea cum arată încă două fișiere ale modulului buclei principale de program

Hal.h este fișierul antet pentru modulul principal al buclei.

#ifndef HAL_h #define HAL_h #include #include // Bibliotecă standard inclusiv întreruperi #define LED1 0 #define LED2 1 #define LED3 2 #define LED4 3 #define Komparator ACSR // comparator #define ViklKomparator 1<

După cum probabil ați observat, acest fișier, în esența sa, nu conține o singură linie de cod executabil - toate acestea sunt substituții de macro și conexiuni de bibliotecă. Având acest fișier, pur și simplu face viața foarte bună, îmbunătățește claritatea.

Dar fișierul Hal.c este deja un fișier executabil și, așa cum am menționat deja, conține diverse inițializari ale perifericelor.

#include "hal.h" void INIT_PEREF (void) (// Inițializați porturile I/O // ########################## # ############################################### ### Komparator = ViklKomparator; // inițializarea comparatorului - dezactivarea DDRD = 1<

Ei bine, am arătat modulul buclei programului principal, acum trebuie să facem ultimul pas, trebuie să scriem modulele mașinilor în sine.

Pasul 3.

Ne rămâne să scriem modulele mașinilor de stare, în cazul nostru mașina LEDON și mașina LEDOFF. Pentru început, voi da textul programului mașinii care aprinde LED-ul, fișierul ledon.c.

// fișier ledon.c #include "ledon.h" #include "timers.h" #include "messages.h" nesemnat char ledon_state; // variabilă de stat void InitLEDON (void) (ledon_state = 0; // aici puteți inițializa alte // variabile de mașină, dacă există) void ProcessLEDON (void) (comutați (ledon_state) (cazul 0: // stare inactivă dacă (GetMessage) (MSG_LEDON_ACTIVATE)) // dacă există un mesaj, acesta va fi acceptat (// și cronometrul va fi verificat dacă (GetGTimer (TIMER_SEK) == one_sek) // dacă timer-ul a numărat 1 secundă, apoi executați (StopGTimer (TIMER_SEK) ); PORTD = 1<

Aici, în primele rânduri, ca întotdeauna, bibliotecile sunt conectate și variabilele sunt declarate. Mai mult, am trecut deja la funcțiile cu care ne-am întâlnit deja. Aceasta este funcția de inițializare a mașinii InitLEDON și funcția de gestionar al mașinii ProcessLEDON în sine.

În corpul handlerului, funcțiile din modulul temporizator și modulul de mesaje sunt deja procesate. Iar logica automatului în sine se bazează pe construcția casetei comutatorului. Și aici puteți vedea că gestionarea automatelor se poate complica și prin adăugarea mai multor comutatoare de carcasă.

Fișierul antet pentru automat va fi și mai simplu:

// fisier fsm1 #ifndef LEDON_h #define LEDON_h #include "hal.h" void InitLEDON (void); void ProcessLEDON (void); #endif

Aici includem fișierul de legătură hal.h și indicăm și prototipurile funcțiilor.

Fișierul responsabil cu stingerea LED-ului va arăta aproape la fel doar într-o reflexie speculară, așa că nu îl voi afișa aici - sunt reticent 🙂

Puteți descărca toate fișierele proiectului de pe acest link ==== >>> LEGĂTURĂ.

Iată doar trei pași și programul nostru a dobândit o formă finalizată, ceea ce înseamnă că misiunea mea de astăzi s-a încheiat și este timpul să închei. Mi se pare că informațiile date în acest articol îți vor fi foarte utile. Dar va aduce beneficii reale doar atunci când vei pune aceste cunoștințe în practică.

Apropo, am planificat o serie de proiecte interesante care vor fi deosebit de interesante, așa că asigurați-vă că abonați-vă la articole noi ... De asemenea, plănuiesc să trimit materiale suplimentare, așa că mulți se abonează deja prin pagina principală a site-ului. Vă puteți abona și aici.

Ei bine, acum chiar am de toate, așa că vă doresc mult noroc, bună dispoziție și ne revedem.

Cu n/a Vladimir Vasiliev

Teoria mașinilor cu stări finite

Teoria automatelor stă la baza teoriei construcției compilatoarelor. O mașină cu stări finite este unul dintre conceptele de bază. Un automat nu înseamnă un dispozitiv tehnic real, deși un astfel de dispozitiv poate fi construit, ci un anumit model matematic, ale cărui proprietăți și comportament pot fi simulate cu ajutorul unui program de pe un computer. Automatul finit este cel mai simplu dintre modelele teoriei automatelor și, de regulă, servește ca dispozitiv de control pentru toate celelalte tipuri de automate. O mașină cu stări finite are o serie de proprietăți:

· Mașina de stare poate rezolva o serie de probleme ușoare de compilare. Blocul lexical este aproape întotdeauna construit deasupra unei mașini de stat.

· Munca mașinii de stat este caracterizată de performanțe ridicate.

· Simularea unei mașini cu stări finite necesită o cantitate fixă ​​de memorie, ceea ce simplifică gestionarea memoriei.

· Există o serie de teoreme și algoritmi care vă permit să proiectați și să simplificați mașini cu stări finite.

Există câteva definiții excelente ale unei mașini de stat în literatură. Cu toate acestea, ceea ce au în comun este că mașina de stări simulează un dispozitiv de calcul cu o cantitate fixă ​​de memorie care citește secvențe de caractere de intrare aparținând unui set de intrare. Diferențele fundamentale în definiții sunt legate de ceea ce face automatul la ieșire. Ieșirea automatului poate fi un indiciu dacă lanțul de intrare dat este „permis” sau nu. Un șir bine format sau corect din punct de vedere sintactic se numește „valid”. De exemplu, un șir care se presupune că reprezintă o constantă numerică este considerat construit incorect dacă conține două zecimale.

Definiție: O mașină cu stări finite este un sistem formal care este definit folosind următoarele obiecte:

· Un set finit de caractere de intrare;

· Un set finit de stări;

· Funcția de tranziții, care atribuie o nouă stare fiecărei perechi (starea curentă, simbol de intrare);

· Stare initiala;

· Un subset de state, selectate ca admise sau definitive.

Exemplu. Să analizăm munca unui controler care verifică numărul par sau impar de uni dintr-un lanț arbitrar format din zerouri și unu. Să presupunem că automatul finit corespunzător trebuie să „admite” toate șirurile care conțin un număr impar de unități și să „respinge” șirurile cu un număr par de unități. Să numim acest automat „controler de paritate”. Credem că alte caractere decât 0 și 1 nu pot fi introduse la intrarea mașinii. Deci, alfabetul de intrare al controlerului este setat (0, 1). Presupunem că la un anumit moment de timp mașina cu stări finite se ocupă de un singur simbol de intrare și stochează informații despre simbolurile anterioare ale lanțului de intrare folosind un set finit de stări. Ca set de stări vom considera o mulțime (par, impar), una dintre aceste stări ar trebui să fie aleasă ca cea inițială. Fie o stare (pară), deoarece la primul pas numărul celor citite este zero, iar zero este un număr par. La citirea următorului simbol de intrare, starea automatului fie se schimbă, fie rămâne aceeași, iar noua sa stare depinde de simbolul de intrare și de starea curentă. Această schimbare de stare se numește tranziție.

Funcționarea automatului poate fi descrisă matematic printr-o funcție de tranziție de forma d (Stek., X) = Snov. În caz contrar, se poate scrie după cum urmează:

d (par, 0) = par d (par, 1) = impar.

d (impar, 0) = impar. d (impar, 1) = par

Controlerul are o singură stare de admitere de ODD, iar EVEN este starea de „respingere”. Să reflectăm secvența de tranziții ale automatului atunci când lanțul 1101 este alimentat la intrarea sa.

EVEN ® ODD ® EVEN® EVEN® ODD

Tabelul de tranziție al unui astfel de automat arată astfel:

chiar	chiar	ciudat
ciudat	ciudat	chiar

Definiție. O mașină de stat este un sistem formal

S = (A, Q, d, l, V),

ale căror obiecte sunt următoarele:

* A - un set finit de caractere de intrare (set

terminale);

* Q este un set finit de stări interne ale automatului

(multe non-terminale);

* V - un set finit de caractere de ieșire (alfabet de ieșire);

* d - funcţie de tranziţie, care se caracterizează prin A ´ Q ® Q;

* l este funcția de ieșire care determină afișarea vizualizării.

Adnotare: Această prelegere discută cele două modalități cele mai comune de a finaliza un limbaj formal: gramaticile și automatele. Considerăm automate finite care corespund gramaticilor drept-liniare în ierarhia Chomsky, definim conceptele unui automat finit, un automat finit nedeterminist și un limbaj recunoscut de un automat finit. Oferă exemple practice și exerciții pentru consolidarea materialului

Cele mai comune două moduri de a finaliza o limbă formală sunt gramaticile și automatele. În acest context, mașinile sunt numite modele matematice ale unor dispozitive de calcul. În această prelegere, luăm în considerare mașinile cu stări finite care corespund gramaticilor drept-liniare din ierarhia Chomsky. Mai puternica modele de calcul vor fi definite ulterior în cursurile „10”, „14” și „15”. Termenul „limbaj automat” este atribuit limbilor care sunt recunoscute de mașinile cu stări finite și nu de familii mai largi de automate (de exemplu, automate cu un automat de tip push-pull sau delimitat liniar).

Secțiunea 2.1 definește conceptele unui automat finit (pentru claritate, un astfel de automat poate fi numit un automat finit nedeterminist) și un limbaj recunoscut de un automat finit. Următoarea secțiune oferă o definiție diferită, dar echivalentă cu prima, a unui limbaj recunoscut de o mașină de stat. Nu este necesar pentru prezentarea ulterioară, dar tocmai această definiție se pretează la generalizare la cazurile de automate de alte tipuri.

În Secțiunea 2.3, demonstrăm că aceeași clasă de limbaje automate poate fi obținută folosind numai automate finite de o formă specială (aceștia citesc exact un simbol la fiecare ciclu de ceas și au exact o stare inițială). În multe manuale, astfel de mașini sunt numite mașini cu stări finite.

Teoremele privind corespondența exactă a anumitor clase de gramatici cu anumite clase de automate constituie o serie întreagă de rezultate clasice în teoria limbajelor formale. Prima teoremă din această serie, care afirmă că gramaticile liniare drepte generează exact limbaje automate, este demonstrată în Secțiunea 2.4.

O altă serie de rezultate este legată de posibilitatea de a restrânge o anumită clasă de gramatici fără a schimba clasa de limbi generate de acestea. De obicei, în acest caz, gramaticile din clasa mai mică sunt numite gramatici în formă normală. Secțiunea 2.5 * formulează un rezultat de acest tip pentru gramaticile drept-liniare. Această teoremă în sine este de puțin interes, dar rezultate similare, dovedite mai târziu pentru gramatici fără context, sunt folosite în multe dovezi și algoritmi.

Nu toate mașinile de stat sunt potrivite pentru construirea de dispozitive de recunoaștere potrivite pentru aplicații practice, deoarece în cazul general mașină cu stări finite nu oferă o indicație exactă a modului de a proceda la pasul următor, dar permite ca procesul de calcul să fie continuat în mai multe moduri. Mașinile cu stări finite deterministe (un caz special de mașini cu stări finite nedeterministe), definite în Secțiunea 2.6, nu au acest dezavantaj. În Secțiunea 2.7, demonstrăm că fiecare limbaj automat este definit de un automat finit determinist.

2.1. Mașini nedeterministe cu stări finite

Definiție 2.1.1. Mașină cu stări finite(automat finit, mașină cu stări finite) este un cinci, unde este un finit alfabet de intrare(sau pur și simplu alfabet) ale unui automat finit dat și sunt mulțimi finite,

,. Elementele lui Q se numesc state(stat), elementele I - iniţială stări (inițiale), elemente F - final sau admitând(final, acceptare) state. Dacă apoi sunat tranziție(tranziție) de la p la q și cuvântul x este eticheta(eticheta) acestei tranziții.

Exemplul 2.1.2... Fie Q = (1,2), , I = (1), F = (2),

Atunci - mașină de stat.

Observație 2.1.3... Mașinile cu stări finite pot fi reprezentate ca diagrame de stare(diagrama stărilor) (numit uneori diagrame de tranziție(diagrama de tranziție)). În diagramă, fiecare stare este indicată printr-un cerc, iar o tranziție este indicată printr-o săgeată. Săgeata de la p la q, etichetată cu cuvântul x, arată care este tranziția mașinii de stări date. Fiecare stare inițială este recunoscută printr-o săgeată scurtă care duce la ea. Fiecare stare de acceptare este marcată pe diagramă cu un cerc dublu.

Exemplul 2.1.4... Diagrama prezintă mașina de stări din exemplul 2.1.2.

Observație 2.1.5... Dacă automatul finit are mai multe tranziții cu un început și un sfârșit comun, atunci se numesc astfel de tranziții paralel... Uneori, tranzițiile paralele sunt descrise printr-o singură săgeată în diagrama mașinii de stări a unei mașini de stări. În acest caz, etichetele de salt sunt listate separate prin virgule.

Exemplul 2.1.6... Diagrama ilustrează din nou mașina de stări din Exemplul 2.1.2.

Definiție 2.1.7. Cale(calea) a unei mașini de stări este un tuplu, unde și pentru fiecare i. Mai mult, q 0 - începutul drumului q n - Sfarsit de drum n - lungimea drumului w 1 ... w n - marca de cale.

Observație 2.1.8... Există o cale pentru orice stat. Eticheta sa este, începutul și sfârșitul sunt același.

Definiție 2.1.9... Calea este numită de succes dacă începutul îi aparține lui I și sfârșitul îi aparține lui F.

Exemplul 2.1.10... Luați în considerare mașina de stări din Exemplul 2.1.2. Calea este reușită. Eticheta sa este baaab. Lungimea acestei căi este de 4.

Definiția 2.1.11... Cuvântul w permis(este acceptat, este recunoscut) de către mașina de stări M dacă este o etichetă a unei căi reușite.

Definiția 2.1.12... Limba, recognoscibilă mașina cu stări finite M este limbajul L (M), constând din etichetele tuturor căilor reușite (adică din toate cuvintele admise de automatul dat). Vom spune, de asemenea, că automatul M recunoaște(recunoaște, acceptă) limba L (M).

Observația 2.1.13... Dacă , apoi limba recunoscută de mașina de stat , conține.

Exemplul 2.1.14... Fie, unde Q = (1,2), , I = (1), F = (1,2),

Definiția 2.1.15... Două mașini de stat sunt echivalente dacă recunosc aceeaşi limbă.

Definiția 2.1.16... Se numește limba L automat(limbaj cu stări finite) dacă există o mașină cu stări finite care recunoaște acest limbaj.

Observația 2.1.17... De obicei, manualele folosesc o definiție mai restrânsă a unui automat finit nedeterminist, dar acest lucru nu schimbă clasa de limbaje automate (a se vedea Lema 2.3.3.).

Exemplul 2.1.18... Luați în considerare un alfabet cu o literă. Cu orice fix și limbaj este automată.

Observația 2.1.19... Fiecare limbaj finit este automat.

Definiția 2.1.20... Starea q realizabil(accesibil) din starea p dacă există o cale care începe cu p și se termină cu q.

Lema 2.1.21. Fiecare limbaj automat este recunoscut de un automat finit în care fiecare stare este accesibilă dintr-o stare inițială și din fiecare stare cel puțin o stare finală este accesibilă..

Exemplul 2.1.22... Luați în considerare o mașină cu stări finite , unde Q = (1,2,3,4), , I = (1,2,4), F = (1,3,4),

În acest articol, termenul „mașină de stări” înseamnă un algoritm care poate fi într-una dintr-un număr mic de stări. „Starea” este o anumită condiție care determină relația specificată între semnalele de intrare și de ieșire, precum și semnalele de intrare și stările ulterioare. Cititorul inteligent va observa imediat că mașinile cu stări finite descrise în acest articol sunt mașini cu stări Mealy. Un automat Mealy este o mașină cu stări finite în care ieșirile sunt funcții ale stării curente și un semnal de intrare, spre deosebire de un automat Moore, în care ieșirile sunt doar funcții de stare. În ambele cazuri, starea ulterioară este o funcție a stării curente și a semnalului de intrare.

Luați în considerare un exemplu de mașină de stare simplă. Imaginați-vă că trebuie să recunoașteți secvența de caractere „//” dintr-un șir de text. Figura 1 arată cum se face acest lucru folosind o mașină de stări. Prima apariție a unei bare oblice nu dă un semnal de ieșire, dar duce la faptul că mașina intră în a doua stare. Dacă automatul nu găsește o bară oblică în a doua stare, revine la prima, deoarece este necesar să existe 2 bare oblice la rând. Dacă se găsește a doua bară oblică, aparatul emite un semnal „gata”.

Aflați de ce are nevoie clientul.

Realizați o diagramă de tranziție a stărilor

Codați „scheletul” mașinii de stări fără a detalia operațiunile de tranziție.

Asigurați-vă că tranzițiile funcționează corect.

Restrângeți detaliile tranzițiilor.

Fa un test.

Exemplu de mașină de stat

Luați în considerare un exemplu mai interesant de mașină de stat, un program care controlează retragerea și extinderea trenului de aterizare al unei aeronave. În timp ce majoritatea aeronavelor efectuează această procedură folosind un mecanism de control electro-hidraulic (pur și simplu pentru că nu există un computer la bord), în unele cazuri, cum ar fi vehiculele aeriene fără pilot, merită să utilizați controlul software.

Mai întâi, să aruncăm o privire la echipament. Trenul de aterizare al aeronavei este format dintr-un suport frontal, un tren principal de aterizare stânga și un tren principal de aterizare dreapta. Sunt actionate hidraulic. O pompă hidraulică acționată electric furnizează presiune către servomotorul de putere. Software-ul pornește sau oprește pompa. Calculatorul ajustează poziția supapei direcționale - „jos” sau „sus” pentru a permite presiunii să ridice sau să coboare șasiul. Fiecare dintre picioarele trenului de aterizare are un întrerupător de limită: unul dintre ele se închide când șasiul este ridicat, celălalt - dacă este blocat în poziția „jos”. Pentru a determina dacă avionul este la sol, întrerupătorul de limită de pe piciorul de sprijin din față este închis atunci când greutatea avionului este pe suportul din față. Comenzile pilot constau dintr-un stick al trenului de aterizare superior/inferior și trei lumini (una pentru fiecare picior) care pot fi stinse, verzi (jos) sau roșii (tranziție).

Acum să trecem la dezvoltarea unei mașini de stat. Primul și cel mai dificil pas este înțelegerea așteptărilor reale ale clientului. Unul dintre avantajele unei mașini de stări este că forțează programatorul să se gândească la toate cazurile posibile și, ca urmare, să primească toate informațiile necesare de la client. De ce o consider cea mai dificilă etapă? Și de câte ori vi s-a oferit o descriere a unei probleme de genul acesta: nu mișcați trenul de aterizare în timp ce avionul este la sol.

Desigur, acest lucru este important, dar clientul crede că aici se termină totul. Dar restul cazurilor? Este suficient să retragi trenul de aterizare când avionul este de la sol? Ce se întâmplă dacă avionul sare într-o denivelare de pe pistă? Ce se întâmplă dacă pilotul schimbă schimbătorul de viteze în poziția sus în timpul parcării și, ca urmare, începe să decoleze? Ar trebui să se ridice șasiul în acest caz?

Unul dintre avantajele gândirii în termenii unei mașini cu stări finite este că puteți desena rapid o diagramă de tranziție a stărilor pe o placă de proiecție, chiar în fața clientului, și puteți parcurge procesul împreună cu el. Se acceptă următoarea denumire a tranziției stării: „evenimentul care a provocat tranziția” / „semnalul de ieșire ca urmare a tranziției”. Dacă am dezvoltat doar ceea ce a cerut inițial clientul („nu mișcați trenul de aterizare dacă avionul este la sol”), atunci am obține mașina prezentată în Figura 2.

Când elaborați o diagramă de tranziție de stare (sau orice alt algoritm), țineți cont de următoarele:

Calculatoarele sunt foarte rapide în comparație cu hardware-ul mecanic

Este posibil ca inginerul mecanic care explică ceea ce trebuie făcut să nu știe tot ce știi despre computere și algoritmi. Și acesta este și un punct pozitiv, altfel nu ți se cere!

Cum se va comporta programul dumneavoastră dacă se rupe o piesă mecanică sau electrică?

O mașină de stare bazată pe ceea ce își dorește cu adevărat clientul este prezentată în Figura 3. Aici dorim să împiedicăm retragerea trenului de aterizare până când trenul de aterizare este cu siguranță în aer. Pentru a face acest lucru, după deschiderea comutatorului de aterizare, mașina așteaptă câteva secunde. De asemenea, vrem să răspundem la marginea în sus a stick-ului pilotului, mai degrabă decât la nivel, ceea ce va evita problemele dacă cineva mișcă stick-ul în timp ce avionul este parcat. Retragerea sau extinderea trenului de aterizare durează câteva secunde și trebuie să fim pregătiți pentru situația în care pilotul se răzgândește în timpul acestei operațiuni și mișcă maneta în sens invers. De asemenea, rețineți că dacă avionul aterizează din nou în timp ce suntem în starea „Așteptăm decolarea”, cronometrul va reporni și trenul de aterizare se va retrage doar dacă avionul este în aer timp de 2 secunde.

Implementarea mașinii de stat

Lista 1 este implementarea mea a mașinii de stare prezentată în Figura 3. Să discutăm câteva dintre detaliile codului.

/ * lista 1 * /

typedef enumerare(GEAR_DOWN = 0, WTG_FOR_TKOFF, RAISING_GEAR, GEAR_UP, LOWERING_GEAR) State_Type;

/ * Această matrice conține pointeri către funcții care sunt apelate în anumite stări * /

gol(* state_table) () = (GearDown, WtgForTakeoff, RaisingGear, GearUp, LoweringGear);

State_Type curr_state;

InitializeLdgGearSM ();

/ * Inima mașinii este această buclă nesfârșită. Funcția corespunzătoare

Starea curentă, apelată o dată pe iterație * /

in timp ce (1) {

tabel_state ();

DecrementTimer ();

gol InitializeLdgGearSM ( gol )

curr_state = GEAR_DOWN;

/ * Opriți hardware-ul, stingeți luminile etc. * /

gol GearDown ( gol )

/ * Comutați în starea de așteptare dacă avionul

Nu la sol și a fost primită comanda de ridicare a trenului de aterizare */

dacă((pârghia de viteze == SUS) && (pârghia_de_troale_prev == JOS) && (comutator_de_squat == SUS)) (

curr_state = WTG_FOR_TKOFF;

prev_gear_lever = gear_lever;

gol RaisingGear ( gol )

dacă((nosegear_is_up == MADE) && (leftgear_is_up == MADE) && (rtgear_is_up == MADE)) (

curr_state = GEAR_UP;

/ * Dacă pilotul s-a răzgândit, treceți în starea „trejn de aterizare” * /

dacă(pârghia de viteze == JOS) (

curr_state = LOWERING_GEAR;

gol Se pregătesc ( gol )

/ * dacă pilotul a mutat maneta în poziția „jos”,

Intrăm în starea de „coborâre a șasiului” * /

dacă(pârghia de viteze == JOS) (

curr_state = LOWERING_GEAR;

gol WtgForTakeoff ( gol )

/ * Așteptați înainte de a ridica șasiul. * /

dacă(temporizator<= 0.0) {

curr_state = RAISING_GEAR;

/ * Dacă ne atingem din nou sau pilotul se răzgândește - începe totul de la capăt * /

dacă((squat_switch == DOWN) || (pârghia de viteze == DOWN)) (

curr_state = GEAR_DOWN;

/ * Nu vreau să-i ceri să comute din nou maneta

Aceasta a fost doar o săritură. * /

prev_gear_lever = DOWN;

gol Coborârea vitezei ( gol )

dacă(pârghia de viteze == SUS) (

curr_state = RAISING_GEAR;

dacă((nosegear_is_down == MADE) && (leftgear_is_down == MADE) && (rtgear_is_down == MADE)) (

curr_state = GEAR_DOWN;

În primul rând, puteți observa că funcționalitatea fiecărei stări este implementată de o funcție C separată. Desigur, ar fi posibil să se implementeze un automat utilizând o instrucțiune switch cu un caz separat pentru fiecare stare, dar acest lucru poate duce la o funcție foarte lungă (10-20 de linii de cod per stare pentru fiecare dintre 20-30 de stări). ). De asemenea, poate duce la erori dacă modificați codul în etapele finale ale testării. Poate că nu ați uitat niciodată declarația break de la sfârșitul unui caz, dar mi s-au întâmplat astfel de cazuri. Codul unui stat nu va intra niciodată în codul altuia dacă aveți o funcție separată pentru fiecare stat.

Pentru a evita utilizarea instrucțiunii switch, folosesc o matrice de pointeri pentru a stabili funcțiile și declar variabila folosită ca index de matrice de tip enum.

Pentru simplitate, hardware-ul I/O responsabil de citirea stării comutatoarelor, pornirea și oprirea pompelor etc., sunt reprezentate ca variabile simple. Se presupune că aceste variabile reprezintă „adrese magice” asociate echipamentelor prin mijloace invizibile.

Un alt lucru evident este că codul nu prea contează în acest moment. Doar trece de la o stare la alta. Acesta este un pas intermediar important și nu trebuie ignorat. Apropo, ar fi bine să adăugați instrucțiuni print între directivele de compilare condiționată (#ifdef DEBUG .. #endif) care ar tipări starea curentă și valorile semnalelor de intrare.

Cheia succesului constă în codul care declanșează tranziția de stare, adică. identifică faptul că a avut loc introducerea datelor.

Dacă codul trece corect prin toate stările, următorul pas este să scrieți „umplerea” codului, adică exact ceea ce produce semnalul de ieșire. Amintiți-vă că fiecare tranziție are o intrare (evenimentul care a declanșat-o) și o ieșire (I/O hardware, ca în exemplul nostru). Este adesea util să capturați acest lucru ca un tabel de tranziție de stare.

În tabelul de tranziție de stare, există un rând pe tranziție de stare.

Când codificați o mașină de stat, încercați să-i păstrați puterea - o potrivire puternică între cerințele clientului și cod. Este posibil să fie nevoie să ascundeți detaliile hardware într-un alt strat de funcții, de exemplu, pentru a face codul mașinii de stare cât mai aproape posibil de tabelul de tranziție de stare și diagrama de tranziție de stare. Această simetrie ajută la prevenirea erorilor și explică de ce mașinile de stat sunt o parte atât de importantă din arsenalul programatorului de sisteme încorporate. Desigur, puteți obține același efect cu casete de selectare și un număr infinit de declarații if imbricate, dar ar fi foarte dificil să urmăriți codul și să-l comparați cu dorințele clientului.

Fragmentul de cod din Lista 2 extinde funcția RaisingGear (). Rețineți că codul pentru funcția RaisingGear () tinde să oglindească cele 2 rânduri ale tabelului de tranziție pentru starea Raising Gear.

gol RaisingGear ( gol )

/ * După ce toate comutatoarele sunt activate, treceți la starea „șasiu sus” * /

dacă((nosegear_is_up == MADE) && (leftgear_is_up == MADE) && (rtgear_is_up == MADE)) (

pump_motor = OPRIT;

gear_lights = STINGERE;

curr_state = GEAR_UP;

/ * Dacă pilotul se răzgândește, începe să retragi trenul de aterizare * /

dacă(pârghia de viteze == JOS) (

direcția_pompei = JOS;

curr_state = GEAR_LOWERING;

Amintiți-vă să evitați stările latente. Starea latentă apare atunci când, din lene, încerci să adaugi o substare condiționată în loc să adaugi o anumită stare. De exemplu, dacă codul dumneavoastră gestionează același semnal de intrare în moduri diferite (adică inițiază tranziții diferite de stare) în funcție de mod, atunci este o stare ascunsă. În acest caz, m-aș întreba, nu ar trebui să fie împărțită această stare în două? Utilizarea stărilor ascunse anulează toate beneficiile utilizării unei mașini de stări.

Ca antrenament, puteți extinde mașina de stare la care tocmai ne-am uitat adăugând un timeout la ciclul de retragere sau extensie a șasiului, deoarece un inginer mecanic nu vrea ca o pompă hidraulică să funcționeze mai mult de 60 de secunde. Dacă ciclul se termină, pilotul ar trebui să fie alertat prin rotirea luminilor verzi și roșii și ar trebui să poată mișca din nou maneta pentru a încerca din nou. De asemenea, puteți întreba un ipotetic inginer mecanic cum este afectată pompa de inversarea direcției în timp ce funcționează, deoarece acest lucru se întâmplă de 2 ori când pilotul se răzgândește. Desigur, mecanicul va spune negativ. Atunci cum ați schimba mașina de stare pentru a opri rapid pompa atunci când schimbați direcția?

Testarea mașinii de stat

Frumusețea algoritmilor de codare ca mașini cu stări finite este că planul de testare este scris aproape automat de la sine. Tot ce trebuie să faci este să treci prin fiecare tranziție de stat. De obicei fac acest lucru cu un marker în mână, tăind săgețile de pe diagrama de tranziție a stărilor pe măsură ce trec testul. Aceasta este o modalitate bună de a evita „stările latente” - acestea sunt trecute cu vederea mai des în teste decât stări specifice.

Acest lucru necesită multă răbdare și multă cafea, deoarece chiar și o mașină de stat de dimensiuni medii poate avea până la 100 de tranziții diferite. Apropo, numărul de hop este o modalitate excelentă de a măsura complexitatea unui sistem. Acesta din urmă este determinat de cerințele clientului, iar mașina de stat face evidentă domeniul testării. Cu o abordare mai puțin organizată, cantitatea de testare necesară poate fi la fel de impresionantă, dar pur și simplu nu vei ști.

Este foarte convenabil să utilizați instrucțiuni de tipărire în cod care afișează starea curentă, valorile semnalelor de intrare și de ieșire. Acest lucru vă permite să observați cu ușurință ceea ce exprimă „Regula de aur a testării software-ului”: asigurați-vă că programul face ceea ce este intenționat să facă și că nu face nimic de prisos. Cu alte cuvinte, obțineți doar rezultatele pe care le așteptați și ce se mai întâmplă în afară de asta? Există vreo tranziție de stare „dificilă”, de ex. state care trec accidental, pentru o singură iterație a buclei? Semnalele de ieșire se schimbă atunci când nu vă așteptați? În mod ideal, rezultatul printfs-ului dvs. ar trebui să semene vizibil cu un tabel de tranziție a stărilor.

În cele din urmă - și acest lucru se aplică oricărui firmware, nu doar software-ului bazat pe mașini de stat - fiți foarte atenți la prima dată când rulați software-ul pe hardware real. Este foarte ușor să greșești cu polaritatea semnalelor - „Oh, am crezut că” 1 „a menit să ridice șasiul și” 0 „a menit să-l coboare”. În multe ocazii, asistentul meu de echipament a folosit un „comutator de pui” temporar pentru a proteja componentele valoroase până când a fost sigur că software-ul meu mișca elementele în direcția corectă.

Alergare

Când toate cerințele clientului sunt îndeplinite, pot rula o mașină de stat de această complexitate în câteva zile. Automatele fac aproape întotdeauna ce vreau eu. Cel mai dificil este, desigur, să înțelegi exact ce își dorește clientul și să te asiguri că clientul însuși știe ce vrea. Acesta din urmă durează considerabil mai mult!

Martin Gomez este programator la Laboratorul de Fizică Aplicată de la Universitatea Johns Hopkins. El este implicat în dezvoltarea de software pentru sprijinirea zborului navelor spațiale de cercetare. A lucrat în dezvoltarea sistemelor încorporate timp de 17 ani. Martin deține o licență în Inginerie Aerospațială și un MS în Inginerie Electrică de la Universitatea Cornell.

Articolul discută mașinile de stare simple și implementarea lor în C ++ folosind constructe de comutare, tabele de rulare și biblioteca Boost Statechart.

Introducere

În linii mari, o mașină cu stări finite, prin ochii unui utilizator, este o cutie neagră în care poți transfera ceva și poți primi ceva de acolo. Aceasta este o abstractizare foarte convenabilă pentru a ascunde algoritmi complecși, iar mașinile de stare sunt foarte eficiente.

Mașinile cu stări finite sunt descrise sub formă de diagrame constând din stări și tranziții. Să explic cu un exemplu simplu:

După cum probabil ați ghicit, aceasta este o diagramă de stare a unui bec. Starea inițială este indicată printr-un cerc negru, tranzițiile prin săgeți, unele săgeți sunt etichetate - acestea sunt evenimente după care automatul trece la o altă stare. Deci, imediat din starea inițială, intrăm în stare Lumina stinsa- lampa este stinsă. Dacă apăsați butonul, aparatul își va schimba starea și va urma săgeata marcată Apasa butonul, în statul Lumina pe- becul este aprins. Puteți trece din nou din această stare de-a lungul săgeții, după apăsarea butonului, la starea Lumina stinsa.

Tabelele de navigare sunt, de asemenea, utilizate pe scară largă:

Aplicarea practică a mașinilor

Mașinile cu stări finite sunt utilizate pe scară largă în programare. De exemplu, este foarte convenabil să ne imaginăm funcționarea unui dispozitiv sub forma unui automat. Acest lucru va face codul mai simplu și mai ușor de experimentat și întreținut.

Mașinile de stări sunt, de asemenea, folosite pentru a scrie tot felul de analizoare și analizoare de text, pot fi folosite pentru a căuta eficient subșiruri, expresiile regulate sunt, de asemenea, traduse într-o mașină de stări.

De exemplu, vom implementa un automat pentru numărarea numerelor și a cuvintelor dintr-un text. Pentru început, să fim de acord că un număr va fi o succesiune de cifre de la 0 la 9 de lungime arbitrară, înconjurată de caractere cu spații albe (spațiu, tabulare, avans de linie). Un cuvânt va fi considerat o secvență de lungime arbitrară constând din litere și, de asemenea, înconjurat de caractere cu spații albe.

Luați în considerare diagrama:

Din starea inițială, ajungem la stare start... Verificăm simbolul curent, iar dacă este o literă, atunci mergem la stat Cuvânt de-a lungul săgeții marcate ca Scrisoare... Această stare presupune că, în momentul în care luăm în considerare un cuvânt, analiza simbolurilor ulterioare fie va confirma această presupunere, fie o va infirma. Deci, luați în considerare următorul simbol, dacă este o literă, atunci starea nu se schimbă (rețineți săgeata circulară marcată ca Scrisoare). Dacă caracterul nu este o literă, ci corespunde unui caracter de spațiu, atunci aceasta înseamnă că presupunerea a fost corectă și am găsit cuvântul (ne deplasăm de-a lungul săgeții Spaţiu intr-o stare start). Dacă caracterul nu este o literă sau un spațiu, atunci am făcut o greșeală în ipoteză și secvența pe care o luăm în considerare nu este un cuvânt (mergi de-a lungul săgeții Necunoscut intr-o stare Ocolire).

Capabil de Ocolire stăm până când se întâlnește un caracter alb. După ce spațiul a fost detectat, urmăm săgeata Spaţiu intr-o stare start... Acest lucru este necesar pentru a sări peste o linie care nu se potrivește cu modelul nostru de căutare.

După intrarea în stat start, ciclul de căutare se repetă de la început. Ramura de recunoaștere a numerelor este similară cu ramura de recunoaștere a cuvântului.

Automatizează folosind instrucțiuni switch

Prima este stările posibile:

După aceea, repetăm ​​șirul, introducând caracterul curent în mașină. Automatul în sine este o instrucțiune de comutare care efectuează mai întâi o tranziție la secțiunea stării curente. În interiorul secțiunii există o construcție if-else, care, în funcție de eveniment (simbol de intrare), schimbă starea curentă:

const size_t length = text.length (); pentru (size_t i = 0; i! = length; ++ i) (const char current = text [i]; switch (state) (case State_Start: if (std :: isdigit (current)) (state = State_Number;) else if (std :: isalpha (curent)) (state = State_Word;) break; case State_Number: if (std :: isspace (current)) (

Aici ne uităm la diagramă - starea curentă Număr, eveniment Spaţiu(a fost întâlnit un spațiu alb), ceea ce înseamnă că a fost găsit un număr:

FoundNumber (); stare = State_Start; ) else if (! std :: isdigit (current)) (state = State_Skip;) break; case State_Word: if (std :: isspace (current)) (FoundWord (); state = State_Start;) else if (! std :: isalpha (current)) (state = State_Skip;) break; caz State_Skip: if (std :: isspace (current)) (state = State_Start;) break; ))

Rezultat:

Eficiență ridicată

Ușurință de implementare pentru algoritmi simpli

- E greu de întreținut

Interpretarea timpului de execuție

Ideea acestei abordări este simplă - trebuie să creați un tabel de tranziție, să îl completați și apoi, atunci când are loc un eveniment, să găsiți următoarea stare în tabel și să faceți o tranziție:

Enum Evenimente (Event_Space, Event_Digit, Event_Letter, Event_Unknown); void ProcessEvent (eveniment Evenimente); ... struct Tranziție (State BaseState_; Evenimente Event_; State TargetState_;); void AddTransition (State din stat, eveniment Evenimente, State la stat); ... typedef std :: vector< transition>TransitionTable; TransitionTable Transitions_; State CurrentState_;

Popularea tabelului:

AddTransition (Stare_Start, Event_Digit, State_Number); AddTransition (Start_Start, Event_Letter, State_Word); AddTransition (Număr_de stat, Spațiu_Eveniment, Stare_Start); AddTransition (Număr_de stat, Scrisoare_Eveniment, Omitere_stat); AddTransition (Număr_de stat, Eveniment_Necunoscut, Stat_Omite); AddTransition (State_Word, Event_Space, State_Start); AddTransition (State_Word, Event_Digit, State_Skip); AddTransition (State_Word, Event_Unknown, State_Skip); AddTransition (State_Skip, Event_Space, State_Start);

A ieșit destul de clar. Prețul pentru claritate va fi funcționarea mai lentă a mașinii, care, totuși, adesea nu contează.

Pentru ca automatul, la apariția unor evenimente, să poată notifica un cod, puteți adăuga la structură informații despre tranziție ( Tranziție) indicatorul funcției ( Acțiune), care se va numi:

typedef void (DynamicMachine :: * Action) (); struct Tranziție (State BaseState_; Events Event_; States TargetState_; Action Action_;); ... void AddTransition (State din stat, eveniment Evenimente, State la stat, acțiune de acțiune); ... AddTransition (Număr_de stat, Spațiu_Eveniment, Stare_Start și DynamicMachine :: FoundNumber);

Rezultat:

Flexibilitate si vizibilitate

Mai usor de intretinut

- Performanță mai scăzută în comparație cu blocurile comutatoare

Interpretarea timpului de rulare. Optimizat pentru viteza

Puteți combina vizibilitatea cu viteza? Este puțin probabil ca un automat să fie la fel de eficient ca un automat pe blocurile de comutatoare, dar este posibil să se închidă decalajul. Pentru a face acest lucru, trebuie să construiți o matrice din tabel, astfel încât, pentru a obține informații despre tranziție, nu efectuați o căutare, ci faceți o selecție după starea și numărul evenimentului:

Rezultatul este atins datorită consumului de memorie.

Rezultat:

Flexibilitate, vizibilitate

Efectiv

- Consum de memorie (cel mai probabil nesemnificativ)

Boost Statechart

Am discutat mai multe moduri de a implementa singur o mașină de stat. Pentru o schimbare, îmi propun să luăm în considerare o bibliotecă pentru construirea de automate de la Boost. Această bibliotecă este foarte puternică, capabilitățile oferite vă permit să construiți mașini cu stări finite foarte complexe. O să aruncăm o privire rapidă.

Deci, mai întâi, să definim evenimentele:

namespace Evenimente (struct Digit: boost :: statechart :: event< Digit>(); struct Letter: boost :: statechart :: eveniment< Letter>(); struct Space: boost :: statechart :: eveniment< Space>(); struct Necunoscut: boost :: statechart :: eveniment< Unknown> { } ; }

Mașina în sine (rețineți că al doilea parametru al șablonului este starea inițială):

struct Machine: boost :: statechart :: state_machine< Machine, States:: Start > { } ;

Și statele înseși. În interiorul stărilor, este necesar să se definească un tip care să descrie tranzițiile ( reactii), iar dacă există mai multe tranziții, atunci enumerați-le în lista de tipuri boost :: mpl :: list. Al doilea parametru de șablon stare_simplu- tipul care descrie mașina. Tranzițiile sunt descrise de parametrii șablonului de tranziție, câteva Eveniment - Următorul stat:

Namespace State (struct Start: boost :: statechart :: simple_state< Start, Machine> < boost:: statechart :: transition < Events:: Digit , States:: Number >< Events:: Letter , States:: Word >> reactii; ); struct Number: boost :: statechart :: simple_state< Number, Machine>(typedef boost :: mpl :: listă< boost:: statechart :: transition < Events:: Space , States:: Start >, boost :: statechart :: tranziție< Events:: Letter , States:: Skip >, boost :: statechart :: tranziție< Events:: Unknown , States:: Skip >> reactii; ); struct Cuvânt: boost :: statechart :: simple_state< Word, Machine>(typedef boost :: mpl :: listă< boost:: statechart :: transition < Events:: Space , States:: Start >, boost :: statechart :: tranziție< Events:: Digit , States:: Skip >, boost :: statechart :: tranziție< Events:: Unknown , States:: Skip >> reactii; ); struct Skip: boost :: statechart :: simple_state< Skip, Machine>(typedef boost :: statechart :: transition< Events:: Space , States:: Start >reacții; ); )

Mașina este construită, rămâne doar să o inițializați și puteți utiliza:

Mașină mașină; mașină.inițiat (); ... mașină .process_event (Evenimente :: Space ());

Rezultat:

Flexibilitate, extensibilitate

- Eficienta

Performanţă

Am scris un program de testare pentru a testa performanța automatelor construite. Prin mașini, am rulat textul cu o dimensiune de ~ 17 MB. Iată rezultatele cursei:

Se încarcă text Lungimea textului: 17605548 octeți 0,19 s Rularea BoostMachine Cuvinte: 998002, numere: 6816 0,73 s Rularea DynamicMachine Cuvinte: 998002, numere: 6816 0,56 s Rularea FastDynamic Words: 802, 69002, 698002, 698002, 6816 s 6816 0,20 s

Ceea ce este lăsat neconsiderat

Încă câteva implementări ale mașinilor cu stări finite au rămas neacoperite (recomand http://www.rsdn.ru/article/alg/Static_Finite_State_Machine.xml și http://www.rsdn.ru/article/alg/FiniteStateMachine.xml), generatoare care construiesc automate din descrieri, biblioteca Meta State Machine din Boost versiunea 1.44.0, precum și descrieri formale ale mașinilor de stat. Cititorul curios se poate familiariza cu toate cele de mai sus.