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

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

4 голосов
/ 17 июля 2011

Есть ли (простой) способ в грамматике (PEG) синтаксического анализа выразить "неупорядоченную последовательность"? Правило, такое как 

Rule <- A B C

требует, чтобы A, B и C соответствовали по порядку. Правило, такое как 

Rule <- (A B C) / (B C A) / (C A B) / (A C B) / (C B A) / (B A C)

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

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

Rule <- (A / B / C){3}

и семантически проверить, что каждое правило соответствует только один раз?

Тот факт, что, например, Relax NG Compact Syntax имеет оператор «неупорядоченный список» для анализа XML, подсказывает мне, что не существует очевидного решения.

Последний вопрос: как вы думаете, добавление такого оператора приведет к неоднозначности в PEG?

1 Ответ

1 голос
/ 17 июля 2011

Правила грамматики точно отражают последовательность форм, которую вы хотите, независимо от выбранного вами механизма синтаксического анализа (например, PEG, LALR, LL (k), ...).

Единственный способ выразить, что вы хотите, чтобы все возможные последовательности чего-то просто использовали правила BNF, - это предложенное вами большое уродливое правило.

Стандартное решение состоит в том, чтобы просто определить: 

rule <- (A | B | C)*

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

Часто люди, строящие генераторы синтаксического анализатора, добавляют специальные нотации "расширенного BNF", чтобы позволить им описывать особые обстоятельства; Вы привели пример использования {3} в качестве специального синтаксиса, подразумевающего, что вы хотели только «3 из» в предположении, что генератор синтаксического анализатора принимает эту нотацию и выполняет соответствующее применение. Можно представить расширение обозначения {уникальное} , которое позволит вам описать вашу ситуацию. Я никогда не видел генератора парсеров, который бы реализовал эту идею.

...