正式语言理论 - 自动机

Question

我想知道正式语言。我有一种解析器：它读取类似XML的序列化树结构，并将其变成一个多中性阵列。

我的观点在于所使用的算法和不同类型的自动机（State Machines Turing Machines堆栈...）之间的相似之处。

因此，问题是：我在这里暗示使用哪种自动机，以及适合哪种形式语言？递归呢？

我的意思是“我隐式使用的自动机”是“这是完成相同工作的最小自动机”。

这是完整的来源：

$单词; // XML标签的数组'u003Ctag> '，'u003C/tag> '和简单的文本内容

$ tree = array（'type'=>'root'，'sub'=> array（））;

$ ptree = array（＆$ tree）;

$ deep = 0;

foreach（$单词为$ elem）{

if ( preg_match($openTag, $elem) ) { // $elem is an open tag

    $pTree[$deep++]['sub'][] = array( // we add an element to the multidim array
        'type' => 'block',
        'content' => $elem,
        'sub' => array()
    );

    $size = sizeof($pTree[$deep - 1]['sub']);
    $pTree[$deep] = &$pTree[$deep - 1]['sub'][$size - 1]; // down one level in the tree

} elseif ( preg_match($closeTag, $elem) ) { // it is a close tag

    $deep--; // up in the tree 

} else { // simple element

    $pTree[$deep]['sub'][] = array(
        'type' => 'simple',
        'content' => $elem
    );

}

}

Answer 1

请再次查看您的问题。您指的是 $words 变量，这不是您的示例。另外，没有代码，不知道正在做什么，很难回答您。

从变量的名称来看 $deep, ，可能不是国家。自动机中的状态是特定于自动机的集合的元素； $deep 看起来它可以包含一个深度，任何积极的整数。同样，没有代码很难说出。

无论如何，如果您没有将代码设计为实现，则可能根本不会“隐式使用”任何自动机。

您的简单类似XML的文件可能可以通过确定性的堆栈计算机识别，也可以通过确定性的无上下文语法生成，使其在Chomsky层次结构中成为2型。再一次，这只是一个猜测，“ XML样的序列化树结构”对于任何形式主义而言都太模糊了。

简而言之，如果您想使用任何形式的理论，请更正式地做您的问题。

---

编辑（查看代码后）：

您正在建一棵树。对于自动机来说，这是遥不可及的（至少是“标准”）。有限的自动机仅适用于输入和状态，堆栈机添加了堆栈，图灵机具有可以在两个方向上移动的读写胶带。

自动机的“输出”是一个简单的“是”（接受）或“否”（不接受，或无限循环）。 （可以将图灵机定义为在其磁带上提供更多的输出。）我可以回答的最好的“最小自动机可以完成相同的工作”，这是您的语言可以被堆栈计算机接受；但是它的工作方式会大不相同，不会给您树木。

但是，您可能会调查 语法 - 另一个介绍概念的正式语言结构 解析树。您在这里做的是用自上而下的解析器创建这样的解析树。