Написание лексера для контекстно-зависимого языка разметки, имеющего рекурсивные структуры, такие как вложенные списки.

Я работаю над транспилятором reStructuredText в Rust, и мне нужен совет относительно того, как следует структурировать лексирование в языках с рекурсивными структурами. Например, списки внутри списков возможны в rST:

* This is a list item

  * This is a sub list item

* And here we are at the preceding indentation level again.

По умолчанию docutils.parsers.rst использует подход сканирования ввод по одной строке за раз:

Синтаксический анализатор reStructuredText реализован как конечный автомат, проверяющий ввод по одной строке за раз.

Упомянутый конечный автомат в основном работает с набором состояний в форме (regex, match_method, next_state). Он пытается сопоставить текущую строку с regex на основе текущего состояния и запускает match_method при переходе к next_state, если совпадение завершается успешно, делая это до тех пор, пока не закончатся строки для сканирования.

Тогда мой вопрос: это лучший подход к сканированию такого языка, как rST? До сих пор мой подход заключался в создании итератора Chars для источник и разъедают источник, пытаясь сопоставить со структурами в текущем скаляре Unicode. В какой-то степени это работает, когда все, что я делаю, - это сканирование встроенного контента, но теперь я пришел к осознанию того, что обработка рекурсивных структур уровня тела, таких как вложенные списки, будет головной болью. Похоже, мне понадобится целая куча состояний с повторяющимися регулярными выражениями и родственными методами во многих состояниях для сопоставления с отступами перед новыми строками и т. Д.

Было бы лучше иметь итератор строк исходного кода и сопоставить их на построчной основе, и если такая строка, как

    * this is an indented list item

встречается в State::Body, просто перейти в такое состояние, как State::BulletList, и начать лексирование строк в соответствии с указанными там правилами? Вышеупомянутая строка может быть преобразована, например, в последовательность

TokenType::Indent, TokenType::Bullet, TokenType::BodyText

Есть мысли по этому поводу?


parsing rust lexer restructuredtext
person SeSodesa    schedule 05.06.2020    source источник
comment
Вы можете задать свой вопрос о r / compilers. К вашему сведению, вы, кажется, путаете лексирование и синтаксический анализ; и вообще Regex - не лучший подход ни к лексированию, ни к синтаксическому анализу, хотя их можно использовать для быстрых и грязных экспериментов.   -  person Matthieu M.    schedule 05.06.2020
comment
@MatthieuM. У меня есть представление о том, что такое лексирование и синтаксический анализ: лексер генерирует токены, а синтаксический анализатор строит из них синтаксическое дерево. Парсер documenttils, кажется, представляет собой сочетание того и другого, и мой вопрос касался идеи создания полностью отдельных лексера и парсера для rST.   -  person SeSodesa    schedule 05.06.2020
comment
Отдельный лексер не должен заботиться о том, есть ли * для (1) маркированного списка, (2) начала курсива или (3) начала жирного шрифта. В этом смысле лексический анализатор не зависит от контекста. И поэтому вашему лексеру не должен требоваться конечный автомат.   -  person Matthieu M.    schedule 05.06.2020
comment
Единственная проблема - если вы хотите представить отступ как часть потока токенов. Я лично считаю, что это чище, чем аннотировать каждый токен информацией о строке / столбце. Если вы просто представляете уровень отступа (x пробелов / табуляции), тогда он все еще не зависит от контекста, если вы представляете Indent / Deindent, то он слегка контекстно-зависимый, но все же не требует конечного автомата - - только уровень отступа предыдущей (значащей) строки.   -  person Matthieu M.    schedule 05.06.2020
comment
@MatthieuM. Я предполагаю, что моя путаница связана с тем, что я все еще буду использовать скомпилированные регулярные выражения (также известные как детерминированные конечные автоматы) для обнаружения этих более простых неконтекстных токенов, поэтому, когда кто-то говорит мне, что я не использую конечный автомат с теми, у меня возникает когнитивный диссонанс . В любом случае, я думаю, что это то направление, в котором я хочу двигаться, построчно генерируя токены. Затем синтаксический анализатор может беспокоиться об уровнях отступов (пробелов в начале строки), поскольку он будет знать, как считать как автомат выталкивания.   -  person SeSodesa    schedule 05.06.2020
comment
@JohnKugelman Если бы я знал длину отступа, например, количество пробелов, не мог бы я проверить уровень отступа в синтаксическом анализаторе, который будет иметь состояния в любом случае?   -  person SeSodesa    schedule 05.06.2020
comment
Позвольте нам продолжить это обсуждение в чате.   -  person Matthieu M.    schedule 05.06.2020

Ответы (1)


arrow_upward
2
arrow_downward

Я мало что знаю о rST. Но вы говорите, что у него «рекурсивные» структуры. В этом случае вы не сможете полностью лексировать его как рекурсивную структуру, используя только конечные автоматы, регулярные выражения или даже генераторы лексических выражений.

Но это неправильный способ думать об этом. Работа лексера - идентифицировать атомы языка. Работа парсера - распознавать структуру, особенно если она рекурсивна (да, парсеры часто строят деревья, записывая рекурсивные структуры, которые они нашли). Поэтому создайте лексер, игнорируя контекст, если можете, и используйте синтаксический анализатор для сбора рекурсивных структур, если они вам нужны. Вы можете узнать больше о различиях в моем SO-ответе о Parsers Vs. Лексеры https://stackoverflow.com/a/2852716/120163

Если вы настаиваете на том, чтобы все это выполнялось в лексере, вам нужно будет дополнить его стеком выталкивания для отслеживания рекурсивных структур. Тогда вы создаете неаккуратный парсер, замаскированный под лексер. (Вам, вероятно, по-прежнему понадобится настоящий синтаксический анализатор для обработки вывода этого «лексера»).

Наличие выталкивающего стека действительно полезно, если в языке есть разные атомы в разных контекстах, особенно если контексты вложены; в этом случае вам нужен стек режимов, который вы изменяете, когда лексер обнаруживает токены, указывающие на переключение из одного режима в другой. Действительно полезным расширением этой идеи является то, что при изменении режима выбираются различные лексеры, каждый из которых создает лексемы, уникальные для этого режима.

Например, вы можете сделать это для лексирования языка, содержащего встроенный SQL. Строим парсеры для JavaScript; наш лексер использует стек для обработки содержимого литералов регулярного выражения и отслеживания вложенности {...} [...] и (...). (У этого, возможно, есть обратная сторона: он отклоняет версии JQuery.js, содержащие искаженные регулярные выражения [да, они существуют]. Javascript не заботится о том, определяете ли вы неверный литерал регулярного выражения и никогда не используете его, но это кажется довольно бессмысленным.)

Особый случай стека возникает, если у вас есть только пары треков "(" ... ")" или их эквивалент. В этом случае вы можете использовать счетчик, чтобы записать, сколько «толчков» или «толчков» вы могли сделать на реальном стеке. Если у вас есть две или более таких пар жетонов, счетчики не работают.

person Ira Baxter    schedule 05.06.2020
comment
Да, я думаю, что теперь у меня есть более четкое представление о разделении проблем. Я собираюсь просто сканировать по одной строке за раз и проверять маркеры, такие как маркеры, обычный текст, отступы и так далее. Затем я передам этот поток токенов синтаксическому анализатору (для реализации). Дело в том, что я хочу избавиться от лишних пробелов уже на этапе лексирования, и, сделав это более модульным, мне будет легче понять. Мой первый транспайлер и т. Д. - person SeSodesa; 05.06.2020