Теория формальных языков - Автомат

Question

Я задаюсь вопросом о формальных языках. У меня есть своего рода парсер: он читает XML-подобную сериализованную древовидную структуру и превращает ее в многомерный массив.

Я имею в виду сходство между используемым алгоритмом и различными типами автоматов (конечные автоматы стекают машины...).

Поэтому возникает вопрос: какой автомат я здесь имплицитно использую, и к какому семейству формальных языков он подходит? А как насчет рекурсии?

Под "автоматом, который я использую неявно", я подразумеваю "минимальный автомат, выполняющий ту же работу".

Вот полный источник:

$ слов; // массив тегов XML '', '' и простой текстовый контент

$ tree = array ('type' => 'root', 'sub' => array ());

$ pTree = array (& $ tree);

$ deep = 0;

foreach ($ words как $ 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-подобные файлы, вероятно, могут быть распознаны детерминированной машиной стеков или сгенерированы детерминированной контекстно-свободной грамматикой, что делает их Типом 2 в иерархии Хомского. Еще раз, это всего лишь предположение, что "XML-подобная сериализованная древовидная структура" слишком расплывчата для любого вида формализма.

Короче говоря, если вы хотите использовать какую-либо формальную теорию, сформулируйте свои вопросы более формально.

---

Изменить (после просмотра кода):

Вы строите дерево. Это вне досягаемости для автомата (по крайней мере, "стандартных"). Конечные автоматы работают только с входом и состоянием, стековые машины добавляют к этому стек, а у машин Тьюринга есть лента чтения-записи, которую они могут перемещать в обоих направлениях.

"Выход" автомата - это простое "Да" (принято) или "Нет" (не принято или бесконечный цикл). (Машины Тьюринга могут быть определены для обеспечения большей производительности на их ленте.) Лучшее, на что я могу ответить "какой минимальный автомат для выполнения той же работы", - это то, что ваш язык может быть принят стековой машиной; но это будет работать совсем по-другому и не даст вам деревья.

Однако вы можете взглянуть на грамматику - еще одну формальную языковую конструкцию, которая вводит понятие деревьев разбора. То, что вы делаете здесь, это создание такого дерева разбора с анализатором сверху вниз.