BNF к регулярным выражениям

Question

Как я могу описать язык

A → AA | ( A ) | ε

генерирует с использованием регулярных выражений?

Answer 1

Регулярные выражения принимают строки из обычных языков. Обычные языки также могут быть приняты ФСМ.

В вашем языке есть потенциально бесконечное количество скобок, которые вы должны сопоставить. Это означает, что вам нужно бесконечное состояние, которое, очевидно, невозможно в любом Конечном состоянии Поэтому ваш язык не является регулярным и не может быть сопоставлен с регулярным выражением.

Answer 2

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

Answer 3

Я не уверен, как вы могли бы записать этот язык, но этот язык не является регулярным, как можно показать, используя лемму прокачки для обычных языков (и, таким образом, это не может быть отмечено регулярным выражением). Интуитивно понятное объяснение состоит в том, что принятие слов с этого языка потребует от FDA «запоминания» количества открывающих скобок, которые он просто читает каждый раз, когда начинает читать закрывающие скобки, и это невозможно для них, поскольку у них нет «памяти» ». С другой стороны, автомат с нажатием кнопки ...

Может ли этот язык быть отмечен как {( ⁿ ) ⁿ } ^* для любого n?

Answer 4

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

Примечание: Вам также понадобится прохожий, чтобы убедиться, что скобки правильно спарены. Так что «(() ()» будет размечать, но не будет разбирать.

Answer 5

Вы не можете - регулярные выражения могут распознавать только небольшое подмножество возможных языков. В частности, неофициально, любой язык, который требует неограниченного объема памяти, потенциально распознаваемого, не распознается RE.

Здесь вам понадобится неограниченный объем памяти, чтобы запомнить, сколько открывающих скобок вы видели, чтобы убедиться, что количество закрывающих скобок одинаково.

Вам понадобится какой-то механизм, способный анализировать контекстно-свободные грамматики, чтобы можно было распознавать языки, описанные BNF в целом. Современные парсеры очень хороши в этом!