Pages: [1]   Go Down
Print
Author Topic: Esercizio sulle espressioni regolari con il passaggio degli stati  (Read 1117 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
rondey
Matricola
*
Offline Offline

Posts: 74


« on: 05-04-2016, 14:52:35 »

Code:
-module(exprReg).
-export([manager/0,state/2,create/1, read/0]).

%States=[{state0, [{Char, WhatNextState}, {Char, WhatNextState}, ...], Final}, {state1, [{Char, WhatNextState}, {Char, WhatNextState}, ...], Final}, ...]
%ES: States=[{state0,[{a,state1},{b, none}, {c, state3}],notfinal }, {state1,[{a, none},{b, state2},{c, none} ], notfinal}, {state2, [{a, none}, {b, none}, {c, state2}],final}, {state3,[{a, none}, {b, state4}, {c, none} ], final}, {state4, [ {a, none}, {b,state3}, {c,none} ], notfinal } ].
%In modo equivalente: States=[{state0,[{a,state1}, {c, state3}],notfinal }, {state1,[{b, state2} ], notfinal}, {state2, [{c, state2}],final}, {state3,[{b, state4} ], final}, {state4, [ {b,state3}], notfinal } ]
create (States) ->          %%we create the manager and the (process-)states. The PID of manager is returned.

                      IDmanager = spawn(exprReg,manager,[]),
                      %applicare per ogni elemento della lista
                      PIDstates = spawnStates (IDmanager, States, []),

                      %%we connect the manager to qinit and the various states among themselves

 %Collego IDmanager allo stato iniziale
 {state0, PID} = lists:keyfind(state0, 1, PIDstates),
                      IDmanager!PID,
                      connectStates (PIDstates, States, PIDstates),
                      IDmanager.
                      
%Crea il processo per ogni stato
spawnStates (_, [], PIDstates) -> PIDstates;
spawnStates (IDmanager, [State|States], PIDstates) ->
{NameState, _, Final} = State,
PIDstate={NameState, spawn(exprReg,state,[IDmanager, Final])},
spawnStates (IDmanager, States, PIDstates++[PIDstate]).

%Collego ciascun stato con i relativi stati successivi
connectStates ([], _, PIDstatesList) -> PIDstatesList;
connectStates ([PIDstate|PIDstates], States, PIDstatesList)->
{NameState, PID} = PIDstate,
{NameState, NextStates, _} = lists:keyfind(NameState, 1, States),
PID!getPIDnextStates(PIDstatesList, NextStates, []),
connectStates (PIDstates, States, PIDstatesList).

%Ricavo la lista di PIDstate a partire dal nome dello stato successivo
getPIDnextStates (_, [], PIDnextStates) -> PIDnextStates;
getPIDnextStates (PIDstates, [NextState|NextStates], PIDnextStates) ->
{Char, NameNextState} = NextState,
Ps=lists:keyfind(NameNextState, 1, PIDstates),
if  (Ps == false) ->
PIDnextState = {Char, none};
(true) ->
{NameNextState, PID} = Ps,
PIDnextState = {Char, PID}
end,
getPIDnextStates(PIDstates, NextStates, PIDnextStates++[PIDnextState]).

manager() -> receive
               IDinitial -> loopmanager(IDinitial)
             end.                      
                  

loopmanager(IDinitial) ->
               receive

                   {requestParsing,ID,List} -> IDinitial ! {List,ID,List};
                                              
                   {accepted,ID,List}       -> ID ! {accepted,List};

                   {rejected,ID,List}       -> ID ! {rejected,List}

               end,
            
               loopmanager(IDinitial).




                    


state(IDmanager,Final) -> receive
                             PIDs -> loop(PIDs,IDmanager,Final)
                          end.




 loop(PIDs,IDmanager,Final) ->
          
         receive

              {[],ID,List}          ->    if
                                             (Final == final)  -> IDmanager ! {accepted,ID,List};
                            
                                              true             -> IDmanager ! {rejected,ID,List}
                    
                                          end;

              {[ Char | Cs ],ID,List}  ->  
NextPID = lists:keyfind(Char, 1, PIDs),
  if
    (NextPID==false) -> IDmanager ! {rejected,ID,List};
 
true ->   {Char, Next} = NextPID,
                                          
  if
 (Next == none)    ->  IDmanager ! {rejected,ID,List};

  true             -> Next ! {Cs,ID,List}
  end
end
          end,
            
         loop(PIDs,IDmanager,Final).


read() -> receive Y -> Y end.

« Last Edit: 06-04-2016, 09:29:14 by rondey » Logged
rondey
Matricola
*
Offline Offline

Posts: 74


« Reply #1 on: 06-04-2016, 09:42:09 »

Questa è la soluzione nella quale la funzione getPIDnextStates non usa la tecnica della coda di ricorsione(perciò la funzione non ha come argomento la lista di PIDnextStates).

Code:
-module(exprReg).
-export([manager/0,state/2,create/1, read/0]).

%States=[{state0, [{Char, WhatNextState}, {Char, WhatNextState}, ...], Final}, {state1, [{Char, WhatNextState}, {Char, WhatNextState}, ...], Final}, ...]
%ES: States=[{state0,[{a,state1},{b, none}, {c, state3}],notfinal }, {state1,[{a, none},{b, state2},{c, none} ], notfinal}, {state2, [{a, none}, {b, none}, {c, state2}],final}, {state3,[{a, none}, {b, state4}, {c, none} ], final}, {state4, [ {a, none}, {b,state3}, {c,none} ], notfinal } ].
%In modo equivalente: States=[{state0,[{a,state1}, {c, state3}],notfinal }, {state1,[{b, state2} ], notfinal}, {state2, [{c, state2}],final}, {state3,[{b, state4} ], final}, {state4, [ {b,state3}], notfinal } ]
create (States) ->          %%we create the manager and the (process-)states. The PID of manager is returned.

                      IDmanager = spawn(exprReg,manager,[]),
                      %applicare per ogni elemento della lista
                      PIDstates = spawnStates (IDmanager, States, []),

                      %%we connect the manager to qinit and the various states among themselves

 %Collego IDmanager allo stato iniziale
 {state0, PID} = lists:keyfind(state0, 1, PIDstates),
                      IDmanager!PID,
                      connectStates (PIDstates, States, PIDstates),
                      IDmanager.
                      
%Crea il processo per ogni stato
spawnStates (_, [], PIDstates) -> PIDstates;
spawnStates (IDmanager, [State|States], PIDstates) ->
{NameState, _, Final} = State,
PIDstate={NameState, spawn(exprReg,state,[IDmanager, Final])},
spawnStates (IDmanager, States, PIDstates++[PIDstate]).

%Collego ciascun stato con i relativi stati successivi
connectStates ([], _, PIDstatesList) -> PIDstatesList;
connectStates ([PIDstate|PIDstates], States, PIDstatesList)->
{NameState, PID} = PIDstate,
{NameState, NextStates, _} = lists:keyfind(NameState, 1, States),
PID!getPIDnextStates(PIDstatesList, NextStates),
connectStates (PIDstates, States, PIDstatesList).

%Ricavo la lista di PIDstate a partire dal nome dello stato successivo
getPIDnextStates (_, []) -> [];
getPIDnextStates (PIDstates, [NextState|NextStates]) ->
{Char, NameNextState} = NextState,
Ps=lists:keyfind(NameNextState, 1, PIDstates),
if  (Ps == false) ->
PIDnextState = {Char, none};
(true) ->
{NameNextState, PID} = Ps,
PIDnextState = {Char, PID}
end,
[PIDnextState]++getPIDnextStates(PIDstates, NextStates).

manager() -> receive
               IDinitial -> loopmanager(IDinitial)
             end.                      
                  

loopmanager(IDinitial) ->
               receive

                   {requestParsing,ID,List} -> IDinitial ! {List,ID,List};
                                              
                   {accepted,ID,List}       -> ID ! {accepted,List};

                   {rejected,ID,List}       -> ID ! {rejected,List}

               end,
            
               loopmanager(IDinitial).




                    


state(IDmanager,Final) -> receive
                             PIDs -> loop(PIDs,IDmanager,Final)
                          end.




 loop(PIDs,IDmanager,Final) ->
          
         receive

              {[],ID,List}          ->    if
                                             (Final == final)  -> IDmanager ! {accepted,ID,List};
                            
                                              true             -> IDmanager ! {rejected,ID,List}
                    
                                          end;

              {[ Char | Cs ],ID,List}  ->  
NextPID = lists:keyfind(Char, 1, PIDs),
  if
    (NextPID==false) -> IDmanager ! {rejected,ID,List};
 
true ->   {Char, Next} = NextPID,
                                          
  if
 (Next == none)    ->  IDmanager ! {rejected,ID,List};

  true             -> Next ! {Cs,ID,List}
  end
end
          end,
            
         loop(PIDs,IDmanager,Final).


read() -> receive Y -> Y end.
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.792



WWW
« Reply #2 on: 06-04-2016, 10:09:56 »

Benissimo.

Pero' di dice "ricorsione di coda", non "coda di ricorsione" ...  
Logged
Ocelot92
Apprendista Forumista
**
Offline Offline

Posts: 301



« Reply #3 on: 10-04-2016, 22:08:14 »

Strano doppio post, vedi sotto.
« Last Edit: 11-04-2016, 12:31:19 by Ocelot92 » Logged

I'm happy to tell you all that...
((λf.λx.f(f(x))) (λy.y^2)) (5)  = 5^4

"Si ma dillo che bisogna cliccare APPLY per crearle le partizioni…" - cit. Utente dopo aver seguito un How-To... .-.
Ocelot92
Apprendista Forumista
**
Offline Offline

Posts: 301



« Reply #4 on: 10-04-2016, 22:13:41 »

Ecco la mia versione. L'automa può essere definito o come matrice di transizione come si vede del primo commento oppure si può anche scriverlo come un automa a stati finiti (cioè si possono omettere le transizioni mancanti come {b,none}, questo modo risulta più comodo).

La strategia è che una volta creati gli stati scansiono la matrice d'input(che è una lista... ma semanticamente rappresenta la matrice di transizione) e sostituisco lo stato col suo rispettivo PID. Fatto questo ad ogni stato mando la riga della "matrice" che corrisponde alle sue transizioni.
L'unica funzione di Erlang già esistente che uso è lists:nth, ma solo perchè già so come "ricavarmela"...
Code:
-module(automa).
-export([read/0,createStates/2,  create/1, manager/0, configState/1, loopState/2, checkChar/2, loopManager/1, transmittingPids/3, transmitting2qStates/2, scanMatrixByRows/3, scanTransitions/2  ]).
% Man=automa:create([{q0,[{a,1},{b,none}] ,notfinal}, {q1,[{a,2},{b,none}],notfinal}, {q2,[{a, none}, {b,2} ],final}  ] ).
% [{q0, [{a,none},{b,1}], final}, {q1,[],nofinal}  ]
% It creates the manager and the q-states. Then it sends the q0'pid to the manager and the i-th matrix row to the i-th q-state
create(TransitionMatrix) ->
    ManPid = spawn(automa, manager, []),
ListQs = createStates(ManPid, count(TransitionMatrix)),
    NewMatrix = scanMatrixByRows(TransitionMatrix, ListQs,[]),
    transmittingPids(NewMatrix, ListQs, ManPid),
    ManPid.

count ([]) -> 0;
count([Element | Others]) ->
1 + count(Others).

createStates(MPid, 0) -> [];
createStates(MPid, NumStates) ->
[spawn(automa,configState,[MPid])] ++ createStates(MPid, NumStates - 1).
    
configState(ManPid) ->
    receive
        {matrixRow, Row} -> loopState(ManPid, Row)
    end.
    
loopState(ManPid, Row) ->
    receive
        {[], ClientPid, Original} ->

            {_,_,Final} = Row,
            if
                (Final == final) ->
                    ManPid ! {accepted, ClientPid, Original};
                true ->
                    ManPid ! {rejected, ClientPid, Original}
            end;
            
        {[Char | Chars], ClientPid, Original} ->
{_,List,_} = Row,
{Match, Next} = checkChar(Char, List),
if
(Match == true) ->
Next ! {Chars, ClientPid, Original};
true ->
ManPid ! {rejected, ClientPid, Original}
end;
_ -> loopState(ManPid,Row)
    end,
    loopState(ManPid,Row).

checkChar(Char, []) -> {false,none};  
checkChar(Char, [Element|Others] ) ->
{ElemChar, Next} = Element,
if
(Char == ElemChar) ->
{true, Next};
true ->
checkChar(Char, Others)
end.

manager() ->
    receive
        {init,Q0PID} ->
loopManager(Q0PID)
    end.
    
loopManager(Q0Pid) ->

    receive
        {requestParsing,ClientPid,Original} -> Q0Pid ! {Original,ClientPid,Original};
        {accepted,ClientPid,Original}       -> ClientPid ! {accepted,Original};
        {rejected,ClientPid,Original}       -> ClientPid ! {rejected,Original};
        _ -> loopManager(Q0Pid)
    end,
    loopManager(Q0Pid).


    
transmittingPids(NewMatrix, ListQs, ManPid) ->
    [Q0 | _ ] = ListQs,
    ManPid ! {init, Q0},
    transmitting2qStates(NewMatrix, ListQs).
    
transmitting2qStates([],[]) -> transmissionEnded;
transmitting2qStates([Row|NewMatrix], [Qpid|ListQs]) ->
Qpid!{matrixRow,Row},
transmitting2qStates(NewMatrix, ListQs).

    
scanMatrixByRows([],ListQs,NewMatrix)-> NewMatrix;
scanMatrixByRows([Row|Matrix], ListQs, NewMatrix) ->
    {State,List,Final} = Row,
    NewTransitions = scanTransitions(List,ListQs),
    scanMatrixByRows(Matrix, ListQs, NewMatrix ++ [{State,NewTransitions,Final}]).
    
scanTransitions([],ListQs) -> [];  
scanTransitions([Cell|Row], ListQs) ->
    {Char, Index} = Cell,
    if
%     io:format("@@@The value is: ~p.@@@", [Index+1]),
(Index =/= none) ->
Aux = [{Char,lists:nth(Index +1 ,ListQs)}];
true ->
Aux = [{Char,none}]
%     io:format("@@@The value is: ~p.@@@", [Aux]),
end,
    Aux ++ scanTransitions(Row,ListQs).
    
    
read() ->
receive
Y -> Y
end.
« Last Edit: 11-04-2016, 09:34:06 by Ocelot92 » Logged

I'm happy to tell you all that...
((λf.λx.f(f(x))) (λy.y^2)) (5)  = 5^4

"Si ma dillo che bisogna cliccare APPLY per crearle le partizioni…" - cit. Utente dopo aver seguito un How-To... .-.
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.792



WWW
« Reply #5 on: 11-04-2016, 10:36:06 »

Pare interessante.
Metti anche qualche automa di test.

Salutoni
FB
Logged
Ocelot92
Apprendista Forumista
**
Offline Offline

Posts: 301



« Reply #6 on: 11-04-2016, 12:29:30 »

Pare interessante.
Metti anche qualche automa di test.

Salutoni
FB
Il primo commento è il primo test che ho fatto. Serve per riconoscere stringhe del tipo aab*.

Ho provato anche con questo automa:
Code:
Man=automa:create([{q0,[{a,1},{b,1}],notfinal}, {q1,[{a,2},{c,1},{d,5}],notfinal}, {q2,[{b,3}],notfinal}, {q3,[{c,4}],notfinal},{q4,[],final},{q5,[{d,6}],notfinal}, {q6,[],final}] ).
Che riconosce stringhe del tipo: [ab]c*(abc|dd) (preso da qua)
« Last Edit: 11-04-2016, 12:33:00 by Ocelot92 » Logged

I'm happy to tell you all that...
((λf.λx.f(f(x))) (λy.y^2)) (5)  = 5^4

"Si ma dillo che bisogna cliccare APPLY per crearle le partizioni…" - cit. Utente dopo aver seguito un How-To... .-.
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.792



WWW
« Reply #7 on: 11-04-2016, 13:14:23 »

OK!
Logged
Pages: [1]   Go Up
Print
Jump to: