我想知道正式语言。我有一种解析器: 它读取类似 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
);
}
最佳答案
请再看看你的问题。您指的是 $words
变量,该变量不在您的示例中。另外,没有代码,在不知道正在做什么的情况下很难回答你。
从变量$deep
的名称来看,它很可能不是状态。自动机中的状态是特定于自动机的集合的元素; $deep
看起来它可以包含深度,任何正整数。同样,如果没有代码就很难判断。
无论如何,如果您没有将代码设计为自动机的实现,那么您可能根本就没有“隐式使用”任何自动机。
您的简单的类 xml 文件可能会被确定性堆栈机识别,或者由确定性上下文无关语法生成,从而使它们成为 Chomsky 层次结构中的 Type-2。再说一遍,这只是一个猜测,“类似 xml 的序列化树结构”对于任何形式主义来说都太模糊了。
简而言之,如果您希望使用任何正式理论,请更正式地表达您的问题。
编辑(看到代码后):
你正在 build 一棵树。这对于自动机(至少是“标准”自动机)来说是遥不可及的。有限自动机仅处理输入和状态,堆栈机在其中添加堆栈,而图灵机有一个可以双向移动的读写磁带。
自动机的“输出”是简单的"is"(接受)或“否”(不接受,或无限循环)。 (图灵机可以被定义为在磁带上提供更多输出。) 对于“这是完成相同工作的最小自动机”,我能回答的最好的答案是,你的语言可以被堆栈机接受;但它的工作方式会非常不同,并且不会给你树。
但是,您可能会研究语法 - 另一种引入解析树概念的形式语言结构。 您在这里所做的就是使用自上而下的解析器创建这样一个解析树。
关于language-theory - 形式语言理论 - 自动机,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2892653/