[프로그래밍 언어론] 4. 프로그래밍 언어의 구문과 구현 기법

BNF

구문 형식을 정의하는 가장 보편적인 표기

<정의될 대상> ::= 정의

<> 비단말 (nonterminal) : BNF 규율로 다시 정의될 대상을 의미한다.

단말 (terminal) : 키보드에서 입력할 수 있는 기호

EBNF

BNF를 확장해서 보다 읽기 쉽고 간단하게 표현

• 메타기호
  {} : 0번 이상 반복 {s}+
  [] : 0번 또는 1번 선택
  () : 범위중 택1

BNF
<수식> ::= <수식> + <수식> | <수식> - <수식> | <수식> * <수식> | <수식> / <수식>

EBNF
<수식> ::= <수식> ( + | - | * | / ) <수식>

• ::= 같은거(메타기호)를 Terminal로 쓸때 : ‘’로 감싼다

<BNF-rule> ::=<left-part> '::=' <right-part> 
<right-part> ::=<right-part-element> {'|' <right-part-element> }

 

구문 도표

• 오른쪽으로 가는게 produce
• 왼쪽으로 가는게 reduce

 

모호성

<exp> ::= <exp>-<exp> | <exp>\*<exp> 일 때, 3 - 2 * 5 의 경우 다른 파싱 트리를 두개 만들 수 있음

• 해결방법 : 순위 폭포 (새 비단말 기호 <term> 과 새 규칙을 추가해서 문법의 우선순위를 정함)

결합성

<exp> ::= <exp>-<exp> | <term> 일 때, 7 - 3 - 2 의 경우 다른 파싱 트리를 두개 만들 수 있음

→ (7 - 3) - 2 / 7 - (3 - 2)

• 해결방법 : BNF 문법을 좌순환 규칙으로 바꿈
  좌결합 : <exp> ::= <exp>-<term>

 

기존 문법

개정된 문법

획일성 향상

전
const <ident> = <number>{;<ident> = <number>}; 
후
const {<ident> = <number>;}