JavaScript で数式をパースする
最終更新：2009/08/07
●数式をパースするスクリプト
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
●動作確認１
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>
●動作確認２
ブラウザで動作確認。数式を入力して「parse it!」ボタンのクリックで、ツリー表現を表示する。