[프로그래밍언어론] 3. Syntax 와 BNF, Parse Tree

개요

syntax와 semantics는 프로그래밍 언어의 2가지 축이다.

syntax는 문법과 문법에 따라 만들어 놓은 문장을 의미한다.

semantics는 수식, 문장, 프로그램 유닛들이 지니는 의미를 말한다.

 

예를 들어 x = 3 이라는 문장이 주어졌을 때

syntax는 'x' 라는 문자 옆에 '=' 이라는 문자, '3' 이라는 문자가 올 수 있다는 그 문법을 체크하는 것이 목표고,

semantics 는 x가 변수, = 가 대입 연산자, 3은 정수라는 의미를 부여하는 것이 목표이다.

 

문법은 문장이 어떻게 쓰여야 하는지 그 규칙을 기술한 것.

시멘틱은 각 문장과 그 요소들이 갖는 의미를 기술한 것이라고 볼 수 있다.

Syntax

sentence (문장) : 문자들의 집합

language (언어) : 문장들의 집합

lexeme (어휘) : 문법적으로 가장 낮은 레벨의 단위 (더 이상 문법적으로 쪼갤 수 없는 단위)

token : 어휘를 하나하나 분리하여 컴퓨터가 이해할 수 있도록 숫자를 부여한 것

 

문장을 분석하는 lexical analyzer 는 렉심을 하나하나 찾아 컴퓨터 내부에서 사용하기에 알맞은 서로 다른 숫자를 붙여 준다. 이 과정을 거친 렉심을 토큰이라고 한다. (lexical token)

syntax analyzer는 주어진 lexical token과 문법 규칙을 토대로 작성한 문장이 문법에 맞게 알맞게 작성되었는지 확인한다.

 

거꾸로 문법을 토대로 문장을 만드는 generator 도 있다.

대표적인 예시가 Chat GPT이다.

 

---

 

BNF

사람이 작성하는 문장은 문맥에 따라 다르게 해석될 수 있다.

예를들어 time flies like an arrow 라는 문장이 있다고 해보자.

 

보통은 '시간은 쏜살같이 지나간다' 라고 해석할 것이다.

하지만 공상 과학 소설에서 '시간 파리' 라는 존재가 있다고 하면, '시간 파리는 화살을 좋아한다.' 라는 문장이 될 수도 있다.

 

하지만 프로그래밍 언어는 절대로 이런 일이 있으면 안된다.

하나의 문장(구문)은 반드시 하나의 의미로 해석되어야만 한다.

그래서 프로그래밍 언어는 context 에 관계 없이 동일하게 해석되는 문법을 가져야 한다.

이를 Context - Free Grammers 라고 하며, 놈 촘스키라는 사람이 만들었다.

이 문법을 따르면 반드시 하나의 문장이 하나의 의미만 가지게 된다.

 

이 Context-Free Grammer(CFG)를 표현하기 위해 만든 도구가 바로 BNF (Backus-Naur Form) 이다.

(Backus는 포트란을 만든 사람이고, Naur는 그 조수이다.)

 

BNF에서는 lexeme 또는 token (lexical token)을 'terminal' 이라고 부른다.

터미널이 아닌 것은 Non-Terminal 이라고 부른다. (비슷한 종류의 토큰을 모은 클래스)

 

BNF 규칙은 LHS (Left Hand Side) 와 RHS (Right Hand Side) 로 구성된다.

LHS은 non-terminal 이 있어 더 전개해야 하는 대상 (abstraction) 이 온다.

RHS은 전개할 터미널 또는 논터미널의 조합이 온다.

 

논터미널은 보통 < > (angle bracket) 으로 감싸 표현한다.

예를 들어 위와 같은 규칙이 있을 때 <ident_list> 라는 논터미널이 LHS 에 존재한다.

이 논 터미널은 → 기호를 사용하여 RHS 와 같이 확장될 수 있음을 나타낸다.

identifier 라는 터미널 또는 ( | 기호 ) identifier, <ident_list> 형태로 확장된다.

따라서 <ident_list> 는 identifier 를 , 로 나열한 형태로 확장된다.

이렇게 표현하는 것을 재귀 (recursion) 이라고 하는데, 위 예시와 같이 오른쪽 끝에서 재귀가 일어나는 것을 right recursion 또는 tail recursion 이라고 한다.

 

문법(grammer)는 이러한 규칙들의 공집합이 아닌 유한 집합이다.

또한 처음 확장이 시작되는 논 터미널을 start symbol 이라고 한다.

 

 

위와 같은 BNF 가 있다고 하면 그 의미는,

stmt 라는 논터미널이 single_stmt 라는 논터미널로 확장되거나,

begin 과 end 라는 키워드 (렉시컬 토큰, 터미널) 사이에 있는 stmt_list 라는 논 터미널로 확장될 수 있다는 의미를 나타낸다.

 

예제

 

이런 BNF 규칙이 있다.

이 규칙을 따라서 a = b + const 라는 한 줄의 프로그램을 다음과 같이 분석할 수 있다.

 

 

논 터미널을 터미널만이 나올 때까지 쭉 전개하면 a = b + const 가 나온다.

이렇게 터미널로만 구성된 나열을 sentence 라고 한다.

반면 전개 중간에 터미널과 논터미널이 섞여서 나오는 모든 심볼 문자열들을 sentential form 이라고 한다.

 

leftmost derivation 은 sentential form을 전개할 때 가장 왼쪽에 있는 non-terminal 부터 전개하는 것을 말한다.

(전개 순서는 leftmost derivation, rightmost derivation 어느 방향으로 하든 상관없다.)

 

---

Parse Tree (Parsing Tree)

이렇게 BNF로 된 문장을 보면서 프로그램이 어떻게 전개되는지 보는 것은 보기 힘들다.

이때 전개 과정을 트리형태로 나타내면 더 보기 편한데, 이 트리를 파싱 트리라고 한다.

 

 

위 트리가 앞에서 본 예제의 파싱트리이다.

이 파싱트리를 보면 거꾸로 BNF 를 추측할 수도 있다.

 

 

이 이미지는 변수명에 대한 BNF와 identifier를 전개하는 과정을 그린 파싱트리를 나타낸다.

이 규칙을 통해 변수명을 지을 때 반드시 문자 뒤에 숫자가 나와야 하는 이유를 알 수 있다.

거꾸로 TEST1 이 identifier 인지 확인하고 싶을 때는 거꾸로 타고 올라가서 identifier가 나오는지 보면 된다.

(위 BNF 에서 ::= 는 → 와 같은 의미이다.)

 

모호한 문법

BNF를 통해 문장을 전개하는 과정에서 어떻게 전개하는지에 따라 서로 다른 결과가 나올 때가 있다.

어떤 문법이 모호하다는 뜻은 sentential form 을 전개했을 때 서로 다른 파싱트리가 2개 이상 나오는 경우를 말한다.

 

구체적인 예시를 보자.

 

위 예시는 identifier를 B37로 전개하는 과정이다.

위 전개는 오른쪽부터 terminal 로 전개하고 있고 (rightmost derivation),

아래 전개는 왼쪽부터 terminal 로 전개하고 있다. (leftmost derivation)

이때 두 전개 결과로 같은 파싱트리가 만들어졌다. 이런 경우는 모호하지 않다.

즉, context free grammer 이다.

 

 

반면 이 예시는 전개 방향에 따라 파싱트리가 서로 다르게 나온다.

왼쪽은 - 부터 계산하고, 오른쪽은 / 부터 먼저 계산한다.

이 경우는 연산자의 우선순위에 모호함이 있는 경우다.

수학 정의대로 하려면 나눗셈을 먼저 계산해야 하므로, 나눗셈은 leaf에 가까워야 하고, 빼기는 root 쪽에 가까워야 한다.

따라서 오른쪽 파싱트리가 올바른 파싱트리이다.

 

이 예제를 보면, expression 은 exp - exp 또는 exp * exp 또는 (exp) 또는 number 로 확장된다.

number 는 숫자(digit)의 연속을 의미한다.

 

이 문법을 3 - 2 * 5 라는 표현식에 적용하면 위와 같이 2가지 파싱트리가 나온다.

따라서 이 문법도 모호한 분법이다.

이 경우, 수학적으로 올바른 계산은 3 - (2 * 5) 이므로, 우선순위가 높은 곱셈을 leaf 로 보내야 한다.

따라서 윗 파싱트리가 올바른 파싱트리이다.

 

따라서 이를 위해 term 이라는 중간 논터미널을 추가하여 아래와 같이 문법을 만들면 모호하지 않은 문법을 만들 수 있다.

 

이렇게 곱셈이라는 연산자의 우선순위를 위해 새로운 터미널을 추가해서 레벨을 나눠준 것을 우선순위 계단 (Precedence Cascade) 라고 한다.

연산자의 종류가 많아지면 이 우선순위 계단도 더 깊이가 깊어질 것이다.

따라서 파싱 트리가 연산자의 우선순위 단계를 만족하도록 구성하면 모호성을 가지지 않게 된다.

---

 

그런데 연산자의 우선순위가 같더라도 모호성이 발생할 수 있다.

 

첫번째 BNF는 모호한 BNF 이고, 두번째 BNF는 명확한 BNF이다.

위 수식은 const + const + const 라는 식에 대해 파싱트리를 만들 때 2가지 파싱트리가 나올 수 있다.

왼쪽부터 더할지 오른쪽부터 더할지 모호하기 때문이다.

 

하지만 아래 BNF는 그렇지 않다. 반드시 왼쪽부터 더하도록 명시하고 있기 때문에 명확하다.

이렇게 왼쪽부터 전개하도록 명시한 것을 left associativity 라고 한다.

left associativity를 달성하려면 left recursive 하게 BNF를 만들면 된다.

 

연산자가 반드시 left associativity를 가져야 하는 것은 아니다.

C의 = 연산자는 right associativity 하다.

a = b = c ; 라고하면 c 를 b에 대입하고, b를 a에 대입하기 때문이다.

 

 

이 수식도 뺄셈과 곱셈에 대해 우선순위는 나눠져 있지만, 뺄셈에 대해서는 연산 순서가 명확하지 않아 모호하다.

그래서 사진과 같이 뺄셈이 연속해서 나올 경우 2가지 파싱트리가 나온다.

 

뺄셈은 왼쪽부터 연산해야하는 left associativity 가 필요한 연산이다.

따라서 왼쪽 recursion 만 남기고 오른쪽 recursion 은 없애야 한다.

 

 

위는 이를 해결한 예시이다.

 

마지막으로 위는 모호하지 않은 BNF 들의 예시이다.

 

---

Extended BNF

기존 BNF 로 표현할 때 불편한 점을 간편하게 작성할 수 있도록 문법을 확장한 BNF 이다.

어떤 부분이 있어도 되고 없어도 되는 옵셔널한 파트라면  [ ] 대괄호로 감싸서 표현한다.

어떤 두 터미널/논터미널 중에 선택하는 상황은 ( ) 괄호와 | vertical bar 기호를 사용한다.

0번 이상의 반복을 나타낼 때는 { } 중괄호를 사용한다.

 

 

 

이를 사용한 예시를 보자.

 

 

위는 기존 BNF로 표현한 문법이다.

이렇게 | 를 이용하여 연속적으로 나타낸 표현을 EBNF를 사용하면 1줄로 간단히 줄여 쓸 수 있다.

 

 

최근의 EBNF 는 이렇게 약속해서 사용하기도 한다.

다양한 바리에이션이 있다.

 

마지막으로 이 사진은 Pascal 의 ENBF 일부를 나타낸 것이다.