Должны ли мы предполагать, что парсер заранее считывает токены?

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

Возьмем такой пример ввода:

[groups]
syscon:
    0x000   sysmemremap
    0x004   presetctrl

[registers]
sysmemremap:
    map     1-0
    rsvd    31-2
presetctrl:32
    mux     2-0
..etc...

Так что «syscon:» и «sysmemremap:» выглядят одинаково, но один является именем группы, а другой-REGISTERNAME. Существует изменение контекста между [группами] и [регистрами], которое определяет, что каждый токен в действительности.

Это парсер, который находится в лучшем положении, чтобы сделать это контекстуальное изменение? Поскольку синтаксический анализатор не имеет секционной грамматики, где один набор грамматики применяется в одном наборе обстоятельств, а другой в другом наборе, я предполагаю, что лексер должен быть тем, кто решает, что «syscon:» генерирует имя группы, если режим таков, что он должен.

EDIT: Just spotted» The lexer hack » запись в Википедии, которая резюмирует проблему:

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

Кроме (и это вопрос, который у меня есть), что вы можете предположить о предварительном чтении парсером токенов? Если парсер идет вперед и читает больше токенов, чтобы сделать лучшее соответствие — чего я ожидал бы от него в какой-то степени, по крайней мере, он может столкнуться с ситуацией, что изменение состояния в парсере слишком поздно для лексера, поскольку он уже встретил и обработал этот токен!

Или я слишком много об этом думаю?

1 ответ

  1. Возможно, я смогу ответить на свой вопрос. Я думаю, что любая зависимость от того, что парсер делает внутри, вероятно, плохой план.

    Теперь, когда я нашел свою книгу Lex и Yacc (The O’Reilly one), одним из примеров в разделе Lex является изменение состояния — если он видит слово «verb», он начинает определять глаголы, а не искать их. Эта работа выполняется в лексере, поэтому я думаю, что это так — сделать это в лексере.