有限状态机和FSM间信令

StackOverflow https://stackoverflow.com/questions/1441077

题

对具有本机（因此没有FSM生成工具）的语言的建议支持状态机开发和执行以及消息/信号的传递。这适用于电信，例如实现这种复杂程度的FSM。

我已经考虑过Erlang，但是会喜欢一些反馈，建议，教程指针，替代方案，尤其是基于Java的框架。也许斯卡拉？

仅限开源。我不是在寻找UML或与正则表达式相关的解决方案。

由于这是用于实施电信协议，因此FSM可能并非易事。许多状态，许多转换，基于信号，输入约束/保护。动态实例化将是一个加号。切换语句是不可能的，它很快就会无法使用。如果/ else，那几乎没有好处。

我更愿意不依赖于图形设计;格式FSM描述应该是人类可读/可编辑/可管理的。

-

我决定专注于基于Actor的C ++解决方案

例如，Theron框架提供了一个起点 http://theron.ashtonmason.net/ 和为了避免基于FSM的事件处理程序中的switch语句，这个C ++ FSM模板框架看起来很有用 http：// satsky.spb.ru/articles/fsm/fsmEng.php

有帮助吗？

解决方案

我同意转换声明应该是不可能的......它们最终会导致维护噩梦。你不能使用

其他提示

我不同意FSM的实施是微不足道的。这是非常短视的，表明对替代方案缺乏了解，或者缺乏复杂状态机的经验。

根本问题是状态机图是显而易见的，但FSM 代码不是。一旦你超过十几个状态和一系列过渡，FSM代码变得丑陋且难以理解。

有一些工具可以绘制状态机，并为其生成Java代码。但是，我不知道有任何开源工具。

现在，回到Erlang / Scala，Scala也有Actors和消息传递，并且基于JVM，所以考虑到你的约束，它可能是比Erlang更好的选择。

Scala上还有一个DFA / NFA库，虽然它不是特别好。它支持从任意正则表达式（即文字不必是字符）转换为DFA / NFA。

我会在下面发布一些代码。在这段代码中，我们的想法是创建一个FSM，它将接受任意前缀的任何顺序组合，用于单词列表，这个想法是在没有预定义键绑定的情况下查找菜单选项。

import scala.util.regexp._
import scala.util.automata._

// The goal of this object below is to create a class, MyChar, which will
// be the domain of the tokens used for transitions in the DFA. They could
// be integers, enumerations or even a set of case classes and objects. For
// this particular code, it's just Char.
object MyLang extends WordExp {
  type _regexpT = RegExp
  type _labelT = MyChar

  case class MyChar(c:Char) extends Label
}

// We now need to import the types we defined, as well as any classes we
// created extending Label.    
import MyLang._

// We also need an instance (singleton, in this case) of WordBerrySethi,
// which will convert the regular expression into an automatum. Notice the
// language being used is MyLang.    
object MyBerrySethi extends WordBerrySethi {
  override val lang = MyLang
}

// Last, a function which takes an input in the language we defined,
// and traverses the DFA, returning whether we are at a sink state or
// not. For other uses it will probably make more sense to test against
// both sink states and final states.
def matchDet(pat: DetWordAutom[MyChar], seq: Seq[Char]): Boolean =
  !pat.isSink((0 /: seq) ((state, c) => pat.next(state, MyChar(c))))

// This converts a regular expression to a DFA, with using an intermediary NFA    
def compile(pat: MyLang._regexpT) = 
  new SubsetConstruction(MyBerrySethi.automatonFrom(pat, 100000)).determinize

// Defines a "?" function, since it isn't provided by the library
def Quest(rs: _regexpT*) = Alt(Eps, Sequ(rs: _*)) // Quest(pat) = Eps|pat = (pat)?


// And now, the algorithm proper. It splits the string into words
// converts each character into Letter[MyChar[Char]],
// produce the regular expression desired for each word using Quest and Sequ,
// then the final regular expression by using Sequ with each subexpression.
def words(s : String) = s.split("\\W+")
def wordToRegex(w : String) : Seq[MyLang._regexpT] = w.map(c => Letter(MyChar(c)))
def wordRegex(w : String) = Quest(wordToRegex(w) reduceRight ((a,b) => Sequ(a, Quest(b))))
def phraseRegex(s : String) = Sequ(words(s).map(w => wordRegex(w)) : _*)

// This takes a list of strings, produce a DFA for each, and returns a list of
// of tuples formed by DFA and string.
def regexList(l : List[String]) = l.map(s => compile(phraseRegex(s)) -> s)

// The main function takes a list of strings, and returns a function that will
// traverse each DFA, and return all strings associated with DFAs that did not
// end up in a sink state.
def regexSearcher(l : List[String]) = {
  val r = regexList(l)
  (s : String) => r.filter(t => matchDet(t._1, s)).map(_._2)
}

我几乎无法想到实现FSM的任何语言都是非平凡的。也许这一个。

...
if (currentState == STATE0 && event == EVENT0) return STATE1;
if (currentState == STATE1 && event == EVENT0) return STATE2;
...

状态模式（使用Java枚举）是我们在电信应用中使用的模式，但是我们使用小型FSM：

public class Controller{
    private State itsState = State.IDLE;

    public void setState(State aState){
        itsState = aState;
    }

    public void action1(){
        itsState.action1(this);
    }

    public void action2(){
        itsState.action2(this);
    }

    public void doAction1(){
        // code
    }

    public void doAction2(){
        // code
    }
}

public enum State{
    IDLE{
        @Override
        public void action1(Controller aCtx){
            aCtx.doAction1();
            aCtx.setState(State.STATE1);
        }
    },

    STATE1{
        @Override
        public void action2(Controller aCtx){
            aCtx.doAction2();
            aCtx.setState(State.IDLE);
        }
    },

    public void action1(Controller aCtx){
        throw new IllegalStateException();
    }

    public void action2(Controller aCtx){
        throw new IllegalStateException();
    }
}

使用任何具有案例陈述的语言实施FSM应该是微不足道的。您的语言选择应该基于有限状态机需要做的事情。

例如，您声明需要为电信开发和提及消息执行此操作。我会看一下支持分布式消息传递的系统/语言。 Erlang做到了这一点，并且我确信几乎所有其他通用语言都通过该语言的API /库来支持它。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top