Связь между лексером и парсером

Каждый раз, когда я пишу простой лексер и парсер, я натыкаюсь на один и тот же вопрос: как должен взаимодействовать лексер и парсер? Я вижу четыре разных подхода:

Лексер с нетерпением преобразует всю входную строку в вектор токенов. Как только это будет сделано, вектор будет передан в парсер, который преобразует его в дерево. Это, безусловно, самое простое решение для реализации, но поскольку все маркеры хранятся в памяти, он тратит много места.
Каждый раз, когда lexer находит маркер, он вызывает функцию в синтаксическом анализаторе, передавая текущий токен. По моему опыту, это работает только в том случае, если парсер, естественно, может быть реализован как конечный автомат, такой как парсер LALR. В отличие от этого, я не думаю, что это будет работать для рекурсивных парсеров спуска.
Каждый раз, когда парсеру нужен токен, он запрашивает лексер для следующего. Это очень легко реализовать на С# из-за ключевого слова yield, но довольно сложно в С++, который его не имеет.
Лексер и парсер взаимодействуют через асинхронную очередь. Это широко известно под названием "производитель/потребитель", и это должно упростить общение между лексером и парсером. Превосходит ли он и другие решения на многоядерных процессорах? Или лексирование слишком тривиально?

Является ли мой анализ звуком? Есть ли другие подходы, о которых я не думал? Что используется в реальных компиляторах? Было бы здорово, если бы авторы-компиляторы, такие как Эрик Липперт, могли пролить свет на эту проблему.

Ответ 1

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

Лексинг всего ввода перед запуском анализатора имеет много преимуществ перед другими параметрами. Реализации различаются, но в целом память, необходимая для этой операции, не является проблемой, особенно если вы рассматриваете тип информации, которую вы хотели бы иметь, чтобы сообщать об ошибках компиляции.
- Преимущества
  - Потенциально больше информации доступно во время отчетов об ошибках.
  - Языки, написанные таким образом, чтобы лексирование происходило до синтаксического анализа, легче указать и написать компиляторы для.
- Недостатки
  - Для некоторых языков требуются контекстные лексеры, которые просто не могут работать до фазы анализа.
Примечание о внедрении языка:. Это моя предпочтительная стратегия, поскольку она приводит к отделимому коду и лучше всего подходит для перевода в реализацию среды IDE для этого языка.

Замечание о реализации Parser: Я экспериментировал с ANTLR v3 в отношении объема памяти с этой стратегией. Цель C использует более 130 байт на токен, а цель Java использует около 44 байт на токен. С измененной целью С# я показал, что можно полностью представить токенированный ввод только с 8 байтами на токен, что делает эту стратегию практичной даже для довольно больших исходных файлов.

Примечание по дизайну:. Я призываю людей, разрабатывающих новый язык, сделать это таким образом, чтобы эта стратегия синтаксического анализа, независимо от того, выбрали ли они ее для своего ссылочного компилятора.
Похоже, вы описали "push" версию того, что я обычно вижу, как "pull" parser, как у вас в # 3. Мой основной упор всегда делался на синтаксический анализ LL, поэтому для меня это был не вариант. Я был бы удивлен, если есть преимущества для этого по сравнению С# 3, но не может их исключить.
Самой вводящей в заблуждение частью является утверждение о С++. Правильное использование итераторов в С++ делает его исключительно подходящим для такого типа поведения.
Очередь кажется перефразированной # 3 с посредником. Хотя абстрагирование независимых операций имеет много преимуществ в таких областях, как модульная разработка программного обеспечения, пара лексеров/парсеров для дистрибутивного продукта предлагает очень высокую производительность, и этот тип абстракции устраняет возможность выполнять определенные виды оптимизации в отношении структуры данных и макета памяти, Я бы посоветовал использовать вариант № 3.

В качестве дополнительной заметки о многоядерном разборе: начальные фазы лексера/парсера компиляции для одного модуля компиляции обычно не могут быть распараллелены, и они не должны учитывать, насколько просто просто выполнять параллельные задачи компиляции на разных (например, одна операция лексера/парсера в каждом исходном файле, распараллеливание по исходным файлам, но только использование одного потока для любого заданного файла).

Что касается других параметров: для компилятора, предназначенного для широкого использования (коммерческого или иного), обычно разработчики выбирают стратегию синтаксического анализа и реализацию, которая обеспечивает наилучшую производительность при ограничениях целевого языка. Некоторые языки (например, Go) могут быть проанализированы исключительно быстро с помощью простой стратегии анализа LR, а использование "более мощной" стратегии синтаксического анализа (чтение: ненужные функции) будет только замедлять работу. Другие языки (например, С++) чрезвычайно сложны или невозможны для анализа типичных алгоритмов, поэтому используются более медленные, но более мощные/гибкие парсеры.

Ответ 2

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

"Вектор жетонов". Это решение может иметь большой объем памяти. Представьте себе компиляцию исходного файла с большим количеством заголовков. Хранение самого токена недостаточно. Сообщение об ошибке должно содержать контекст с именем файла и номером строки. Может случиться, что lexer зависит от анализатора. Разумный пример: " → " - это оператор сдвига, или это закрытие 2-х слоев экземпляров шаблонов? Я бы проголосовал за этот вариант.
(2,3). "Одна часть требует другого". Мое впечатление, что более сложная система должна назвать менее сложной. Я считаю lexer более простым. Это означает, что парсер должен вызывать лексер. Я не понимаю, почему С# лучше, чем С++. Я реализовал C/С++ lexer в качестве подпрограммы (на самом деле это сложный класс), который вызывается из парсера, основанного на грамматике. В этой реализации не было никаких проблем.
"Коммуникационные процессы". Мне это кажется излишним. В этом подходе нет ничего плохого, но, может быть, лучше держать вещи простыми? Многоуровневый аспект. Компиляция одного файла - относительно редкий случай. Я бы рекомендовал загрузить каждое ядро со своим собственным файлом.

Я не вижу других разумных вариантов комбинирования lexer и parser вместе.

Я написал эти заметки, думая о компиляции источников программного проекта. Разбор короткого запроса запроса совершенно другой, и причины могут значительно отличаться. Мой ответ основан на моем собственном опыте. Другие люди могут видеть это по-другому.

Ответ 3

Отношение lexer-parser проще, чем самый общий случай сопрограммы, потому что в общем случае общение одностороннее; синтаксическому анализатору не нужно отправлять информацию в лексер. Вот почему метод нетерпеливого генерации работает (с некоторым штрафом, хотя это означает, что вы можете отказаться от ввода раньше).

Как вы заметили, если либо лексер, либо синтаксический анализатор могут быть записаны в стиле revocable, то другой можно рассматривать как простую подпрограмму. Это всегда можно реализовать как преобразование исходного кода, причем локальные переменные переведены в слоты объектов.

Хотя С++ не поддерживает языковую поддержку сопрограмм, возможно использовать поддержку библиотеки, в частности волокна. Семейство Unix setcontext является одним из вариантов; другой - использовать многопоточность, но с синхронной очередью (в основном однопотоковой, но между двумя потоками управления).

Ответ 4

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

#4 просто не стоит того. Лексинг и синтаксический анализ по своей сути являются синхронными - недостаточно просто обработки, чтобы оправдать затраты на связь. Кроме того, как правило, вы одновременно парсируете /lex несколькими файлами - это может уже максимизировать все ваши ядра сразу.

Ответ 5

То, как я справляюсь с этим в моем проекте по сборке игрушек, - это создать класс чтения файлов с функцией bool next_token(std::string&,const std::set<char>&). Этот класс содержит одну строку ввода (для сообщений об ошибках с номером строки). Функция принимает ссылку std::string для ввода токена и a std::set<char>, которая содержит символы с символом "токен". Мой класс ввода - это как синтаксический анализатор, так и лексер, но вы можете легко разделить его, если вам нужно больше причудливости. Таким образом, функции разбора просто вызывают next_token и могут выполнять свою задачу, включая очень подробный вывод ошибок.

Если вам нужно сохранить дословный ввод, вам нужно сохранить каждую строку, которая читается в vector<string> или что-то в этом роде, но не хранить каждый токен отдельно и/или дважды.

Код, о котором я говорю, находится здесь:

https://github.com/rubenvb/Ambrosia/blob/master/libAmbrosia/Source/nectar_loader.cpp

(поиск ::next_token и функция extract_nectar - это где все начинается)