수식 파서 트리를 만들기 전에 입력 소스에 사용할 수식을 정규화를 하기로 해요. 정규화는 같은 종류의 표현을 묶어 간소화하는 과정입니다. 여기에서는 정규화 표현에 많이 사용하는 BNF로 표현할게요.
BNF 표기법은 Backus Naur Form의 약자로 존 배커스와 나우르가 만든 표기법으로 문법을 수학적인 수식으로 나타낼 때 사용하는 표기법입니다.
단말 표현과 비단말 표현 및 기호를 이용하여 문장 생성 과정을 유도합니다.
단말 표현이란 더 이상 유도할 수 없는 표현으로 수식에서 1, 2, …, +, -, *, / 등이 있습니다.
비단말 표현이란 유도가 가능한 표현으로 <digit> 처럼 < >를 이용하여 표현합니다.
유도 과정에서 := 는 정의를 의미하며 <digit>:=0|1|2|3|4|5|6|7|8|9 처럼 표현합니다.
만약 순서를 유지해야 하는 표현은 <operator><operand>처럼 순서대로 나열합니다.
생략할 수 있는 선택 표현은 [<sign>]처럼 나타낼 수 있습니다.
그리고 <digit>+처럼 표현하면 <digit>을 최소 한 개 있어야 하고 반복해서 올 수 있음을 의미합니다.
<mid expr>* 처럼 표현하면 <mid expr>이 없거나 반복해서 올 수 있음을 의미합니다.
여기에서는 피연산자로 부호없는 정수가 오고 연산자가 사칙 연산만 가능한 수식을 입력 문장으로 받는 수식 파서 트리를 만들어 봅시다. 이러한 수식을 BNF 표기법으로 표현하면 다음처럼 표현할 수 있습니다.
수식 표현은 맨 먼저 피연산자가 오고 중간 표현이 없거나 반복해서 올 수 있습니다.
<expr>:= <operand><mid expr>*
중간 표현이라 연산자와 피연산자가 순서대로 오는 것을 말합니다.
<mid expr>:=<operator><operand>
연산자는 + 혹은 – 혹은 * 혹은 / 입니다.
<operator>:=+|-|*|/
피연산자는 숫자가 최소 한 개 이상 반복해서 오는 것을 말합니다.
<operand>:=<digit>+
숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 입니다.
<digit>:=0|1|2|3|4|5|6|7|8|9
따라서 다음과 같은 표현은 여기서 만드는 수식 파서 트리에 맞는 표현입니다.
23+4*7-45-6
3*6/2-5*7
29
34-6*9/2
다음과 같은 표현은 여기서 만드는 수식 파서 트리에 맞지 않는 표현입니다.
23+4*745#6
3*6/-25*7
*45