Какая именно часть анализа должна выполняться лексическим анализатором?

Question

Существует ли формальное определение цели или, при четкой наилучшей практике использования, лексического анализа (лексера) во время / перед синтаксическим анализом?

Я знаю, что цель лексера - преобразовать поток символов в поток токенов, но не может случиться так, что в некоторых (неконтекстных) языках предполагаемое понятие "токен" тем не менее может зависеть от контекста а "токены" может быть сложно идентифицировать без полного разбора?

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

Существуют ли какие-то четкие правила, которым нужно следовать при принятии решения о том, что делать лексеру, а что оставить парсеру?

Answer 1

Существует ли формальное определение цели [лексического анализатора]?

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

… Или четкая лучшая практика использования

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

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

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

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

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

Конечно. Классический пример можно найти в регулярном выражении EcmaScript "литералы", которое необходимо лексически анализировать с помощью совершенно другого сканера. EcmaScript 6 также определяет строковые литералы шаблона, для которых требуется отдельная среда сканирования. Это может мотивировать обработку без сканера, но также может быть реализовано с помощью синтаксического анализатора LR(1) с лексической обратной связью, в котором действие сокращения отдельных нетерминалов маркера вызывает переключение на другой сканер.

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

Все приемлемо, если это работает, но этот конкретный пример мне кажется не особо полезным. Синтаксические анализаторы выражений LR (и даже LL) не нуждаются в помощи лексического сканера для отображения контекста знака минус. (Наивные грамматики предшествования операторов действительно нуждаются в такой помощи, но более тщательно продуманная архитектура op-prec не будет. Однако существование генераторов синтаксического анализатора LALR более или менее устраняет необходимость в синтаксических анализаторах op-prec.)

Вообще говоря, чтобы лексер мог идентифицировать синтаксический контекст, он должен дублировать анализ, выполняемый синтаксическим анализатором, тем самым нарушая одну из основных лучших практик разработки кода ("не дублируйте функциональность"). Тем не менее, иногда это может быть полезно, поэтому я бы не стал защищать абсолютный запрет. Например, многие синтаксические анализаторы для правил производства, подобных yacc/bison, компенсируют тот факт, что наивной грамматикой является LALR(2), путем специальной маркировки токенов ID, за которыми сразу следует двоеточие.

Другой пример, вновь взятый из EcmaScript, - это эффективная обработка автоматической вставки точек с запятой (ASI), которая может быть выполнена с использованием таблицы поиска, ключи которой представляют собой 2 набора последовательных токенов. Точно так же синтаксис с поддержкой пробелов в Python удобно обрабатывать с помощью лексического сканера, который должен уметь понимать, когда имеет место отступ (например, не внутри скобок или скобок).