Fragen aus dem zweiten Kapitel des Drachenbuchs

Question

Auf Seite 29 heißt es: "Die Blätter eines Parsebaums, gelesen von links nach rechts, bilden den Ertrag des Baumes, der die vom Nichtterminal an der Wurzel von der Parse-Baum. In Abb. 2.2 ist die generierte Zeichenkette 9-5 * 2. In dieser Abbildung sind alle Blätter auf der unteren Ebene dargestellt. Von nun an müssen wir die Blätter nicht mehr auf diese Weise ausrichten. " warum nicht?

Es sagt auch "Jeder Baum verleiht seinen Blättern eine natürliche Links-nach-rechts-Ordnung, basierend auf der Idee, dass wenn a und b zwei Kinder mit demselben Elternteil sind und a links von b ist, dann Alle Nachkommen von a sind links von Nachkommen von b. " Was heißt das?

P.S Es ist die zweite Auflage des Buches

Answer 1

Also zunächst einmal, für alle anderen kommentieren, dies zu wollen, die Seitenzahlen beziehen sich oben auf der ersten Auflage. In der zweiten Ausgabe ist die Seitenzahl 46, und das Diagramm, auf das verwiesen wird, ist Abbildung 2.5.

BEARBEITEN: Der Autor, wenn es sich auf die Erweiterung der Blätter nach unten bezieht, spricht davon, alle Blätter des Baumes vertikal aufeinander auszurichten, ob sie auf der gleichen Ebene im Baum sind oder nicht. Abbildung 2.2 hat sie nach unten erweitert, so dass jedes Blatt unten im Diagramm vertikal von links nach rechts ausgerichtet ist. Wenn Sie sich später im Buch einige andere Diagramme ansehen, wird dies nicht getan, und die Blätter werden vertikal mit anderen Knoten auf derselben Ebene ausgerichtet, unabhängig davon, ob diese anderen Knoten Blätter sind oder nicht. Dieser letztere Weg ist der normale Weg Bäume zu zeichnen und ist der platzsparendste.

Was Ihre erste Frage angeht, glaube ich, dass der Grund, warum sie das nicht tun, Platz spart. Wenn Sie auf der rechten Seite von Abbildung 2.4 nachsehen, ob der Autor die Blätter nach unten ausstrecken sollte, müsste der Unterbaum mit dem Buchstaben als Wurzel nach rechts verschoben werden und mehr Platz einnehmen, als tatsächlich vorhanden ist erforderlich. Während dies ein minimaler Fall ist und keinen großen Unterschied macht, könnte man sich einen größeren Baum vorstellen (von dem ich sicher bin, dass er in dem Buch ist, obwohl ich nicht hinsah), der mehr Platz benötigen würde. Für die zweite Frage, es ist im Wesentlichen, dass, wenn Sie a * b + c * d hatten, und Sie die Multiplikationen als Geschwister betrachteten (wie sie wären, um die Reihenfolge der Operationen gültig zu halten), dann die Blätter a und b wäre links von c und d im Baum, so wie sie links von c und d in der Gleichung stehen. Im Wesentlichen sagt es nur, was es bereits im ersten Teil gesagt hat, nämlich dass die Blätter des Baumes von links nach rechts gelesen werden können, um die originale Syntax exakt zu reproduzieren, nicht um die Reihenfolge irgendwelcher Teile zu ändern (dh wenn der Baum gelesen wird von links nach rechts c * d + a * b, das könnte immer noch gültig sein, wäre aber kein Baum, den wir in Betracht ziehen).