flat assembler
Message board for the users of flat assembler.

Index > DOS > Finite Automata in FASM

Goto page Previous  1, 2, 3, 4
Author
Thread Post new topic Reply to topic
MHajduk



Joined: 30 Mar 2006
Posts: 6038
Location: Poland
MHajduk
All missing images in my posts have been reconstructed. Some questions (especially referring to the neural networks basics) have now more elaborated descriptions:
Post 27 Oct 2010, 00:13
View user's profile Send private message Visit poster's website Reply with quote
aq83326



Joined: 25 Jun 2011
Posts: 21
aq83326
Something I wrote this morning, here is a more general version, the example reconstructs the same DFA as the original post.
Code:
use64 ; very important this line

; a future improvement would be to chain together multiple DFA's using procedure calls, where higher level elements
; are really arrays of lower level elements
actionsize equ 1
macro DeterministicFiniteAutomatonState Name, StateType, InvalidAction, [next, action]
{
    common
      Name:
        cmp rcx, rdx         ; compare curenrt Address, RCX, and end Address, RDX, if they are the same, we have reached the end of the string
        je StateType         ; jump to StateType (ST should tell us whether this state is an Accepting state or not)
        match =1 , actionsize { movzx r9, byte [rcx] \}
        match =2 , actionsize { movzx r9, word [rcx] \}  ; retrieve the value pointed at by current address, put it in R9
        match =4 , actionsize { movzx r9, dword [rcx] \}  
        match =8 , actionsize { movzx r9, qword [rcx] \}
        add rcx, actionsize  ; increment the current address pointer by size bytes
    forward
        cmp r9, action      ; compare what's in R9 to the given action argument
        je next             ; if equal, jump to the next state, else pass through to the next comparison
    common
        jmp InvalidAction   ; if we get to this point, the current action is invalid, so Jump to InvalidAction
}


DeterministicFiniteAutomatonState StartState, NotAccepting,  InvalidAct,  S0,   0, S1,   1
DeterministicFiniteAutomatonState S0,         Accepting,     InvalidAct,  S0,   0, S1,   1
DeterministicFiniteAutomatonState S1,         NotAccepting,  InvalidAct,  S10,  0, S11,  1
DeterministicFiniteAutomatonState S10,        NotAccepting,  InvalidAct,  S100, 0, S0,   1
DeterministicFiniteAutomatonState S11,        NotAccepting,  InvalidAct,  S1,   0, S10,  1
DeterministicFiniteAutomatonState S100,       NotAccepting,  InvalidAct,  S11 , 0, S100, 1


Accepting:
NotAccepting:
InvalidAct:    

edit: updated it for actions represented by more than just bytes.
I wanted to have it more general in the beginning but I didn't know you needed to put a \} when using a match inside a macro.
Although if you need more than 256 actions, you have quite the DFA on your hands.


Last edited by aq83326 on 24 Oct 2011, 02:55; edited 1 time in total
Post 22 Oct 2011, 16:31
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6038
Location: Poland
MHajduk
Yes, that's a very nice generalization of the original macro. Smile We can analyze with it not only strings made of 0's and 1's but also more complicated sequences. BTW, you can modify your macro a bit to get something that can work also, for example, with UTF-16 input strings. Wink
Post 22 Oct 2011, 17:52
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page Previous  1, 2, 3, 4

< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.

Website powered by rwasa.