Javascript-форум (https://javascript.ru/forum/)
-   Общие вопросы Javascript (https://javascript.ru/forum/misc/)
-   -   Как создать абстрактное синтаксическое дерево на JS (https://javascript.ru/forum/misc/84067-kak-sozdat-abstraktnoe-sintaksicheskoe-derevo-na-js.html)

Дмитрий Луценко 25.05.2022 22:41

Как создать абстрактное синтаксическое дерево на 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 26.05.2022 02:06

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

Дмитрий Луценко 26.05.2022 08:36

Цитата:

Сообщение от Gvozd (Сообщение 545623)
Если вы пишите учебник, то, полагаю, вы уже умеет решать задачу построения 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: Если проект получится удачным, скину ссылку на репозиторий, чтобы у людей с похожими вопросами была возможность понять эту сложную но интересную тему как транслятор/компиллятор:)

Rise 26.05.2022 11:08

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

Дмитрий Луценко 26.05.2022 11:39

Цитата:

Сообщение от Rise (Сообщение 545625)
Дмитрий Луценко,
У jquery есть парсер, esprima называется, на typescript написан.

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

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

Rise 26.05.2022 12:01

Цитата:

Сообщение от Дмитрий Луценко
без использования готовых либ

Это пример синтаксического анализатора на js.
Цитата:

Сообщение от Дмитрий Луценко
без использования серверного JS.

Typescript это не серверный js.

MallSerg 26.05.2022 12:16

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


Часовой пояс GMT +3, время: 18:00.