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

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

0 голосов
/ 18 февраля 2019

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

Это мой пример грамматики BNF: 

%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.

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

1 Ответ

0 голосов
/ 18 февраля 2019

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

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

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

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

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

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

...