2

我想知道形式语言。我有一种解析器：它读取类似 xml 的序列化树结构并将其转换为多维数组。

我的观点是所使用的算法与不同类型的自动机（状态机图灵机堆栈......）之间的相似之处。

所以问题是：我在这里隐含使用的自动机是什么，它适合哪些正式的语言家族？什么是递归？

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

这是完整的来源：

$words; // an array of XML tag '<tag>', '</tag>' and simple text content
$tree = array(
    'type' => 'root',
    'sub' => array()
);
$pTree = array(&$tree);
$deep = 0;

foreach ( $words as $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
        );
        
    }
4

1 回答 1

4

请再看看你的问题。您指的是一个$words变量，该变量不在您的示例中。此外，没有代码，不知道正在做什么很难回答你。

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

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

您简单的类似 xml 的文件可能会被确定性堆栈机器识别，或者由确定性上下文无关语法生成，从而使它们成为 Chomsky 层次结构中的 Type-2。再一次，这只是一种猜测，“类似 xml 的序列化树结构”对于任何形式的形式来说都太模糊了。

简而言之，如果你想使用任何正式的理论，请更正式地表达你的问题。

编辑（看到代码后）：

你正在建造一棵树。这对于自动机（至少是“标准”自动机）来说是遥不可及的。有限自动机只在输入和状态下工作，堆栈机器向其中添加堆栈，图灵机有一个可以双向移动的读写磁带。

自动机的“输出”是简单的“是”（接受）或“否”（不接受，或无限循环）。（图灵机可以被定义为在他们的磁带上提供更多的输出。）我能回答的“这是做同样工作的最小自动机”的最佳答案是你的语言可以被堆栈机器接受；但它的工作方式会非常不同，不会给你树。

但是，您可能会研究语法——另一种引入解析树概念的正式语言结构。您在这里所做的是使用自上而下的解析器创建这样的解析树。

于 2010-05-23T17:44:48.070 回答