如何在 JavaScript 中实现具有文字状态和转换的基本迭代下推自动机解析算法？
How to implement a basic iterative pushdown automaton parsing algorithm with literal states and transitions in JavaScript?
我们希望创建一个 下推 自动机 (PDA)，它使用以下“字母表”（字母表是指一组独特的符号 strings/keys）：
+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
鉴于此字母表和这些示例树，问题是您将如何编写通用下推自动机来解析这些树。规则是：
- 任何字母对（open/close 对）都可以有任意数量的嵌套子项，并且嵌套哪些字母对作为子项并不重要。
如何在 JavaScript 中编写下推自动机来将字符串解析为 AST？
我的意思是，实现必须确实有 stack、states 和 transitions。我的意思是，不实现临时解析器，甚至不实现递归下降解析器。这应该是一个迭代的 while 循环，以某种方式循环转换，而不是使用递归。
输出应该是一个非常简单的“AST”，看起来像这样（对于 +aaa+bbb-bbb-aaa 树）：
{
"type": "aaa",
"children": [
{
"type": "bbb",
"children": []
}
]
}
我想知道如何构建 PDA，以便在我使用自定义编程语言的特定情况下，转换我正在工作的相当复杂的 AST，并将其解析为对象图。这个问题太复杂了，无法在 SO 上写出来，也很难简化，这就是为什么我在这里询问 JavaScript.
中非常基本的 PDA 实现
我很想知道您在执行 PDA 算法时如何跟踪每个分支点的上下文以及转换是什么样的。
注意：我听说过/看到过偶尔在这里和那里提到的“2 态”PDA。听起来您有一种状态可以进行计算，还有一种“最终”状态。甚至可能只是一个 single state。如果可以像这样做，那就太好了。如果没有，不用担心。
如果有必要，你可以先写一个Context Free Grammar，然后用它来动态构造一个PDA，但这里的关键问题是PDA在技术上是如何实现的。我认为手动编写每个转换函数可能/直接，但我不完全确定。无论哪种方式都适合我。
在伪代码中，DPDA 可以这样实现：
transitions <- map from (state, char, char) to (state, char[0-2])
stack <- stack initialized with a sentinel value 'Z'
input <- string of tokens to parse
currentState <- initial state
for each inputCharacter in input:
stackCharacter <- stack.pop()
currentState, charsToPush <- transitions[(currentState, inputCharacter, stackCharacter)]
if currentState is not valid:
return false
for charToPush in charsToPush.reverse():
stack.push(charToPush)
return (currentState in acceptingStates) and (stack contains only 'Z')
PDA如括号匹配是这样指定的：
transitions <- {
(0, '(', 'Z') -> (0, "(Z"),
(0, '(', '(') -> (0, "(("),
(0, ')', 'Z') -> nope,
(0, ')', '(') -> (0, ""),
}
acceptingStates <- [0]
initialState <- 0
请注意，以上是确定性的。一般的 PDA 是不确定的，并不是所有的上下文无关语言都可以由 DPDA 决定。您可以，并且必须注意指定转换的方式。
为了使其更通用（非确定性），转换映射需要映射到（state，char[]）元组的列表，而不仅仅是一个元组；循环中的每一步都需要考虑所有匹配的元组，而不仅仅是一个。
有帮助吗？
对于你的语法，你的标记是这些“+aaa”、“-aaa”的东西。您的字母表是有限的但非常大，因此您不希望必须在过渡图中指定所有内容。所以这是你必须做出的决定：你想要一个纯 PDA（完全指定的地图）还是你想要编写一个类似 PDA 的东西但不完全是 PDA 来避免这种情况？
如果是后者，您想在循环中添加一个与 + 和 - 标记的标识相匹配的检查。此时您还不如编写自己的代码，因为创建一个可以处理所有事情的通用解析器是一项大量的工作。只为您的特定需求编写解析器会更容易。
这就是人们创建像 flap.js 这样的库的原因，因为这些东西很复杂。
详细说明我的评论，如果您将转换函数设为任意而不是地图，您可以用这种方式表达您的语言。
transition <- arbitrary function taking input (state, token, token) and output (state, token[0-2])
stack <- stack initialized with a sentinel token 'Z'
input <- string of tokens to parse
currentState <- initial state
for each inputToken in input:
stackToken <- stack.pop()
currentState, tokensToPush <- transition(currentState, inputToken, stackToken)
if currentState is not valid:
return false
for tokenToPush in tokensToPush.reverse():
stack.push(tokenToPush)
return (currentState in acceptingStates) and (stack contains only 'Z')
像这样定义转换：
function transition(state, input, stack):
if (input.type = +)
return (0, [input, stack])
else if (input.id = stack.id)
return (0, [])
else
return nope
您的标记有“类型”（+ 或 -）和“id”（“aaa”、“bbb”等）。
您必须小心使用任意转换函数，因为解决方案现在受到的约束更少，更有可能意外地不是上下文无关的。
下面的解决方案分三个阶段进行：
- 输入字符串被标记为序列和前缀
- 作为数组的标记化结果通过转换规则转换为 AST
- AST 转换为所需的 JSON 输出。
首先，定义标记、转换和标记化函数：
class Token{
constructor(vals, t_type){
this.vals = vals;
this.t_type = t_type
}
type_eq(t_type){
return this.t_type === t_type
}
static val_eq(t1, t2){
//check if two tokens objects t1 and t2 represent a +tag and a -tag
return t1.t_type === 'o_tag' && t2.t_type === 'c_tag' && t1.vals[1].vals[0] === t2.vals[1].vals[0]
}
}
var lexer = [[/^\-/, 'minus'], [/^\+/, 'plus'], [/^[a-z]+/, 'label']];
var transitions = [{'pattern':['plus', 'label'], 'result':'o_tag', 't_eq':false}, {'pattern':['minus', 'label'], 'result':'c_tag', 't_eq':false}, {'pattern':['o_tag', 'c_tag'], 'result':'block', 't_eq':true}, {'pattern':['o_tag', 'block', 'c_tag'], 'result':'block', 't_eq':true}, {'pattern':['block', 'block'], 'result':'block', 't_eq':false}]
function* tokenize(s){
//tokenize an input string `s`
//@yield Token object
while (s.length){
for (var [p, t] of lexer){
var m = s.match(p)
if (m){
yield (new Token([m[0]], t))
s = s.substring(m[0].length)
break
}
}
}
}
接下来，定义一个函数，该函数接受标记化字符串并在 stack 上运行迭代 shift-reduce 以自下而上构建 AST：
function pattern_match(stack, pattern){
//takes in the stack from `shift_reduce` and attempts to match `pattern` from the back
if (pattern.length > stack.length){
return false
}
return Array.from(Array(pattern.length).keys()).every(x => stack[stack.length-1-x].type_eq(pattern[pattern.length - 1-x]))
}
function shift_reduce(tokens){
//consumes `tokens` until empty and returns the resulting tree if in a valid state
var stack = []
while (true){
//per your comment, the line below displays the contents of the stack at each iteration
console.log(stack.map(x => x.t_type))
if (!stack.length){
//stack is empty, push a token on to it
stack.push(tokens.shift())
}
var f = false;
for (var {pattern:p, result:r, t_eq:tq} of transitions){
//try to match patterns from `transitions`
if (pattern_match(stack, p)){
var new_vals = p.map(_ => stack.pop()).reverse();
if (!tq || Token.val_eq(new_vals[0], new_vals[new_vals.length-1])){
//match found
f = true
stack.push((new Token(new_vals, r)))
break
}
else{
while (new_vals.length){
stack.push(new_vals.shift())
}
}
}
}
if (!f){
if (!tokens.length){
//no more tokens to consume, return root of the token tree.
if (stack.length > 1){
//stack was not reduced to a single token, thus an invalid state
throw new Error('invalid state')
}
return stack[0]
}
//no match found, push another token from `tokens` onto the stack
stack.push(tokens.shift())
}
}
}
最后，将 AST 转换为 JSON 的函数：
function* to_json(tree){
if (tree.vals.every(x => x.t_type === 'block')){
for (var i of tree.vals){
yield* to_json(i)
}
}
else{
yield {'type':tree.vals[0].vals[1].vals[0], ...(tree.vals.length === 2 ? {} : {'children':[...to_json(tree.vals[1])]})}
}
}
综合起来：
function to_tree(s){
var tokens = [...tokenize(s)] //get the tokenized string
var tree = shift_reduce(tokens) //build the AST from the tokens
var json_tree = [...to_json(tree)] //convert AST to JSON
return json_tree
}
console.log(to_tree('+eee-eee'))
console.log(to_tree('+aaa+bbb-bbb-aaa'))
console.log(to_tree('+bbb+aaa+ccc+eee-eee-ccc+ccc-ccc+ddd+ccc+eee-eee-ccc-ddd-aaa-bbb'))
输出：
[
{
"type": "eee"
}
]
[
{
"type": "aaa",
"children": [
{
"type": "bbb"
}
]
}
]
[
{
"type": "bbb",
"children": [
{
"type": "aaa",
"children": [
{
"type": "ccc",
"children": [
{
"type": "eee"
}
]
},
{
"type": "ccc"
},
{
"type": "ddd",
"children": [
{
"type": "ccc",
"children": [
{
"type": "eee"
}
]
}
]
}
]
}
]
}
]
首先我应该指出，我不是计算机科学家，也没有编写编译器代码的实际经验。因此，在实施甚至基本思想上可能存在明显的漏洞。但是，如果您想要一个发现这个有趣问题的日常工作程序员的想法，请看这里。
我们可以编写一个 pda 函数来简单地识别我们的语法，我们可以像这样使用它。 （这里我们只从 aaa 到 ccc，但你可以很容易地将它扩展到 eee 或其他。）
const {push: PUSH, pop: POP} = pda
const myParser = pda ('S', ['S'], [
// ^ ^
// | `----------------- accepting states
// +----------------------- initial state
// +----------------------------------------- current state
// | +-------------------------------- token
// | | +--------------------------- top of stack
// | | | +-------------------- new state
// | | | | +---------- stack action
// V V V V V
[ 'S', '+aaa', '', 'A', PUSH ('A') ],
[ 'S', '+bbb', '', 'B', PUSH ('B') ],
[ 'S', '+ccc', '', 'C', PUSH ('C') ],
[ 'A', '+aaa', '', 'A', PUSH ('A') ],
[ 'A', '-aaa', 'AA', 'A', POP ],
[ 'A', '-aaa', 'BA', 'B', POP ],
[ 'A', '-aaa', 'CA', 'C', POP ],
[ 'A', '-aaa', '', 'S', POP ],
[ 'A', '+bbb', '', 'B', PUSH ('B') ],
[ 'A', '+ccc', '', 'C', PUSH ('C') ],
[ 'B', '+aaa', '', 'A', PUSH ('A') ],
[ 'B', '+bbb', '', 'B', PUSH ('B') ],
[ 'B', '-bbb', 'AB', 'A', POP ],
[ 'B', '-bbb', 'BB', 'B', POP ],
[ 'B', '-bbb', 'CB', 'C', POP ],
[ 'B', '-bbb', '', 'S', POP ],
[ 'B', '+ccc', '', 'C', PUSH ('C') ],
[ 'C', '+aaa', '', 'A', PUSH ('A') ],
[ 'C', '+bbb', '', 'B', PUSH ('B') ],
[ 'C', '+ccc', '', 'C', PUSH ('C') ],
[ 'C', '-ccc', 'AC', 'A', POP ],
[ 'C', '-ccc', 'BC', 'B', POP ],
[ 'C', '-ccc', 'CC', 'C', POP ],
[ 'C', '-ccc', '', 'S', POP ],
])
我们会用它来测试一系列令牌，如下所示：
myParser (['+aaa', '-aaa']) //=> true
myParser (['+aaa', '-bbb']) //=> false
myParser (['+aaa', '+bbb', '+ccc', '-ccc', '+aaa', '-aaa', '-bbb', '-aaa']) //=> true
这不完全符合 PDA 的数学定义。我们没有符号来描绘堆栈的开始，我们测试堆栈的顶部两个值，而不仅仅是顶部的一个。但它相当接近。
然而，这只是报告一串标记是否在语法中。你想要的不止于此。您需要使用它来构建语法树。很难抽象地看出如何做到这一点。但是从您可以使用的解析中生成一系列事件非常容易。一种方法是在每次推送到堆栈时捕获新节点值并捕获堆栈中的每个弹出。
有了这个，我们可能会联系到这样的东西：
const forestBuilder = () => { // multiple-rooted, so a forest not a tree
const top = (xs) => xs [ xs .length - 1 ]
const forest = {children: []}
let stack = [forest]
return {
push: (name) => {
const node = {name: name, children: []}
top (stack) .children .push (node)
stack.push (node)
},
pop: () => stack.pop(),
end: () => forest.children
}
}
const {push, pop, end} = forestBuilder ()
push ('aaa')
push ('bbb')
pop ()
push ('ccc')
push ('aaa')
pop()
pop()
pop()
push ('bbb')
push ('aaa')
end()
这会产生这样的结果：
[
{
"name": "aaa",
"children": [
{
"name": "bbb",
"children": []
},
{
"name": "ccc",
"children": [
{
"name": "aaa",
"children": []
}
]
}
]
},
{
"name": "bbb",
"children": [
{
"name": "aaa",
"children": []
}
]
}
]
因此，如果我们为 pda 函数提供一些用于推送和弹出（也用于完成和错误）的事件侦听器，我们可能能够从一系列令牌构建您的树。
这是一种尝试：
console .clear ()
const pda = (() => {
const PUSH = Symbol(), POP = Symbol()
const id = (x) => x
return Object .assign (
(start, accepting, transitions) =>
(tokens = [], onPush = id, onPop = id, onComplete = id, onError = () => false) => {
let stack = []
let state = start
for (let token of tokens) {
const transition = transitions .find (([st, tk, top]) =>
st == state &&
tk == token &&
(top .length == 0 || stack .slice (-top.length) .join ('') == top)
)
if (!transition) {
return onError (token, stack)
}
const [, , , nst, action] = transition
state = nst
action (stack)
if (action [PUSH]) {onPush (token)}
if (action [POP]) {onPop ()}
}
return onComplete (!!accepting .includes (state))
},{
push: (token) => Object.assign((stack) => stack .push (token), {[PUSH]: true}),
pop: Object.assign ((stack) => stack .pop (), {[POP]: true}),
}
)
})()
const {push: PUSH, pop: POP} = pda
const myParser = pda ('S', ['S'], [
// ^ ^
// | `----------------- accepting states
// +----------------------- initial state
// +----------------------------------------- current state
// | +-------------------------------- token
// | | +--------------------------- top of stack
// | | | +-------------------- new state
// | | | | +---------- stack action
// V V V V V
[ 'S', '+aaa', '', 'A', PUSH ('A') ],
[ 'S', '+bbb', '', 'B', PUSH ('B') ],
[ 'S', '+ccc', '', 'C', PUSH ('C') ],
[ 'A', '+aaa', '', 'A', PUSH ('A') ],
[ 'A', '-aaa', 'AA', 'A', POP ],
[ 'A', '-aaa', 'BA', 'B', POP ],
[ 'A', '-aaa', 'CA', 'C', POP ],
[ 'A', '-aaa', '', 'S', POP ],
[ 'A', '+bbb', '', 'B', PUSH ('B') ],
[ 'A', '+ccc', '', 'C', PUSH ('C') ],
[ 'B', '+aaa', '', 'A', PUSH ('A') ],
[ 'B', '+bbb', '', 'B', PUSH ('B') ],
[ 'B', '-bbb', 'AB', 'A', POP ],
[ 'B', '-bbb', 'BB', 'B', POP ],
[ 'B', '-bbb', 'CB', 'C', POP ],
[ 'B', '-bbb', '', 'S', POP ],
[ 'B', '+ccc', '', 'C', PUSH ('C') ],
[ 'C', '+aaa', '', 'A', PUSH ('A') ],
[ 'C', '+bbb', '', 'B', PUSH ('B') ],
[ 'C', '+ccc', '', 'C', PUSH ('C') ],
[ 'C', '-ccc', 'AC', 'A', POP ],
[ 'C', '-ccc', 'BC', 'B', POP ],
[ 'C', '-ccc', 'CC', 'C', POP ],
[ 'C', '-ccc', '', 'S', POP ],
])
const forestBuilder = () => {
const top = (xs) => xs [ xs .length - 1 ]
const forest = {children: []}
let stack = [forest]
return {
push: (name) => {
const node = {name: name .slice (1), children: []}
top (stack) .children .push (node)
stack.push (node)
},
pop: () => stack.pop(),
end: () => forest.children
}
}
const {push, pop, end} = forestBuilder ()
console .log (myParser (
["+ccc", "-ccc", "+aaa", "+bbb", "-bbb", "-aaa", "+bbb", "+aaa", "+ccc", "+bbb", "-bbb", "-ccc", "+ccc", "-ccc", "+aaa", "+ccc", "+ccc", "-ccc", "-ccc", "-aaa", "-aaa", "-bbb"],
push,
pop,
(accepted) => accepted ? end () : 'Error: ill-formed',
(token, stack) => `Error: token = '${token}', stack = ${JSON.stringify(stack)}`
))
.as-console-wrapper {max-height: 100% !important; top: 0}
有很多方法可以实现。也许打开事件不仅应该包含令牌，还应该包含压入堆栈的值。可能有一种从更具声明性的语法生成 table 转换的好方法。我们可能需要一个不同版本的堆栈操作列，一个接受字符串而不是接受函数的版本。等等。但这仍然可能是一个不错的开始。
无法创建用于生成此树数据结构的 PDA，因为：
- PDA 具有有限数量的状态和堆栈符号，并且没有输出磁带。然而，这个 PDA 应该能够以某种方式表示（并提供）的树木数量是无限的。如果我们考虑面向对象结构中树的节点，那么可能有无数个不同的节点，因为节点的身份也由它所拥有的引用决定。这与 PDA 具有的有限符号集相冲突。如果我们不选择面向对象的输出，那么我们将一无所获：输入已经是树的序列化表示。
- 即使您向该自动机添加输出磁带，使其成为 rewrite system，您也不会获得太多收益，因为输入已经以序列化格式表示树。如果我理解正确的话，你对序列化输出不感兴趣（比如 JSON，这很简单，因为输出顺序与输入顺序相同），而是结构化输出（JavaScript-like objects） .
因此，正如其他人也指出的那样，我们需要以某种方式放宽规则。我们可以想到几种（组合）方法来做到这一点：
- 允许无限数量的状态，或者
- 允许无限堆叠字母表，或者
- 允许 PDA 访问栈顶元素以外的更多内容
- 让转换 table 引用堆栈顶部元素的特定 属性 ，而不是整个元素 - 允许其他属性的无限可能性堆叠元素，同时确保此特定属性的值属于有限集。
- 在 PDA 之外建造树
- ...解决PDA不兼容生成结构化树的需求的其他措施
其中一些选项会推断出无限转换 table，因此在这种情况下它不能是 table，但可以是函数。
实施选择
1。对于通用引擎
考虑到您对树构建的关注，以及对“堆栈、状态和转换”的要求，我选择了以下实现选项，有时还进行了简化：
- 我从上面的列表中选择策略 4
- 通用引擎将自己创建树。所以它只是在有限的意义上是通用的。它只能验证和生成树。
- 它将（仅）采用转换 table 作为配置输入
- 它只有两个状态（布尔值），表示到目前为止是否一切正常。
- 只有在转换中没有匹配的转换时，OK 状态才能从 true 变为 false table
- 一旦 OK 状态为假，引擎甚至不会尝试寻找转换，而只会忽略任何进一步的输入。
- 因此，转换 table 将不包括当前状态和未来状态部分，因为它们都暗示为真（即“OK”）。
- 树将在堆栈中编码。堆栈元素的
data 属性 将是用于识别转换的特殊属性。每个堆栈元素的 children 属性将用于定义树，并且不被视为过渡 table 目标的堆栈字母表的一部分。
- 堆栈从一个元素开始。它的
children 属性将是引擎的输出。在每一步都可以查询此输出，因为此元素永远不会从堆栈中删除。
- 输入符号不能包含空字符串，空字符串是为表示输入流结束而保留的。这允许引擎给出反馈是否是结束输入流的有效时刻。
- 当指示输入结束时，引擎要求其堆栈为“空”（只有 1 个条目）。
- 我假设输入符号不包含 spaces：space 在转换查找算法中用作定界符
- 给定的转换 table 被转换为（散列）映射，以允许在给定当前状态和堆栈顶部的数据的情况下进行快速查找。此映射中的键是输入和堆栈数据值的串联，正是在这里选择 space 作为分隔符。如果 space 是输入符号中的有效字符，则应选择另一种编码机制来序列化此密钥对（例如 JSON），但我想保持简单。
- 引擎不需要获取输入符号集，也不需要获取堆栈符号集作为配置输入，因为这些将从转换 table.
中隐含
- 引擎的初始状态设置为 OK（可以通过简单的 属性 赋值进行不同的设置，但那将是无用的，因为它会忽略输入）
2。对于特定的 +/- 输入格式
解决方案中更具体的部分涉及您在问题中给出的实际输入格式。一个函数将类型集转换为转换 table，另一个函数将根据“+”和“-”字符标记输入，但没有任何验证（没有符号检查，也没有符号长度检查，. ..)，因为无论如何这都会在调用引擎时显示为错误。
输入中的任何白色 space 都将被忽略。
实施
// 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));
我同意@trincot 的回答（除了他声称它不是 PDA）。
我不确定复杂的模式，但你拥有的简单模式对于构建机器来说几乎是微不足道的。它是 DCFG（确定性上下文无关文法），即它是正则表达式和 Dyck（括号匹配）机的交集。所有 DCFG 都对 PDA 进行编码。因此，我不同意他说这不是 PDA。
它是一个正则表达式，因为你的“标记”（括号）不是单个字符长的，所以你需要正确的正则表达式将那些字符序列变成单个符号标记。 +aaa -> 一个标记，例如 '(', -aaa -> 另一个标记 ')', +bbb -> 另一个 '[', ... 注意我为标记选择的字符不是任意的（尽管它们可以be) 而是帮助您将其可视化为括号匹配。注意它们是如何配对的。
您的标记列表将是有限的（您的字符串，虽然没有限制，但仍然是有限的）。并且，将有两种（或三种，类型的令牌）。将有左括号（括号等）和右括号，以及两者都没有的东西（即不需要匹配）。在左括号中，您将某些东西压入堆栈。在右括号中，弹出堆栈。在两者都不是的情况下，您要么忽略堆栈，要么压入和弹出两者——两种模型都有效。
运行机器的 FSM 每对都需要一个状态。在推送时，您进入该状态，它会告诉您需要看到什么样的令牌才能弹出它。如果您看到不同的弹出令牌，则表明您出错了。
现在，只要你的token类型很容易分为这三种token，问题就小了。如果你的标记，例如，如果你正在寻找没有中点标记的回文，（即一些标记可以是左括号和右括号，你不能从左上下文中分辨它是什么），问题变得不确定，您将需要实现一个 GLR 类型的解析器，该解析器保留仍然是候选的备选方案的解析林（如果输入不明确，最终会得到不止一棵可能的树）。
但是，我认为如果您尝试解析 AST，就不会遇到这个问题。你真的有一个非常简化的 SLR 版本（最基本的 LR 解析算法）在 parens 级别。并且序列到正则表达式的转换也可能是微不足道的，因为它们只是一组固定的字符串。
我们希望创建一个 下推 自动机 (PDA)，它使用以下“字母表”（字母表是指一组独特的符号 strings/keys）：
+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
鉴于此字母表和这些示例树，问题是您将如何编写通用下推自动机来解析这些树。规则是：
- 任何字母对（open/close 对）都可以有任意数量的嵌套子项，并且嵌套哪些字母对作为子项并不重要。
如何在 JavaScript 中编写下推自动机来将字符串解析为 AST？
我的意思是，实现必须确实有 stack、states 和 transitions。我的意思是，不实现临时解析器，甚至不实现递归下降解析器。这应该是一个迭代的 while 循环，以某种方式循环转换，而不是使用递归。
输出应该是一个非常简单的“AST”，看起来像这样（对于 +aaa+bbb-bbb-aaa 树）：
{
"type": "aaa",
"children": [
{
"type": "bbb",
"children": []
}
]
}
我想知道如何构建 PDA，以便在我使用自定义编程语言的特定情况下，转换我正在工作的相当复杂的 AST，并将其解析为对象图。这个问题太复杂了，无法在 SO 上写出来，也很难简化，这就是为什么我在这里询问 JavaScript.
中非常基本的 PDA 实现我很想知道您在执行 PDA 算法时如何跟踪每个分支点的上下文以及转换是什么样的。
注意：我听说过/看到过偶尔在这里和那里提到的“2 态”PDA。听起来您有一种状态可以进行计算，还有一种“最终”状态。甚至可能只是一个 single state。如果可以像这样做，那就太好了。如果没有，不用担心。
如果有必要，你可以先写一个Context Free Grammar，然后用它来动态构造一个PDA，但这里的关键问题是PDA在技术上是如何实现的。我认为手动编写每个转换函数可能/直接，但我不完全确定。无论哪种方式都适合我。
在伪代码中，DPDA 可以这样实现：
transitions <- map from (state, char, char) to (state, char[0-2])
stack <- stack initialized with a sentinel value 'Z'
input <- string of tokens to parse
currentState <- initial state
for each inputCharacter in input:
stackCharacter <- stack.pop()
currentState, charsToPush <- transitions[(currentState, inputCharacter, stackCharacter)]
if currentState is not valid:
return false
for charToPush in charsToPush.reverse():
stack.push(charToPush)
return (currentState in acceptingStates) and (stack contains only 'Z')
PDA如括号匹配是这样指定的：
transitions <- {
(0, '(', 'Z') -> (0, "(Z"),
(0, '(', '(') -> (0, "(("),
(0, ')', 'Z') -> nope,
(0, ')', '(') -> (0, ""),
}
acceptingStates <- [0]
initialState <- 0
请注意，以上是确定性的。一般的 PDA 是不确定的，并不是所有的上下文无关语言都可以由 DPDA 决定。您可以，并且必须注意指定转换的方式。
为了使其更通用（非确定性），转换映射需要映射到（state，char[]）元组的列表，而不仅仅是一个元组；循环中的每一步都需要考虑所有匹配的元组，而不仅仅是一个。
有帮助吗？
对于你的语法，你的标记是这些“+aaa”、“-aaa”的东西。您的字母表是有限的但非常大，因此您不希望必须在过渡图中指定所有内容。所以这是你必须做出的决定：你想要一个纯 PDA（完全指定的地图）还是你想要编写一个类似 PDA 的东西但不完全是 PDA 来避免这种情况？
如果是后者，您想在循环中添加一个与 + 和 - 标记的标识相匹配的检查。此时您还不如编写自己的代码，因为创建一个可以处理所有事情的通用解析器是一项大量的工作。只为您的特定需求编写解析器会更容易。
这就是人们创建像 flap.js 这样的库的原因，因为这些东西很复杂。
详细说明我的评论，如果您将转换函数设为任意而不是地图，您可以用这种方式表达您的语言。
transition <- arbitrary function taking input (state, token, token) and output (state, token[0-2])
stack <- stack initialized with a sentinel token 'Z'
input <- string of tokens to parse
currentState <- initial state
for each inputToken in input:
stackToken <- stack.pop()
currentState, tokensToPush <- transition(currentState, inputToken, stackToken)
if currentState is not valid:
return false
for tokenToPush in tokensToPush.reverse():
stack.push(tokenToPush)
return (currentState in acceptingStates) and (stack contains only 'Z')
像这样定义转换：
function transition(state, input, stack):
if (input.type = +)
return (0, [input, stack])
else if (input.id = stack.id)
return (0, [])
else
return nope
您的标记有“类型”（+ 或 -）和“id”（“aaa”、“bbb”等）。
您必须小心使用任意转换函数，因为解决方案现在受到的约束更少，更有可能意外地不是上下文无关的。
下面的解决方案分三个阶段进行：
- 输入字符串被标记为序列和前缀
- 作为数组的标记化结果通过转换规则转换为 AST
- AST 转换为所需的 JSON 输出。
首先，定义标记、转换和标记化函数：
class Token{
constructor(vals, t_type){
this.vals = vals;
this.t_type = t_type
}
type_eq(t_type){
return this.t_type === t_type
}
static val_eq(t1, t2){
//check if two tokens objects t1 and t2 represent a +tag and a -tag
return t1.t_type === 'o_tag' && t2.t_type === 'c_tag' && t1.vals[1].vals[0] === t2.vals[1].vals[0]
}
}
var lexer = [[/^\-/, 'minus'], [/^\+/, 'plus'], [/^[a-z]+/, 'label']];
var transitions = [{'pattern':['plus', 'label'], 'result':'o_tag', 't_eq':false}, {'pattern':['minus', 'label'], 'result':'c_tag', 't_eq':false}, {'pattern':['o_tag', 'c_tag'], 'result':'block', 't_eq':true}, {'pattern':['o_tag', 'block', 'c_tag'], 'result':'block', 't_eq':true}, {'pattern':['block', 'block'], 'result':'block', 't_eq':false}]
function* tokenize(s){
//tokenize an input string `s`
//@yield Token object
while (s.length){
for (var [p, t] of lexer){
var m = s.match(p)
if (m){
yield (new Token([m[0]], t))
s = s.substring(m[0].length)
break
}
}
}
}
接下来，定义一个函数，该函数接受标记化字符串并在 stack 上运行迭代 shift-reduce 以自下而上构建 AST：
function pattern_match(stack, pattern){
//takes in the stack from `shift_reduce` and attempts to match `pattern` from the back
if (pattern.length > stack.length){
return false
}
return Array.from(Array(pattern.length).keys()).every(x => stack[stack.length-1-x].type_eq(pattern[pattern.length - 1-x]))
}
function shift_reduce(tokens){
//consumes `tokens` until empty and returns the resulting tree if in a valid state
var stack = []
while (true){
//per your comment, the line below displays the contents of the stack at each iteration
console.log(stack.map(x => x.t_type))
if (!stack.length){
//stack is empty, push a token on to it
stack.push(tokens.shift())
}
var f = false;
for (var {pattern:p, result:r, t_eq:tq} of transitions){
//try to match patterns from `transitions`
if (pattern_match(stack, p)){
var new_vals = p.map(_ => stack.pop()).reverse();
if (!tq || Token.val_eq(new_vals[0], new_vals[new_vals.length-1])){
//match found
f = true
stack.push((new Token(new_vals, r)))
break
}
else{
while (new_vals.length){
stack.push(new_vals.shift())
}
}
}
}
if (!f){
if (!tokens.length){
//no more tokens to consume, return root of the token tree.
if (stack.length > 1){
//stack was not reduced to a single token, thus an invalid state
throw new Error('invalid state')
}
return stack[0]
}
//no match found, push another token from `tokens` onto the stack
stack.push(tokens.shift())
}
}
}
最后，将 AST 转换为 JSON 的函数：
function* to_json(tree){
if (tree.vals.every(x => x.t_type === 'block')){
for (var i of tree.vals){
yield* to_json(i)
}
}
else{
yield {'type':tree.vals[0].vals[1].vals[0], ...(tree.vals.length === 2 ? {} : {'children':[...to_json(tree.vals[1])]})}
}
}
综合起来：
function to_tree(s){
var tokens = [...tokenize(s)] //get the tokenized string
var tree = shift_reduce(tokens) //build the AST from the tokens
var json_tree = [...to_json(tree)] //convert AST to JSON
return json_tree
}
console.log(to_tree('+eee-eee'))
console.log(to_tree('+aaa+bbb-bbb-aaa'))
console.log(to_tree('+bbb+aaa+ccc+eee-eee-ccc+ccc-ccc+ddd+ccc+eee-eee-ccc-ddd-aaa-bbb'))
输出：
[
{
"type": "eee"
}
]
[
{
"type": "aaa",
"children": [
{
"type": "bbb"
}
]
}
]
[
{
"type": "bbb",
"children": [
{
"type": "aaa",
"children": [
{
"type": "ccc",
"children": [
{
"type": "eee"
}
]
},
{
"type": "ccc"
},
{
"type": "ddd",
"children": [
{
"type": "ccc",
"children": [
{
"type": "eee"
}
]
}
]
}
]
}
]
}
]
首先我应该指出，我不是计算机科学家，也没有编写编译器代码的实际经验。因此，在实施甚至基本思想上可能存在明显的漏洞。但是，如果您想要一个发现这个有趣问题的日常工作程序员的想法，请看这里。
我们可以编写一个 pda 函数来简单地识别我们的语法，我们可以像这样使用它。 （这里我们只从 aaa 到 ccc，但你可以很容易地将它扩展到 eee 或其他。）
const {push: PUSH, pop: POP} = pda
const myParser = pda ('S', ['S'], [
// ^ ^
// | `----------------- accepting states
// +----------------------- initial state
// +----------------------------------------- current state
// | +-------------------------------- token
// | | +--------------------------- top of stack
// | | | +-------------------- new state
// | | | | +---------- stack action
// V V V V V
[ 'S', '+aaa', '', 'A', PUSH ('A') ],
[ 'S', '+bbb', '', 'B', PUSH ('B') ],
[ 'S', '+ccc', '', 'C', PUSH ('C') ],
[ 'A', '+aaa', '', 'A', PUSH ('A') ],
[ 'A', '-aaa', 'AA', 'A', POP ],
[ 'A', '-aaa', 'BA', 'B', POP ],
[ 'A', '-aaa', 'CA', 'C', POP ],
[ 'A', '-aaa', '', 'S', POP ],
[ 'A', '+bbb', '', 'B', PUSH ('B') ],
[ 'A', '+ccc', '', 'C', PUSH ('C') ],
[ 'B', '+aaa', '', 'A', PUSH ('A') ],
[ 'B', '+bbb', '', 'B', PUSH ('B') ],
[ 'B', '-bbb', 'AB', 'A', POP ],
[ 'B', '-bbb', 'BB', 'B', POP ],
[ 'B', '-bbb', 'CB', 'C', POP ],
[ 'B', '-bbb', '', 'S', POP ],
[ 'B', '+ccc', '', 'C', PUSH ('C') ],
[ 'C', '+aaa', '', 'A', PUSH ('A') ],
[ 'C', '+bbb', '', 'B', PUSH ('B') ],
[ 'C', '+ccc', '', 'C', PUSH ('C') ],
[ 'C', '-ccc', 'AC', 'A', POP ],
[ 'C', '-ccc', 'BC', 'B', POP ],
[ 'C', '-ccc', 'CC', 'C', POP ],
[ 'C', '-ccc', '', 'S', POP ],
])
我们会用它来测试一系列令牌，如下所示：
myParser (['+aaa', '-aaa']) //=> true
myParser (['+aaa', '-bbb']) //=> false
myParser (['+aaa', '+bbb', '+ccc', '-ccc', '+aaa', '-aaa', '-bbb', '-aaa']) //=> true
这不完全符合 PDA 的数学定义。我们没有符号来描绘堆栈的开始，我们测试堆栈的顶部两个值，而不仅仅是顶部的一个。但它相当接近。
然而，这只是报告一串标记是否在语法中。你想要的不止于此。您需要使用它来构建语法树。很难抽象地看出如何做到这一点。但是从您可以使用的解析中生成一系列事件非常容易。一种方法是在每次推送到堆栈时捕获新节点值并捕获堆栈中的每个弹出。
有了这个，我们可能会联系到这样的东西：
const forestBuilder = () => { // multiple-rooted, so a forest not a tree
const top = (xs) => xs [ xs .length - 1 ]
const forest = {children: []}
let stack = [forest]
return {
push: (name) => {
const node = {name: name, children: []}
top (stack) .children .push (node)
stack.push (node)
},
pop: () => stack.pop(),
end: () => forest.children
}
}
const {push, pop, end} = forestBuilder ()
push ('aaa')
push ('bbb')
pop ()
push ('ccc')
push ('aaa')
pop()
pop()
pop()
push ('bbb')
push ('aaa')
end()
这会产生这样的结果：
[
{
"name": "aaa",
"children": [
{
"name": "bbb",
"children": []
},
{
"name": "ccc",
"children": [
{
"name": "aaa",
"children": []
}
]
}
]
},
{
"name": "bbb",
"children": [
{
"name": "aaa",
"children": []
}
]
}
]
因此，如果我们为 pda 函数提供一些用于推送和弹出（也用于完成和错误）的事件侦听器，我们可能能够从一系列令牌构建您的树。
这是一种尝试：
console .clear ()
const pda = (() => {
const PUSH = Symbol(), POP = Symbol()
const id = (x) => x
return Object .assign (
(start, accepting, transitions) =>
(tokens = [], onPush = id, onPop = id, onComplete = id, onError = () => false) => {
let stack = []
let state = start
for (let token of tokens) {
const transition = transitions .find (([st, tk, top]) =>
st == state &&
tk == token &&
(top .length == 0 || stack .slice (-top.length) .join ('') == top)
)
if (!transition) {
return onError (token, stack)
}
const [, , , nst, action] = transition
state = nst
action (stack)
if (action [PUSH]) {onPush (token)}
if (action [POP]) {onPop ()}
}
return onComplete (!!accepting .includes (state))
},{
push: (token) => Object.assign((stack) => stack .push (token), {[PUSH]: true}),
pop: Object.assign ((stack) => stack .pop (), {[POP]: true}),
}
)
})()
const {push: PUSH, pop: POP} = pda
const myParser = pda ('S', ['S'], [
// ^ ^
// | `----------------- accepting states
// +----------------------- initial state
// +----------------------------------------- current state
// | +-------------------------------- token
// | | +--------------------------- top of stack
// | | | +-------------------- new state
// | | | | +---------- stack action
// V V V V V
[ 'S', '+aaa', '', 'A', PUSH ('A') ],
[ 'S', '+bbb', '', 'B', PUSH ('B') ],
[ 'S', '+ccc', '', 'C', PUSH ('C') ],
[ 'A', '+aaa', '', 'A', PUSH ('A') ],
[ 'A', '-aaa', 'AA', 'A', POP ],
[ 'A', '-aaa', 'BA', 'B', POP ],
[ 'A', '-aaa', 'CA', 'C', POP ],
[ 'A', '-aaa', '', 'S', POP ],
[ 'A', '+bbb', '', 'B', PUSH ('B') ],
[ 'A', '+ccc', '', 'C', PUSH ('C') ],
[ 'B', '+aaa', '', 'A', PUSH ('A') ],
[ 'B', '+bbb', '', 'B', PUSH ('B') ],
[ 'B', '-bbb', 'AB', 'A', POP ],
[ 'B', '-bbb', 'BB', 'B', POP ],
[ 'B', '-bbb', 'CB', 'C', POP ],
[ 'B', '-bbb', '', 'S', POP ],
[ 'B', '+ccc', '', 'C', PUSH ('C') ],
[ 'C', '+aaa', '', 'A', PUSH ('A') ],
[ 'C', '+bbb', '', 'B', PUSH ('B') ],
[ 'C', '+ccc', '', 'C', PUSH ('C') ],
[ 'C', '-ccc', 'AC', 'A', POP ],
[ 'C', '-ccc', 'BC', 'B', POP ],
[ 'C', '-ccc', 'CC', 'C', POP ],
[ 'C', '-ccc', '', 'S', POP ],
])
const forestBuilder = () => {
const top = (xs) => xs [ xs .length - 1 ]
const forest = {children: []}
let stack = [forest]
return {
push: (name) => {
const node = {name: name .slice (1), children: []}
top (stack) .children .push (node)
stack.push (node)
},
pop: () => stack.pop(),
end: () => forest.children
}
}
const {push, pop, end} = forestBuilder ()
console .log (myParser (
["+ccc", "-ccc", "+aaa", "+bbb", "-bbb", "-aaa", "+bbb", "+aaa", "+ccc", "+bbb", "-bbb", "-ccc", "+ccc", "-ccc", "+aaa", "+ccc", "+ccc", "-ccc", "-ccc", "-aaa", "-aaa", "-bbb"],
push,
pop,
(accepted) => accepted ? end () : 'Error: ill-formed',
(token, stack) => `Error: token = '${token}', stack = ${JSON.stringify(stack)}`
))
.as-console-wrapper {max-height: 100% !important; top: 0}
有很多方法可以实现。也许打开事件不仅应该包含令牌，还应该包含压入堆栈的值。可能有一种从更具声明性的语法生成 table 转换的好方法。我们可能需要一个不同版本的堆栈操作列，一个接受字符串而不是接受函数的版本。等等。但这仍然可能是一个不错的开始。
无法创建用于生成此树数据结构的 PDA，因为：
- PDA 具有有限数量的状态和堆栈符号，并且没有输出磁带。然而，这个 PDA 应该能够以某种方式表示（并提供）的树木数量是无限的。如果我们考虑面向对象结构中树的节点，那么可能有无数个不同的节点，因为节点的身份也由它所拥有的引用决定。这与 PDA 具有的有限符号集相冲突。如果我们不选择面向对象的输出，那么我们将一无所获：输入已经是树的序列化表示。
- 即使您向该自动机添加输出磁带，使其成为 rewrite system，您也不会获得太多收益，因为输入已经以序列化格式表示树。如果我理解正确的话，你对序列化输出不感兴趣（比如 JSON，这很简单，因为输出顺序与输入顺序相同），而是结构化输出（JavaScript-like objects） .
因此，正如其他人也指出的那样，我们需要以某种方式放宽规则。我们可以想到几种（组合）方法来做到这一点：
- 允许无限数量的状态，或者
- 允许无限堆叠字母表，或者
- 允许 PDA 访问栈顶元素以外的更多内容
- 让转换 table 引用堆栈顶部元素的特定 属性 ，而不是整个元素 - 允许其他属性的无限可能性堆叠元素，同时确保此特定属性的值属于有限集。
- 在 PDA 之外建造树
- ...解决PDA不兼容生成结构化树的需求的其他措施
其中一些选项会推断出无限转换 table，因此在这种情况下它不能是 table，但可以是函数。
实施选择
1。对于通用引擎
考虑到您对树构建的关注，以及对“堆栈、状态和转换”的要求，我选择了以下实现选项，有时还进行了简化：
- 我从上面的列表中选择策略 4
- 通用引擎将自己创建树。所以它只是在有限的意义上是通用的。它只能验证和生成树。
- 它将（仅）采用转换 table 作为配置输入
- 它只有两个状态（布尔值），表示到目前为止是否一切正常。
- 只有在转换中没有匹配的转换时，OK 状态才能从 true 变为 false table
- 一旦 OK 状态为假，引擎甚至不会尝试寻找转换，而只会忽略任何进一步的输入。
- 因此，转换 table 将不包括当前状态和未来状态部分，因为它们都暗示为真（即“OK”）。
- 树将在堆栈中编码。堆栈元素的
data属性 将是用于识别转换的特殊属性。每个堆栈元素的children属性将用于定义树，并且不被视为过渡 table 目标的堆栈字母表的一部分。 - 堆栈从一个元素开始。它的
children属性将是引擎的输出。在每一步都可以查询此输出，因为此元素永远不会从堆栈中删除。 - 输入符号不能包含空字符串，空字符串是为表示输入流结束而保留的。这允许引擎给出反馈是否是结束输入流的有效时刻。
- 当指示输入结束时，引擎要求其堆栈为“空”（只有 1 个条目）。
- 我假设输入符号不包含 spaces：space 在转换查找算法中用作定界符
- 给定的转换 table 被转换为（散列）映射，以允许在给定当前状态和堆栈顶部的数据的情况下进行快速查找。此映射中的键是输入和堆栈数据值的串联，正是在这里选择 space 作为分隔符。如果 space 是输入符号中的有效字符，则应选择另一种编码机制来序列化此密钥对（例如 JSON），但我想保持简单。
- 引擎不需要获取输入符号集，也不需要获取堆栈符号集作为配置输入，因为这些将从转换 table. 中隐含
- 引擎的初始状态设置为 OK（可以通过简单的 属性 赋值进行不同的设置，但那将是无用的，因为它会忽略输入）
2。对于特定的 +/- 输入格式
解决方案中更具体的部分涉及您在问题中给出的实际输入格式。一个函数将类型集转换为转换 table，另一个函数将根据“+”和“-”字符标记输入，但没有任何验证（没有符号检查，也没有符号长度检查，. ..)，因为无论如何这都会在调用引擎时显示为错误。
输入中的任何白色 space 都将被忽略。
实施
// 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));
我同意@trincot 的回答（除了他声称它不是 PDA）。
我不确定复杂的模式，但你拥有的简单模式对于构建机器来说几乎是微不足道的。它是 DCFG（确定性上下文无关文法），即它是正则表达式和 Dyck（括号匹配）机的交集。所有 DCFG 都对 PDA 进行编码。因此，我不同意他说这不是 PDA。
它是一个正则表达式，因为你的“标记”（括号）不是单个字符长的，所以你需要正确的正则表达式将那些字符序列变成单个符号标记。 +aaa -> 一个标记，例如 '(', -aaa -> 另一个标记 ')', +bbb -> 另一个 '[', ... 注意我为标记选择的字符不是任意的（尽管它们可以be) 而是帮助您将其可视化为括号匹配。注意它们是如何配对的。
您的标记列表将是有限的（您的字符串，虽然没有限制，但仍然是有限的）。并且，将有两种（或三种，类型的令牌）。将有左括号（括号等）和右括号，以及两者都没有的东西（即不需要匹配）。在左括号中，您将某些东西压入堆栈。在右括号中，弹出堆栈。在两者都不是的情况下，您要么忽略堆栈，要么压入和弹出两者——两种模型都有效。
运行机器的 FSM 每对都需要一个状态。在推送时，您进入该状态，它会告诉您需要看到什么样的令牌才能弹出它。如果您看到不同的弹出令牌，则表明您出错了。
现在，只要你的token类型很容易分为这三种token，问题就小了。如果你的标记，例如，如果你正在寻找没有中点标记的回文，（即一些标记可以是左括号和右括号，你不能从左上下文中分辨它是什么），问题变得不确定，您将需要实现一个 GLR 类型的解析器，该解析器保留仍然是候选的备选方案的解析林（如果输入不明确，最终会得到不止一棵可能的树）。
但是，我认为如果您尝试解析 AST，就不会遇到这个问题。你真的有一个非常简化的 SLR 版本（最基本的 LR 解析算法）在 parens 级别。并且序列到正则表达式的转换也可能是微不足道的，因为它们只是一组固定的字符串。