[프로그래밍언어론] 8. BNF, EBNF

우리가 어떻게 프로그램언어(PL)에 대한 옳고 그름을 판단할 수 있을까?
또한 코드가 올바르게 작성되었는지 판단할 수 있는 기준은 뭘까?
우리는 주어진 코드에 구문 오류가 있는지 확인하면 된다.

 

---

형식 언어(Formal Language)

• 프로그래밍 언어의 일반적인 특성을 추상화
• 일련의 기호, 일부 형성 규칙(기호를 결합)으로 구성
• 언어 문법
  
  • E → E + E | E * E | N, N → 0N | 1N | λ

 

---

배커스-나우르 표기법(BNF)

• 원래는 John Backus가 개발한 Backus Normal Form
• Peter Naur가 확장하여 사용한 후 Donald Knuth의 제안으로 Backus-Naur Form(BNF)으로 이름 변경
• 문맥 자유 문법(context-free grammars)을 위한 표기법
• 언어 구문 설명은 BNF와 유사한 방법으로 제공되는 경우가 많다.

 

표기법

기호	의미	설명(예시)
<, >	변수(또는 논터미널)	<expression>, <term>, <operator>
표시가 없다.	터미널 기호	int, void, for
::=	치환	<논터미널 기호> ::= 대체될 문자열 <논터미널 기호>가 '대체된 문자열'로 치환
" ", ' '	문자열	두개의 연속한 문자열 또는 논터미널 기호는 하나의 문자열로 인식
|	선택	<bool-literal> ::= true | false <A> ::= "abc"와 <A> ::= "def"를 한번에 표현하면 <A> ::= "abc" | "def"

 

표기법 활용

• 생략가능
  
  • <A> ::= <B> | ""
  • ""는 공문자열 𝜀과 같다.
• 0번 이상의 반복
  • <A> ::= <A> <B> | ""
• 한번 이상의 반복
  • <A> ::= <A> <B> | <B>
• 최소 3번 이상 반복
  • <A> ::= <A> <B> | <B> <B> <B>
  • 우측에 최소 반복 횟수를 나타낼수 있다.
• 최소 2개에서 최대 5개
  • <A> ::= <B> <B> | <B> <B> <B> | <B> <B> <B> <B> | <B> <B> <B> <B> <B>

 

예시) 단어

• <digit1> ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
• <digit> ::= "0" | <digit1>
• <upper> ::= "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" 
• <lower> ::= "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z"
• <alpha> ::= <upper> | <lower>
• <alphanumeric> ::= <alpha> | <digit>
• <word> = <word> <alphanumeric> | ""
  • 0번 이상 반복

 

예시) 실수

• <real-num> ::= <int-part> . <frac-part>
• <int-part> ::= <digit> | <int-part> <digit>
  • 한번 이상 반복
• <frac-part> ::= <digit> | <digit> <frac-part>
  • 한번 이상 반복
• <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
• 시작 논터미널 : <real-num>
• 시작 논터미널을 터미널 문자열로 변환하는 프로세스를 파생(derivation)이라고 한다.

 

Left-most Derivation(좌측우선 유도)

• 둘 이상의 논터미널이 있는 경우 항상 가장 왼쪽의 논터미널을 교체
• 예시) 3.14
  
  • <real-num> ⇒ <int-part> . <frac-part>
  • ⇒ <digit> . <frac-part> ⇒ 3. <frac-part>
  • ⇒ 3.<digit> <frac-part> ⇒ 3.1 <frac-part>
  • ⇒ 3.1 <digit> ⇒ 3.14

 

Right-most Derivation(우측우선 유도)

• (())를 도출
• <balanced> ::= (<balanced>)<balanced> | 𝜀
• <balanced> ⇒ (<balanced>)<balanced>
• ⇒ (<balanced>)𝜀 ⇒ (<balanced>)
• ⇒ ((<balanced>)<balanced>) ⇒ ((<balanced>)𝜀)
• ⇒ ((<balanced>)) ⇒ ((𝜀)) ⇒ (())

 

---

 

EBNF(Extended BNF ; 확장된 BNF)

• BNF와 동일한 표현력을 갖지만 훨씬 더 간단하다.
• 추가 표기법을 사용
  
  • {X}, [X], *, +, (X)
• 복잡한 BNF 표현이 단축되어 이해하기 쉽다.

 

표기법

기호	의미	설명(예시)
{ }, *	0번 이상 반복	{ <X> } <digits> ::= <digit>* <digits> ::= {<digit>}
+	1번 이상 반복	<digits> ::= <digit>+ <digits> ::= <digit>{<digit>}
[ ], ?	생략, 0 또는 1번 (선택사항)	[ <X> ] <X> ? <signed> ::= ['-'] <num> <signed> ::= '-' ? <num>
( )	그룹, 원하는 부분 묶음	( <A> <B> ) <C>

 

예시) 실수

BNF

• <real-num> ::= '-' <num> | <num>
• <num> ::= <digits> | <digits> . <digits>
• <digits> ::= <digit> | <digit> <digits>
• <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

EBNF

• 1. <real-num> ::= ['-'] <digit>+ ['.'<digit>+]
• 2. <real-num> ::= '-'? <digit>+ ('.'<digit>+)?
• <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
  
  
• BNF보다 훨씬 간단.
• '?' 사용 가능

 

예시) ID

BNF

• <expr> ::= <digits>
• <digits> ::= <digit> | <digit> <digits>
  • 한번 이상 반복
• <id> ::= <letter> | <id> <letter> | <id> <digit>

EBNF

• <expr> ::= <digit>+
• 1. <id> ::= <letter> (<letter> | <digit>)*
• 2. <id> ::= <letter> {<letter> | <digit>}