상세 컨텐츠

본문 제목

자바스크립트로 수식 파싱하기

프로그래밍

by ∫2tdt=t²+c 2015. 9. 9. 10:24

본문

사지방에서 가장 쉽게 사용할수있는 스크립트 언어가 자바스크립트이다 보니 자바스크립트를 많이 애용하게 됐는데 이 녀석 쓰면쓸수록 생각보다 우아한 언어라는걸 깨닫게 됐습니다.우아한 언어로는 우아한 걸 해야하는게 옳겠죠. 그래서 우아한 수식 파싱을 만들고 싶어져서 한번 만들어봤습니다. 생각보다 어렵지 않게 잘 됩니다.


파서를 잘 짜려면 BNF 규칙만 잘 세워두면 됩니다. 우리는 수식을 파싱할거니깐 다음과 같은 BNF 규칙을 가지고 시작하면 되겠죠.


<AddExp> := '-' ? <MulExp> (('+'|'-') <MulExp>)*

<MulExp> := <DotExp> (('*'|'/' <DotExp>))*

<DotExp> := <PowExp>+

<PowExp> := <LeafExp> ('^' <LeafExp>)?

<LeafExp> := '(' <AddExp> ')' |

<ID> '(' <AddExp> (',' <AddExp>)* ')' |

<ID> |

<Num>

<ID> := /[a-zA-Z][a-zA-Z0-9]*/

<Num> := /-?[0-9]+(\.[0-9]+)?/


차근차근 규칙을 하나씩 따라가보면 연산자 우선순위(괄호 및 함수호출 > 거듭제곱 > 곱셈 기호 없는 곱셈 > 곱셈 및 나눗셈 > 덧셈 및 뺄셈)에 따라 BFN를 잘 정의했음을 알 수 있습니다. 이걸 바탕으로 파싱을 시작해봅시다.


일단 사용되는 토큰을 모두 모아보죠.


가장 먼저 해야하는 일은 문자열을 토큰의 배열로 쪼개는 겁니다. 아주 간단하게 할 수 있어요.


이렇게 간단하게 10몇줄만으로 Tokenize를 할수있습니다.


다음 단계는 실제 BNF 규칙에 따라 트리 구조를 만들어내는 것입니다. 먼저 트리를 정의해야겠죠. 우리가 사용할 트리는 다음과 같습니다.

S : 덧셈으로 연결된 식을 담는 트리 (뺄셈은 -1을 곱한 항으로 더하는걸로 처리할거여서 따로 다루지 않겠습니다)

M : 곱셈으로 연결된 식을 담는 트리

D : 나눗셈으로 연결된 식을 담는 트리

P : 거듭제곱으로 연결된 식을 담는 트리

C : 상수가 들어있는 말단 트리 노드

V : 변수가 들어있는 말단 트리 노드

F : 함수 호출(함수명과 인수들로 연결된 트리)


트리 오브젝트를 정의해봅시다.


이제 이 작업에서 가장 귀찮기도 한데 가장 재밌기도 한 진짜 파싱입니다. 길어보이는데, 사실 별거 없고 BNF 규칙에 따라 각각의 단계를 서술해 놓은것에 불과합니다.


pAdd에서 부호뒤집힌 트리를 만드는 함수 makeNeg가 나왔는데 다음과 같게 만들수 있습니다.


마지막으로 파싱결과 함수!


근데 트리만 만들어 무얼하겠습니까! 수식이면 계산해줘야지. 계산할수 있게 수식 트리에 eval함수를 추가해보겠습니다.


연산용 함수들을 좀 추가해봅시다. Math에 정의된 녀석들을 써보죠.


짜잔 실제로 실행해볼까요


실제로 써먹어봤습니다. 적분의 수학이야기 - 수식 계산기 (물론 이 페이지에는 다중정밀도 연산 기능도 추가되어 있지만, 수식 파싱하는데 사용한 기술은 본질적으로 같습니다.)


관련글 더보기

댓글 영역