2

形式言語について疑問に思っています。私は一種のパーサーを持っています：それは、xmlのようなシリアル化されたツリー構造を読み取り、それを多次元配列に変換します。

私のポイントは、使用されているアルゴリズムとさまざまな種類のオートマトン（ステートマシンチューリングマシンスタック...）の類似点です。

したがって、問題は次のとおりです。ここで暗黙的に使用するオートマトンはどれですか。また、どの形式言語ファミリに適合しますか？そして、再帰についてはどうですか？

「暗黙的に使用するオートマトン」とは、「同じ仕事をするための最小限のオートマトン」という意味です。

完全なソースは次のとおりです。

$words; // an array of XML tag '<tag>', '</tag>' and simple text content
$tree = array(
    'type' => 'root',
    'sub' => array()
);
$pTree = array(&$tree);
$deep = 0;

foreach ( $words 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
        );
        
    }
4

1 に答える 1

4

もう一度質問を見てください。$words例にない変数を参照しています。また、コードはありません。何が行われているのかを知らなければ、答えるのは難しいです。

変数の名前から判断すると、$deepおそらく状態ではありません。オートマトンの状態は、オートマトンに固有のセットの要素です。$deep深さ、任意の正の整数を含めることができるように見えます。繰り返しますが、コードなしではわかりません。

とにかく、コードをオートマトンの実装として設計していなければ、おそらくオートマトンを「暗黙的に使用」しているわけではありません。

単純なxmlのようなファイルは、おそらく決定性スタックマシンによって認識されるか、決定性文脈自由文法によって生成され、チョムスキー階層のタイプ2になります。繰り返しになりますが、これは単なる推測であり、「xmlのようなシリアル化されたツリー構造」は、どのような形式主義にもあいまいすぎます。

つまり、正式な理論を使用する場合は、質問をより正式に表現してください。

編集（コードを見た後）：

あなたは木を作っています。これは、オートマトン（少なくとも「標準」のもの）には届きません。有限オートマトンは入力と状態でのみ機能し、スタックマシンはそれにスタックを追加し、チューリングマシンには両方向に移動できる読み取り/書き込みテープがあります。

オートマトンの「出力」は、単純な「はい」（受け入れられる）または「いいえ」（受け入れられない、または無限ループ）です。（チューリングマシンは、テープでより多くの出力を提供するように定義できます。）「同じジョブを実行するための最小限のオートマトンです」に答えることができる最善の方法は、スタックマシンで言語を受け入れることができることです。しかし、それは非常に異なった働きをし、あなたに木を与えません。

ただし、文法を調べることもできます。これは、解析ツリーの概念を導入する別の形式言語構造です。ここで行っているのは、トップダウンパーサーを使用してこのような解析ツリーを作成することです。

于 2010-05-23T17:44:48.070 に答える