태그: BNF 표기법

수식 파서 트리를 만들기 전에 입력 소스에 사용할 수식을 정규화를 하기로 해요. 정규화는 같은 종류의 표현을 묶어 간소화하는 과정입니다. 여기에서는 정규화 표현에 많이 사용하는 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