source: icGREP/icgrep-devel/icgrep/re/re_star_normal.h

Last change on this file was 5866, checked in by cameron, 12 days ago

Revised canonical form for nullable expressions; extended star-normal xfrm

File size: 545 bytes
Line 
1#ifndef RE_STAR_NORMAL_H
2#define RE_STAR_NORMAL_H
3
4namespace re {
5
6class RE;
7
8//A regular expression E is in star normal form if, for each starred
9//subexpression H * of E, the following SNF-conditions hold:
10//1> The follow(H, last(H)) and first(H) are disjoint.
11//2> H is not Nullable.
12//
13//For example: (a + b)* is the star normal form of (a*b*)* .
14//Both of them have the same Glushkov NFA.
15//
16
17
18class RE_Star_Normal {
19public:
20        static RE * star_normal(RE * re);
21private:
22    static RE * star_rule(RE * re);
23};
24
25}
26
27#endif // RE_STAR_NORMAL_H
Note: See TracBrowser for help on using the repository browser.