Взаимная рекурсия в Regex

Question

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

Например, регулярное выражение, распознающее язык {a^n b^n}, будет/a $ 0b/где $ 0 обозначает текущее регулярное выражение. Это была бы базовая рекурсия.

Взаимная рекурсия такая же, но с различными регулярными выражениями.

Как мы можем сделать это с помощью Javascript?

Спасибо за ваши ответы!

Answer 1

К сожалению, Javascript не поддерживает рекурсивные регулярные выражения.

Вы можете реализовать основную рекурсивную функцию с проверками на первую и последнюю букву (чтобы они a и b соответственно) и рекурсивный вызов для внутренней струны ($0 в вашем примере).

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

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

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

Чтобы по-настоящему воплотить конечный автомат, пойдите с помощью токена, когда вы делаете проверки; для примера выше, сначала проверьте, что у вас есть a в начале, а затем рекурсия, затем проверьте на b в конце.

Язык, который вы описываете, даже не является regular language, и поэтому взаимно рекурсивный язык будет далек от него. Вы не можете использовать механизм регулярных выражений в Javascript для создания взаимно-рекурсивного языка, поэтому вам нужно написать конечный автомат для одновременного ввода токена и перейти к следующему состоянию, если мы столкнемся с совпадением.