Computer Engineering/프로그래밍 언어론

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

Js0l 2025. 4. 12. 09:01

1. 구문과 의미란?

프로그래밍 언어는 단순한 문자열이 아니라 의미 있는 구조와 해석이 가능한 표현이다.

- 구문(Syntax): 프로그램이 어떤 모양이어야 하는가? - 형식적 구조

- 의미(Semantics): 프로그램이 무엇을 의미하는가? - 실행 시 동작

 

2. 언어의 구성요소

  • 알파벳(Σ): 유한한 심볼의 집합 ex) {a, b}
  • 문자열(String): 알파벳의 유한한 나열 ex) abab
  • 공집합∅: 아무 문자열도 포함하지 않는 언어
  • 빈 문자열 λ: 길이 0의 문자열
  • 언어 Language: Σ*의 부분집합, 즉 문자열들의 집합

→ 모든 프로그래밍 언어도 결국 문자열의 집합이다. 이를 생성하기 위한 도구가 문법(Grammar)이다.

 

문법의 구성요소

G = (V, T, S, P)

  • V: 변수(비단말 기호 Nonterminal)
  • T: 단말 기호 Terminal
  • S: 시작 기호 Start symbol
  • P: 생성 규칙 

언어 생성 문법

G = ( Σ, N, S, R)

  • Σ: 단말기호(Terminal)의 집합
  • N: 비단말기호(Nonterminal)의 집합 ex) if, for, while
  • S: 시작기호
  • R: 생성규칙

3. 문맥자유문법(베커스 노어 형식)이 다루는 것

- 유도: 시작 기호로부터 규칙을 반복 적용하여 문자열을 생성하는 과정

- 파서트리: 유도 과정을 트리 형태로 시각화한 것

- 최좌단 유도: 가장 왼쪽 비단말부터 규칙 적용

- ★ 모호성: 문법이 동일한 문자열에 대해 2개 이상의 파서트리를 생성할 수 있는 경우 → 모호성은 컴파일러 구현에서 반드시 제거

               ex) A = B + C * A는 두 가지 트리 가능 (덧셈 먼저 vs 곱셈 먼저)

<assign> -> <id> = <expr>
<id> -> A | B | C
<expr> -> <expr> + <expr> | <expr> * <expr> | ( <expr> ) | <id>

모호성의 예제

 

4. 촘스키 문법 분류 Chomsky Hierarchy

촘스키는 생성 규칙의 제약 정도에 따라 문법을 다음과 같이 4단계로 나눈다. 

Type 0  무제약 문법 아무 규칙 가능 (Turing 기계 수준)
Type 1 문맥 의존 문법 CSG 좌/우 문맥 조건 필요
Type 2 문맥 자유 문법 CFG 단 하나의 비단말 -> 문자열
Type 3 정규 문법 RG 우변이 단말 or 단말+비단말 (ex. A -> aB)

→ 프로그래밍 언어는 대부분 Type2 문맥자유문법 CFG 기반이다.

 

5. BNF와 EBNF

베커스 노어 형식 - BNF(Backus-Naaur Form)

: Algol 언어 구문을 정의하기 위해 도입된 메타언어이다.

<assign> → <var> = <expression>
<if_stmt> → if (<logic_expr>) <stmt>
          | if (<logic_expr>) <stmt> else <stmt>

 

재귀표현

: BNF는 반복을 직접 표현하지 못하므로 재귀 규칙을 통해 리스트 등을 표현함

<ident_list> → identifier
            | identifier , <ident_list>

 

EBNF 확장

  • { }: 반복 (0회 이상)
  • [ ]: 옵션 (0회 또는 1회)
  • | : 대체
<expr> → <term> {(+ | -) <term>}
<term> → <factor> {(* | /) <factor>}
<factor> → <exp> [** <factor>]
<exp> → (<expr>) | id

→ EBNF는 BNF보다 간결하며 실제 프로그래밍 언어 정의에 자주 사용된다.

 

 

6. 예제

첫번째, BNF 기반으로 파서트리 작성

<assign> -> <id> = <expr>
<id> -> A| B | C
<expr> -> <id> + <expr> | <id> * <expr> | ( <expr>) | <id>

 

두번째, 최좌단 유도를 한다.

A = B * ( A + C )

<assign> => <id> = <expr> 
         => A = <expr>
         => A = <id> * <expr>
         => A = B * <expr>
         => A = B * ( <expr>)
         => A = B * ( <id> + <expr>)
         => A = B * ( A + <expr>)
         => A = B * ( A + <id>)
         => A = B * ( A + C )

 

세번째, 파서트리로 표현한다. : 모든 내부노드는 비단말 기호를 레이블로 가지며 모든 잎 노드는 터미널 기호를 레이블로 갖는다.

7. 연산자 우선순위와 결합 규칙

우선순위

ex) +, -  <  *, /  <  **

 

★ 결합규칙

- 좌결합: 연산을 왼쪽부터 차례대로 수행 (대부분의 이항연산자 +,-,*,/)

ex) ((A - B) - C) : 좌순환 <expr> → <expr> - <term>      

 

- 우결합: 연산을 오른쪽부터 차례대로 수행(지수 연산 또는 일부 함수형 언어 연산자)

ex) (A ** (B ** C)): 우순환 <factor> → <exp> ** <factor>

 

좌결합은 파싱 구현시 좌순환 문법을 유도하지만, LL파서에서는 좌순한 제거가 필요하다.

→ 우결합은 우순환 구조로 표현되며, 일반적으로 LL파서에서 더 쉽게 처리 가능하다.