Печать синтаксического дерева как динамического списка на языке c

Question

Я написал код на C для реализации таблицы разбора LR(1), однако сейчас я сталкиваюсь с проблемой печати дерева разбора. Как мы это делаем в C? Дерево может иметь переменные дочерние элементы, и, поскольку алгоритм синтаксического анализа является восходящим, я не уверен, с чего начать. Я хочу, чтобы это выглядело как результат pstree команда или что-то в этом роде.

Благодарю вас

Answer 1

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

Я собирался вставить доказательство того, что не получается нарисовать дерево синтаксического анализа, пока вы выполняете синтаксический анализ слева направо, но, к моему удивлению, я убедил себя, что это возможно, если вы немного ослабите правила: Вы должны быть в состоянии перемещать курсор вверх и вниз, влево и вправо, но вы можете делать это без всякой надпечатки. Чтобы сделать это, вы должны нарисовать дерево с листьями (терминалами) либо на левом поле, либо наверху, а затем вы можете нарисовать сокращения, рисуя линии от каждого дочернего элемента и помня, что такое "точка соединения" результирующий узел есть. Я не знаю, подходит ли это упражнение по программированию для кого-то, кто только начинает разбирать, но это возможно, даже с консольным приложением.

Вот пример графика "обратного pstree":

(41*x) + (27/y) - sin(2*pi*z);

(───────────────────────┐
41─factor─term┐         │
*─────────────┤         │
x─factor──────┴term─expr┤
)───────────────────────┴factor─term─expr┐
+────────────────────────────────────────┤
(───────────────────────┐                │
27─factor─term┐         │                │
/─────────────┤         │                │
y─factor──────┴term─expr┤                │
)───────────────────────┴factor─term─────┴expr┐
-─────────────────────────────────────────────┤
sin─────────────────────────┐                 │
(───────────────────────────┤                 │
2─factor─term┐              │                 │
*────────────┤              │                 │
pi─factor────┴term┐         │                 │
*─────────────────┤         │                 │
z─factor──────────┴term─expr┤                 │
)───────────────────────────┴factor─term──────┴expr

Алгоритм, используемый для получения, который сохраняет ширину и высоту каждого элемента стека; Терминалы начинаются с высоты 1 и ширины самого терминала. В каждом правиле сокращения:

• курсор перемещается вправо, пока не окажется справа от каждого дочернего элемента;

• курсор перемещается вверх первого дна

• для каждого дочернего элемента горизонтальная линия рисуется из его нижнего правого угла в столбец, в котором находится курсор, а затем вертикальная линия отображается до тех пор, пока не будет достигнута строка следующего дочернего элемента. На последнем дочернем элементе печатается нетерминальное имя сокращения, а высота и ширина результирующего нетерминала записываются.