Разбор выражений с неопределенным количеством аргументов - PullRequest
Новая
       11

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

1 голос
/ 18 марта 2009

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

# 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.

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

РЕДАКТИРОВАТЬ: Кажется, что я ищу источники в постфиксной записи с переменным числом аргументов.

1 Ответ

3 голосов
/ 18 марта 2009

Я не мог полностью понять ваш вопрос, но, похоже, вам нужно определение грамматики и генератор парсера. Я предлагаю вам взглянуть на ANTLR , с ним должно быть довольно просто определить грамматику для вашего исходного синтаксиса или RPN.

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

# a * b c d

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

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

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

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

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

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

...