Как превратить поток токенов в дерево синтаксического анализа

Я бы очень порекомендовал http://www.antlr.org/ и, конечно же, классическую книгу Dragon Compilers.

Для такого простого языка, как JavaScript, нетрудно вручную развернуть парсер рекурсивного спуска, но почти всегда проще использовать такие инструменты, как yacc или antlr.

Я думаю, что если вернуться к основам вашего вопроса, вы действительно хотите изучить синтаксис грамматики в стиле BNF и выбрать синтаксис для своей цели. Если у вас есть это, дерево синтаксического анализа должно как бы выпасть, являясь «экземпляром» проявления этой грамматики.

Кроме того, не пытайтесь превратить создание вашего дерева синтаксического анализа в ваше окончательное решение (например, создание кода или что-то еще). Это могло показаться выполнимым и более эффективным; но неизменно наступит время, когда вы действительно захотите, чтобы у вас было это дерево синтаксического анализа «как есть».

Вам следует изучить инструменты генератора парсеров для вашей платформы. Генератор синтаксического анализатора позволяет вам определять контекстно-свободную грамматику для вашего языка. Язык состоит из ряда правил, которые «сокращают» серию символов до нового символа. Обычно вы также можете указать приоритет и ассоциативность для различных правил, чтобы устранить двусмысленность в языке. Например, очень простой язык калькулятора может выглядеть примерно так:

%left PLUS, MINUS           # low precedence, evaluated left-to-right
%left TIMES, DIV            # high precedence, left-to-right

expr ::= INT
| expr PLUS expr
| expr MINUS expr
| expr TIMES expr
| expr DIV expr
| LEFT_PAREN expr RIGHT_PAREN

Обычно вы можете связать фрагмент кода с каждым правилом, чтобы построить новое значение (в данном случае выражение) из других символов в этом правиле. Генератор синтаксического анализатора примет грамматику и создаст код на вашем языке, который преобразует поток токенов в дерево синтаксического анализа.

Большинство генераторов парсеров зависят от языка. ANTLR хорошо известен и поддерживает C, C ++, Objective C, Java и Python. Я слышал, что это сложно использовать. Я использовал bison для C / C ++, CUP для Java и ocamlyacc для OCaml, и все они довольно хороши. Если вы уже используете генератор лексера, вам следует поискать генератор синтаксического анализатора, специально совместимый с ним.

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

Как описано выше Маркосом Марином, конечный автомат, который использует правила вашего языка в BNF для анализа вашего списка токенов, подойдет вам, если вы захотите сделать это самостоятельно. Только, как сказано в вышеприведенном комментарии Пола Холлингсворта, более простой способ - использовать Pushdown-Automaton который имеет простой стек памяти FiFo. У каждого класса токенов есть следующий ожидаемый токен в вашей грамматике, который также представлен в вашем конечном автомате. Стек используется для «запоминания» того, каким был предыдущий класс токена, для уменьшения требуемых состояний (можно было бы сделать без стека, но вам потребуется новое состояние для каждого класса и подкласса, разделенного в дереве грамматики). Принимающее состояние (а) будет (в естественных языках и в большинстве языков программирования) начальным состоянием и, возможно, некоторым другим состоянием в определенных случаях.

Я бы посоветовал Antlr использовать какой-либо инструмент (более быстрый и менее обширный). Удачи!