29ページには、「左から右に読み取られる解析ツリーの葉は、解析ツリーのルートにある非終端記号から生成または導出された文字列であるツリーの収率を形成します。図2.2では、生成された文字列は次のとおりです。 9-5*2. その図では、すべての葉が一番下のレベルに表示されています。以降、必ずしもこのように葉を並べる必要はありません。" なぜだめですか？
また、「a と b が同じ親を持つ 2 人の子であり、a が b の左側にある場合、a のすべての子孫は、その葉に自然な左から右の順序を与えます。 b の子孫の左側にあります。」どういう意味ですか？
PS 本書の第 2 版です。
したがって、まず第一に、これについてコメントしたい他の人のために、上記のページ番号は初版を指しています. 第 2 版では、ページ数は 46 で、参照されている図は図 2.5 です。
編集: 著者は、葉を下まで伸ばすことについて言及するとき、ツリー内で同じレベルにあるかどうかに関係なく、ツリーのすべての葉を移動して互いに垂直に整列させることについて話しています。図 2.2 では、すべてのリーフが図の下部にあり、左から右に垂直に整列するように、それらを下部に拡張しています。本書の後半で他の図を見ると、これは行われておらず、他のノードが葉であるかどうかに関係なく、葉は同じレベルの他のノードと垂直に整列して表示されます。この後者の方法は、ツリーを描画する通常の方法であり、スペース効率が最も高くなります。
あなたの最初の質問に関しては、彼らがそれをしない理由は、スペースを節約するためだと思います. 図 2.4 の右側を見ると、作成者がリーフを一番下まで拡張した場合、ルートとして文字を持つサブツリーを右に移動する必要があり、実際よりも多くのスペースを占有します。必要です。これは最小限のケースであり、大きな違いはありませんが、より大きなツリー (見に行きませんでしたが、本の中にあるはずです) を想像することもできます。
2 番目の質問では、基本的には、a*b + c*d があり、乗算を兄弟と見なした場合 (操作の順序を有効に保つため)、葉 a と b は次のようになります。式の c と d の左側にあるのと同じように、ツリーの c と d の左側。本質的には、最初の部分ですでに述べたことを言っているだけです。つまり、元の構文を正確に再現するために、ツリーの葉は左から右に読み取れる必要があり、部分の順序を切り替えることはありません (つまり、ツリーが読み取った場合左から右へ c*d + a*b、これはまだ有効かもしれませんが、私たちが検討しているツリーではありません)。