Как бы вы разбирали отступы (стиль Python)?

Question

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

Я уже погуглил и нашел умный подход для его анализа, генерируя токены INDENT и DEDENT в лексере.

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

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

Answer 1

Это гипотетически, так как это будет зависеть от того, какую технологию вы используете для своего лексера и анализатора, но проще всего было бы получить токены BEGINBLOCK и ENDBLOCK, аналогичные фигурным скобкам в C. Использование " правило офсайда " ваш лексер должен следить за стеком уровней неопределенности. Когда уровень отступа увеличивается, выдает BEGINBLOCK для парсера; когда уровень отступа уменьшается, выдает ENDBLOCK и всплывающие уровни из стека.

Вот еще одно обсуждение этого на SO, кстати.

Answer 2

Также вы можете отследить где-нибудь в лексере, сколько идентичных элементов предшествует первой строке и передать его парсеру. Самая интересная часть - попытаться передать его парсеру правильно :) Если ваш парсер использует lookahead (здесь я имею в виду, что парсер может запросить переменное число токенов, прежде чем он действительно будет соответствовать хотя бы одному), тогда попытка передать его через одну глобальную переменную кажется это очень плохая идея (потому что лексер может проскользнуть на следующую строку и изменить значение счетчика отступов, пока анализатор все еще пытается проанализировать предыдущую строку). Кроме того, глобальные переменные являются злом во многих других случаях;) Маркировка «реального» токена первой строки в некотором смысле с помощью счетчика отступов более разумна. Я не могу дать вам точный пример (я даже не знаю, какие генераторы парсеров и лексеров вы собираетесь использовать, если таковые имеются ...), но что-то вроде хранения данных на токенах первой строки (это может быть неудобно, если вы можете ' t легко получить такой токен из анализатора) или сохранение пользовательских данных (карта, которая связывает токены с отступом, массив, где каждая строка в исходном коде как индекс и значение отступа как значение элемента) кажется достаточным. Недостатком этого подхода является дополнительная сложность для синтаксического анализатора, который должен будет различать идентичные значения и изменять его поведение на его основе. Здесь может работать что-то вроде LOOKAHEAD ({yourConditionInJava}) для JavaCC, но это НЕ очень хорошая идея. Многие дополнительные токены в вашем подходе кажутся менее злыми вещами:)

В качестве другой альтернативы я бы предложил смешать эти два подхода. Вы можете генерировать дополнительные токены только тогда, когда счетчик отступов меняет свое значение на следующей строке. Это как искусственный токен BEGIN и END. Таким образом, вы можете уменьшить количество «искусственных» токенов в вашем потоке, передаваемых в анализатор от лексера. Только грамматика вашего парсера должна быть скорректирована для понимания дополнительных токенов ...

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