Mercurial > hg > Applications > Grep
annotate c/regexParser/main.cc @ 56:8901bc071d33
implement string() and literal()
author | Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Thu, 11 Jun 2015 16:24:40 +0900 |
parents | 883e3473a9f5 |
children | 71b497d25273 |
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>* |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
5 * <or> ::= '('<regex>'|'<regex>')' |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
6 * <*> ::= <regex>'*' |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
7 * <regex> ::= <literal>|<conc>|<or>|<charClass> |
55 | 8 */ |
9 | |
45 | 10 #include <stdio.h> |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
11 #include <stdlib.h> |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
12 #include <string.h> |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
13 char *ptr; |
55 | 14 |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
15 typedef struct node { |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
16 int character; |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
17 struct node *left; |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
18 struct node *right; |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
19 } Node, *NodePtr; |
52
a2826bf4e80a
remove magic number
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
51
diff
changeset
|
20 |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
21 NodePtr charClass(); |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
22 NodePtr string(); |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
23 NodePtr _or(); |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
24 NodePtr asterisk(); |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
25 NodePtr regex(); |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
26 NodePtr createNode(int,NodePtr,NodePtr); |
55 | 27 |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
28 NodePtr createNode(int character, NodePtr left, NodePtr right) { |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
29 NodePtr n; |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
30 n = (NodePtr)malloc(sizeof(Node)); |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
31 n->character = character; |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
32 n->left = left; |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
33 n->right = right; |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
34 return n; |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
35 } |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
36 |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
37 // <charClass> ::= '['<literal>'-'<literal>']' |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
38 NodePtr charClass() { |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
39 NodePtr n = createNode(0,0,0); |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
40 return n; |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
41 } |
55 | 42 |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
43 // <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
|
44 NodePtr literal() { |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
45 char c = *ptr; |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
46 createNode(c,0,0); |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
47 } |
55 | 48 |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
49 // <string> ::= <literal><literal>* |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
50 NodePtr string() { |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
51 char c = *ptr; |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
52 NodePtr n = (NodePtr)malloc(sizeof(Node)); |
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 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
|
55 n = createNode(0,literal(),string()); |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
56 return n; |
55 | 57 } else { |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
58 n = createNode(0,0,0); |
55 | 59 } |
60 } | |
61 | |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
62 // <or> ::= '('<regex>'|'<regex>')' |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
63 NodePtr _or() { |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
64 regex(); |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
65 while(*ptr++ == ')') { |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
66 if (*ptr == '|') { |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
67 ptr++; |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
68 regex(); |
55 | 69 } |
70 } | |
71 } | |
72 | |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
73 // <*> ::= <regex>'*' |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
74 NodePtr asterisk() { |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
75 |
55 | 76 } |
77 | |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
78 // <regex> ::= <literal>|<string>|<or>|<charClass> |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
79 // <literal> は <string> に内包されるから、<regex> ::= <string>|<or>|<charClass>が正しい?? |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
80 NodePtr regex() { |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
81 |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
82 NodePtr n; |
49
f76fe618d5a7
implement bitset
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
83 |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
84 while (int c = *ptr++) { |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
85 if (c == '(') { |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
86 ptr++; |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
87 _or(); |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
88 } else if (c == '[') { |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
89 charClass(); |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
90 } else { |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
91 n = createNode(0,string(),regex()); |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
92 } |
55 | 93 } |
50
bb0e88fbbe02
impl bitGet and bitSet
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
49
diff
changeset
|
94 |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
95 return n; |
55 | 96 } |
97 | |
98 int | |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
99 main(int argc, char **argv) |
55 | 100 { |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
101 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
|
102 if (strcmp(argv[i],"-regex") == 0) { |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
103 ptr = argv[i+1]; i++; |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
104 } |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
105 } |
55 | 106 |
56
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
107 printf("regex : %s\n",ptr); |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
108 NodePtr n = regex(); |
8901bc071d33
implement string() and literal()
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
109 |
45 | 110 return 0; |
111 } |