PL 구문법(2)

정규식, 문법 형태, 유도(좌측/우측), 모호성과 그 해결 방법, 그리고 BNF와 EBNF 표기법에 대해 설명합니다. 특히 모호성은 우선순위 적용이나 언어 구문 변경을 통해 해결할 수 있습니다.

구문법 - 문법검사

좌측, 우측 유도와 모호성 구분하고 좌, 우 결합과 햇갈리지말고 구분할 것

프로그래밍 언어의 구문 구조를 어떻게 표현할 수 있을까? 재귀를 이용

이러한 재귀 구조를 자연스럽게 표현하기 위한 문법은? 문맥-자유 문법(CFG)

정규식

• x : 문자 x를 나타냄

• M | N : M 또는 N을 표현

• MN : M 다음에 N이 나타나는 접합을 표현
• M^* : M이 0번 이상 반복

• M⁺ : MM^* 를 나타내며 M이 1번 이상 반복됨

• M? : M이 0번 또는 1번 나타남을 표현

• [..] : 문자 집합을 나타냄
  • 예시
  • [aeiou] = a|e|i|o|u
  • [A-Z] = A|\~\~|Z
  • [0-9] = 0|1|~~|9

문법 형태

N -> D | ND : 한자리(D), 두자리이상(ND) 의미 => 구문법

• 유한한 형태의 방법으로 무한한것을 보여줌.
  • 숫자가 2자리 이상일시? N -> ND -> NDD -> NDDD -> ... 이런ㄴ식으로 무한한것을 처리할 수 있음.
• 참고 : 구문법을 활용해서 V(D), V(ND)를 십진수 값을 구하는 공식으로 정의해두면 => 의미론
  • 십진수 - 구문법(왼쪽)과 의미론(오른쪽) 예시
  • 
• 문맥-자유 문법 CFG(=Context-free grammar)
  • 터미널 심볼의 집합 T
  • 논터미널 심볼의 집합 N
  • 시작 심볼 S (논터미널 심볼 중에 하나)
  • 다음과 같은 형태의 생성(문법) 규칙들의 집합
    • X → Y1 Y2… Yn 여기서 X ∊ N 그리고 Yi ∊ T ∪N
    • X → ε (오른쪽이 빈 스트링인 경우)
  • 보통 논터미널(nonterminal) 심볼은 대문자로, 터미널(terminal) 심볼은 소문자로 표기한다.

유도

논터미널이 없을때까지 시작 심볼부터 생성규칙에 맞게 계속 반복

• 예시로 S → aS | b 일때?
  • S => aS => aaS => aaaS => aaab
• 생성 규칙을 여러번 적용하는 유도는 화살표뒤에 *이 붙어있다.

• 생성 규칙 한번 적용은 그냥 화살표 하나(직접유도)

• 좌측 유도 : 가장 왼쪽 논터미널 선택
• 우측 유도 : 가장 오른쪽 논터미널 선택
• 유도 트리 = 파스 트리 = 구문 트리 : 유도 과정, 구문 구조를 보여주는 트리
  • 좌측, 우측 유도 둘 다 같은 파스트리
  • 차이점은 가지가 추가되는 순서일 뿐
  • 처음 시작심볼에서는 당연히 좌, 우측 유도 불가
  • 즉, 조건에 맞는걸로 바로 유도해야하는 것
  • 아래 모호성의 첫번째 예시 E => E+E 와 E => E*E 처럼 여기는 좌, 우 유도한게 아님.
  • 그저 조건에 맞는걸로 유도한것. 그리고 그 뒤에부터가
  • 해야하는 좌측, 우측 유도를 결정해서 유도를 해야하는 것임.

모호성

2개이상의 좌측(우측) 유도, 파스트리를 가짐. 즉, 3+(2*3), (3+2)*3 같은 단점 발생

• 예시로 아래 CFG 이고, 3+4*5 를 유도 하는 경우
  E -> E*E
  | E+E
  | (E)
  | N
  N → N D | D D → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
  • E => E+E => N+E => D+E => 3+E =>^* 3+4*5
    E => E*E => E+E*E =>^* 3+4*5
  • 2개의 좌측 유도를 가짐 (좌측,우측)
  • 우선순위로 모호성 해결
• 예시로 아래 CFG 이고, if e1 then if e2 then s1 else s2 를 유도 하는 경우
  S -> if E then S
  | if E then S else S
  • 직접 해보면 2개의 유도가 나오는것을 알 수 있음
  • 이를 언어 구문 일부 변경으로 모호성 해결 가능

모호성 해결법 1(우선순위 적용)

• 문법 재작성 : 원래 언어와 같은 언어 정의하면서 모호하지 않게 문법 재작성
  • CFG 재작성
    E -> E+T|T
    T -> T*F|F
    F -> N|(E)

모호성 해결법 2(if 끝에 end 붙이기 등등)

• 언어 구문 일부 변경 : 원래 언어와 약간 다른 언어를 정의
  • CFG 재작성, if e1 then if e2 then s1 else s2 end 즉, end를 추가해서 유도한 경우
    S -> if E then S end
    | if E then S else S

직접 해보면 모호성이 해결되었다는 것을 알 수 있음

BNF, EBNF

BNF(Backus-Naur Form)

• BNF 사용 기호

  • ::= : 정의
  • | : 또는(택일)
  • <> : 비단말(종료X)
    • 예 : <expr> -> <term>
      | <expr> + <term>

• <expr> →  <expr> + <term> | <term> 
  <term> →  <term> * <factor> | <factor> 
  <factor> →  number | (<expr>)
  

EBNF(Extended BNF)

• EBNF 사용 기호(BNF에 추가)

  • [] : 0 or 1번
  • {} : 0번 이상
  • () : 한정된 범위의 택일(| 또는 과 함께 쓰임)
  • '' : ‘(‘ 처럼 메타 기호를 단말 기호로 사용
    • 예 : <expr> -> <term> { + <term> }

• <expr> →  <term> {+ <term>} 
  <term> →  <factor> {* <factor>} 
  <factor> →  number | (<expr>)