16 - Context-Free Grammar (CFG)

Syntax analysis를 위한 코드의 표현방법으로, BNF 표현법이라고 한다.

BNF는 만든 사람이 Backus-Naur Form 이라 BNF이다.

화살표를 ::=와 같이 표기하며, Formal language랑 유사하다.

<id> ::= <letter> | <id><letter>
<letter> ::= 'a'|'b'|'c'... |'z'
<digit> ::= '0'|'1'|...|'9'

이와 같이 표현된다.

 

하지만 반복되는 방식을 다 적어야 하는데, 이를 개선한것이 EBNF이다.

<id_list> ::= <id_list> ',' <id> | <id>를

<id_list> ::= <id> {','<id>} 로 표기할 수 있다. formal language의 *와 같이

한번이상부터 무한대까지 나올 수 있다는 이야기이다.

 

 

Syntax Diagram

---

이 문법을 다이어그램으로 표기하면,

터미널일 경우 동그라미, 터미널이 아닐경우 네모로 표기한다.

 

 

A ::= B | C | D일 경우

로 표기할 수 있다.

반복되는 경우는,

 

이와 같이 표기할 수 있다.

이 다이어그램은 C언어의 변수명 구조인데,

처음엔 _ 또는 문자이고, 그 뒤로는 문자, 숫자, _ 중 하나가 나오는데 무한반복 가능하다는 뜻이다.