Какой объем буферизации требуется для лексирования, управляемого таблицами?

Я пишу реализацию оболочки POSIX на Rust. Это связано с некоторыми довольно неудобными требованиями:

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

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

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


rust dfa lexical-analysis lex
person Demi    schedule 04.03.2015    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Это может стать слишком общим вопросом или генерировать ответы, содержащие слишком много мнений, что не является хорошим признаком ТАК вопрос. Это очень сложный вопрос, касающийся реализации существующих алгоритмов генератора лексеров, программирования конечных автоматов, лексических требований языка оболочки и характеристик программ на Rust и, возможно, еще нескольких тем.

Во-первых, давайте рассмотрим вопрос о возможностях лексеров, генерируемых инструментами. Давайте рассмотрим один из наиболее часто доступных, flex генератор лексеров GNU. Ответ: да; он может создать лексер, который сделает то, что вы хотите. Он достаточно гибкий и содержит достаточно различных функций для выполнения работы (как и другие подобные инструменты). Будет ли это легко и просто? Не обязательно. Инструмент позволяет вам использовать встроенные считывающие и конечные автоматы, но вы можете предоставить свои собственные процедуры ввода, написать свой собственный конечный автомат или даже обработать сложные биты внутри частей самописного кода (в C < / strong> или C ++). В руководстве, учебных веб-сайтах, обучающих видео, учебниках и есть множество примеров того, как этого добиться. вопросы здесь, на SO.

Как это поможет вам при кодировании на Rust, когда flex генерирует код на C или C ++? Нам нужен лексер на основе Rust. Однажды можно выполнить поиск литературы и посмотреть, что есть в наличии. Википедия хороша для списков и содержит список доступных инструментов синтаксического анализатора и лексера. Однако ни один из них не генерирует Rust. Однако в Rust есть такие инструменты:

Поскольку оба эти варианта находятся в стадии разработки, вам необходимо оценить их самостоятельно.

Другой альтернативой является создание собственной версии инструмента с открытым исходным кодом (например, flex) для работы с Rust. Это можно было сделать двумя способами:

  1. Вы можете пост-обработать вывод flex, чтобы преобразовать код C в код Rust, а затем скомпилировать его.
  2. Вы можете изменить код инструмента, чтобы он генерировал Rust вместо C. (Чтобы достичь желаемого, его не нужно писать на самом Rust.)

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

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

while ( NOT <<EOF>> ) {
  switch ( next_symbol() ) {

     case state_symbol[1]: 
              ....
             break;

      case state_symbol[2]:
              ....
              break;

       default:
             error(diagnostic);
  }
}

Функционально это можно сделать даже так:

action[state_symbol[next_symbol()]];

Можно вручную написать довольно компактный и эффективный анализатор регулярного языка FSA для лексирования, но это вопрос опыта владения языком и алгоритмами.

Результатом вашего широкого и неточного вопроса стал широкий и неточный ответ: да, все возможно, и Нет, это не зависит от буферизации и поиска с возвратом.

person Brian Tompsett - 汤莱恩    schedule 24.04.2015