Théorie des langues officielles - Automaton

Question

Je me demande sur les langues officielles. J'ai une sorte d'analyseur: Il lit à XML comme structure arborescente sérialisés et le transformer en un tableau multidimmensionnal.

Mon point est sur les similitudes entre l'algorithme utilisé et les différents types d'automates (machines d'état des machines de Turing pile ...).

La question est: qui est l'automate que j'utilise implictly ici, et à quelle famille langues formelle-t-il en forme? Et ce qui est sur la récursivité?

Qu'est-ce que je veux dire par « automate j'utilise implicitement » est « qui est l'automate minimal pour faire le même travail ».

Voici la source complète:

mots $; // un tableau de balise XML '', '' et simple contenu du texte

$ arbre = array (     'Type' => 'root',     'Sous' => array () );

$ ptree = array (& $ arbre);

$ en profondeur = 0;

foreach ($ mots comme $ 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

S'il vous plaît jeter un oeil à votre question. Vous faites référence à une variable $words, ce qui est dans votre exemple. En outre, il n'y a pas de code, sans savoir ce qui est fait, il est difficile de vous répondre.

A en juger par le nom de la $deep variable, il est probablement pas l'état. L'état dans un automate est un élément d'un ensemble qui est spécifique à l'automate; ressemble $deep comme il pourrait contenir une profondeur, tout entier positif. Encore une fois, difficile à dire sans le code.

Quoi qu'il en soit, vous n'êtes probablement pas « en utilisant implicitement » tout automate du tout, si vous ne l'avez pas concevoir votre code comme une mise en œuvre d'un.

Votre simples fichiers de type XML pourrait probablement être reconnu par une machine à pile déterministe ou généré par une grammaire sans contexte déterministe, ce qui les rend de type 2 dans la hiérarchie de Chomsky. Encore une fois cela est juste une supposition, « une structure arborescente sérialisé comme XML » est trop vague pour tout type de formalisme.

En bref, si vous cherchez à utiliser toute théorie formelle, ne formulez vos questions plus formellement.

---

Modifier (après avoir vu le code):

Vous construisez un arbre. C'est hors de portée pour un automate (au moins les « standards »). que de finis automates travail avec une entrée et un état, les machines à pile ajouter une pile à cela, et les machines de Turing ont une bande de lecture-écriture, ils peuvent se déplacer dans les deux sens.

La « sortie » d'un automate est un simple « oui » (accepté) ou « Non » (non acceptée, ou une boucle infinie). (Machines de Turing peuvent être définis pour fournir plus de puissance sur leur bande.) Le mieux que je peux répondre à « qui est l'automate minimal pour faire le même travail » est que votre langue peut être acceptée par une machine à pile; mais cela fonctionnerait très différemment et ne pas vous donner des arbres.

Cependant, vous pouvez regarder dans grammaires - une autre construction de langage formel qui introduit le concept de arbres parse . Ce que vous faites ici est la création d'un tel arbre d'analyse syntaxique avec un analyseur de haut en bas.