배커스-나우어 형식 (BNF)

1. ALGOL (ALGOrithmic Language)

• 1958년에 개발된 알고리즘 표기언어, 문맥자유언어와 매우 비슷한 모습을 가졌다
• 당시에는 미국에서 개발된 FORTRAN에 대항하기 위해 유럽에서 개발되기 시작했음.
• 1958년 취히리에서 열린 회의에서 국제회의에서 IBM에 의해 ALGOL 58(배커스)가 처음 발표되었고,
• 1960년에 ALGOL 58을 개선하고, 네스티드 함수가 추가하여, ALGOL 60(나우어)라는 이름으로
• 다시 학계에 발표했는데데, 이 표기법을 다른 이름으로 BNF(Backers & Naur Form)라고 부르게 됨.

 

2. 배커스 - 나우어 형식 (Backers Naur Form)

• 프로그래밍 언어의 구문을 기술하는데에 매우 자연스러운 표기법으로 C, Java 등에서 사용됨
• 현대 C, Java, Python 등의 대부분 프로그래밍 언어를 정의하는데 쓰임 (다들 BNF로 정의됨)
• 배커스-나우어 형식(BNF)은 문맥자유문법(CFG)에서 생성규칙들의 집합을 의미한다.

 

1) 예시 : 배정문 (assign)

<assign> → <id> = <expr>

• 위 규칙은 우리가 익히 잘 알고있는 배정문(assignment)의 생성규칙을 의미한다.
• 생성규칙의 왼쪽(Left hand side, 이하 LHS)는 생성규칙(assignment)의 이름을 나타낸다.
• 생성규칙의 오른쪽(Right hand side, 이하 RHS)는 LHS의 이름을 갖는 생성규칙의 내용을 나타낸다.
• 이러한 생성규칙을 만들려면 <id>와 <expr>이 먼저 구현되어있어야 한다.

 

A = B + 10

• 위는 <assign>의 실제 예시이다. 위와 같이 BNF로 만들어진 규칙은 말 그대로 일종의 Form이고,
• 이를 실제로 구현하면 식별자(identifier, 변수 등) = 식(expression, 덧셈 등)을 대입하여 사용하는 것이다.

 

2) 예시 : 식 (expr)

// 1. 하나의 LHS는 다수개의 RHS를 가질 수 있다.

<expr> → <expr> + <expr>
<expr> → <expr> - <expr>


// 2. 다수개의 RHS를 갖는 LHS의 경우, 
// 아래와 같이 논리기호 ' | '를 사용해서 하나로 표현 가능하다.

<expr> → <expr> + <expr>
       | <expr> - <expr>
       

• 하나의 규칙(LHS)는 하나의 RHS만 갖는 것이 아니라, 여러개의 RHS를 가질 수 있다.
• 이러한 경우에는 위와 같이 논리기호 ' | '를 사용해서 하나의 규칙으로 나타낼 수 있다.
• 즉, ' | '는 선택적인 구조 (하나의 LHS가 다수개의 RHS 중 하나를 선택하는 구조)일 때 사용한다.

 

3) 예시 : 수(number)

<number> → <number><digit> | <digit>
     
<digit> → 0 | 1 | 2 | 3 | 4 | 5| 6| 7| 8| 9

• 이 규칙을 해석해보자면, <digit>은 0~9 중 한가지 종류일 수 있고,
• number는 한자리 digit이거나, 여러자리의 digit일 수 있다는 것이다.
• <digit>의 경우 0, 1, 2와 같은 숫자이고, <digit><digit>인 경우 01, 22가 되고
• <digit><digit><digit>인  경우 541와 같이 쓸 수 있다.
• 그런데 <digit>도 <digit><digit>도 <digit><digit><digit>도 모두 <number>이므로
• 깔끔하게 <number><digit>이라고 표기하면 간단하다.

 

// 기호의 종류


1. 단말기호 (terminal symbol) : 0, 1, 2, ..., 9, A, B, int, String, return, ; 등

2. 비단말기호 (non terminal symbol) : <assign>, <expr>, <number>, <digit> 등

3. 메타기호 (meta symbol) : <>, →, | 등

• 여기에서 <number>와 같이 <>로 묶인 기호를 비단말 기호이라고 하며,
• 0 ~ 9와 같이 <>에 묶여있지 않고 실제 프로그래밍 언어에서 사용되는 기호는 단말기호,
• 그리고 <> →, |와 같은 기호들은 메타기호라고 한다. (규칙을 만들기 위해 쓰이는 기호)

 

4) 예시 : 123을 유도(Deriveration)해보자.

// Backers - Naur Form

<number> → <number><digit> | <digit>
               
<digit> → 0 | 1 | 2 | 3 | 4 | 5| 6| 7| 8| 9


// Derivation "123"

<number> → <number><digit>
         → <number><digit><digit>         // <--- <number>를 <number><digit>으로 변환
         → <digit><digit><digit>          // <--- <number>를 <digit>으로 변환
         → 1<digit><digit>                // <--- <digit>을 1로 변환
         → 12<digit>                      // <--- <digit>을 2로 변환
         → 123                            // <--- <digit>을 3으로 변환 (종료)
         

• 프로그래밍 언어의 문장들은 BNF 규칙으로부토 생성되는데,
• 시작기호(start symbol)이라고 불리는 비단말 기호에서 시작된다. 이렇게 비단말기호 <number>에서
• 단말 기호인 123까지 생성하는 과정을 "유도(Derivation)"이라고 한다. (위 규칙에서 시작기호는 <number>)

 

5) 예시 : A = 3 + (5 - 2)를 유도(Derivative)해보자.

<assign> → <id> = <expr>

<id> → A | B | C

<expr> → <expr> + <expr>
       | <expr> - <expr>
       | (<expr>)
       | <number>
       
<number> → <number><digit> | <digit>

<digit> → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

<assign> → <id> = <expr>
         → A = <expr>                   // <--- id를 A로 변환
         → A = <expr> + <expr>          // <--- expr을 expr + expr로 변환
         → A = <number> + <expr>        // <--- expr을 number로 변환
         → A = <digit> + <expr>         // <--- number를 digit으로 변환
         → A = 3 + <expr>               // <--- digit을 3으로 변환
         → A = 3 + (<expr>)             // <--- expr을 (expr)로 변환
         → A = 3 + (<expr> - <expr>)    // <--- expr을 expr - expr로 변환
         → A = 3 + (<number> - <expr>)  // <--- expr을 number로 변환
         → A = 3 + (<digit> - <expr>)   // <--- number를 digit으로 변환
         → A = 3 + (5 - <expr>)         // <--- digit을 5로 변환
         → A = 3 + (5 - <number>)       // <--- expr을 number로 변환
         → A = 3 + (5 - <digit>)        // <--- number를 digit으로 변환
         → A = 3 + (5 - 2)              // <--- digit을 2로 변환 (종료)

• 실제 프로그래밍 언어에서 쓰일 법한 A = 3 + (5 - 2)가 <assign>라는 시작기호로부터 유도되었다.
• 그러나 위 규칙만 이용해서는 AB = 5 + (A * 3)과 같은 문장은 유도 할 수 없다
• *라는 기호도 정의되지 않았으며, <id>인 A와 B를 위 처럼 붙여서 쓸 수 있는 문법도 정의되지 않았다.
• 때문에 AB = 5 + (A * 3)과 같은 문장은 위 문법에 맞지 않는 문법이다. (컴파일러가 에러를 띄울 것이다)