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

[Дмитрий Луценко]

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

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

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

int var_a = +1;

Итоговое дерево для объявленной переменной 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"}
];

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

[Gvozd]

Если вы пишите учебник, то, полагаю, вы уже умеет решать задачу построения 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/
тут без комментариев, так как давно читал статью, и не сильно помню

[Дмитрий Луценко]

Если вы пишите учебник, то, полагаю, вы уже умеет решать задачу построения 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 на любом другом языке).

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

[Rise]

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

[Дмитрий Луценко]

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

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

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

[MallSerg]

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