Разбор "простой" грамматики

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

Я хотел бы написать синтаксический анализатор для следующего "языка", который содержит одну "специальную структуру", которая выглядит так:

\command[ options ]{ contents }

Содержимое может быть любым, включая вложенные команды, и может содержать экранированные скобки или обратную косую черту \{ \} \\. Я понимаю, что "что-то" не является конкретным, но в идеале они должны определяться путем сопоставления скобок (исключая экранированные), если это возможно.

Параметры должны быть разделены запятыми списком выражений присваивания, такими как name = value, но это может быть строка с кавычками, содержащая символы = или ,. Наконец, предыдущие name и command должны проверять регулярное выражение \w[\w\d\._-+*]*, то есть первым символом должна быть буква, а остальные символы должны быть буквой, цифрой или одной из . _ - + *.

Написание этого с помощью регулярных выражений кажется чрезмерно сложным (например, поскольку значения могут содержать цитируемые символы , =, которые иначе разделяли назначения или пары имя/значение). Поэтому я считаю, что наиболее подходящим инструментом здесь является грамматика, но, несмотря на поверхностные чтения, я просто не уверен, как ее написать (BNF, PEG и т.д.), Какой тип парсеров использовать (LR, рекурсивный и т.д.)?, и как я мог бы использовать вывод синтаксического анализа в практической программе.

Я бы предпочел ответы на Python, который объясняет тег, но, конечно, я был бы совершенно доволен комбинацией инструментов, если это необходимо/лучше подходит.

ПРИМЕЧАНИЕ: это НЕ о LaTeX. Я понимаю сходство, конечно, но LaTeX чрезвычайно сложнее, чем предыдущий язык, например, с кодами символов, зависящими от контекста. Я просто прошу практический пример, который (я думаю) достаточно прост для SO, и все же уже будет полезен для меня в моей повседневной работе.

Ответы

Ответ 1

Начните с выражения вашей грамматики более формально, в любой нотации, которую вы предпочитаете. например, из вашего описания, EBNF будет выглядеть следующим образом:

program := element+
element := command | literal
literal := (not '\')+

command := '\'identifier options? '{' program '}'
options := option | options ',' option
option  := identifier '=' value
value   := number | string

string  := '"' (escape | not '\' or '"')* '"'
escape  : = '\' char

Затем либо передайте это генератору синтаксического анализатора (pyParsing, pyYACC, ANTLR), либо напишите парсер вручную. В последнем случае простейший вариант - сверху вниз: начинайте с вершины грамматики и преобразовывайте каждое правило в функцию, которая либо вернет анализируемый AST node, либо потребляет вход или ничего не возвращает или не бросает. Пример:

 def program():
    elements = []
    while next_sym():
        elements.append(element())
    return {'type': 'program', 'children': elements}

 def element():
     return command() or literal()

 def command():
     if next_sym() == '\\':
         get_sym()
         ...parse command here
         return {'type': 'command', 'children': ...}
     return None

где next_sym возвращает следующий символ из ввода (или None в EOF), а get_sym потребляет символ и продвигает входной буфер.