Как создать абстрактное синтаксическое дерево на JS
 

Доброго времени суток

Я пишу учебный проект по СПО, суть которого сводится к разработке транслятора входного языка в выходной (грубо говоря, программа на С++
должна быть переведена на язык Python).

Я испытываю затык на создании синтаксического анализатора, к сожалению не могу понять, как создать нужную структуру, к примеру, для конструкций вида:
Итоговое дерево для объявленной переменной var_a, судя по всему, должно быть таким:
Скриншот дерева

Мой код пока оставляет желать лучшего, я сделал такую реализацию

class Node {
	
	constructor (value, left = null, right = null){
		
		this.value = value;
		this.left  = left;
		this.right = right;
	}
}
class NodeTree {

	constructor () {
		this.root = null;
		this.children = [];
	}
}

let tree = new NodeTree();

tree.children.push(
	new Node(
		'L_EQUAL', 
		new Node (
			'L_DECLARE',
			'int',
			'var_a'
		),
		new Node (
			'L_UNAR',
			'+',
			'1'
		)
	)
);
console.log(tree);

Вопрос в реализации: как вообще обходить таблицу с токенами и создать абстрактное синтаксическое дерево?
Таблицу с токенами я получаю в таком виде.

var lexer_res = [
	{'id': 0, 'tokenType': "L_TYPE", 'tokenValue': "int"},
	{'id': 1, 'tokenType': "L_VAR", 'tokenValue': "var_a"}
];

Посоветуйте, пожалуйста, как реализовать этот алгоритм.

Если вы пишите учебник, то, полагаю, вы уже умеет решать задачу построения AST-дерева на каком-то другом языке?
Так как задача чисто алгоритмическая, то код на JS принципиально мало чем будет отличаться от любого другого языка

С точки зрения высокоуровневого построения парсера языка - есть библиотеки:
Например https://github.com/zaach/jison - аналог Bison.
Декларативно описываете свои токены, и правила вывода нод(лексем), а он геренирует код парсера

Также есть еще и куча других. список npm-модулей:
jison-plus, jscc-parser, kison, packrattle, parsly, pegjs, pegjs-fn


Если же задача описать построение парсера с нуля, то делайте это примерно также, как делали бы на привычном вам языке
Задача же описать концепцию, а не сделать идеальный по каким-то параметрам парсер?

Для написания парсера с нуля, возможно вам будут полезны статьи
1) https://habr.com/ru/post/224081/ - если не ошибаюсь такой парсер не все грамматики
Хотя какие генераторы парсеров реализуют все виды грамматик?)
Но конкретно этот настолько же ограниченный, как и простой
Я уже забыл как называется проблема в теории парсеров, с которой я столкнулся
Но что-то связанное с контекстом, а именно зацикливание при реализации простейшего списка повторяющихся лексем
Если напомните как это ограничение парсеров, или вид контексто-зависимости правильно называется - буду благодарен
В общем этим парсером мне не удалось распарсить CSS-селекторы, что я тогда понял как фундаментальное ограничение этого конкретно парсера
2) https://habr.com/ru/post/227241/
тут без комментариев, так как давно читал статью, и не сильно помню

Мне необходимо писать парсер с нуля: транслятор С++ на Python.
Синтаксис входного языка C++ включает в себя ограниченное количество операторов и операндов:

• Целочисленный тип: int
• Распознавание любой переменной: ^([a-zA-z_]{1,})([0-9]{0,})$
• Операторы сравнения: <, >, ==
• конструкция if-else: stmnt -> if (cond) stmnt else stmnt
• оператор присваивания: =
• Инкремент/декремент (постфиксного достаточно): ++/--
• Фигурные и круглые скобки: {, }, (, )

Универсальный транслятор написать - это задача для меня пока невыполнима:)

Да, моя проблема в том, что я уперся в реализацию деревьев именно на JS, ища только конкретный алгоритм (Вы правы, надо посмотреть реализацию ast на любом другом языке).

За ссылочки спасибо, ознакомлюсь:thanks: Если проект получится удачным, скину ссылку на репозиторий, чтобы у людей с похожими вопросами была возможность понять эту сложную но интересную тему как транслятор/компиллятор:)

Дмитрий Луценко,
У jquery есть парсер, esprima называется, на typescript написан.

Эх, хорошее предложение, но мне требуется написать свой парсер без использования готовых либ и без использования серверного JS.

Все равно спасибо за предложение, ознакомлюсь на досуге:thanks:

Подсмотреть построение AST парсером можно на https://astexplorer.net/
выбрать любой доступный язык и посмотреть исходный код парсера (ссылка в верхнем правом углу).