Skip to content

Latest commit

 

History

History
146 lines (141 loc) · 7.7 KB

chap02.md

File metadata and controls

146 lines (141 loc) · 7.7 KB

CHAP 02

구문 및 구문법

  • 구문법(Syntax)
    • 문장 혹은 프로그램을 작성하는 방법
    • 자연어(영어,한국어)의 문법처럼 프로그래밍 언어의 구문법이 있음
    • 프로그래밍 언어의 이론적 기초
  • 어떤 언어의 가능한 문장 or 프로그램의 개수는 무한하지 않는가? 무한한 것들을 어떻게 유한하게 정의할 수 있는가?
    • 점화식, 재귀식(recurrence relation)을 통해 해결 가능

재귀적 정의: 이진수의 구문법

  • 숫자(D)는 0,1 중 하나
  • 이진수 구성 방법
    1. 숫자(D)는 이진수(N)이다
    2. 이진수(N) 다음에 숫자(D)가 오면 이진수(N)이다
  • 논리 규칙 형태
    • P->Q 의 형태 P이면 Q이다. (분자: P / 분모: Q)
    • D는 숫자이다/ D는 이진수 N이다
    • N이 이진수이고 D가 숫자이다/ ND는 이진수이다
  • 문법 형태
    • N->D :이진수 N을 작성하는 첫 번째 방법은 숫자 D 하나로 작성하는 것
    • N->ND: 이진수(N) 다음에 숫자(D)를 하나 붙여서 작성한다
    • 더 간단한 형태
      • N -> D | ND
      • 이진수(N)을 구성하는 방법은 D 또는 ND 라는 의미
  • 이진수의 시맨틱스 : 이진수의 의미를 그 이진수가 의미하는 십진수 값으로 생각하는 것
    • V('0')=0
    • V('1')=1
    • V(D)
    • V(ND)=V(N)*2+V(D)
    • V('101')=V('10')*2+V('1') = 4 + 1 = 5
      • V('10')=V('1')*2+V('0')= 2

수식의 구문법

    E -> E*E | E+E | (E) | N 
    N-> ND | D
    D-> 0|1|2|3|4|5|6|7|8|9
  • 수식의 의미(시맨틱스) 
    V(E*E)=V(E)*V(E)
V(E+E)=V(E)+V(E)
V((E))=V(E)
V(N)

프로그래밍 언어의 구문구조

  • 재귀를 이용한 구문법으로 구문구조 정의 가능
  • 프로그래밍 언어의 기본적인 문장: 대입문, 조건문, 반복문 등
  • 문장 S의 구문법
    • id=E
    • if E then S else S
    • while E do S
      • (E는 수식, S는 임의의 문장)
  • 문맥-자유 문법(CFG: Context-free grammar)
    • 재귀적 정의를 이용하여 재귀구조를 자연스럽게 표현할 수 있음
    • 프로그래밍 언어의 문장 S의 구문법 정의 
      S -> id = E 
    | if E then S else S
    | while ( E ) S 
    | ...
    • 구성
      • 넌터미널 심볼의 집합 N
        • 끝나지 않은 심볼
        • 넌터미널 심볼이 나타내는 스트링들의 작성법이 문법 규칙에 의해 정의되어 있다
        • 넌터미널 심볼은 문법 규칙의 왼족에 위치할 수 있음
        • 일종의 구문적 변수 역할
      • 터미널 심볼의 집합 T
        • 터미널 심볼은 그 자체가 기초 심볼로 더 이상의 작성법이 정의되어 있지 않음
        • 문법 규칙의 왼쪽에 위치할 수 없고 오른쪽에만 나타날 수 있음
      • 시작 심볼 S (넌터미널 중에 하나)
      • X -> Y1, Y2 . . . Yn 와 같은 생성 규칙들의 집합
      • X는 N에 속하고 Yi는 T와 U의 합집합에 속함
      • 자세한 내용은 책, PPT 참고

유도

  • 구문검사: 입력된 문장 or 프로그램이 문법에 맞는지 검사하는 것
  • 어떤 문장 or 프로그램이 구문법에 맞는지 어떻게 검사?
    • 입력된 스트링이 문법에 맞는지 검사하려면 문법으로부터 유도(derivation) 해 보아야 함
  • 어떤 스트링이 문법으로부터 유도 가능하면 문법에 맞는 스트링, 그렇지 않으면 문법에 맞지 않는 스트링

유도

  • 핵심 아이디어
    1. 시작 심볼 S부터 시작
    2. 넌터미널 심볼 X를 생성규칙을 적용하여 Y1,Y2, ..Yn으로 대치
      • X -> Y1,Y2,..Yn 적용
        • X를 Y1,Y2,..Yn으로 대치 OR X가 Y1,Y2,..Yn을 생성
    3. 이 과정을 넌터미널 심볼이 없을 떄까지 반복
      • 터미널 심볼은 대치할 규칙이 없으므로 일단 생성되면 끝 (터미널 심볼은 그 언어의 토큰)
  • 직접 유도(Direct derivation)
    • 생성규칙을 한번 적용
  • 유도(derivation)
    • 생성규칙을 여러번 적용
  • 예시는 ppt와 책 참고..
  • 좌측 유도, 우측 유도
    • 좌측 유도(leftmost derivation): 각 직접 유도 단계에서 가장 왼쪽 넌터미널을 선택하여 이를 대상으로 생성규칙을 적용
    • 우측 유도(rightmost derivation): 각 직접 유도 단계에서 가장 오른쪽 넌터미널을 선택하여 이를 대상으로 생성 규칙을 적용
  • 문법 G 언어
    • 문법 G에 의해서 정의되는 언어 L(G)
      • 문법 G에 의해서 유도되는 모든 스트링들의 집합
      • 예시 ppt 참고
  • 유도 트리(Derivation tree)
    • 유도 과정 혹은 구문 구조를 보여주는 트리
    • 유도 트리 = 파스 트리 = 구문 트리
    • 유도는 시작심볼로부터 시작하여 연속적으로 직접 유도를 함
    • 유도 과정을 트리 형태로 그릴 수 있다
      1. S가 트리의 루트
      2. 규칙 X->Y1,Y2,..Yn 을 적용하여 직접 유도를 할때마다 X노드는 Y1,..Yn을 자식 노드로 갖도록 트리를 구성함
    • 예제 ppt, 책 참고
    • 주의
      1. 좌측유도, 우측유도 모두 같은 파스트리를 가짐
      2. 차이점은 파스트리에 가지가 추가되는 순서

모호성(Ambiguity)

  • 예를 들어, 3+4*5는 두 개의 좌측 유도를 가지게 됨 (ppt 참고)
    • 고로 두 개의 파스트리를 가지게 됨
  • 모호한 문법(ambiguous grammar)
    • 어떤 스트링에 대해 2개 이상의 좌측 유도를 갖는다
    • 어떤 스트링에 대해 2개 이상의 우측 유도를 갖는다
    • 어떤 스트링에 대해 2개 이상의 파스 트리를 갖는다
    • 좌측 유도, 유도 트리, 우측 유도 사이에는 일대일 대응 관계가 있다
  • 모호성은 나쁘다
    • 이유: 어떤 스트링에 대한 구문 구조를 두개 이상으로 해석할 수 있기 때문 -> 컴파일러가 해당 문법에 대해서 제대로 작동하지 못함 (기계는 하나의 방법만을 가지고 반복실행하는 것이 원칙이기 떄문)
  • 모호성 처리 방법
    1. 문법 재작성 : 원래 언어와 같은 언어를 정의하면서 모호하지 않도록 문법 재작성 (예시 ppt 참고)
    2. 언어 구문 일부 변경 : 원래 언어와 약간 다른 언어를 정의하도록 언어의 구문을 일부 변경하여 모호하지 않은 문법 작성 (예시 ppt 참고)

BNF와 구문 다이어그램

BNF/EBNF

  • BNF(Backus-Naur Form) : 재귀적으로 정의되어 있음
  • EBNF(Extended BNF): 반복적 정의 형태로 표현됨
  • []: 0번 혹은 1번 (optional을 의미)
  • {}: 0번 이상 반복

구문 다이어그램

  • 각 생성규칙을 다이어그램으로 표현
  • 넌터미널은 사각형, 터미널은 원, 순서는 화살표

재귀 하강 파싱 (recursive-descent parsing)

  • 파싱: 입력 스트링을 유도하여 문법에 맞는지 검사
  • 파서: 입력 스틀이을 유도하여 문법에 맞는지 검사하는 프로그램
  • 기본 원리: 입력 스트링을 좌측 유도하도록 문법으로부터 직접 파서 프로그램을 만듦
  • 구현
    • 각 넌터미널: **하나의 프로시저(함수, 메소드)**를 만듦
    • 프로시저 내에서
      • 생성규칙 우변을 적용하여 좌우선 유도하도록 작성
      • 프로시저 호출: 생성 규칙을 적용하여 유도 *** match(문자);** : 다음 입력(토큰)이 문자와 일치하는지 검사