Где я должен провести границу между лексером и синтаксическим анализатором?

Question

Где я должен провести границу между лексером и синтаксическим анализатором?

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

* FLAGS (Answered Deleted)

Этот ответ определяется в формальном синтаксисе следующим образом:

mailbox-data   = "FLAGS" SP flag-list
flag-list      = "(" [flag *(SP flag)] ")"
flag           = "Answered" / "Deleted"

Поскольку они задаются как строковые литералы (они же "терминальные" токены) , было бы более правильным для лексера выдавать уникальный токен для каждого, например:

(TknAnsweredFlag)
(TknSpace)
(TknDeletedFlag)

Или это было бы так же правильно чтобы испустить что-то вроде этого:

(TknBackSlash)
(TknString "Answered")
(TknSpace)
(TknBackSlash)
(TknString "Deleted")

Моя путаница заключается в том, что первый метод может чрезмерно усложнить лексер - если бы Answered имел два значения в двух разных контекстах, лексер не испускал бы правильный токен. В качестве надуманного примера (эта ситуация не произойдет, потому что адреса электронной почты заключены в кавычки), как бы лексер справился с адресом электронной почты, таким как Answered@googlemail.com или формальный синтаксис никогда не допускает такой двусмысленности?

3 11

parsing lexer

3 ответа:

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

1

Я бы рекомендовал избегать разделения лексера и парсера - современные подходы к парсингу (такие как PEGs) позволяют смешивать лексику и парсинг. Таким образом, вам вообще не понадобятся жетоны.

0

Ira Baxter · Accepted Answer · 2011-03-20 07:28:38

Как правило, вы не хотите, чтобы лексический синтаксис распространялся в грамматику, потому что это просто детали. Например, лексер для языка программирования, такого как C, безусловно, распознает числа, но обычно нецелесообразно создавать шестнадцатеричные и десятичные маркеры, потому что это не важно для грамматики.
Я думаю, что то, что вы хотите, - это самые абстрактные лексемы, которые позволяют вашей грамматике различать случаи, представляющие интерес относительно вашей цели. Вы можете опосредовать это путаницей, вызванной в одной части грамматики, выбором, который вы можете сделать в других частях.
Если ваша цель - просто прочитать значения флага, то на самом деле вам не нужно различать их, и TknFlag без связанного содержимого будет достаточно хорош.

Если ваша цель-обработать значения флагов по отдельности, вам нужно знать, получили ли вы ответ и/или удалили показания. Как они лексически пишутся, не имеет значения; поэтому я бы пошел с ваше решение TknAnsweredFlag. Я бы сбросил TknSpace, потому что в любой последовательности флагов должны быть промежуточные пробелы (так говорят ваши спецификации), поэтому я бы попытался исключить использование любого механизма подавления пробелов, который предлагает лексер.

Иногда я сталкиваюсь с ситуациями, когда есть десятки таких флагоподобных вещей. Тогда ваша грамматика начинает загромождаться, если у вас есть маркер для каждого. Если грамматика не нуждается в знании конкретных флагов, то вы должны иметь TknFlag с связанное строковое значение. Если небольшое подмножество флагов необходимо грамматике для различения, но большинство из них не являются таковыми, то вы должны пойти на компромисс: иметь отдельные маркеры для тех флагов, которые важны для грамматики, и поймать все TknFlag с соответствующей строкой для остальных.

Что касается трудностей, связанных с двумя различными интерпретациями: это один из таких компромиссов. Если у вас есть эта проблема, то ваши токены должны иметь достаточно тонкую детализацию в обоих местах, где они находятся. необходимы в грамматике, чтобы вы могли различать. Если " \ " уместно в качестве лексемы где-то еще в грамматике, вы, конечно, можете создать как TknBackSlash, так и TknAnswered. Однако, если способ обработки чего-либо в одной части грамматики отличается от другого, вы часто можете обойти это, используя управляемый режимом лексер. Думайте о модах как о машине с конечным состоянием, каждая из которых имеет ассоциированный (суб)лексер. Переходы между режимами инициируются маркерами, которые являются сигналами (вы должны иметь Flags token; это именно такой сигнал, что вы собираетесь забрать значения флага). В режиме вы можете создавать токены, которые не будут создаваться другими режимами; таким образом, в одном режиме вы можете создавать токены"\", но в режиме флага вам это не нужно. Поддержка режима довольно распространена в лексерах, потому что эта проблема более распространена, чем можно было бы ожидать. Смотрите документацию Flex для примера.

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