Придумать жетоны для лексера

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

Я читаю о синтаксических анализаторах здесь: http://www.ferg.org/parsing/index.html и работаю над написанием лексера, который, если я правильно понял, разделил содержимое на токены. Мне трудно понять, какие типы токенов мне следует использовать или как их создавать. Например, типы токенов в приведенном мной примере:

• STRING
• ИДЕНТИФИКАТОР
• ЧИСЛО
• WHITESPACE
• КОММЕНТАРИЙ
• EOF
• Многие символы, такие как {и (считаются их собственным типом токена

У меня проблема в том, что более общие типы токенов кажутся мне немного произвольными. Например, почему STRING имеет свой собственный отдельный тип токена и IDENTIFIER. Строка может быть представлена ​​как STRING_START + (IDENTIFIER | WHITESPACE) + STRING_START.

Это также может быть связано с трудностями моего языка. Например, объявления переменных пишутся как {var-name var value}и развертываются с помощью {var-name}. Похоже , что '{'и '}'должно быть их собственные маркеры, но var_name и VAR_VALUE правомочные лексем типа, или же они оба падают под IDENTIFIER? Более того, VAR_VALUE может содержать пробелы. Пробел после var-nameиспользуется для обозначения начала значения в объявлении. Любой другой пробел является частью значения. Становится ли этот пробел собственным токеном? Пустое пространство имеет только это значение в этом контексте. Более того, {может не быть началом объявления переменной ... это зависит от контекста (это слово снова!). {:начинает объявление имени, и{ может даже использоваться как часть некоторого значения.

Мой язык похож на Python в том, что блоки создаются с отступом. Я читал о том, как Python использует лексер для создания токенов INDENT и DEDENT (которые служат более или менее так же, как {и }во многих других языках). Python утверждает, что он не зависит от контекста, что означает для меня, что, по крайней мере, лексеру не нужно заботиться о том, где он находится в потоке, при создании токенов. Откуда лексер Python знает, что он создает токен INDENT определенной длины, не зная о предыдущих символах (например, предыдущая строка была новой строкой, поэтому начните создавать пробелы для INDENT)? Я спрашиваю, потому что мне тоже нужно это знать.

Мой последний вопрос - самый глупый: зачем нужен лексер? Мне кажется, что синтаксический анализатор может идти посимвольно и выяснять, где он находится и чего он ожидает. Добавляет ли лексер преимущество простоты?

Ваш вопрос (как подсказывает ваш последний абзац) на самом деле не о лексере, а о правильном дизайне интерфейса между лексером и анализатором. Как вы можете себе представить, есть много книг о дизайне лексеров и парсеров. Мне нравится книга парсера Дика Груна , но она не может быть хорошей вводной книгой. Мне случается сильно не нравиться книга Аппеля на основе C , потому что код не может быть полезен для расширения в ваш собственный компилятор (из-за проблем управления памятью, связанных с решением притвориться, что C подобен ML). Моим собственным введением была книга П.Дж. Брауна , но это не очень хорошее общее введение (хотя и довольно хорошее для переводчиков). Но вернемся к вашему вопросу.

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

Это означает, что (в зависимости, конечно, от деталей языка) вы должны распознать строку как «символ, за которым следует последовательность не-, а затем другого» символа. Вернуть его в анализатор как одну единицу. Существует несколько Причины этого, но важные

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

Очень часто парсеры могут предпринять немедленные действия при получении токена от лексера. Например, как только IDENTIFIER получен, анализатор может выполнить поиск в таблице символов, чтобы выяснить, известен ли уже этот символ. Если ваш синтаксический анализатор также анализирует строковые константы как QUOTE (IDENTIFIER SPACES) * QUOTE, вы будете выполнять много неуместных поисков в таблице символов, или вы в конечном итоге поднимите таблицы поиска символов выше дерева синтаксических элементов синтаксического анализатора, потому что вы можете сделать только это в тот момент, когда вы уверены, что не смотрите на строку.

Чтобы переформулировать то, что я пытаюсь сказать, но по-другому, лексер должен быть заинтересован в написании вещей, а анализатор - в структуре вещей.

Вы можете заметить, что мое описание того, как выглядит строка, очень похоже на регулярное выражение. Это не случайно. Лексические анализаторы часто реализуются на небольших языках (в смысле превосходной книги Джона Бентли « Программирование жемчужин» ), в которых используются регулярные выражения. Я просто привык думать в терминах регулярных выражений при распознавании текста.

Что касается вашего вопроса о пробелах, узнайте его в лексере. Если ваш язык предназначен для работы в свободном формате, не возвращайте токены WHITESPACE парсеру, потому что ему нужно будет просто выбросить их, поэтому производственные правила вашего парсера будут по сути спам-шумом - вещи, которые нужно распознать, просто выбрасывая их прочь.

Что касается того, что это означает, о том, как вы должны обрабатывать пробелы, когда они синтаксически значимы, я не уверен, что смогу вынести решение, которое действительно сработает, не зная больше о вашем языке. Я предпочитаю избегать случаев, когда пробелы иногда важны, а иногда нет, и использовать какой-либо разделитель (например, кавычки). Но если вы не можете разработать язык так, как вам нравится, эта опция может быть недоступна для вас.

Существуют и другие способы создания систем синтаксического анализа языка. Конечно, существуют системы конструирования компиляторов, которые позволяют вам указать комбинированную систему лексера и парсера (я думаю, что это делает версия ANTLR на Java ), но я никогда не использовал ее.

Последняя историческая заметка. Несколько десятилетий назад для лексера было важно сделать как можно больше, прежде чем передать парсеру, потому что две программы не помещались в памяти одновременно. Делая больше в лексере, вы оставляете больше памяти, чтобы сделать анализатор умным. Раньше я использовал компилятор C Whitesmiths в течение ряда лет, и если я правильно понял, он работал бы только на 64 КБ ОЗУ (это была программа MS-DOS для небольшой модели) и даже переводил вариант C, который был очень очень близок к ANSI C.

Я отвечу на ваш последний вопрос, который на самом деле не глупый. Синтаксические анализаторы могут создавать сложные конструкции на индивидуальной основе. Насколько я помню, грамматика в Harbison and Steele («Справочное руководство C - A») имеет произведения, в которых в качестве терминалов используются отдельные символы, а идентификаторы, строки, числа и т. Д. Используются как нетерминалы из отдельных символов.

С точки зрения формальных языков все, что лексер на основе регулярных выражений может распознавать и классифицировать как «строковый литерал», «идентификатор», «число», «ключевое слово» и т. Д., Может распознавать даже анализатор LL (1). Так что нет никакой теоретической проблемы с использованием генератора парсера для распознавания всего.

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

Я бы сказал, что практические соображения заставляют людей принимать отдельные лексеры и парсеры.

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

Лексеры делают вещи проще.

Обзор грамматики. Грамматика - это набор правил того, как должен выглядеть некоторый синтаксис или ввод. Например, вот игрушечная грамматика (simple_command - начальный символ):

simple_command:
 WORD DIGIT AND_SYMBOL
simple_command:
     addition_expression

addition_expression:
    NUM '+' NUM

Эта грамматика означает, что -
простая_команда состоит из
A) WORD, за которым следует DIGIT, за которым следует AND_SYMBOL (это «токены», которые я определяю)
B) «дополнение_выражение» (это правило или «нетерминальное»)

Выражение дополнения состоит из:
NUM, за которым следует «+», за которым следует NUM (NUM - это «токен», который я определяю, «+» - это буквальный знак плюс).

Поэтому, поскольку simple_command является «символом начала» (место, где я начинаю), когда я получаю токен, я проверяю, подходит ли он для simple_command. Если первый токен на входе - это WORD, а следующий токен - DIGIT, а следующий токен - AND_SYMBOL, то я сопоставил некоторую simple_command и могу предпринять некоторые действия. В противном случае я попытаюсь сопоставить его с другим правилом simple_command, которое является добавлением_экспрессии. Таким образом, если первым токеном был NUM, за которым следовал '+', за которым следовал NUM, то я сопоставил simple_command и предпринял некоторые действия. Если это не так, то у меня есть синтаксическая ошибка.

Это очень, очень базовое введение в грамматику. Для более глубокого понимания просмотрите эту вики-статью и поищите в Интернете учебники по грамматике без контекста.

Используя расположение лексера / парсера, вот пример того, как может выглядеть ваш парсер:

bool simple_command(){
   if (peek_next_token() == WORD){
       get_next_token();
       if (get_next_token() == DIGIT){
           if (get_next_token() == AND_SYMBOL){
               return true;
           } 
       }
   }
   else if (addition_expression()){
       return true;
   }

   return false;
}

bool addition_expression(){
    if (get_next_token() == NUM){
        if (get_next_token() == '+'){
             if (get_next_token() == NUM){
                  return true;
             }
        }
    }
    return false;
}

Итак, этот код выглядит ужасно, и я бы никогда не порекомендовал тройные вложенные операторы if. Но дело в том, представьте , что вы пытаетесь делать это выше посимвольно, вместо того, чтобы использовать ваши симпатичные модульные функции "get_next_token" и "peek_next_token" . Серьезно, дай ему шанс. Вам не понравится результат. Теперь имейте в виду, что приведенная выше грамматика примерно в 30 раз менее сложна, чем практически любая полезная грамматика. Видите ли вы выгоду от использования лексера?

Честно говоря, лексеры и парсеры - не самые основные темы в мире. Я бы порекомендовал сначала прочитать и понять грамматику, затем немного прочитать о лексерах / парсерах, а затем углубиться в.

Мой последний вопрос - самый глупый: зачем нужен лексер? Мне кажется, что синтаксический анализатор может идти посимвольно и выяснять, где он находится и чего он ожидает.

Это не глупо, это просто правда.

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

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

Итак, наконец, вы можете даже анализировать на уровне битов.

STRING_START + (IDENTIFIER | WHITESPACE) + STRING_START.

Нет, не может. Как насчет "("? По вашему мнению, это недопустимая строка. И убегает?

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