Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #1 (permalink)  
Старый 25.05.2022, 22:41
Аспирант
Отправить личное сообщение для Дмитрий Луценко Посмотреть профиль Найти все сообщения от Дмитрий Луценко
 
Регистрация: 24.05.2022
Сообщений: 36

Как создать абстрактное синтаксическое дерево на 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"}
];


Посоветуйте, пожалуйста, как реализовать этот алгоритм.
Ответить с цитированием
  #2 (permalink)  
Старый 26.05.2022, 02:06
Аватар для Gvozd
Матрос
Отправить личное сообщение для Gvozd Посмотреть профиль Найти все сообщения от Gvozd
 
Регистрация: 04.04.2008
Сообщений: 6,246

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

Последний раз редактировалось Gvozd, 26.05.2022 в 02:09.
Ответить с цитированием
  #3 (permalink)  
Старый 26.05.2022, 08:36
Аспирант
Отправить личное сообщение для Дмитрий Луценко Посмотреть профиль Найти все сообщения от Дмитрий Луценко
 
Регистрация: 24.05.2022
Сообщений: 36

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

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

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

За ссылочки спасибо, ознакомлюсь Если проект получится удачным, скину ссылку на репозиторий, чтобы у людей с похожими вопросами была возможность понять эту сложную но интересную тему как транслятор/компиллятор
Ответить с цитированием
  #4 (permalink)  
Старый 26.05.2022, 11:08
Профессор
Отправить личное сообщение для Rise Посмотреть профиль Найти все сообщения от Rise
 
Регистрация: 07.11.2013
Сообщений: 4,662

Дмитрий Луценко,
У jquery есть парсер, esprima называется, на typescript написан.
Ответить с цитированием
  #5 (permalink)  
Старый 26.05.2022, 11:39
Аспирант
Отправить личное сообщение для Дмитрий Луценко Посмотреть профиль Найти все сообщения от Дмитрий Луценко
 
Регистрация: 24.05.2022
Сообщений: 36

Сообщение от Rise Посмотреть сообщение
Дмитрий Луценко,
У jquery есть парсер, esprima называется, на typescript написан.
Эх, хорошее предложение, но мне требуется написать свой парсер без использования готовых либ и без использования серверного JS.

Все равно спасибо за предложение, ознакомлюсь на досуге
Ответить с цитированием
  #6 (permalink)  
Старый 26.05.2022, 12:01
Профессор
Отправить личное сообщение для Rise Посмотреть профиль Найти все сообщения от Rise
 
Регистрация: 07.11.2013
Сообщений: 4,662

Сообщение от Дмитрий Луценко
без использования готовых либ
Это пример синтаксического анализатора на js.
Сообщение от Дмитрий Луценко
без использования серверного JS.
Typescript это не серверный js.
Ответить с цитированием
  #7 (permalink)  
Старый 26.05.2022, 12:16
Аватар для MallSerg
Профессор
Отправить личное сообщение для MallSerg Посмотреть профиль Найти все сообщения от MallSerg
 
Регистрация: 07.03.2011
Сообщений: 1,126

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


Опции темы Искать в теме
Искать в теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Как создать глобальную функцию внутри другой функции? sovsem-nub Элементы интерфейса 2 18.01.2020 15:50
Как через JS задать ширину родителя как у ребенка? ethereal Элементы интерфейса 6 13.01.2020 11:05
Как запомнить число или значение в js (координаты курсора)? Новичок. Teno Элементы интерфейса 5 16.04.2019 07:19
Как вы относитесь к наркоманам? Maxmaxmaximus7 Оффтопик 7 05.02.2014 13:29
Как создать такой филд в JS? remember_me Элементы интерфейса 6 07.12.2013 13:26