Я бы использовал
Dictionary<NonTerminalSymbol,Set<List<Symbol>>>
, разрешив поиск нетерминалом набора правого производственного правила (которые представлены в виде списков терминальных / нетерминальных символов), связанных сНетерминал.(Вопрос OP показывает, что Нетерминал E может быть связан с двумя правилами, но нам нужны только правые стороны, если у нас есть левая сторона).
Это представление работает только дляванильные определения грамматики BNF, в которых нет синтаксического сахара для общих определяющих грамматику идиом.Такие идиомы обычно включают выбор , звезду Клини / плюс , ... и когда они доступны для определения грамматики, вы получаете так называемый расширенный BNF или EBNF.Если мы пишем EBNF только с разрешением choice , обозначенным | , грамматика выражения в плоской форме, на которую намекает OP в качестве примера:
E = S ;
S = P | S + P | S - P ;
P = T | P * T | P / T ;
T = T ** M | ( E ) | Number | ID ;
и мой первыйПредложение может представлять это, потому что чередование используется только для показа разных правил справа.Однако это не будет отображаться так:
E = S ;
S = P A* ;
A = + P | - P ;
P = T M+ ; -- to be different
M = * T | / T ;
T = T ** M | ( E ) | Number | ID | ID ( E ( # | C) * ) ; -- function call with skipped parameters
C = , E ;
Ключевая проблема, которую представляет эта дополнительная нотация, заключается в возможности многократно составлять операторы WBNF в определениях под-синтаксиса, и в этом весь смысл EBNF.
Чтобы представить EBNF, вы должны хранить произведения, по существу, как деревья , которые представляют, ну, в общем, структуру выражения EBNF (фактически, это по сути та же проблема, что и представление любой грамматики выражения).
Чтобы представить дерево EBNF (выражение), необходимо определить древовидную структуру EBNF.Вам нужны узлы дерева для:
- символов (терминальных или нет)
- Чередование (со списком альтернатив)
- Клини *
- Клини+
- "Необязательно"?
- другие, которые вы решаете, что ваш EBNF имеет в качестве операторов (например, списки запятых, способ сказать, что у каждого есть список грамматических элементов, разделенных выбраннымсимвол "запятая" или оканчивается выбранным символом "точка с запятой", ...)
Самый простой способ сделать это - сначала написать грамматику EBNF для самого EBNF:
EBNF = RULE+ ;
RULE = LHS "=" TERM* ";" ;
TERM = STRING | SYMBOL | TERM "*"
| TERM "+" | ';' STRING TERM | "," TERM STRING
"(" TERM* ")" ;
Обратите внимание, что я добавил список с запятыми и точками с запятой в EBNF (расширенный, помните?)
Теперь мы можем просто проверить EBNF, чтобы решить, что нужно.Теперь вам нужен набор записей (ОК, классы для C # 'er) для представления каждого из этих правил.Итак:
- класс для EBNF, который содержит набор правил
- класс для ПРАВИЛА, имеющего символ LHS и LIST
- абстрактный базовый класс дляTERM с несколькими конкретными вариантами, по одному для каждой альтернативы TERM (так называемый «дискриминируемый союз», обычно реализуемый с помощью проверок наследования и instance_of на языке OO).
Обратите внимание, что некоторые из конкретных вариантовможет ссылаться на другие типы классов в представлении, как вы получаете дерево.Например:
KleeneStar inherits_from TERM {
T: TERM:
}
Сведения, оставленные читателю для кодирования остальных.
Это поднимает неустановленную проблему для OP: как вы используете это грамматическое представление для разбора строк?
Простой ответ: получить генератор синтаксического анализатора , что означает, что вам нужно выяснить, что EBNF использует ,(В этом случае может быть проще сохранить ваш EBNF в виде текста и передать его генератору синтаксического анализатора, что делает весь этот разговор спорным.)
Если вы не можете его получить (?)или вы хотите создать свой собственный, ну, теперь у вас есть представление, на которое нужно перелезть, чтобы построить его.Еще одна альтернатива - создать анализатор рекурсивного спуска, управляемый этим представлением, для анализа.Подход к этому слишком велик, чтобы вместить его в поле ответа, но он прост для тех, кто имеет опыт рекурсии.
РЕДАКТИРОВАТЬ 10/22: ОП разъясняет, что он настаивает на разборе всех контекстно-свободных грамматик и "особенно NL". Для всех контекстно-свободных грамматик ему понадобится очень мощный механизм синтаксического анализа (Earley, GLR, full backtracking, ...). Для естественного языка ему понадобятся парсеры намного сильнее, чем те; люди десятилетиями пытались создавать такие парсеры с некоторым, но определенно не легким успехом. Кажется, что любое из этих двух требований делает обсуждение представления грамматики довольно бессмысленным; если он представляет прямую контекстно-свободную грамматику, он не будет анализировать естественный язык (доказано теми, кто пытался это делать десятилетиями), и если ему нужен более мощный анализатор NL, ему нужно будет просто использовать то, что имеют передовые типы производится. Считайте меня пессимистом в его вероятном успехе, если только он не решит стать настоящим экспертом в области анализа NL.