Разбор правил CF-грамматики с использованием регулярных выражений (как с использованием шаблонов)

Question

У меня есть CF-грамматика. Это правила таковы:

S-> а | AS

A-> AB | | б

B-> B

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

Мое регулярное выражение:

\ б ([A-Z]) -> (?:? ([A-Za-Z] +) \ |) +

Для: "A-> AB | a | b" результат:

0: A-> AB | a | b

1: A

2: b

но я хочу это:

0: A-> AB | a | b

1: A

2: AB

3:

4: b

Answer 1

Вы можете просто разделить каждое правило с помощью ->|\|, чтобы получить нужный список.

Answer 2

Регулярные выражения не являются достаточно мощными для этой задачи, но используются, например, в EBFN для повышения выразительности грамматики.Вы могли бы рассмотреть синтаксический анализатор сверху вниз (сформированный через рекурсивные вызовы), чтобы проанализировать ваш ввод.Это легко реализовать на всех языках, которые допускают взаимно рекурсивные вызовы.Требуется грамматика с некоторыми ограничениями (см. Википедию по этому поводу, если вы заинтересованы).На первый взгляд ваша грамматика должна быть LL (1), т. Е. Требует 1 токен.