Токенизация абстрактных терминалов в грамматике LL

Question

В настоящее время я пишу базовый парсер для XML-аромата. В качестве упражнения я реализую парсер LL, управляемый таблицами.

Это мой пример грамматики БНФ:

%token name data string

%% /* LL(1) */

doc          :  elem

elem         :  "<" open_tag

open_tag     :  name attr close_tag

close_tag    :  ">" elem_or_data "</" name ">"
             |  "/>"
             ;

elem_or_data :  "<" open_tag elem_or_data
             |  data elem_or_data
             |  /* epsilon */
             ;

attr         :   name ":" string attr
             |  /* epsilon */
             ;

Правильна ли эта грамматика?

Каждый конечный литерал находится в кавычках. Абстрактные терминалы определяются как %token,

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

Answer 1

Классический подход заключается в написании регулярного выражения (или другого распознавателя) для каждого возможного терминала.

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

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

Сложность в вашем случае заключается в том, что токенизация вашего языка зависит от контекста. В частности, когда целью является elem_or_data, единственные возможные токены <, </ и "данные". Однако внутри тега "данные" невозможны, а теги "имя" и "строка" возможны (среди прочих).

Также возможно, что значение атрибута может иметь ту же лексическую форму, что и ключ (то есть имя). В самом XML значение атрибута должно быть строкой в ​​кавычках, а использование строки без кавычек будет помечено как ошибка, но, безусловно, существуют "XML-подобные" языки (например, HTML), в которые можно вставлять значения атрибутов без пробелов. некотируемый.

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