Блог

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

Итак if (x == 3) , у вас есть lex, проверьте, что это в данном случае if, снова lex и убедитесь, что это a (, проанализируйте выражение, которое запрашивает 3 в этом случае, пока оно не завершит синтаксический анализ выражения, а затем вы lex и ожидаете закрывающую скобку.

Другой альтернативой является то, что вы называете этот входной поток as keyword, symbol, identifier, equality, number, symbol , а затем передаете этот список токенов синтаксическому анализатору, который преобразует его в AST.

Каковы плюсы / минусы этих двух методов?

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

Однако, если грамматика требует более одного символа lookahead или не является left-right, тогда вам может потребоваться добавить больше лексики. В то время как естественные языки имеют некоторые странные правила синтаксического анализа («время летит, как стрела, фруктовые мухи, как бананы»), компьютерные языки обычно предназначены для разбора с помощью простого синтаксического анализатора рекурсивного спуска с одним символом предвидения.