解析ツリー

構文木または構文解析木^{[1] （}導出木または具象構文木とも呼ばれる）は、文脈自由文法に従って文字列の構文構造を表す順序付きルート木である。構文木という用語は主に計算言語学で使用され、理論的な構文では構文木という用語がより一般的である。

具体的な構文木は入力言語の構文を反映しており、コンピュータ プログラミングで使用される抽象構文木とは異なります。文法の指導に使用されるリード ケロッグ文図とは異なり、構文解析木では異なるタイプの構成要素に対して異なる記号形状を使用しません。

構文木は通常、構成文法（句構造文法）の構成関係または依存文法の依存関係に基づいて構築されます。構文木は、自然言語の文（自然言語処理を参照）に対して生成される場合もあれば、プログラミング言語などのコンピュータ言語の処理中に生成される場合もあります。

関連する概念として、変形生成文法で使用される句マーカーまたはPマーカーがあります。句マーカーは、句構造についてマークされた言語表現です。これは、ツリーの形式または括弧で囲まれた表現として表されます。句マーカーは句構造ルールを適用することによって生成され、それ自体がさらなる変形ルールの対象となります。^[2]構文的に曖昧な文の可能な構文解析ツリーのセットは、「構文解析フォレスト」と呼ばれます。^[3]

構文解析木はノードとブランチで構成されています。^[4]図では、構文解析木はSから始まり、各リーフノード（John、ball、the、hit）で終わる全体の構造です。構文解析木では、各ノードはルートノード、ブランチノード、またはリーフノードのいずれかです。上記の例では、Sはルートノード、NPとVPはブランチノード、John、ball、the、hitはすべてリーフノードです。

ノードは、親ノードおよび子ノードとも呼ばれます。親ノードとは、その下にブランチでリンクされた他のノードが少なくとも 1 つあるノードです。例では、S は NP と VP の両方の親です。子ノードとは、その上にツリーのブランチでリンクされたノードが少なくとも 1 つあるノードです。この例では、hit は V の子ノードです。

非終端関数は、そのツリー内のルートまたはブランチのいずれかである関数 (ノード) ですが、終端関数は、解析ツリー内のリーフである関数 (ノード) です。

バイナリ ツリー (各親ノードに 2 つの直接の子ノードがある) の場合、n語の文の可能な構文解析ツリーの数は、カタロニア数 で与えられます。 ${\displaystyle C_{n}}$

構成文法 (句構造文法)の構成ベースの構文解析ツリーは、終端ノードと非終端ノードを区別します。内部ノードは文法の非終端カテゴリでラベル付けされ、リーフノードは終端カテゴリでラベル付けされます。以下の画像は構成ベースの構文解析ツリーを表しており、英語の文「John hit the ball」の構文構造を示しています。

解析ツリーは、 S から始まり、各リーフ ノード ( John、hit、the、ball ) で終わる構造全体です。ツリーでは次の略語が使用されています。

• S は、この例の最上位構造であるsentenceを表します。

• 名詞句を表す NP 。最初の (左端の) NP である単一の名詞「John」は、文の主語として機能します。2 番目は、文の目的語です。

• 述語として機能する動詞句の VP です。

• V はverbを表します。この場合、他動詞 hitです。

• D は限定詞、この場合は定冠詞「the」です。

• 名詞の場合はN。

ツリー内の各ノードは、ルートノード、ブランチノード、またはリーフノードのいずれかです。^[5]ルートノードは、その上にブランチを持たないノードです。文の中には、ルートノードは1つしかありません。ブランチノードは、2つ以上の子ノードに接続する親ノードです。ただし、リーフノードは、ツリー内の他のノードを支配しない末端ノードです。Sはルートノード、NPとVPはブランチノード、John (N)、hit (V)、the (D)、ball (N)はすべてリーフノードです。リーフは、文の語彙トークンです。親ノードとは、その下のブランチによってリンクされている他のノードが少なくとも1つあるノードです。例では、SはNとVPの両方の親です。子ノードとは、その真上にツリーのブランチによってリンクされているノードが少なくとも1つあるノードです。例では、hitはVの子ノードです。母と娘という用語は、この関係を表すために使用されることもあります。

依存文法^[6]の依存ベースの構文木は、すべてのノードを終端と見なします。つまり、終端カテゴリと非終端カテゴリの区別を認識しません。ノード数が少ないため、平均すると構成ベースの構文木よりも単純です。上記の例文の依存ベースの構文木は次のようになります。

この構文解析ツリーには、上記の構成要素ベースの構文解析ツリーに見られる句カテゴリ (S、VP、NP) がありません。構成要素ベースのツリーと同様に、構成要素の構造が認識されます。ツリーの完全なサブツリーはすべて構成要素です。したがって、この依存関係ベースの構文解析ツリーは、構成要素ベースの構文解析ツリーと同様に、主語名詞Johnと目的語名詞句the ball を構成要素として認識します。

構成要素と依存性の区別は広範囲にわたります。構成要素ベースの構文木に関連付けられた追加の構文構造が必要か有益かは議論の余地があります。

句マーカー、または P マーカーは、ノーム・チョムスキーらによって開発された初期の変形生成文法で導入されました。句構造規則を適用することで、文の深層構造を表す句マーカーが生成されます。その後、この適用によってさらに変形が行われることがあります。

フレーズ マーカーはツリーの形式で表現されることもあります(上記の構成要素ベースの解析ツリーのセクションのように) が、メモリの占有スペースが少ない「括弧付き表現」の形式で提供されることがよくあります。たとえば、上記の構成要素ベースのツリーに対応する括弧付き表現は次のようになります。

${\displaystyle [_{S}\ [_{\mathit {N}}\ {\text{ジョン}}]\ [_{\mathit {VP}}\ [_{V}\ {\text{ヒット}}]\ [_{\mathit {NP}}\ [_{\mathit {D}}\ {\text{ザ}}]\ [_{N}\ {\text{ボール}}]]]]}$

ツリーと同様に、このような表現の正確な構成と表示される詳細の量は、適用される理論とクエリ作成者が説明したいポイントによって異なります。

• 構文ツリーエディタ
• 言語ツリーコンストラクタ
• phpSyntaxTree – オンライン構文解析ツリー描画サイト
• phpSyntaxTree (Unicode) – オンライン構文解析ツリー描画サイト (Unicode をサポートする改良版)
• rSyntaxTree Unicode とベクトル化されたグラフィックスを備えた Ruby の phpSyntaxTree の拡張バージョン
• Qtree –解析木を描くためのLaTeXパッケージ
• TreeForm 構文ツリー描画ソフトウェア
• 構文解析ツリーの導入と変換のビジュアル紹介
• OpenCourseOnline 依存関係解析入門 (Christopher Manning)
• ペン ツリーバンク II 構成タグ