时间戳

首页 > 解决方案 > 如何在 JavaScript 中实现具有文字状态和转换的基本迭代下推自动机解析算法？

javascript - 如何在 JavaScript 中实现具有文字状态和转换的基本迭代下推自动机解析算法？

问题描述

我们希望创建一个下推自动机（PDA），它使用以下“字母表”（字母表是指一组唯一的符号字符串/键）：

+aaa
+bbb
+ccc
+ddd
+eee
-aaa
-bbb
-ccc
-ddd
-eee

此字母表中的“符号”（带有 + 或 - 前缀的 3 个字母序列）用于制作树。以下是一些示例树：

+eee-eee
+aaa+bbb-bbb-aaa
+bbb+aaa+ccc+eee-eee-ccc+ccc-ccc+ddd+ccc+eee-eee-ccc-ddd-aaa-bbb

可视化为一棵实际的树，它们更像是：

+eee
-eee

+aaa
  +bbb
  -bbb
-aaa

+bbb
  +aaa
    +ccc
      +eee
      -eee
    -ccc
    +ccc
    -ccc
    +ddd
      +ccc
        +eee
        -eee
      -ccc
    -ddd
  -aaa
-bbb

所以给定这个字母表和这些示例树，问题是你将如何编写一个通用的下推自动机来解析这些树。规则是：

  1. 任何字母对（打开/关闭对）都可以有任意数量的嵌套子级，并且将哪些字母对嵌套为子级并不重要。

您将如何在 JavaScript 中编写下推自动机来将字符串解析为 AST？

我的意思是，实现必须从字面上具有stack,states和transitions. 我的意思是，不实现临时解析器，甚至不实现递归下降解析器。这应该是一个迭代的 while 循环，以某种方式循环转换，而不是使用递归。

输出应该是一个非常简单的“AST”，看起来像这样（对于+aaa+bbb-bbb-aaa树）：

{
  "type": "aaa",
  "children": [
    {
      "type": "bbb",
      "children": []
    }
  ]
}

我想知道如何构建一个 PDA，以便在我使用自定义编程语言的特定情况下，我可以转换我正在工作的相当复杂和复杂的 AST，并将其解析为对象图。这个问题在 SO 上写得太复杂，也太难简化，这就是为什么我在这里询问 JavaScript 中非常基本的 PDA 实现的原因。

我有兴趣了解在执行 PDA 算法时如何跟踪每个分支点的上下文以及转换的样子。

注意：我听说过/见过偶尔提到的“2-state”PDA。听起来您有一种状态来进行计算，还有一种“最终”状态。甚至可能只是一个状态。如果有可能做到这一点，那就太酷了。如果没有，请不要担心。

如有必要，您可以先编写一个上下文无关语法并使用它来动态构建 PDA，但这里的关键问题是 PDA 在技术上是如何实现的。我认为手动编写每个转换函数可能是可能/直接的，但我并不完全确定。无论哪种方式都适合我。

标签： javascriptalgorithmtreeautomata

解决方案

不可能创建一个 PDA 来生成这种树形数据结构，因为：

  • PDA 具有有限数量的状态和堆栈符号，并且没有输出磁带。然而，这个 PDA 应该能够以某种方式表示（并提供）的树的数量是无限的。如果我们在面向对象的结构中考虑树的节点，那么可能有无数个不同的节点，因为节点的身份也由它所拥有的引用决定。这与 PDA 具有的有限符号集相冲突。如果作为替代方案，我们不会选择面向对象的输出，那么我们将一无所获：输入已经是树的序列化表示。
  • 即使您将输出磁带添加到此自动机，使其成为重写系统，您也不会获得太多收益，因为输入已经以序列化格式表示树。如果我理解正确，您对序列化输出不感兴趣（如 JSON，因为输出顺序与输入顺序相同，这将是微不足道的），而是结构化输出（类似 JavaScript 的对象）。

因此，正如其他人也指出的那样，我们需要以某种方式放松规则。我们可以想到几种（组合）方法来做到这一点：

  1. 允许无限数量的状态，或
  2. 允许无限堆栈字母表，或
  3. 允许 PDA 访问堆栈的更多内容，而不仅仅是其顶部元素
  4. 让转换表引用堆栈顶部元素的特定属性，而不是整个元素 - 允许堆栈元素的其他属性的无限可能性，同时确保该特定属性的值属于有限集。
  5. 将树形建筑保持在 PDA 之外
  6. ...解决 PDA 与生成结构化树的要求不兼容的任何其他措施。

其中一些选项会推断出无限转换表，因此在这种情况下它不能是表，但可以是函数。

实施选择

1.对于通用引擎

考虑到您对树构建的关注以及对“堆栈、状态和转换”的要求，我选择了以下实现选择，有时还进行了简化：

  • 我从上面的列表中选择策略 4
  • 通用引擎将自己创建树。所以它只是在有限的意义上是通用的。它只能验证和生成树。
  • 它将（仅）将转换表作为配置输入
  • 它只有两个状态（布尔值），表示到目前为止是否一切正常。
  • 只有在转换表中没有匹配的转换时，OK 状态才能从 true 变为 false
  • 一旦 OK 状态为假，引擎甚至不会尝试找到转换，而是会忽略任何进一步的输入。
  • 结果，转换表将不包括当前状态和未来状态部分，因为它们都被暗示为真（即“OK”）。
  • 树将在堆栈中编码。堆栈元素的data属性将是用于识别转换的特殊属性。每个堆栈元素的children属性将用于定义树，并且不被视为转换表所针对的堆栈字母表的一部分。
  • 堆栈从一个元素开始。它的children属性将是引擎的输出。在每一步都可以查询这个输出，因为这个元素永远不会从堆栈中删除。
  • 输入符号不能包含空字符串，该字符串保留用于指示输入流的结束。这允许引擎给出反馈是否是结束输入流的有效时刻。
  • 当指示输入结束时，引擎要求其堆栈为“空”（只有 1 个条目）。
  • 我假设输入符号不包含空格：空格在转换查找算法中用作分隔符
  • 给定的转换表被转换为（散列）映射，以允许在给定当前状态和堆栈顶部的数据的情况下快速查找。此映射中的键是输入和堆栈数据值的串联，并且在这里选择空格作为分隔符。如果空格是输入符号中的有效字符，则应选择另一种编码机制来序列化此密钥对（例如 JSON），但我想保持简单。
  • 引擎不需要获取输入符号集，也不需要获取堆栈符号集作为配置输入，因为这些将在转换表中隐含。
  • 引擎的初始状态设置为 OK（可以通过简单的属性分配进行不同的设置，但这将是无用的，因为它会忽略输入）

2.对于具体的+/-输入格式

解决方案的更具体部分处理您在问题中给出的实际输入格式。一个函数会将一组类型转换为转换表，另一个函数将基于“+”和“-”字符对输入进行标记，但没有任何验证（没有符号检查，也没有符号长度检查......），因为无论如何，当调用引擎时，这一切都会显示为错误。

输入中的任何空白都将被忽略。

执行

// To peek the top element of a stack:
Array.prototype.peek = function () { return this[this.length - 1] };

function createParser(transitions) {
    function createNode(data) {
        return { 
            data, 
            children: [] 
        };
    }

    function addChild(parentNode, data) {
        const childNode = createNode(data);
        parentNode.children.push(childNode);
        return childNode;
    }

    let isOK = true; // It's a 2-state (boolean) engine. Transitions implicitly only apply to OK-state
    const stack = [createNode("")]; // Stack is private, and always has Sentinel node with value ""
    // Create a map for the transitions table, for faster lookup
    // We use space as a delimiter for the key pair, assuming an input symbol does not include spaces.
    const transMap = new Map(transitions.map(({whenInput, whenStack, thenPushValue}) =>
        [whenInput + " " + whenStack, thenPushValue]
    ));
    const parser = {
        read(input) { // Returns true when parser can accept more input after this one
            // Once the engine is in an error state, it will not process any further inputs
            if (!isOK) {
                return false;
            }
            // Consider the empty string as the end-of-input marker
            if (input === "") { 
                // Even when state is OK, the stack should now also be "empty"
                isOK &&= stack.length === 1;
                return false; // Not an error condition, but indication that no more input is expected
            }
            // Transitions do not include state requirements, nor new state definitions.
            // It is assumed that a transition can only occur in an OK state, and that all 
            //    included transitions lead to an OK state.
            const pushValue = transMap.get(input + " " + stack.peek().data);
            if (pushValue === undefined) { // No matching transition in the table implies that state is not OK
                isOK = false;
            } else {
                // As this is a two-state engine, with defined transitions only between OK states,
                // each defined transition will affect the stack: so it's either a push or pop.
                // A push is identified by the (non-empy) value to be pushed. An empty string denotes a pop.
                if (pushValue) {
                    stack.push(addChild(stack.peek(), pushValue));
                } else {
                    stack.pop();
                }
            }
            
            return isOK;
        },
        isOK, // Expose the (boolean) state
        output: stack[0].children // Don't expose the stack, but just the forest encoded in it
    };
    return parser;
}

function createTransition(whenInput, whenStack, thenPushValue) {
    return {whenInput, whenStack, thenPushValue}; // First two values imply the third
}

// Functions specific for the input format in the question:

function createTransitionTable(types) {
    // Specific to the input structure (with + and - tags) given in the question
    // An empty string in the second column represents an empty stack
    return [
        // Transitions for opening tags: O(n²)
        ...["", ...types].flatMap(stack => 
            types.map(type => createTransition("+" + type, stack, type))
        ),
        // Transitions for closing tags
        ...types.map(type => createTransition("-" + type, type, ""))
    ];
}

function tokenizer(str) { // Could be a generator, but I went for a function-returning function
    str = str.replace(/\s+/g, ""); // remove white space from input string

    let current = 0; // Maintain state between `getNextToken` function calls
    
    function getNextToken() {
        const start = current++;
        while (current < str.length && str[current] !== "+" && str[current] !== "-") {
            current++;
        }
        const token = str.slice(start, current);
        
        console.log("read", token); // For debugging
        return token;
    }
    return getNextToken;
}

// Example input language, as defined in the question:
const types = ["aaa", "bbb", "ccc", "ddd", "eee"];
const transitionTable = createTransitionTable(types);
const parser = createParser(transitionTable);

// Example input for it:
const rawInput = `
+eee-eee
+aaa+bbb-bbb-aaa
+bbb+aaa+ccc+eee-eee-ccc+ccc-ccc+ddd+ccc+eee-eee-ccc-ddd-aaa-bbb`;
const getNextToken = tokenizer(rawInput);

// Process tokens
while (parser.read(getNextToken())) {}

console.log("Parser state is OK?: ", parser.isOK);
console.log("Parser output:\n");
console.log(JSON.stringify(parser.output, null, 3));

推荐阅读