Каждый раз, когда я пишу простой лексер и парсер, я натыкаюсь на один и тот же вопрос :как должны взаимодействовать лексер и парсер? Я вижу четыре разных подхода:
Лексер охотно преобразует всю входную строку в вектор токенов. Как только это будет сделано, вектор передается анализатору, который преобразует его в дерево. Это, безусловно, самое простое решение для реализации, но поскольку все токены хранятся в памяти, это занимает много места.
Каждый раз, когда лексер находит токен, он вызывает функцию синтаксического анализатора, передавая текущий токен. По моему опыту, это работает только в том случае, если синтаксический анализатор может быть естественным образом реализован в виде конечного автомата, такого как синтаксические анализаторы LALR. Напротив, я не думаю, что это вообще сработает для парсеров рекурсивного спуска.
Каждый раз, когда синтаксическому анализатору требуется токен, он запрашивает у лексера следующий. Это очень легко реализовать в C #благодаря ключевому слову yield
,но довольно сложно на С++, у которого его нет.
Лексер и синтаксический анализатор взаимодействуют через асинхронную очередь. Это широко известно под названием «производитель/потребитель», и это должно значительно упростить взаимодействие между лексером и парсером. Он также превосходит другие решения на многоядерных процессорах? Или лексинг слишком тривиален?
Является ли мой анализ здравым? Есть ли другие подходы, о которых я не подумал? Что используется в компиляторах реального -мира? Было бы здорово, если бы авторы компиляторов, такие как Эрик Липперт, могли пролить свет на этот вопрос.