如何将嵌套函数调用树转换为状态机？

Question

假设你有这样的系统：

const input = [0, [1, 2, [3, 4, [8, 9], 6, 7], 4], [5, 6, 7], 3, 4, [8, 9], 6, 7, [1], 9]
const output = parse(input)
console.log(output.join('-'))

function parse(input) {
  const output = []
  iterate(input, value => {
    check(() => isArray(value),
      () => { // yes array
        const children = parse(value)
        output.push(...children)
      },
      () => { // not array
        check(() => isEven(value), () => {
          output.push(value)
        })
      })
  })
  return output
}

function isArray(value) {
  return Array.isArray(value)
}

function isEven(value) {
  return value % 2 == 0
}

function check(condition, success, failure) {
  if (condition()) success()
  else if (failure) failure()
}

function iterate(array, block) {
  array.forEach(block)
}

本质上这就像一个树语法：

parse =
  iterate input, value =>
    check isArray(value)
      call parse(value)
    check isNumber(value)
      check isEven(value)
        push(value)

你可以把它想象成 JSON:

{
  type: 'function',
  name: 'parse',
  children: [
    {
      type: 'iterate',
      children: [
        {
          type: 'check',
          checker: 'isArray',
          children: [
            {
              type: 'call',
              function: 'parse'
            }
          ]
        },
        {
          type: 'check',
          checker: 'isNumber',
          children: [
            {
              type: 'check',
              checker: 'isEven',
              children: [
                {
                  type: 'push',
                }
              ]
            }
          ]
        }
      ]
    }
  ]
}

Basically my real problem is I have something like this JSON in a custom programming language, and I want to convert it into a state machine rather than the nested/recursive function calls like we started with in this post.

所以我的问题是，如何从这个 post 的开头重写递归函数系统，使其使用状态机？

You don't have to go all the way and make the state machine from the JSON (which in this example is incomplete, as I don't have a good example to simplify from).

相反，如果您能展示如何从这个 post 的开头重写这个递归或嵌套函数系统作为状态机，那就够了。

我想象的是这样的：

let transitions = [
  function1,
  function2,
  ...
]

let transition = transitions[0] // the start function in theory
let currentInput = input
let someStack = []
while (transition) {
  [currentInput, transition] = transition(someStack, currentInput)
}

但我很快就迷失了如何跟踪我们在输入中的位置，以及如何处理迭代（如 iterator 中）或“if 语句” "（如 check 中所示）。

function iterate(input) {
  // you can't do the recursive call here,
  // as the original while loop should handle this.
  // but, we should return some reference to the current input,
  // as well as the next transition.
}

如果必须选择一种语言，那么在 JavaScript 中执行此操作将是最简单的。但它甚至可以用伪代码来完成，以大致展示它是如何完成的。

Answer 1

这是不可能的。 A state machine cannot recognise/parse a language with a recursive grammar but only a regular language. You would need a stack machine.

Answer 2

正如所说，你不能使用状态机，但如果我理解你的例子，你就不需要了。您想要一种从数据构造谓词的方法；这些谓词将适用于复杂的不规则数据结构。

其中一些谓词会有副作用。
其中一些谓词将传播对数据子部分的操作。
我假设您有一种有限的方式来表达您的谓词，因此您可以组合一组有限的谓词来获得您想要的谓词。

如果 Java 个流有一个 'recursive' flatMap，那就足够了。

我是 Java 专家，所以我会在 Java 中写一个尝试。主要思想是有一个 Op 功能接口，将一个对象映射到一个对象列表。

然后你只需计算一个固定点。

interface Op{ List<Object> of(Object t); }
class A{
  Op push(List<Object> res){
    return o->{res.add(o);return List.of();};
    }  
  Op isArray(){
    return t->{
      if (!(t instanceof Object[] os)){ return List.of(); }
      return List.of(os);
      };
    }
  Op isNumber(Op more){
    return t->{
      if (!(t instanceof Integer i)){ return List.of(); }
      return more.of(i);
      };
    }
  Op isEven(Op more){
    return t->{
      if (!(t instanceof Integer i) || i%2==1){ return List.of(); }
      return more.of(i);
      };
    }
  void engine1(List<Op> query,Object input){//not recursive
    List<Object>edge=new ArrayList<>();
    List<Object>nextEdge=new ArrayList<>();
    edge.add(input);
    while(!edge.isEmpty()){
      for(var e:edge){
        for(var f:query){
          nextEdge.addAll(f.of(e));
          }
        }
      edge=nextEdge;
      nextEdge=new ArrayList<>();
      }
    }
  void example1() {
    List<Object> res=new ArrayList<>();
    List<Op> query=List.of(isArray(),isEven(push(res)));
    Object input= new Object[]{1,2,new Object[]{3,4},5,6};
    engine1(query,input);
    System.out.println(res);
    }
  public static void main(String[]arg) {
    new A().example1();//this would print 2,6,4
    }
  }

根据您的问题，您不清楚此订单是否可以接受。即访问副作用是广度优先如果没有，我想我可以获得深度优先订单，但它必须在 12 小时左右，因为现在在我的时区已经晚了。

如何将嵌套函数调用树转换为状态机？

How to convert nested function call tree to state machine?

javascript

algorithm

parsing

automata

state-machine