Руководство по проектированию для парсера и лексера?

Question

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

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

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

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

Answer 1

Что вам действительно нужно сделать, так это написать грамматику для вашего языка.Если у вас есть это, граница проста:

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

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

Answer 2

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

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

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

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