BNF와 재귀 하향 파서

BNF

BNF(배커스-나우르 표기법, Backus-Naur Form)는 문맥 자유 문법(Context-Free Grammar)을 기술하기 위해 존 배커스와 페테르 나우르가 만든 표기법입니다. 그럼 문맥 자유 문법은 뭐냐, 하면 아주 복잡해서 그냥 BNF로 나타낼 수 있는 문법이면 문맥 자유 문법이라 봐도 무방합니다(?). BNF는 단말 기호(terminal symbol)과 비단말 기호(nonterminal symbol)을 이용해서 문법을 기술합니다.

  • 단말 기호: 다른 기호에서 유도되지 않는 기호입니다. "(""+"같이 “있는 그대로” 사용되는 기호라고 하면 되겠습니다.
  • 비단말 기호: 다른 기호에서 유도되는 기호입니다. <formula>처럼 홑화살괄호로 이름을 둘러싸서 표현합니다.

비단말 기호가 어떻게 유도되는지는 명확하게 정의해주어야 합니다. 정의는 ::=를 써서 나타냅니다.

<zero> ::= "0"

<zero>라는 비단말 기호를 "0"으로 정의했습니다. 비단말 기호는 기호를 여러 개 나열하여 정의할 수도 있습니다.

<one> ::= "1"
<ten> ::= <one> <zero>

먼저 <one>을 정의한다음, <ten><one><zero>를 순서대로 늘어놓은 것으로 정의했습니다. 순서가 바뀌면 안  됩니다! 또한 비단말 기호가 여러 정의 중 하나를 선택하게 할 수도 있습니다.

<digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

<digit>"0"부터 "9" 중 하나로 정의했습니다. 이 때 | 기호는 이 정의들 중 하나를 선택하라는 의미입니다.

이게 BNF의 끝입니다. 이토록 간단한 표기법이 어떻게 수많은 문법을 기술할 수 있는지는 예시를 들어 살펴보도록 하겠습니다.

짝이 맞는 괄호 문자열

짝이 맞는 괄호 문자열 <S>는 다음과 같이 정의 가능합니다.

<S> ::= "()" | "(" <S> ")" | <S> <S>

즉, <S>는 안이 빈 괄호 문자열 "()"이거나 여는 괄호와 닫는 괄호로 둘러쌓인 짝이 맞는 괄호 문자열이거나 짝이 맞는 괄호 문자열 두 개를 이어 붙인 것입니다. 이 문법에서 문자열 "(()())()"는 아래 그림처럼 해석됩니다.

십진수

<digit> ::= "0" | "1" | "2" | ... | "9"
<decimal> ::= <digit> | <digit> <decimal>

먼저 위에서 봤던 것과 동일하게 <digit>를 정의하고 (귀찮아서 중간은 건너뛰었습니다…) <decimal><digit>이거나 <digit> 뒤에 <decimal>이 붙은 것으로 정의합니다. 물론 이 문법은 "00018351"같은 것도 십진수로 허용해주지만, 그 정도는 너그럽게 봐줍시다.

표현식

표현식(expression)이란 변수, 함수, 연산자 등이 조합되어 컴퓨터로 값을 계산하여 도출해낼 수 있는 것을 말합니다. 이때 계산 과정은 평가(evaluation)이라고 하죠. 표현식의 예로는 2+3, max(5, 7)+a*c, a+1<b가 있습니다. 반면에 if문, for문 등은 의미는 있지만 이들이 값을 가지는 것이 아니므로 (if문이 어떤 값을 리턴하던가요?) 표현식은 아니고 구문(statement)라고 부릅니다.

십진수 상수와 "+", "-", "*", 괄호만 허용하는 아주 간단한 표현식 문법을 생각합시다. 이때 표현식은 덧셈 또는 뺄셈으로 연결된 항(term)의 나열로 나타낼 수 있습니다. BNF로는

<expr> ::= <term> | <term> "+" <expr> | <term> "-" <expr>

항은 인수(factor)들의 곱으로 나타낼 수 있습니다.

<term> ::= <factor> | <factor> "*" <term>

여기서부터 복잡합니다. 인수로 가능한 것들은 (3+5*7), -65, +(4-1)이 있습니다. 먼저 앞에 부호를 나타내는 "+""-"부터 떼줍니다. 이걸 primary expression이라고 하겠습니다.

<factor> ::= <primary-expr> | "+" <factor> | "-" <factor>

primary expression은 십진수 상수이거나  표현식을 괄호로 감싼 것입니다.

<primary-expr> ::= <decimal> | "(" <expr> ")"

십진수는 위에서 정의했으므로 생략합니다.

예시로 표현식 -(1+2*3)*(4-6)은 아래 그림처럼 해석됩니다.

매우 길지만 이렇게 명확하게 모든 문법 요소를 트리 구조로 나타낼 수 있다는 게 BNF의 장점입니다.

주의: 이 문법은 우리가 실생활에서 쓰는 모든 표현식을 잘 설명하지만, 어딘가 이상한 부분이 있습니다. 뭘까요?

낱말 분석

낱말 분석(Lexical Analysis)은 주어진 문장을 토큰(token)으로 쪼개는 과정입니다. 여기서 토큰은 낱말처럼 의미를 가지는 최소 단위를 말합니다. 토큰에는 식별자(identifier, 변수나 함수 등의 이름), 키워드, 리터럴(상수), 구분자(separator, C에서 세미콜론이나 중괄호같은 것), 연산자, 주석이 있습니다. 그리고 이렇게 낱말 분석을 해주는 프로그램을 렉서(lexer) 또는 토크나이저(tokenizer)라고 합니다.

짝이 맞는 괄호 문자열 "(()())()"은 아래와 같이 쪼갤 수 있습니다. "()"가 한 토큰인 것에 유의합시다.

"(", "()", "()", ")", "()"

코드는 아래와 같습니다. (잘못된 문자열이 들어온 경우는 딱히 처리하지 않았습니다.)

출력 결과:

PAR_OPEN PAR_PAIR PAR_PAIR PAR_CLOSE PAR_PAIR

표현식 -123*(76+5)

"-", 123, "*", "(", 76, "+", 5, ")"

로 쪼개집니다.

마찬가지로 잘못된 입력을 처리하지는 않습니다. 또, 가독성을 위해 공백 문자 입력을 허용했습니다. 물론 낱말 분석시에는 무시해줍니다.

출력 결과:

MINUS PLUS PAR_OPEN INTEGER(123) PLUS INTEGER(64) ASTERISK INTEGER(7) PAR_CLOSE PLUS INTEGER(9) ASTERISK PAR_OPEN INTEGER(50) MINUS INTEGER(8) PAR_CLOSE

사실 어디까지를 “의미를 가지는 최소 단위”로 볼 것이냐에 따라 토큰으로 쪼개는 방법은 달라질 수 있으니 위 방법들도 하나의 예시라고 할 수 있겠습니다.

재귀 하향 파서

파싱(parsing, 또는 구문 분석)은 토큰들의 위계 관계를 분석하는 과정입니다. 즉, 각 토큰이 문법적으로 어떤 요소에 해당하는지 알아내는 것이죠. C에서 따지자면 이 "+"가 덧셈을 의미하는지 부호를 나타내는 단항 연산자인지, 또는 "("가 식의 계산 순서를 나타내기 위한 것인지 함수 호출에 사용되는 괄호인지를 알아내는 과정입니다. 파싱을 거치고 나면 저 위에 그린 BNF 트리 그림과 똑같은 게 나옵니다. 이 트리가 구해지면 식 평가는 쉽습니다. 자식 서브트리들을 먼저 평가하고, 이 루트 노드의 토큰에 따라 적절히 자식 서브트리의 값을 조합해주면 트리가 평가됩니다. 이 파싱을 해주는 프로그램이 바로 파서(parser)입니다.

파서는 크게 하향식과 상향식으로 나뉩니다. 하향식은 전체 토큰들을 받고서 이를 잘게 쪼개고 쪼갠 것들을 다시 처리하는 분할 정복같은 방식으로 작동하고, 상향식은 각 토큰을 하나씩 합치면서 전체 토큰에 해당하는 트리를 만들어냅니다. 여기서는 (아마도) 제일 간단한 재귀 하향 파서(recursive descent parser)를 쓰겠습니다. 이 방식은 모든 비단말 기호에 대응하는 파싱 함수를 만들고, 이 함수가 BNF에 정의된 대로 비단말 기호를 유도하는 다른 기호에 대응되는 함수를 재귀적으로 호출합니다. 예를 들어 다음과 같은 문법이 있으면

<spam> ::= <egg> <bacon> | <baked-beans> <spam>

먼저 <egg>, <bacon>, <baked-beans>에 대응하는 파싱 함수를 만듭니다. 그리고 <spam>에 대응하는 파싱 함수를 만들어야 하는데, 이 함수는 제일 처음 주어진 문자열을 <egg> 함수로 파싱해봅니다. 성공하면, 이미 파싱된 부분은 빼고 나머지를 <bacon>으로 파싱합니다. 여기까지 성공하면 파싱 끝이고, <bacon>으로 파싱이 안 되거나 처음부터 <egg>로 파싱이 안 되면 주어진 문자열은 <baked-beans> <spam> 문법에 대응하는 거죠. 따라서 <baked-beans>로 파싱한 다음 나머지 부분을 <spam> 재귀 호출로 처리합니다. 둘 중 하나라도 실패하면 이 문자열은 <spam>이 아닌 겁니다.

재귀 하향식 파서를 만들 때 주의할 점 / EBNF

혹시 위에서 표현식의 BNF 표기에서 주의라고 써놓은 부분을 보셨나요? BNF는 문법적 구조만 설명해주지, 이 구조가 어떻게 평가될지는 설명하지 않습니다. 분명히 "+", "-", "*", 괄호와 정수 리터럴만 쓰는 모든 표현식은 위 BNF로 파싱할 수 있지만 우리가 생각하는 연산자 우선순위와 안 맞습니다. 가령 4-5-10라는 표현식은 우리가 아는 대로라면 (4-5)-10 형태로 평가되어야 하지만, 위 BNF는 먼저 4를 <term>으로 파싱하고, "-"를 파싱하고 마지막으로 5-10<expr> 재귀 호출로 처리하므로 평가 순서는 4-(5-10)입니다.

이걸 해결하려면 BNF를 조금 손봐야 합니다. <expr>을 이렇게 정의하면 어떨까요?

<expr> ::= <term> | <expr> "+" <term> | <expr> "-" <term>

이 문법에서는 주어진 문자열을 <expr>로 파싱할 때 먼저 <term>인지 확인해봅니다. <term>으로 파싱하고 남는 게 없으면 성공이고, 아니면 다시 <expr>을 호출합니다. 이 <expr>은 다시 <expr>을 부르고, 또 <expr>을 부르고… 결국 무한 재귀의 늪에 빠져버립니다.

재귀 하향 파서를 짤 때 연산자 우선 순위에 잘 맞고 무한 재귀에 빠지지 않게 하려면 BNF로는 불충분합니다. 이를 위해 BNF에 기호 몇 가지를 추가한 것이 EBNF(Extended BNF)입니다.

  • *: *앞에 있는 기호가 0번 이상 반복됨
  • +: +앞에 있는 기호가 1번 이상 반복됨
  • ?: ?앞에 있는 기호가 없을 수도, 있을 수도 있음
  • (): 그룹화

예를 들어

<c> ::= <a> <b>*

<c> ::= <a> | <a> <b> | <a> <b> <b> | ...

와 똑같습니다.

<c> ::= <a> (<b> <a>)+

는 괄호 안 전체가 1번 이상 반복되므로

<c> ::= <a> <b> <a> | <a> <b> <a> <b> <a> | <a> <b> <a> <b> <a> <b> <a> | ...

와 똑같습니다. (<c> ::= <a> | <a> <b> <c>라고 쓸 수도 있겠죠.)

<c> ::= <a> (<a> | <b>)?

는 괄호가 <a> 또는 <b>의 값을 가질 수 있고 이것이 있거나 없으므로

<c> ::= <a> | <a> <a> | <a> <b>

와 똑같습니다.

물론 EBNF는 표시할 수 있는 문법의 범주가 BNF와 완전히 똑같습니다만, 재귀가 아니라 반복을 쓸 수 있게 되어서 재귀 하향 파서를 만들 때 무한 재귀를 피할 수 있게 해줍니다. 위 표현식의 문법을 EBNF로 다시 쓰면

<expr> ::= <term> (("+" | "-") <term>)*
<term> ::= <factor> ("*" <factor>)*
<factor> ::= <primary-expr> | ("+" | "-") <factor>
<primary-expr> ::= <decimal> | "(" <expr> ")"

내친 김에 짝이 맞는 괄호 문자열도 무한 재귀를 피할 수 있도록 EBNF로 써봅시다.

<S> ::= ("()" | "(" <S> ")") <S>?

추상 구문 트리

본격적으로 표현식 파싱을 해봅시다! 들어가기 전에, 이 재귀 하향 파서가 뭘 만들어줄지를 결정해야 합니다. 위 그림처럼 엄격하게 BNF을 따르는 파스 트리를 만들어줘도 되지만, 파스 트리는 트리 노드로 "(", "*" 등의 문자까지 포함합니다. 실제로 표현식을 평가하고 싶다면 단순히 정수 리터럴만 잎새 노드에 넣어준 다음 이들끼리 각 연산자나 구문에 맞게 정의한 노드로 이어주기만 해도 평가에 아무 문제 없습니다. 말이 좀 어려운데, -123*(76+5)를 평가하고 싶으면 아래와 같은 트리를 만들면 됩니다.

즉, 전체 표현식은 -123(76+5)BinMul 구조체의 자식으로 들어간 것이고, -123은 정수 리터럴 123을 자식으로 가지는 UnaryMinus 구조체입니다.  마찬가지로 (76+5)는 정수 리터럴 76과 5을 자식으로 가지는 BinAdd 구조체로 표현됩니다. 이 트리는 추상 구문 트리(Abstract Syntax Tree)라고 하며, 실제 문장에서 나타나는 모든 토큰을 표현하지 않는다는 점에서 파스 트리와 구별됩니다.

따라서 우리가 만들 재귀 하향 파서는 추상 구문 트리를 만들어주면 됩니다. 먼저 각 노드 구조체를 만듭시다. 노드 구조체는 식 평가를 위해 eval 가상 함수를 가져야 합니다.

남은 건 각 비단말 기호별로 함수를 짜는 것 뿐입니다.

출력 결과는 -193입니다.

응용

사실 파싱이란 게 BNF만 잘 정의해주면 함수 짜는 건 노가다라서… 딱히 응용이라 할 것도 없습니다.

파싱 연습용 문제집이 하나 있습니다. https://www.acmicpc.net/workbook/view/2023

BOJ 2504:: 괄호의 값

https://www.acmicpc.net/problem/2504

원래 스택 쓰면 되는 문제인데 재귀 하향 파서로 풀어봅시다. 문제에서 주어지는 문자열의 문법을 EBNF로 나타내면 다음과 같습니다.

<S> ::= ("()" | "[]" | "(" <S> ")" | "[" <S> "]") <S>?

추상 구문 트리에 노드가 몇 종류 필요한지 세어 봅시다. "()""[]"를 나타내는 노드가 하나씩 필요할 거고(노드 하나에 합쳐도 됩니다), <S> 두 개를 붙여놓는 노드가 필요하고, <S>를 괄호로 감싸는 두 경우에 노드가 하나씩 필요하므로(이것도 합칠 수 있습니다) 5종류가 필요합니다.