BNF (Backus-Naur Form)를 이용한 산술 표현에 대한 문법

BNF (Backus-Naur Form)는 프로그래밍 언어에서 문법을 정의할 때 자주 사용하는 형식이다.
BNF 문법의 기본 구조는 다음과 같다.
 
expr ::= { "+" expr expr } | { "-" expr expr } | num
num ::= "1" | "42" | "17" | ...
 
expr은 non-terminal(비종결 기호)이라고 부른다.
무슨 뜻이냐면, 이게 다른 문법 규칙에 의해 더 구체적인 표현으로 재작성될 수 있다는 뜻이다.
::=은 "뭐뭐로 쓸 수 있다"는 뜻이다. 즉, expr는 뒤에 나오는 여러 가지로 변환될 수 있다는 거다.
|는 "또 다른 선택지"를 의미한다. 즉, expr는 +로 시작하는 표현일 수도 있고, -로 시작하는 표현일 수도 있으며, 또는 그냥 숫자일 수도 있다는 뜻이다.
 
이제 각 표현의 의미를 알아보자
{ "+" expr expr }는 더하기 연산이다. 이전에 전위표기법을 사용한다고 말했었는데, 이게 전위표기법이 사용된거다.
{ "-" expr expr } 는 빼기
num은 1, 42, 17 같은 숫자들이 num으로 쓰일 수 있다는 뜻이다.
 
여기서 주의 깊게 봐야 할 점은 num의 정의인데 더 이상 다른 규칙으로 변환되지 않는 고정된 값이다.
 
이제 용어 정리를 해보자
Non-terminal (비종결 기호): expr처럼 더 다른 규칙으로 바꿀 수 있는 기호를 말한다.
Terminal (종결 기호): 더 이상 변환되지 않는 고정된 값, 즉 "1", "42" 같은 걸 의미한다.
Literal (리터럴): 고정된 값이나 상수 같은 걸 말하는데, 여기에선 " " 안에 있는 값들이 그 예시다.
 
 
이를 이용한 예시를 보자

 
 
이를 보면 이해하기 쉬울 것이다.
expression 1을 인터프리터는 34 + 45인 79로 해석하여 답을 도출할 것이고
expression 3와 같은 경우는 5+6 - (4-5) = 12라는 값을 도출할 것이다.
근데 만약 문법을 다음과 같이 바꾼다면 어떤 표현이 가능할까

그러면 우리가 num에 정의해뒀던 숫자들만 사용하여 expression을 만들 수 있다..
 
 
 
각각의 메타변수, 예를 들어 expr는 하나의 집합(set)을 정의한다.
메타변수는 다른 값이나 구조로 대체될 수 있는 변수다. 즉, 실제 값 자체가 아니라 어떤 규칙이나 형식을 정의하는 변수다.
expr과 같은 변수가 메타변수다. expr는 구체적인 숫자나 연산을 포함하는 여러 가지 표현식(expression)으로 대체될 수 있다.
메타변수는 가능한 표현들의 집합을 정의한다는 거다.
예를 들어, expr는 { + expr expr }, { - expr expr }, 또는 num으로 정의될 수 있다.
그러니까 expr는 이 문법을 따르는 모든 가능한 표현들의 집합을 의미한다.
즉, expr는 { + 1 1 }, { - 42 17 }, 그냥 1, 42 이런 것들로 구체화될 수 있는 거다.
 
아무튼 이런 관계를 쉽게 설명하는 표현 하나를 예로 들어보겠다
"42" ∈ num ⊆ expr
42는 num에 속하고 num은 expr의 부분 집합이다.
 
 
 
 
그럼 과연 이 문법을 Scala로 어떻게 구현할 수 있을까
Expr을 Trait으로 정의해보자
 
trait Expr
Num, Add, Sub 클래스들이 이 Expr를 상속받아 각각의 산술 표현식을 구현하게 된다.
 
case class Num(num: Int) extends Expr
숫자 num를 표현하는 클래스다.
이 클래스는 Int 타입의 숫자를 포함하고, Expr를 상속받아 하나의 산술 표현식으로 사용할 수 있다.
 
case class Add(left: Expr, right: Expr) extends Expr
더하기 연산을 표현하는 클래스다.
왼쪽 표현식(left) 과 오른쪽 표현식(right) 을 받아서 두 개의 표현식을 더하는 구조로 되어 있다.
 
case class Sub(left: Expr, right: Expr) extends Expr
이건 빼기다.
 
이를 이용한 예시다.
 
val expr = Add(Num(3), Sub(Num(8), Num(2)))
expr.left
여기서 expr 는 3 + (8 - 2)라는 산술 표현식을 나타낸다.
expr.left는 expr 의 왼쪽 피연산자를 참조하는 거다. 여기서는 Num(3)이 된다. 
 
 
다음으로는 추가적인 BNF 표기법을 설명하겠다.
 
<...> (Non-terminal) : <statement>, <expression> 이런 것들은 비종결 기호다. 비종결 기호는 더 구체적인 표현으로 재작성될 수 있다. 이 비종결 기호 안에 들어가는 말은 마음대로 정할 수 있다.
 
::= (정의) : 이 기호는 뭐뭐로 정의된다는 뜻이다. 
예를 들어서 <expression> ::= <term> { ("+" | "-") <term> } 이런 문법을 만들었다고 하면
<expression>이 <term>과 더하기 또는 빼기 연산이 포함된 표현식으로 변환될 수 있다는 의미다.
 
... (종결 기호, 리터럴) : 작은따옴표나 쌍따옴표 안에 있는 건 종결 기호(terminal), 즉 고정된 문자나 값을 의미한다.
예를 들어 "var", "+", "=" 같은 게 이에 해당한다. 이건 더 이상 변하지 않는 고정된 텍스트다.
 
[] (선택적 요소) : 대괄호 [] 안에 있는 것은 선택적이라는 뜻이다. 즉, 있어도 되고 없어도 된다는 거다.
예를 들어 var <identifier> [ "=" <expression> ] 는 변수 선언에서 등호와 표현식 부분이 선택적이라는 뜻이다. 
즉, 변수 선언에서 값 할당을 안 해도 된다는 거다.
다만 이 대괄호 안에 있는 건 무조건 함께 나오거나 함께 나오지 않아야 한다.
 
{ ... } (반복) : 이건 반복을 의미한다. 0번 이상 반복될 수 있다는 뜻이다.
예를 들어 <expression> ::= <term> { ("+" | "-") <term> } 는 <term> 이 여러 번 나올 수 있다는 뜻이다. 즉, x + 3 - 2 같은 복합 연산을 표현할 수 있다.
 
+, ?, * : +는 1번 이상 반복된다는 의미고, ?는 있을 수도, 없을 수도 있다, 즉 선택적이라는 의미다. 그리고 *는 0번 이상 반복될 수 있다는 뜻이다.
그래서 *는 { } 와 같다고 생각하면 된다.
 
다음은 예시 문법을 소개하겠다.
<statement> ::= <variable_declaration> ";" | <assignment> ";"
문장은 변수 선언이거나 할당일 수 있고, 마지막에 세미콜론(;)으로 끝나야 한다는 뜻이다.
 
<variable_declaration> ::= "var" <identifier> [ "=" <expression> ]
변수 선언은 "var" 키워드로 시작하고, 변수 이름인 <identifier> 가 오며, 선택적으로 = 와 표현식이 따라올 수 있다.
 
<expression> ::= <term> { ("+" | "-") <term> }
표현식은 하나 이상의 <term> 으로 이루어지고, + 또는 - 연산자가 포함될 수 있다.
 
이를 이용한 프로그래밍 언어
 

• var x;: 변수 x를 선언.
• var y = 5;: 변수 y를 선언하고 값 5를 할당.
• y = x + 3 * 2;: 변수 y에 산술 표현식을 할당.
• var result = (10 / 2) + (3 * 4);: 괄호를 사용한 복합 산술 표현.

 
다음은 유명한 프로그래밍 언어들의 문법 정의에 관한 페이지 목록이다.
https://users-cs.au.dk/amoeller/RegAut/JavaBNF.html (자바 문법 정의)
https://cs.wmich.edu/~gupta/teaching/cs4850/sumII06/The%20syntax%20of%20C%20in%20Backus-Naur%20form.htm (C 언어 문법 정의)
https://docs.python.org/3/reference/grammar.html (파이썬 문법 정의)
 
 
자바 문법 정의 한가지 살펴볼까 한다.
<package name> ::= <identifier> | <package name> . <identifier>
이 문법을 다음과 같이 사용할 수 있다.
package my.name.is.java
 
어떻게 .이 연속으로 쓰일 수 있을까?
이 문법을 잘 보면, 재귀적인 정의가 포함되어 있다.
package name을 사용한다면 이런 문법을 또 이용할 수 있는거다