Рекомендации по дизайну для парсера и лексера?

Question

Я пишу lexer (с re2c) и синтаксический анализатор (с лимоном) для слегка свернутого формата данных: CSV-подобный, но с определенными типами строк в определенных местах (только буквенно-цифровые символы, буквенно-цифровые символы и знаки минус, любые char, кроме кавычек и запятой, но со сбалансированными фигурными скобками и т. д.), строки внутри фигурных скобок и строк, которые выглядят как вызовы функций с открытием и закрытием фигурных скобок, которые могут содержать параметры.

Мой первый выстрел в это был лексер со многими состояниями, каждое государство обслуживало определенный формат строки. Но после многих бесполезных сообщений «неожиданного ввода» из lexer (который получил очень большое значение) я понял, что, возможно, он пытался выполнить работу синтаксического анализатора. Я отказался от первой попытки и пошел с лексером только с одним состоянием, с многозначными жетонами символов и парсером, который объединяет токены в разные типы строк. Это работает лучше, я получаю более полезные синтаксические ошибки от парсера, когда что-то отключено, но все еще кажется не совсем правильным. Я думаю о добавлении одного или двух состояний в лексер, но инициирование состояний из синтаксического анализатора, который имеет гораздо лучший «обзор», в котором тип строки требуется в данном экземпляре. В целом я чувствую себя немного глупо :(

У меня нет формального фона CS и немного застенчивы от теории математики. Но, возможно, есть учебник или книга где-то, что объясняет, что lexer должен (и не должен) do и какую часть работы должен выполнять парсер. Как создать хорошие шаблоны токенов, когда использовать слова lexer, когда и как использовать рекурсивные правила (с парсером LALR), как избежать двусмысленных правил. Прагматическая поваренная книга, которая учит Основы «Лекс и YACC-праймер/HOWTO» были приятными, но не достаточно. Поскольку я просто хочу разобрать формат данных, книги по созданию компилятора (например, книга красного дракона) выглядят немного негабарит для меня.

Или, может быть, кто-то может дать мне несколько простых правил здесь.

Answer 1

На самом деле вы должны написать грамматику для своего языка. После того, как вы едите, что граница легко:

• Лексер отвечает за принятие ввода и говорить вам, какие терминала у вас есть.
• Парсер отвечает за соответствие серии терминалов и nonterminals к правилу производства, повторно, до тех пор, пока у вас не будет дерева синтаксического анализа или сбоя анализа.

Лексер не несет ответственности за проверки входных данных за исключением тех случаев, чтобы отклонить невозможные символы и других очень основных бит. Парсер делает все это.

Посмотрите на http://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsing.html. Это вводная страница курса CS по разбору.

Answer 2

Хорошим испытанием для принятия решения, если что-то должно быть сделано с помощью синтаксического анализатора или лексический, чтобы задать себе вопрос:

ли синтаксис имеет каких-либо рекурсивные, вложенных друг в друга самоподобных элементов?
(например, вложенные круглые скобки, фигурные скобки, метки, подвыражения, субтитры и т. Д.).

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

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