Teoria dei linguaggi formali - Automaton

Question

Mi chiedo su linguaggi formali. Ho una specie di parser: Si legge un XML di struttura simile albero serializzato e trasformarlo in una matrice multidimmensionnal.

Il mio punto è sulle somiglianze tra l'algoritmo in uso e le differenti tipi di automi (macchine macchine a stati Turing impilare ...).

Quindi la domanda è: che è l'automa che implicitamente pone uso qui, e per quali lingue formale famiglia mi sta? E cosa c'è di circa ricorsione?

Quello che intendo per "automa io uso implicitamente" è "che è l'automa minimo per fare lo stesso lavoro".

Questa è la sorgente completo:

$ parole; // una serie di tag XML '', '' e contenuto del testo semplice

$ albero = array (     'Tipo' => 'radice',     'Sub' => array () );

$ ptree = array (& $ albero);

$ profonda = 0;

foreach ($ parole come $ 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

Si prega di dare un'occhiata al vostro domanda di nuovo. Ti riferisci a una variabile $words, che non è nel tuo esempio. Inoltre, non esiste un codice, senza sapere che cosa si sta facendo è difficile rispondere a voi.

A giudicare dal nome del $deep variabile, non è probabilmente lo stato. Lo stato in un automa è un elemento di un insieme che è specifico per l'automa; sguardi $deep come esso potrebbe contenere una profondità, qualsiasi numero intero positivo. Anche in questo caso, difficile da dire, senza il codice.

In ogni caso, si sono probabilmente non "implicitamente l'utilizzo di" qualsiasi automa a tutti, se non si progetta il tuo codice come un'implementazione di uno.

Il tuo semplice XML come file potrebbe probabilmente essere riconosciuto da una macchina pila deterministica, o generato da una grammatica context-free deterministica, che li rende di tipo 2 nella gerarchia di Chomsky. Ancora una volta questa è solo una supposizione "un xml-simile struttura ad albero a puntate" è troppo vago per qualsiasi tipo di formalismo.

In breve, se si sta cercando di usare qualsiasi teoria formale, fare la tua domanda in modo più formale.

---

Modifica (dopo aver visto il codice):

Si sta costruendo un albero. Questo è fuori dalla portata di un automa (almeno quelli “standard”). automi finiti funzionano solo con un ingresso e uno stato, macchine pila aggiungere uno stack a ciò, e macchine di Turing avere un nastro di lettura-scrittura possono muoversi in entrambe le direzioni.

L ' “uscita” di un automa è un semplice “Sì” (accettata) o “No” (non accettata, o un ciclo infinito). (Macchine di Turing possono essere definiti per fornire maggiori uscita sul loro nastro.) Il meglio che posso rispondere a “che è l'automa minimo per fare lo stesso lavoro” è che il linguaggio può essere accettato da una macchina pila; ma avrebbe funzionato in modo molto diverso e non vi darà alberi.

Tuttavia, si potrebbe guardare in grammatiche - un altro costrutto del linguaggio formale che introduce il concetto di alberi di analisi . Quello che state facendo qui è la creazione di un tale albero sintattico con un parser top-down.