Mercurial > hg > Applications > Grep

comparison c/regexParser/main.cc @ 56:8901bc071d33

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
comparison
equal deleted inserted replaced
55:883e3473a9f5 56:8901bc071d33
1 /* 1 /*
2 Very Simple Calculator 2 * <literal> ::= [a-z][A-Z][0-9]
3 $Id$ 3 * <charClass> ::= '['<literal>'-'<literal>']'
4 * <string> ::= <literal><literal>*
5 * <or> ::= '('<regex>'|'<regex>')'
6 * <*> ::= <regex>'*'
7 * <regex> ::= <literal>|<conc>|<or>|<charClass>
4 */ 8 */
5 9
6 #include <stdio.h> 10 #include <stdio.h>
11 #include <stdlib.h>
12 #include <string.h>
13 char *ptr;
7 14
8 static char *ptr,*last_ptr; 15 typedef struct node {
9 static int value,lvalue; 16 int character;
10 static int last_token; 17 struct node *left;
11 static int variable[48]; 18 struct node *right;
19 } Node, *NodePtr;
12 20
13 static int expr(); 21 NodePtr charClass();
14 static int aexpr(); 22 NodePtr string();
15 static int mexpr(); 23 NodePtr _or();
16 static int term(); 24 NodePtr asterisk();
17 static int token(); 25 NodePtr regex();
18 static void error(char *); 26 NodePtr createNode(int,NodePtr,NodePtr);
19 27
28 NodePtr createNode(int character, NodePtr left, NodePtr right) {
29 NodePtr n;
30 n = (NodePtr)malloc(sizeof(Node));
31 n->character = character;
32 n->left = left;
33 n->right = right;
34 return n;
35 }
20 36
21 static int 37 // <charClass> ::= '['<literal>'-'<literal>']'
22 token() 38 NodePtr charClass() {
23 { 39 NodePtr n = createNode(0,0,0);
24 int c,d; 40 return n;
41 }
25 42
26 last_ptr = ptr; /* for error position */ 43 // <literal> ::= [a-z][A-Z][0-9]
27 c= *ptr; 44 NodePtr literal() {
28 if(!c) { 45 char c = *ptr;
29 last_token = EOF; 46 createNode(c,0,0);
30 return last_token; 47 }
31 }
32 ptr++;
33 if (c<=' ') { /* comment */
34 while(*ptr++);
35 ptr--;
36 last_token = EOF;
37 last_ptr = ptr;
38 return last_token;
39 }
40 48
41 if('0'<=c && c<='9') { /* Decimal */ 49 // <string> ::= <literal><literal>*
42 d = c-'0'; 50 NodePtr string() {
43 while((c= *ptr++)) { 51 char c = *ptr;
44 if('0'<=c && c<='9') { 52 NodePtr n = (NodePtr)malloc(sizeof(Node));
45 d = d*10 + (c - '0');
46 } else {
47 break;
48 }
49 }
50 c && ptr--;
51 value = d;
52 last_token = '0';
53 return last_token;
54 53
55 } else if ('a'<=c && c<='z') { /* variable */ 54 if (('a'<=c && c<='z')||('A'<=c && c<='Z')||('0'<=c && c<='9')) {
56 value = c-'a'; /* return variable reference */ 55 n = createNode(0,literal(),string());
57 last_token = 'v'; 56 return n;
58 return last_token;
59 } else { 57 } else {
60 last_token = c; 58 n = createNode(0,0,0);
61 return last_token;
62 return c;
63 } 59 }
64 } 60 }
65 61
66 static int 62 // <or> ::= '('<regex>'|'<regex>')'
67 expr() 63 NodePtr _or() {
68 { 64 regex();
69 int d,assign; 65 while(*ptr++ == ')') {
70 66 if (*ptr == '|') {
71 d = aexpr(); 67 ptr++;
72 assign = lvalue; 68 regex();
73 switch(last_token) {
74 case '>':
75 d = (d > aexpr());
76 return d;
77 case '=':
78 if(assign>=0) {
79 d = expr();
80 variable[assign] = d;
81 return d;
82 } else {
83 error("Bad assignment");
84 return 0;
85 } 69 }
86 case ')':
87 return d;
88 case EOF:
89 return d;
90 default:
91 error("Bad expression");
92 return d;
93 } 70 }
94 } 71 }
95 72
96 static int 73 // <*> ::= <regex>'*'
97 aexpr() 74 NodePtr asterisk() {
98 {
99 int d;
100 75
101 d = mexpr();
102 switch(last_token) {
103 case '-':
104 d -= aexpr();
105 return d;
106 case '+':
107 d += aexpr();
108 return d;
109 default:
110 return d;
111 }
112 } 76 }
113 77
114 static int 78 // <regex> ::= <literal>|<string>|<or>|<charClass>
115 mexpr() 79 // <literal> は <string> に内包されるから、<regex> ::= <string>|<or>|<charClass>が正しい??
116 { 80 NodePtr regex() {
117 int d; 81
118 d = term(); 82 NodePtr n;
119 switch(last_token) { 83
120 case '*': 84 while (int c = *ptr++) {
121 d *= mexpr(); 85 if (c == '(') {
122 return d; 86 ptr++;
123 case '/': 87 _or();
124 d /= mexpr(); 88 } else if (c == '[') {
125 return d; 89 charClass();
126 default: 90 } else {
127 return d; 91 n = createNode(0,string(),regex());
92 }
128 } 93 }
129 }
130 94
131 static int 95 return n;
132 term()
133 {
134 int d;
135
136 lvalue= -1;
137 token();
138 if(last_token==EOF) {
139 error("Term expected");
140 }
141 switch(last_token) {
142 case '0':
143 d = value;
144 token();
145 return d;
146 case 'v':
147 d = lvalue = value;
148 token();
149 return variable[d];
150 case '(':
151 d = expr();
152 if(last_token != ')') {
153 error("Unbalanced parenthsis");
154 }
155 token();
156 return d;
157 default:
158 token();
159 error("Unknown term");
160 return 0;
161 }
162 }
163
164 static int lineno = 0;
165
166 void
167 error(char *msg)
168 {
169 fprintf(stderr,"%s on line %d\n",msg, lineno);
170 } 96 }
171 97
172 int 98 int
173 main() 99 main(int argc, char **argv)
174 { 100 {
175 int d; 101 for (int i = 1; i < argc; i++) {
176 char buf[BUFSIZ]; 102 if (strcmp(argv[i],"-regex") == 0) {
103 ptr = argv[i+1]; i++;
104 }
105 }
177 106
178 while (fgets(buf,BUFSIZ,stdin)) { 107 printf("regex : %s\n",ptr);
179 ptr = buf; 108 NodePtr n = regex();
180 d = expr(); 109
181 printf("%s = 0x%08x = %d\n",buf,d,d);
182 fflush(stdout);
183 lineno++;
184 }
185 return 0; 110 return 0;
186 } 111 }