Mercurial > hg > Applications > Grep
annotate c/regexParser/main.cc @ 60:8616a045a7f4
impl asterisk
author | Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 14 Jul 2015 15:30:34 +0900 |
parents | af189c727733 |
children | 67cade0e35b0 |
rev | line source |
---|---|
55 | 1 /* |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
2 * <literal> ::= [a-z][A-Z][0-9] |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
3 * <charClass> ::= '['<literal>'-'<literal>']' |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
4 * <string> ::= <literal><literal>* |
58
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
5 * <group> ::= '('<regex>')' |
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
6 * <or> ::= <regex>'|'<regex> |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
7 * <*> ::= <regex>'*' |
58
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
8 * <regex> ::= <string>|<or>|<charClass>|<group>|<*> |
55 | 9 */ |
10 | |
45 | 11 #include <stdio.h> |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
12 #include <stdlib.h> |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
13 #include <string.h> |
57
71b497d25273
fix literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
56
diff
changeset
|
14 |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
15 typedef struct node { |
58
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
16 struct node *self; |
57
71b497d25273
fix literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
56
diff
changeset
|
17 char character; |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
18 struct node *left; |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
19 struct node *right; |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
20 } Node, *NodePtr; |
52
a2826bf4e80a
remove magic number
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
51
diff
changeset
|
21 |
58
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
22 char *ptr; |
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
23 NodePtr regexHeadNode; |
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
24 |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
25 NodePtr charClass(); |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
26 NodePtr string(); |
58
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
27 NodePtr group(); |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
28 NodePtr _or(); |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
29 NodePtr asterisk(); |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
30 NodePtr regex(); |
57
71b497d25273
fix literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
56
diff
changeset
|
31 NodePtr createNode(char,NodePtr,NodePtr); |
55 | 32 |
60
8616a045a7f4
impl asterisk
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
33 void printNodeDate(NodePtr n) { |
8616a045a7f4
impl asterisk
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
34 puts("---------------------"); |
8616a045a7f4
impl asterisk
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
35 printf("Self Node char : %c\n", n->character); |
8616a045a7f4
impl asterisk
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
36 printf("Self Node addr : %p\n", n->self); |
8616a045a7f4
impl asterisk
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
37 printf("left Node addr : %p\n", n->left); |
8616a045a7f4
impl asterisk
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
38 printf("right Node addr : %p\n", n->right); |
8616a045a7f4
impl asterisk
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
39 puts("---------------------"); |
8616a045a7f4
impl asterisk
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
40 puts(""); |
8616a045a7f4
impl asterisk
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
41 } |
8616a045a7f4
impl asterisk
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
42 |
57
71b497d25273
fix literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
56
diff
changeset
|
43 NodePtr createNode(char character, NodePtr left, NodePtr right) { |
71b497d25273
fix literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
56
diff
changeset
|
44 NodePtr n = (NodePtr)malloc(sizeof(Node)); |
58
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
45 n->self = n; |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
46 n->character = character; |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
47 n->left = left; |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
48 n->right = right; |
58
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
49 |
60
8616a045a7f4
impl asterisk
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
50 printNodeDate(n); |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
51 return n; |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
52 } |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
53 |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
54 // <charClass> ::= '['<literal>'-'<literal>']' |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
55 NodePtr charClass() { |
60
8616a045a7f4
impl asterisk
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
56 |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
57 } |
55 | 58 |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
59 // <literal> ::= [a-z][A-Z][0-9] |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
60 NodePtr literal() { |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
61 char c = *ptr; |
57
71b497d25273
fix literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
56
diff
changeset
|
62 NodePtr n = createNode(c,0,0); |
71b497d25273
fix literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
56
diff
changeset
|
63 ptr++; |
71b497d25273
fix literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
56
diff
changeset
|
64 return n; |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
65 } |
55 | 66 |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
67 // <string> ::= <literal><literal>* |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
68 NodePtr string() { |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
69 char c = *ptr; |
58
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
70 NodePtr n = NULL; |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
71 if (('a'<=c && c<='z')||('A'<=c && c<='Z')||('0'<=c && c<='9')) { |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
72 n = createNode(0,literal(),string()); |
55 | 73 } else { |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
74 n = createNode(0,0,0); |
55 | 75 } |
58
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
76 return n; |
55 | 77 } |
78 | |
58
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
79 // <group> ::= '('<regex>')' | '('<regex>'|'<regex>')' |
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
80 NodePtr group() { |
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
81 NodePtr n; |
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
82 if (*ptr == ')') { |
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
83 n = createNode(0,0,0); |
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
84 ptr++; |
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
85 } else { |
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
86 ptr++; |
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
87 n = regex(); |
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
88 } |
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
89 |
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
90 return n; |
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
91 } |
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
92 |
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
93 |
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
94 // <or> ::= <regex>'|'<regex> |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
95 NodePtr _or() { |
59 | 96 ptr++; |
58
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
97 NodePtr n = createNode('|',regexHeadNode,regex()); |
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
98 return n; |
55 | 99 } |
100 | |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
101 // <*> ::= <regex>'*' |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
102 NodePtr asterisk() { |
60
8616a045a7f4
impl asterisk
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
103 ptr++; |
8616a045a7f4
impl asterisk
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
104 NodePtr n = createNode('*',regexHeadNode,regex()); |
8616a045a7f4
impl asterisk
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
105 return n; |
55 | 106 } |
107 | |
58
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
108 // <regex> ::= <string>|<or>|<charClass>|<group>|<*> |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
109 NodePtr regex() { |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
110 |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
111 NodePtr n; |
49
f76fe618d5a7
implement bitset
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
112 |
58
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
113 while (*ptr != '\0') { |
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
114 if ((*ptr == '(') || (*ptr == ')')) { |
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
115 n = group(); |
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
116 } else if (*ptr == '[') { |
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
117 n = charClass(); |
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
118 } else if (*ptr == '|'){ |
57
71b497d25273
fix literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
56
diff
changeset
|
119 n = _or(); |
60
8616a045a7f4
impl asterisk
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
120 } else if (*ptr == '*'){ |
8616a045a7f4
impl asterisk
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
59
diff
changeset
|
121 n = asterisk(); |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
122 } else { |
57
71b497d25273
fix literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
56
diff
changeset
|
123 n = string(); |
58
4053c3e0fa7f
implement group()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
57
diff
changeset
|
124 regexHeadNode = n; |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
125 } |
55 | 126 } |
50
bb0e88fbbe02
impl bitGet and bitSet
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
49
diff
changeset
|
127 |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
128 return n; |
55 | 129 } |
130 | |
131 int | |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
132 main(int argc, char **argv) |
55 | 133 { |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
134 for (int i = 1; i < argc; i++) { |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
135 if (strcmp(argv[i],"-regex") == 0) { |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
136 ptr = argv[i+1]; i++; |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
137 } |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
138 } |
55 | 139 |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
140 printf("regex : %s\n",ptr); |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
141 NodePtr n = regex(); |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
142 |
45 | 143 return 0; |
144 } |