momente şi schiţe de informatică şi matematică
To attain knowledge, write. To attain wisdom, rewrite.

Notaţia prefix canonică şi reprezentarea DOT a expresiei

C++ | C++11
2014 jun

Urmărim (folosind şi C++11) scopuri practice - cum obţinem reprezentarea prefixată (complet parantezată), împreună cu descrierea DOT a arborelui sintactic pentru expresii algebrice date în formatul obişnuit, infixat; nu vizăm "analiza sintactică" în sine, ca tehnică sau metodologie - ci doar la nivel de algoritm, modelând direct (la nivel de caracter, cu neajunsurile specifice) metoda "precedence climbing".

Algoritm pentru descrierea DOT a arborelui sintactic al unei expresii

C++ | DOT
2014 jun

Ne bazăm pe formatul prefixat canonic (impus de predicatul write_canonical din Prolog); de exemplu, expresia 2+3*4+5 are formatul +(+(2,*(3,4)),5) (separând cu ',' subarborele stâng de cel drept şi parantezând subarborii).

Numerotăm operatorii şi operanzii, imitând metoda clasică de reprezentare pe un tablou a unui arbore binar (fiii nodului N sunt 2N şi 2N+1, N≥1). Pentru nodul curent N creem înregistrarea DOT N[label="op"] unde op este operatorul/operandul respectiv. Când citim '(' - dublăm N-ul curent (urmează fiul stâng), iar când citim ',' - incrementăm N-ul curent (urmează fiul drept); în ambele cazuri, creem înregistrarea DOT a muchiei: N/2 -- N. Când întâlnim ')' - înjumătăţim N-ul curent (regăsind N-ul părintelui, de la care va urma eventual o nouă ramură).

Arbori aritmetici şi expresii uzuale

C++ | C++11
2014 may

Rezultatul - afişarea în anumite formate, a unei expresii - este banal (cum şi anticipasem) şi se putea obţine şi direct (fără clasele ArTree şi Climb de aici - instrumentând în schimb un algoritm "shunting yard"); dar nu rezultatul ca atare ne-a interesat, ci procedeul de analiză bazat pe proprietăţile operatorilor ("precedence climbing" - metodă ingenioasă, compactă şi eficientă de analiză sintactică) - împreună desigur, cu modelarea în C++ plecând de la modelul de arbori aritmetici ArTree.

Limbajul expresiilor aritmetice

FORTRAN | Prolog
2014 may

De prin clasa a V-a, se tot deprind mecanisme de analiză sintactică şi morfologică a unui text (la "Limba română" şi la orele de "limbi străine"); iar aceste mecanisme servesc şi cazului mai simplu, al expresiilor algebrice (tot "texte", având asociate anumite "înţelesuri").

Propoziţiile corecte sunt constituite din anumite "părţi de vorbire", cu respectarea anumitor "reguli gramaticale" - a vedea programa şcolară pentru Limba şi literatura romănă, clasele V - VIII.

Un limbaj oarecare presupune deasemenea, anumite "părţi de vorbire" specifice şi un set de "reguli gramaticale" pe baza căruia se pot produce "propoziţiile" (sau "programele") corecte.

Trasarea şi restrângerea căutării, în metoda backtracking

C++ | backtracking | canvas | javaScript
2014 mar

Pentru analiza unui program bazat pe backtracking putem folosi (fie şi numai în scop instructiv) următorul procedeu (în loc de instrumente de tip "debugger"): rezumăm programul respectiv la un caz tipic (să producă o singură soluţie, nu pe toate) şi intercalăm în anumite puncte două "linii de control" (afişând nodul şi adâncimea). Rezultă un fişier text conţinând întreaga istorie a căutării soluţiei - poate foarte voluminos, dar putem angaja utilitare ca less şi grep pentru a depista ramificări inutile (de evitat în cursul căutării soluţiei).


Prev
Next
ALL (349 titluri)

vezi Cărţile mele (de programare)

despre acesta ~ Home
(sau https://vlad.bazon.net/

Factoriale | Graficul funcţiilor

PGN browser | chess JS engine

Load

in /slightchess

/slightchess

626 partide analizate cu Crafty

(R) Computer Art | Decoraţiuni

Aplicaţii şcolare (javaScript)

Sinteze: