Хорошая практика для синтаксического анализа данных в произвольном формате

Question

Я пишу программу, которая вводит прямое воспроизведение в пользовательском формате, а затем выполняет некоторый анализ на нем (например, количество строк и слов для каждого символа). Это просто для удовольствия и предлог для изучения классных вещей. Первым шагом в этом процессе является создание парсера для этого формата. Идет:

####Play 
###Act I 
##Scene 1 
CHARACTER 1. Line 1, he's saying some stuff. 
#Comment, stage direction 
CHARACTER 2, doing some stuff. Line 2, she's saying some stuff too. 

Это довольно простой формат. Я широко читаю об элементах основного парсера, таких как CFG, поэтому теперь я готов выполнить определенную работу.

Я написал грамматику в EBNF и начал играть со шлейфом/зубров, но вызывает некоторые вопросы:

• ли сгибать/бизон слишком много для такого простого парсера? Должен ли я просто написать это сам, как описано здесь: Is there an alternative for flex/bison that is usable on 8-bit embedded systems??
• Какова хорошая практика в отношении соответствующих задач токенизатора и самого анализатора? Не существует ни одного решения, и для такого простого языка они часто перекрываются. Это особенно верно для flex/bison, где flex может выполнять некоторые интенсивные вещи с использованием регулярного выражения. Например, должен ли «#» быть токеном? Должен ли «####» быть токеном? Должен ли я создавать типы, которые содержат семантическую информацию, чтобы я мог напрямую идентифицировать, например, символ? Или я должен просто обработать его с помощью простейшего способа, а затем разрешить грамматику, определенную в бизоне, решить, что это такое?
• С flex/bison, имеет ли смысл выполнять анализ во время разбора или он более изящный для синтаксического анализа сначала, а затем снова работать с файлом с помощью другого инструмента?

Это меня очень смущает. Я ищу элегантное, возможно простое решение. Любые рекомендации?

Кстати, о языке программирования, мне все равно. На данный момент я использую C из-за flex/bison, но не стесняйтесь советовать мне о чем-то более практичном, если это широко используемый язык.

Answer 1

Очень сложно ответить на эти вопросы, не зная, каковы ваши ожидания синтаксического анализа. То есть, пример нескольких строк текста не дает четкого представления о том, что такое предполагаемый синтаксический анализ; каковы лексические и синтаксические единицы; какие отношения вы хотели бы извлечь; и так далее.

Однако грубая догадка может быть, что вы намерены произвести вложенную разобрана, где ##{i} указывает на уровень вложенности (обратно), с i≥1, поскольку один # не структурный. Это нарушает один принцип конструкции языка («не делают рассчитывать пользователь вещи, которые компьютер может рассчитывать более точно»), что может свидетельствовать структура больше похожа:

@play { 
@act { 
@scene { 
@location: Elsinore. A platform before the castle. 
@direction: FRANCISCO at his post. Enter to him BERNARDO 
BERNARDO: Who's there? 
FRANCISCO: Nay, answer me: stand, and unfold yourself. 
BERNARDO: Long live the king! 
FRANCISCO: Bernardo? 

или даже что-то XML-подобный. Но это был бы другой язык :)

Проблема с разбором любой из них с классической комбинацией сканера/парсера заключается в том, что лексическая структура несовместима; первый токен в строке является особым, но большая часть файла состоит из текста без текста. Это почти неизбежно приведет к распространению синтаксической информации между сканером и синтаксическим анализатором, поскольку сканер должен знать синтаксический контекст, чтобы решить, сканирует ли он необработанный текст.

Возможно, вы сможете избежать этой проблемы.Например, вам может потребоваться, чтобы строка продолжения начиналась с пробела, так что каждая строка, не обозначенная иначе #, начинается с имени символа. Это было бы более надежно, чем распознавание строки диалога только потому, что оно начинается с имени символа и периода, поскольку вполне возможно, что имя персонажа будет использоваться в диалоге даже в конце предложения (что, следовательно, может быть первым словом в строке продолжения.)

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

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

Является ли flex/bison слишком большим для такого простого анализатора? Должен ли я просто написать это сам ...

Тот факт, что гибкие и бизоны (потенциально) более мощные, чем необходимо для разбора определенного языка, - это красная сельдь. C более мощный, чем необходимо для написания факториальной функции - вы можете легко сделать это в ассемблере, но писать факториальную функцию - хорошее упражнение в обучении C. Аналогичным образом, если вы хотите научиться писать парсеры, это хорошо идея начать с простого языка; очевидно, что это не будет использовать каждый вариант в генераторах синтаксического анализатора/сканера, но он заставит вас начать. Вопрос в том, подходит ли тот язык, который вы разрабатываете, для этого стиля разбора, а не слишком ли он.

С flex/bison, имеет ли смысл выполнять анализ во время разбора или он более изящный для синтаксического анализа сначала, а затем снова работать с файлом с помощью другого инструмента?

Либо может быть изящным или катастрофическим; элегантность больше связана с тем, как вы структурируете свое мышление о проблеме. Сказав это, часто бывает лучше построить семантическую структуру (обычно называемую деревом синтаксиса AST - абстрактное синтаксис) во время фазы синтаксического анализа, а затем проанализировать эту структуру, используя другие функции.

Повторное сканирование входного файла вряд ли будет либо изящным, либо эффективным.