字符串匹配中的正则表达式评估(regular expression evaluation in string matching)

字符串匹配中的正则表达式评估(regular expression evaluation in string matching)

我正在阅读Robert Sedgwick的Algorithms中的正则表达式。

这里为正则表达提到下面

A* | (A*BA*BA*)*

这里作者提到的匹配是：AAA，BBAABB和BABAAA。 与上述正则表达式不匹配的是ABA BBB BABBAAA。

我的问题是BBAABB如何匹配以及BABAAA如何匹配。 请解释一下。

一般来说，我正在寻找如何评估| 和正则表达式中的*运算符。 在下面的例子中，如果我们有一个+，我们如何才能在b中单独使用b，因为它说我们必须至少有一个a。

(a+b)* = (λ, a, b, aa, ab, ba, bb, aaa, ...)

I am reading Regular expression in Algorithms by Robert Sedgwick book.

Here for regular expression mention below

A* | (A*BA*BA*)*

Here author mentioned matches are: AAA, BBAABB, and BABAAA. does not match for above regular expression are ABA BBB BABBAAA.

My question is how BBAABB is matching and same way how BABAAA is matching. Kindly explain.

In general I am looking for how to evaluate with | and * operators in regular expressions. in below example how we can get b alone in set if we have a+ since it says we must have atleast 1 a.

(a+b)* = (λ, a, b, aa, ab, ba, bb, aaa, ...)

最满意答案

*和+之间有一个区别。 你放*之后的角色可以没有重复。 但在+情况下，它可以有至少1次重复。 在A* | (A*BA*BA*)* A* | (A*BA*BA*)* ， BBAABB有以下原因并且符合(A*BA*BA*)*模式

A*开头没有A BA*为1 B而没有A BA*和BA* 1B *在(A*BA*BA*)*显示图案可以重复。 所以第二次重复是BB ，这是有效的

这些是BBAABB有效的点。

There is one difference between * and +. The character after which you put * can have no repetition. But in + case, it can have minimum 1 repetition. In A* | (A*BA*BA*)*, BBAABB is valid for following reasons and it is according to (A*BA*BA*)* pattern

No A at start for A* 1 B for BA* and no A 1 B for BA* and 2 A * at end of (A*BA*BA*)*shows that pattern can repeat. So second repetition is BB which is valid

These are the points for which BBAABB is valid.