Синтаксический анализ выражений с неопределенным количеством аргументов

Question

Я пытаюсь разобрать строку на самодельном языке в своего рода дерево, например:

# a * b1 b2 -> c * d1 d2 -> e # f1 f2 * g

должно привести к:

# a
  * b1 b2
    -> c
  * d1 d2
    -> e
# f1 f2
  * g

#, * и -> являются символами.a, b1 и т.д.это текстовые сообщения.

С того момента я знаю только метод rpn для вычисления выражений, и мое текущее решение заключается в следующем.Если я разрешу только один текстовый маркер после каждого символа, я могу легко преобразовать выражение сначала в RPN-нотацию (b = b1 b2;d = d1 d2;f = f1 f2) и проанализируйте его отсюда:

a b c -> * d e -> * # f g * #

Однако объединение текстовых токенов и всего остального, что приходит, кажется проблематичным.Моя идея состояла в том, чтобы создать маркерные токены (M), чтобы RPN выглядел как:

a M b2 b1 M c -> * M d2 d1 M e -> * # f2 f1 M g * #

который также поддается анализу и, кажется, решает проблему.

Это сказало:

1. Есть ли у кого-нибудь опыт работы с чем-то подобным и может ли он сказать, что это жизнеспособное решение на будущее?
2. Существуют ли лучшие методы для синтаксического анализа выражений с неопределенным количеством операторов?
3. Можете ли вы указать мне на какие-нибудь хорошие ресурсы?

Примечание.Да, я знаю, что этот пример очень напоминает префиксную нотацию Lisp, и, возможно, было бы добавить несколько скобок, но у меня здесь нет никакого опыта.Однако исходный текст не должен содержать никаких искусственных скобок, а также я не уверен, что делать с потенциальными смесями инфиксов, такими как # a * b -> [if value1 = value2] c -> d.

Спасибо за любую помощь.

Редактировать:Похоже, что то, что я ищу, - это источники в постфиксной нотации с переменным количеством аргументов.

Answer 1

Я не смог полностью понять ваш вопрос, но, похоже, вам нужно определение грамматики и генератор синтаксического анализа.Я предлагаю вам взглянуть на ANTLR ( АНТЛР ), с его помощью должно быть довольно просто определить грамматику либо для вашего исходного синтаксиса, либо для RPN.

Редактировать: (Проявив самокритику и приложив некоторые усилия для понимания деталей вопроса.) На самом деле, грамматика языка неясна из вашего примера.Однако мне кажется, что преимущества префиксных / постфиксных обозначений (т.е.что вам не нужны ни круглые скобки, ни анализатор с учетом приоритета) проистекают из того факта, что вы знать количество аргументов следовательно, каждый раз, когда вы сталкиваетесь с оператором, вы точно знаете, сколько элементов нужно прочитать (для префиксной нотации) или извлечь из стека (для постфиксной нотации).OTOH, я полагаю, что наличие операторов, которые могут иметь переменное количество аргументов, делает префиксные / постфиксные обозначения не просто сложными для анализа, но и откровенно неоднозначными.Возьмем, к примеру, следующее выражение:

# a * b c d

Какая из следующих трех является канонической формой?

1. (a, *(b, c, d))

2. (a, *(b, c), d)

3. (a, *(b), c, d)

Не зная больше об операторах, сказать это невозможно.Конечно, вы могли бы определить какую-то жадность операторов, например* более жадный, чем #, поэтому он поглощает все аргументы.Но это превзошло бы назначение префиксной нотации, потому что вы просто не смогли бы записать второй вариант из трех приведенных выше;не без дополнительных синтаксических элементов.

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