JavaScript で数式をパースする

最終更新:2009/08/07

●数式をパースするスクリプト

arith_exp_parser.js

JavaScript での実装例。パースするのみで計算するわけではない。

001: // arith_exp_parser.js
002: // Parser for the arithmetic expression
003: // KAKU PROJECT (2009)
004: 
005: // Syntax of the arithmetic expression
006: // exp1 ::= exp2 ( op1 exp2 )*
007: // exp2 ::= exp3 ( op2 exp3 )*
008: // exp3 ::= '(' exp1 ')' | op1 exp2 | num
009: // num ::= ( '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' )+
010: // op1 ::= '+' | '-'
011: // op2 ::= '*' | '/'
012: 
013: 
014: // Usage:
015: //var p = new AEParser("1234+9876-789*67");
016: //var n = p.parse();
017: 
018: var debugItems = {};
019: debugItems['tokenizer.readnum']=0;
020: debugItems['parser.readexp3']=0;
021: debugItems['parser.readexp2']=0;
022: debugItems['parser.readexp1']=0;
023: debugItems['tokenizer.nexttoken']=0;
024: debugItems['tokenizer.accepttoken']=0;
025: 
026: function kdebug (d,x) {
027:   if (debugItems[d] == 1) {
028: //    WScript.Echo(d + ":", x);
029:   }
030: }
031: 
032: // AETokenクラス
033: // インスタンスプロパティ
034: //   String value トークンの値
035: // インスタンスメソッド
036: //   boolean isNum() 数字トークンか
037: //   boolean isOP1() OP1 演算子トークン(+,-)か
038: //   boolean isOP2() OP2 演算子トークン(*,/)か
039: //   boolean isLP() 左括弧トークンか
040: //   boolean isRP() 右括弧トークンか
041: //   boolean isEOT() EOTトークンか
042: //   String toString() トークンの文字列表現
043: 
044: // インスタンスメソッド
045: function AEToken_isNUM () {
046:   return this.type == AEToken.NUM;
047: }
048: function AEToken_isOP1 () {
049:   return this.type == AEToken.OP1;
050: }
051: function AEToken_isOP2 () {
052:   return this.type == AEToken.OP2;
053: }
054: function AEToken_isLP () {
055:   return this.type == AEToken.LP;
056: }
057: function AEToken_isRP () {
058:   return this.type == AEToken.RP;
059: }
060: function AEToken_isEOT () {
061:   return this.type == AEToken.EOT;
062: }
063: function AEToken_toString () {
064:   if (this.isNUM()) {
065:     return "[NUM:" + this.value + "]";
066:   }
067:   if (this.isLP()) {
068:     return "[LP]";
069:   }
070:   if (this.isRP()) {
071:     return "[RP]";
072:   }
073:   if (this.isOP1()) {
074:     return "[OP1:" + String.fromCharCode(this.value) + "]";
075:   }
076:   if (this.isOP2()) {
077:     return "[OP2:" + String.fromCharCode(this.value) + "]";
078:   }
079:   if (this.isEOT()) {
080:     return "[EOT]";
081:   }
082: }
083: 
084: // コンストラクタ
085: function AEToken (type, value) {
086:   this.type = type;
087:   this.value = value;
088: 
089:   this.isNUM = AEToken_isNUM;
090:   this.isOP1 = AEToken_isOP1;
091:   this.isOP2 = AEToken_isOP2;
092:   this.isLP = AEToken_isLP;
093:   this.isRP = AEToken_isRP;
094:   this.isEOT = AEToken_isEOT;
095:   this.toString = AEToken_toString;
096: }
097: // クラスプロパティ
098: AEToken.NUM = 0;
099: AEToken.OP1 = 1;
100: AEToken.OP2 = 2;
101: AEToken.LP  = 3;
102: AEToken.RP  = 4;
103: AEToken.EOT = 99;
104: 
105: // AETokenizer クラス
106: //   コンストラクタ
107: //   AETokenizer(String text)
108: //   インスタンスメソッド
109: //   AEToken nextToken ()
110: //     現在のトークンを取得する。acceptToken するまで後続のトークンを取得しにいかない。
111: //     戻り値 null --- トークン取得失敗
112: //            これ以上トークンを取得できない場合、EOT トークンを返す。
113: //   void acceptToken ()
114: //     現在のトークンを破棄する。次に nextToken すると後続のトークンを取得しにいく。
115: //
116: //   サンプル:
117: //     var tokenizer = new AETokenizer(1234 + 90);
118: //     var token = null;
119: //     while ((token = tokenizer.nextToken()) != null) {
120: //       if (token.isEOT()) {
121: //         //終了処理
122: //         break;
123: //       }
124: //       if (token.isNUM()) {
125: //         token.acceptToken();
126: //         //数字トークンの処理
127: //       }
128: //       //
129: //     }
130: 
131: //function AETokenizer_getc() {
132: //  if (this.pos < this.text.length) {
133: //    return this.text.charAt(this.pos++);
134: //  }
135: //
136: //  return "";
137: //}
138: 
139: function AETokenizer_getcc() {
140:   if (this.pos < this.text.length) {
141:     return this.text.charCodeAt(this.pos++);
142:   }
143: 
144:   return -1;
145: }
146: 
147: function AETokenizer_ungetc() {
148:   if (this.pos > 0) {
149:     this.pos--;
150:   }
151: }
152: 
153: function AETokenizer_isOP1(c) {
154:   return (c == AETokenizer.cPlus || c == AETokenizer.cMinus);
155: }
156: 
157: function AETokenizer_isOP2(c) {
158:   return (c == AETokenizer.cMul || c == AETokenizer.cDiv);
159: }
160: 
161: function AETokenizer_isNUM(c) {
162:   return (c >= AETokenizer.cZero && c <= AETokenizer.cNine);
163: }
164: 
165: function AETokenizer_isSpace(c) {
166:   return (c == AETokenizer.cTAB || c == AETokenizer.cSP || c == AETokenizer.cCR || c == AETokenizer.cLF);
167: }
168: 
169: function AETokenizer_skipSpace() {
170:   var x= -1;
171:   while ((x = this.getcc()) > 0) {
172:     if (! AETokenizer.isSpace(x)) {
173:       this.ungetc();
174:       break;
175:     }
176:   }
177: }
178: 
179: function AETokenizer_readNUM (n) {
180:   var s = String.fromCharCode(n);
181:   var x = -1;
182:   while ((x = this.getcc()) > 0) {
183:     if (AETokenizer.isNUM(x)) {
184:       s += String.fromCharCode(x);
185:     } else {
186:       this.ungetc();
187:       break;
188:     }
189:   }
190: 
191: kdebug('tokenizer.readnum', AEToken.NUM);
192:   return new AEToken(AEToken.NUM, s);
193: }
194: 
195: function AETokenizer_nextToken() {
196: 
197:   if (this.currentToken != null) {
198: kdebug('tokenizer.nexttoken', this.currentToken.toString());
199:     return this.currentToken;
200:   }
201: 
202:   this.skipSpace();
203:   var x = this.getcc();
204:   if (x < 0) {
205: kdebug('tokenizer.nexttoken', 'EOT');
206:     return new AEToken (AEToken.EOT, "");
207:   }
208: 
209:   if (AETokenizer.isNUM(x)) {
210: kdebug('tokenizer.nexttoken', 'num starts with' + String.fromCharCode(x));
211:     return (this.currentToken=this.readNUM(x));
212:   }
213: 
214:   if (AETokenizer.isOP1(x)) {
215: kdebug('tokenizer.nexttoken', 'op2('+String.fromCharCode(x)+')');
216:     return (this.currentToken=new AEToken(AEToken.OP1, x));
217:   }
218: 
219:   if (AETokenizer.isOP2(x)) {
220: kdebug('tokenizer.nexttoken', 'op2('+String.fromCharCode(x)+')');
221:     return (this.currentToken=new AEToken(AEToken.OP2, x));
222:   }
223: 
224:   if (x == AETokenizer.cLP) {
225: kdebug('tokenizer.nexttoken', 'LP');
226:     return (this.currentToken=new AEToken(AEToken.LP, x));
227:   }
228: 
229:   if (x == AETokenizer.cRP) {
230: kdebug('tokenizer.nexttoken', 'RP');
231:     return (this.currentToken=new AEToken(AEToken.RP, x));
232:   }
233: 
234: kdebug('tokenizer.nexttoken', 'null');
235:   this.currentToken=null;
236:   return null;
237: 
238: }
239: 
240: function AETokenizer_acceptToken () {
241: kdebug('tokenizer.accepttoken');
242:   this.currentToken=null;
243: }
244: 
245: function AETokenizer (text) {
246: 
247:   this.text = text;
248:   this.pos = 0;
249: 
250:   this.getcc = AETokenizer_getcc;
251: //  this.getc = AETokenizer_getc;
252:   this.ungetc = AETokenizer_ungetc;
253: 
254:   this.currentToken = null;
255: 
256:   this.skipSpace = AETokenizer_skipSpace;
257:   this.readNUM = AETokenizer_readNUM;
258: 
259:   this.nextToken = AETokenizer_nextToken;
260:   this.acceptToken = AETokenizer_acceptToken;
261: 
262: }
263: 
264: AETokenizer.isNUM = AETokenizer_isNUM;
265: AETokenizer.isSpace = AETokenizer_isSpace;
266: AETokenizer.isOP1 = AETokenizer_isOP1;
267: AETokenizer.isOP2 = AETokenizer_isOP2;
268: 
269: var ctable = "09+-*/()	 \r\n";
270: 
271: AETokenizer.cZero  = ctable.charCodeAt(0);
272: AETokenizer.cNine  = ctable.charCodeAt(1);
273: AETokenizer.cPlus  = ctable.charCodeAt(2);
274: AETokenizer.cMinus = ctable.charCodeAt(3);
275: AETokenizer.cMul   = ctable.charCodeAt(4);
276: AETokenizer.cDiv   = ctable.charCodeAt(5);
277: AETokenizer.cLP    = ctable.charCodeAt(6);
278: AETokenizer.cRP    = ctable.charCodeAt(7);
279: AETokenizer.cTAB   = ctable.charCodeAt(8);
280: AETokenizer.cSP    = ctable.charCodeAt(9);
281: AETokenizer.cCR    = ctable.charCodeAt(10);
282: AETokenizer.cLF    = ctable.charCodeAt(11);
283: 
284: 
285: // Node クラス
286: //   クラスメソッド
287: //   Node genNUM(String num)
288: //   Node genAPP(int op, Node v1, Node v2)
289: //   インスタンスプロパティ
290: //   int op      (演算子の文字コード)
291: //   Node v1     (第一オペランドのノード)
292: //   Node v2     (第二オペランドのノード。op が単項演算子の場合は null)
293: //   インスタンスメソッド
294: //   boolean isNUM ()
295: //   boolean isAPP ()
296: 
297: function Node_isNUM () {
298:   return (this.type == Node.NUM);
299: }
300: 
301: function Node_isAPP () {
302:   return (this.type == Node.APP);
303: }
304: 
305: function Node_toString () {
306:   if (this.isNUM()) {
307:     return this.v1;
308:   }
309:   if (this.isAPP()) {
310:     if (this.v2 == null) {
311:       // 単項演算子のとき
312:       return String.fromCharCode(this.op) + "(" + this.v1.toString() + ")";
313:     }
314:     return "(" + this.v1.toString() + String.fromCharCode(this.op) + this.v2.toString() + ")";
315:   }
316:   return "unknown";
317: }
318: 
319: function Node_genAPP (op, v1, v2) {
320:   return new Node(Node.APP, op, v1, v2);
321: }
322: 
323: function Node_genNUM (v) {
324:   return new Node(Node.NUM, "", v, null);
325: }
326: 
327: function Node (type, op, v1, v2) {
328:   this.type = type;
329:   this.op = op;
330:   this.v1 = v1;
331:   this.v2 = v2;
332:   this.isNUM = Node_isNUM;
333:   this.isAPP = Node_isAPP;
334: 
335:   this.toString = Node_toString;
336: }
337: 
338: Node.NUM = 0;
339: Node.APP = 1;
340: Node.genNUM = Node_genNUM;
341: Node.genAPP = Node_genAPP;
342: 
343: 
344: // AEParser クラス
345: //   コンストラクタ
346: //   AEParser (String text)
347: //   インスタンスメソッド
348: //   Node parse ()
349: //     戻り値 null --- パース失敗
350: 
351: function AEParser_readExp3 () {
352: kdebug('parser.readexp3', 'start');
353:   var x = this.tn.nextToken();
354:   if (x == null) {
355: kdebug('parser.readexp3', 'null1');
356:     return null;
357:   }
358: 
359:   var r = null;
360: 
361:   if (x.isLP()) {
362:     this.tn.acceptToken();
363: kdebug('parser.readexp3', 'LP found');
364:     if ((r = this.readExp1()) != null) {
365:       if ((x = this.tn.nextToken()) != null) {
366:         if (x.isRP()) {
367:     this.tn.acceptToken();
368: kdebug('parser.readexp3', 'RP found.');
369: kdebug('parser.readexp3', r.toString());
370:           return r;
371:         }
372:       }
373:     }
374: kdebug('parser.readexp3', 'null2');
375:     return null;
376:   }
377:   if (x.isOP1()) {
378:     this.tn.acceptToken();
379:     if ((r = this.readExp2()) != null) {
380: kdebug('parser.readexp3', 'op1+exp2');
381:       return Node.genAPP(x.value, r, null);
382:     }
383: kdebug('parser.readexp3', 'null3');
384:     return null;
385:   }
386: 
387:   if (x.isNUM()) {
388:     this.tn.acceptToken();
389: kdebug('parser.readexp3', 'num:'+x.value);
390:     return Node.genNUM(x.value);
391:   }
392: 
393: kdebug('parser.readexp3', 'null4');
394: 
395:   return null;
396: }
397: function AEParser_readExp2() {
398: kdebug('parser.readexp2', 'start');
399:   var v1 = this.readExp3();
400: 
401:   if (v1 == null) {
402: kdebug('parser.readexp2', 'null1');
403:     return null;
404:   }
405: 
406:   var op = this.tn.nextToken();
407: 
408:   var v2 = null;
409: 
410:   while (op != null && op.isOP2()) {
411:     this.tn.acceptToken();
412:     if ((v2 = this.readExp3()) != null) {
413:       v1 = Node.genAPP(op.value, v1, v2);
414:     } else {
415: kdebug('parser.readexp2', 'null2');
416:       return null;
417:     }
418:     op = this.tn.nextToken();
419:   }
420: 
421:   if (op == null) {
422: kdebug('parser.readexp2', 'null3');
423:     return null;
424:   }
425: 
426: kdebug('parser.readexp2', 'end');
427: 
428:   return v1;
429: }
430: 
431: function AEParser_readExp1() {
432: kdebug('parser.readexp1', 'start');
433:   var v1 = this.readExp2();
434: 
435:   if (v1 == null) {
436: kdebug('parser.readexp1', 'null1');
437:     return null;
438:   }
439: 
440:   var op = this.tn.nextToken();
441: 
442:   var v2 = null;
443: 
444:   while (op != null && op.isOP1()) {
445:     this.tn.acceptToken();
446:     if ((v2 = this.readExp2()) != null) {
447:       v1 = Node.genAPP(op.value, v1, v2);
448:     } else {
449: kdebug('parser.readexp1', 'null2');
450:       return null;
451:     }
452:     op = this.tn.nextToken();
453:   }
454: 
455:   if (op == null) {
456: kdebug('parser.readexp1', 'null3');
457:     return null;
458:   }
459: 
460: kdebug('parser.readexp1', 'end');
461: 
462:   return v1;
463: 
464: }
465: 
466: function AEParser_parse () {
467:   var n = this.readExp1();
468:   if (n == null) {
469:     return null;
470:   }
471:   var token = this.tn.nextToken();
472:   if (token != null && token.isEOT()) {
473:     return n;
474:   }
475:   return null;
476: }
477: 
478: function AEParser (text) {
479:   this.tn = new AETokenizer(text);
480: 
481:   this.parse = AEParser_parse;
482:   this.readExp1 = AEParser_readExp1;
483:   this.readExp2 = AEParser_readExp2;
484:   this.readExp3 = AEParser_readExp3;
485: }
486: 
487: // End of arith_exp_parser.js

●動作確認1

sample.wsf

 WSH で動作確認する WSF スクリプト。sample.wsf は arith_exp_parser.js、disptree.js と同じディレクトリに保存し、ダブルクリックで実行。表示される入力ダイアログに数式を入力して「OK」ボタンを押すと、数式の括弧付き表現とツリー表現を表示する。 数式の入力には VBScript の InputBox 関数を使用。JScript に文字入力のプリミティブがないので仕方がないが、WSF スクリプトでは複数のスクリプト言語を組み合わせることが可能。

001: <?xml version="1.0" encoding="Shift_JIS" standalone="yes" ?>
002: <package>
003: <job id="aexp">
004: <runtime>
005: <description>Sample of arith_exp_parser.js</description>
006: </runtime>
007: 
008: <?job error="true" debug="true" ?>
009: <script language="javascript" src="arith_exp_parser.js" />
010: <script language="javascript" src="disptree.js"/>
011: <script language="VBScript">
012: <![CDATA[
013: Function inputExp
014:   inputExp = InputBox("計算式を入力してください。", "計算式", "1234*2345+34/456-56")
015: End Function
016: ]]>
017: </script>
018: <script language="JScript">
019: <![CDATA[
020: try {
021:   var p = new AEParser(inputExp());
022:   var n = null;
023:   WScript.Echo((n=p.parse())?n.toString():"syntax error.");
024:   WScript.Echo(disptree(0, "", n, "\n"));
025: } catch (e) {
026:   WScript.Echo(Number(e.number & 0xffff).toString() + ": " + e.description);
027: } finally {
028:   WScript.Quit();
029: }
030: ]]>
031: </script>
032: </job>
033: </package>

●動作確認2

sample.html

ブラウザで動作確認。数式を入力して「parse it!」ボタンのクリックで、ツリー表現を表示する。