Вопросы со второй главы книги драконов

Question

На странице 29 говорится: «Листья дерева синтаксического анализа, читаемые слева направо, образуют выход дерева, который является строкой, созданной или полученной из нетерминала в корне дерево разбора. На рисунке 2.2 сгенерированная строка 9-5 * 2. На этой фигуре все листья показаны на нижнем уровне. Впредь мы не обязательно будем выравнивать листья таким образом ». почему нет?

В нем также говорится: «Любое дерево привносит естественный порядок слева направо в его листья, основываясь на идее, что если a и b являются двумя детьми с одним и тем же родителем, а a находится слева от b, то все потомки a находятся слева от потомков b. " что это значит?

P.S Это второе издание книги

Answer 1

Итак, прежде всего, для тех, кто еще хочет, чтобы это прокомментировать, номера страниц выше, относятся к первому изданию. Во втором издании номер страницы равен 46, а диаграмма - цифра 2.5.

EDIT: автор, ссылаясь на расширение листьев на дно, говорит о перемещении всех листьев дерева, которые должны быть выровнены по вертикали друг с другом, независимо от того, находятся они на одном уровне в дереве или нет. Рисунок 2.2 расширяет их до дна, так что каждый лист находится внизу диаграммы, выровненной вертикально слева направо. Если вы посмотрите на некоторые другие диаграммы позже в книге, это не будет сделано, и листья будут показаны по вертикали в соответствии с другими узлами на том же уровне, независимо от того, являются ли эти другие узлы листьями. Этот последний способ является обычным способом рисования деревьев и является наиболее эффективным пространством.

Что касается вашего первого вопроса, я верю, что причина, по которой они не делают этого, заключается в том, чтобы сэкономить место. Если вы посмотрите на правую часть рисунка 2.4, если автор должен был продлить листья донизу, то поддерево с буквой в качестве корня должно быть перемещено вправо, заняв больше места, чем на самом деле необходимо. Хотя это минимальный случай и не имеет большого значения, можно представить себе более крупное дерево (что, я уверен, есть в книге, хотя я и не искал), что потребует больше места.

По второму вопросу, по существу, говорится, что если у вас есть * b + c * d, и вы считаете умножения как братья и сестры (так как они должны были поддерживать порядок операций действительными), то листья a и b будет слева от c и d в дереве, так же, как они находятся слева от c и d в уравнении. По сути, он просто говорит, что он уже сказал в первой части, а именно, что листья дерева должны быть прочитаны слева направо, чтобы точно воспроизвести исходный синтаксис, а не переключать порядок любых частей (т. Е. Если дерево читается слева направо c * d + a * b, который может быть действительным, но не будет деревом, которое мы рассматриваем).