Рекомендации по разработке парсера и лексера?

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

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

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

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


string parsing character dataformat lexer
person chiborg    schedule 07.07.2010    source источник

Ответы (2)


arrow_upward
7
arrow_downward

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

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

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

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

person Borealid    schedule 07.07.2010
comment
Спасибо, это полезно. У меня всегда возникает соблазн создать умные регулярные выражения для своих терминалов. Так что в будущем я буду использовать больше производственных правил в моем парсере. - person chiborg; 07.07.2010

arrow_upward
5
arrow_downward

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

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

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

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

person SasQ    schedule 01.09.2010