Взаимодействие сканера и парсера

Question

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

У меня такой вопрос, есть ли какое-то "всестороннее" обсуждение этого аспекта или в какой-либо реализации компилятора используется другая схема взаимодействия сканера / синтаксического анализатора, отличная от "сопрограммной" манеры?

Answer 1

В традиционной схеме анализатор вызывает сканер всякий раз, когда ему нужен токен.

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

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

В некотором смысле нет разницы между вызовом yylex() для получения следующего токена и вызов scanf() для получения следующего значения данных.

Это не всегда самая удобная архитектура для сканера.Иногда сканеру было бы удобно загружать токены в анализатор.Типичный случай использования - это когда сканер генерирует токены, например, через макроразложение, но иногда совпадение одного шаблона сканера содержит более одного токена.

Многие генераторы синтаксического анализатора, включая Bison,может генерировать вызываемые парсеры, обычно называемые «push-парсерами».В этой модели сканер вызывает синтаксический анализатор с каждым последующим токеном.Это все еще не модель сопрограммы, на самом деле;это просто инверсия потока управления.По аналогии с обычным вводом / выводом это эквивалентно использованию процессора данных, который вызывал fgets() для чтения каждой строки ввода, и переписывания ее как функции process_line(), которая получает строку данных для обработки (и, следовательно, невзаимодействовать с библиотекой ввода / вывода).Раннюю реализацию push-разбора можно найти в генераторе синтаксического анализатора Lemon.

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