Theorie der formalen Sprachen - Automaton

Question

Ich wundere mich über formelle Sprachen. Ich habe eine Art Parser: Es liest à XML-ähnliche serialisierte Baumstruktur und verwandelt sie in ein mehrdimensionales Array.

Mein Punkt liegt auf den Ähnlichkeiten zwischen dem verwendeten Algorithmus und den unterschiedlichen Automaten (State -Maschinen -Turing -Maschinen -Stapel ...).

Die Frage ist also: Welches ist der Automaten, den ich hier implizit verwende und zu welcher formalen Sprachenfamilie passt er? Und was ist mit Rekursion?

Was ich mit "Automaten, das ich implizit benutze" meine, ist "der minimale Automaten, der den gleichen Job macht".

Hier ist die vollständige Quelle:

$ wörter; // eine Reihe von XML -Tag 'u003Ctag> ','u003C/tag> 'und einfacher Textinhalt

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

$ pTree = Array (& $ Tree);

$ Deep = 0;

foreach ($ wots 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
    );

}

}

Answer 1

Bitte schauen Sie sich Ihre Frage noch einmal an. Sie beziehen sich auf a $words Variable, die nicht in Ihrem Beispiel steht. Es gibt auch keinen Code, ohne zu wissen, was getan wird, es ist schwierig, Sie zu beantworten.

Beurteilen Sie nach dem Namen der Variablen $deep, Es ist wahrscheinlich nicht der Staat. Der Staat in einem Automaten ist ein Element eines Satzes, das für den Automaten spezifisch ist. $deep Sieht so aus, als könnte es eine Tiefe enthalten, jede positive Ganzzahl. Wieder schwer ohne den Code zu sagen.

Wie auch immer, Sie "verwenden" wahrscheinlich überhaupt keinen Automaten, wenn Sie Ihren Code nicht als Implementierung von einem entworfen haben.

Ihre einfachen XML-ähnlichen Dateien könnten wahrscheinlich von einer deterministischen Stapelmaschine erkannt oder durch eine deterministische kontextfreie Grammatik generiert werden, wodurch sie in der Chomsky-Hierarchie Typ-2 typisiert werden. Auch dies ist nur eine Vermutung, "eine XML-ähnliche serialisierte Baumstruktur" ist für jede Art von Formalismus zu vage.

Kurz gesagt, wenn Sie eine formelle Theorie verwenden möchten, schreiben Sie Ihre Fragen formeller.

---

Bearbeiten (nach dem Codes gesehen):

Sie bauen einen Baum. Das ist nicht in Reichweite für einen Automaten (zumindest die „Standard“). Finite-Automaten arbeiten nur mit einem Eingang und einem Zustand, Stapelmaschinen fügen einen Stapel hinzu, und Turing-Maschinen haben ein Leseschreibband, das sie in beide Richtungen bewegen können.

Die "Ausgabe" eines Automatens ist ein einfaches "Ja" (akzeptiert) oder "Nein" (nicht akzeptiert oder eine unendliche Schleife). (Turing -Maschinen können definiert werden, um mehr Ausgabe auf ihrem Band zu liefern.) Das Beste, was ich am besten beantworten kann, ist „das ist der minimale Automat, um denselben Job zu erledigen“, dass Ihre Sprache von einem Stapelmaschine akzeptiert werden kann. Aber es würde ganz anders funktionieren und Ihnen keine Bäume geben.

Sie könnten sich jedoch untersuchen Grammatiken - Ein weiteres formales Sprachkonstrukt, das das Konzept von vorstellt Bäume analysieren. Was Sie hier tun, ist, einen solchen Parse-Baum mit einem Top-Down-Parser zu erstellen.