javascript - Finite State Machine parsing - Stack Overflow

admin管理员组

文章数量:1420181

This picture depicts finite state machine parsing "nice" string.

The question is how would it look like in JS code?

EDIT

Picture from link above:

This picture depicts finite state machine parsing "nice" string.

The question is how would it look like in JS code?

EDIT

Picture from link above:

• javascript
• fsm

Share Improve this question Follow edited Nov 17, 2011 at 19:02 Anne 27.1k99 gold badges6767 silver badges7171 bronze badges asked Nov 17, 2011 at 18:56 DrStrangeLoveDrStrangeLove 11.6k1616 gold badges6363 silver badges7373 bronze badges 0

Add a ment  | 

2 Answers 2

Sorted by: Reset to default 4

According to wikipedia(where your link points) this refers to an "Acceptor FSM" and "By definition, the languages accepted by FSMs are the regular languages". One could say that it will be just /^nice$/.test(somestring). If this helps and you need more info on regular expressions take a look at RegExp.

I did a little FSM work in Javascript on a project just recently. My code, adapted for the case above, looks like this - you have a factory to make the state automaton, which is just a sequence of steps it's trying to match:

function fsmAutomatonFactory(tests) {
    var step = 0;
    var state = false; // acceptance state

    return {
        testNext: function(element) {
            // matches current step
            if (tests[step].test(element)) {
                // advance step
                step++;
                return true;
            }
            // no match
            return false;
        },
        getState: function() {
            // all steps pleted successfully
            return step >= tests.length
        }
    }
}

Now you can set up an automaton with a series of tests, and run the input series through it:

function fsmTest(str) {
    // set up automaton
    var tests = [
        { test: function(l) { return l == 'n' }},
        { test: function(l) { return l == 'i' }},
        { test: function(l) { return l == 'c' }},
        { test: function(l) { return l == 'e' }}
    ];
    var automaton = fsmAutomatonFactory(tests);

    // run the test letter by letter
    for (var x=0; x<str.length; x++) {
        // you could break early here if you wanted
        automaton.testNext(str[x]); 
    }
    return automaton.getState();
}

This is a lot of code for str == "nice", but it scales relatively well to more plex inputs and tests. This works for a linear pattern like your case; if you needed branching or more plex logic, you might need to implement a state transition table or other mechanism to handle transitions other than state++.

本文标签： javascriptFinite State Machine parsingStack Overflow