[프로그래밍언어론📐] 2장 구문법 (Syntax)

출처 : 프로그래밍 언어론 : 원리와 실제 (창병모, 인피니티북스, 2021)

 

2.1 구문 및 구문법

1) 구문법 (Syntax)

- 문장 혹은 프로그램을 작성하는 방법
- 자연어(영어, 한국어)의 문법처럼 프로그래밍 언어의 구문법이 있다.
- 프로그래밍 언어의 이론적 기초
 

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

- 숫자(D)는 0, 1 중 하나이다.
- 이진수 구성 방법

1. 숫자(D)는 이진수(N)이다.
2. 이진수(N) 다음에 숫자(D)가 오면 이진수(N)이다.

 

3) 수식의 구문법

 

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

 

6) 문맥-자유 문법 CFG

- 넌터미널 심볼은 보통 대문자로, 터미널 심볼은 소문자로 표기
 

7) 생성 규칙 

 

2.2 유도

1) 유도 (Derivation)

- 구문검사 : 입력된 문장 혹은 프로그램이 문법에 맞는지 검사하는 것
- 입력된 스트링이 문법에 맞는지 검사하려면 문법으로부터 유도(derivation)해 보아야 함.

 

2) 좌측 유도와 우측 유도

- 좌측 유도 (leftmost derivation)
: 각 직접 유도 단계에서 가장 왼쪽 넌터미널을 선택하여 이를 대상으로 생성 규칙을 적용
 
- 우측 유도 (rightmost derivation)
: 각 직접 유도 단계에서 가장 오른쪽 넌터머널을 선택하여 이를 대상으로 생성 규칙을 적용
 

3) 문법 G 언어

- 문법 G에 의해서 정의되는 언어 L(G)

• 문법 G에 의해서 유도되는 모든 스트링들의 집합

4) 유도 트리 (Derivation Tree)

- 유도 트리

• 유도 과정 혹은 구문 구조를 보여주는 트리
• 유도 트리 = 파스 트리 = 구문 트리

- 유도는 시작 심볼로부터 시작하여 연속적으로 직접 유도
- 좌측 유도와 우측 유도 모두 같은 파스 트리를 가짐
 

2.3 모호성 (Ambiguity)

1) 모호성

- 모호한 문법 (ambiguous grammer)

• 어떤 스트링에 대해 두 개 이상의 좌측 유도를 가짐
• 어떤 스트링에 대해 두 개 이상의 우측 유도를 가짐
• 어떤 스트링에 대해 두 개 이상의 파스 트리를 가짐

2) 모호성 처리 방법 1

- 문법 재작성 : 원래 언어와 같은 언어를 정의하면서 모호하지 않도록 문법 재작성
- 예 :  우선순위를 적용하여 모호하지 않도록 재작성
 
(1) 모호성 예 : The Dangling Else

3) 모호성 처리 방법 2

- 언어 구문 일부 변경 : 원래 언어와 약간 다른 언어를 정의하도록 언어의 구문을 일부 변경하여 모호하지 않는 문법 작성
 

2.4 BNF와 구문 다이어그램

1) BNF/EBNF

 

2) 구문 다이어그램

- 구문 다이어그램 

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

-  EBNF에서 중괄호로 나타낸 반복 -> 다이어그램에서는 루프를 사용

 

2.5 재귀 하강 파서

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

- 파싱 : 입력 스트링을 유도하여 문법에 맞는지 검사
- 파서 : 입력 스트링을 유도하여 문법에 맞는지 검사하는 프로그램
- 재귀 하강 파서의 기본 원리 : 입력 스트링을 좌측 유도(leftmost derivation)하도록 문법으로부터 직접 파서 프로그램을 만듦
 

2) 재귀 하강 파싱 구현

- 각 넌터미널 : 하나의 프로시저(함수, 메소드)를 구현한다.
- 프로그시저 내에서 생성규칙 우변을 적용하여 좌측 유도 하도록 작성

• 프로시저 호출 : 생성 규칙을 적용하여 좌측 유도
• match(문자); : 다음 입력 심볼(토큰)이 문자와 일치하는지 검사

 

3) 예제

- 수식을 재귀-하강 파싱

int getToken() { // 다음 토큰 (수 or 문자)을 읽어서 리턴
    while (true) {
    	try {
            ch = input.read();
            if (ch == ' ' || ch == '\t' || ch == '\r');
            else if (Character.isDigit(ch)) {
            	value = number();
                input.unread(ch);
                return NUMBER;
            }
            else return ch;
        } catch (IOException e) {
        	System.err.println(e);
        }
}

void match(int c) { // 현재 토큰 확인 후 다음 토큰 읽기
    if (token == c) token = getToken();
    else error();
}

void expr(void) { // <expr> -> <term> { + <term>}
    term();
    while (token == '+') {
    	match('+');
        term();
    } 
}

void command(void) { // <command> -> <expr> '\n'
    int result = expr();
    if (token == '\n') 
    	printf("The result is %d\n", result);
    else error();
}

void parse(void) {
    token = getToken();
    command();
}

main() {
    parse();
    return 0;
}

 
 

4) 수식 값 계산기

- 수식 값 계산 : 재귀 하강 파싱하면서 동시에 수식의 값을 계산

int expr(void) { // <expr> -> <term> { + <term>}
    int result = term();
    while (token == '+') {
    	match('+');
        result += term();
    } 
    return result;
}
 
int term(void) { // <term> -> <factor> {* <factor>}
    int result = factor();
    while (token == '*') {
        match('*');
        result *= factor();
    }
    return result;
}