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

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

2 голосов
/ 23 мая 2010

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

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

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

Что я имею в виду под «автоматом, который я неявно использую», так это «минимальным автоматом, который выполняет ту же работу».

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

$ слов;// массив тегов XML '', '' и простого текстового содержимого

$ 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
    );

}

}

1 Ответ

4 голосов
/ 23 мая 2010

Пожалуйста, взгляните на ваш вопрос еще раз. Вы имеете в виду переменную $words, которой нет в вашем примере. Также нет кода, не зная, что делается, вам сложно ответить.

Судя по названию переменной $deep, это, вероятно, не состояние. Состояние в автомате является элементом набора, который является специфическим для автомата; $deep похоже, что оно может содержать глубину, любое положительное целое число. Опять же, трудно сказать без кода.

В любом случае, вы, вероятно, вообще не «неявно используете» какой-либо автомат, если вы не спроектировали свой код как его реализацию.

Ваши простые xml-подобные файлы, вероятно, могут быть распознаны машиной детерминированного стека или сгенерированы детерминированной грамматикой без контекста, что делает их Тип-2 в иерархии Хомского. Еще раз, это всего лишь предположение, что «XML-подобная сериализованная древовидная структура» слишком расплывчата для любого вида формализма.

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

Редактировать (увидев код):

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

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

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

...