[프로그래밍 언어론] 5강 - 구문 분석

📌 개요

🎯 학습 목표

┗  구문 분석 = 문자 -> 어휘 분석 -> 어휘 -> 구문 분석(파스 트리) -> 구문

 

🔑 학습 키워드

┗  어휘 분석( 문자 / 토큰 -> 식별자, 예약어 등... / 렉심 -> for, if, age(id) 등... )

┗  파스 트리 ( 유도 -> 트리 형태로 표현한 것 )

┗  모호성: 파스 트리의 모호성을 의미함.

┗  모호성 제거: 연산자 우선순위, 좌결합 연산자, 중첩된 if문의 else

 

💡 1. 어휘 분석

[ 프로그램 분석 ]

┗  문자 -> (어휘 분석) -> 어휘 -> (구문 분석) -> 구문

 

[ 어휘 분석 ]
┗  목적: 프로그램에 사용되는 단어를 구별해 냄

┗  토큰: 어휘 분석을 통해 얻는 결과

'토큰 예': 연산자(+, -, = 등), 구분자([,;] 등), 식별자, 예약어, 리터럴 등
** 즉, '어휘 분석'은 '문자'들을 의미있는 '단어(토큰)'으로 만들어 내는 과정 **

┗  토큰과 렉심:

- '렉심': 프로그램에 사용되는 단어
- '토큰': 렉심의 집합

"age"    ─┐
"count"  ─┼──→ 식별자(IDENTIFIER)
"student"─┘
   ↑                ↑
  렉심              토큰
  
- '예약어'나 '연산자' 등 '토큰'과 '렉심'이 같은 경우가 많으므로 '통상 렉심을 토큰'이라고 부르기도 함.
- 즉, '예약어' if, for .. 등은 하나밖에 없으니 '렉심 = 토큰' 될 수도 있음.

- '식별자': 변수나 함수 등의 이름을 나타내는 토큰
- '예약어': 프로그래밍 언어 자체에 정의되어 포함된 토큰 ( if, for, int 등 )
-> C 언어에서 어휘 분석기는 예약어를 먼저 검사한 후 예약어를 토큰으로 변환

 

💡 2. 파스 트리

[ 유도 ]

┗  '구문 규칙'을 이용하여 주어진 프로그램을 만들어 내는 과정

┗  유도가 가능하면 문법적 오류가 없는 유효한 프로그램임.

 

[ 파스 트리 ]

┗  유도를 트리 형태로 나타낸 것

┗  유도 트리, 구문 트리 라고도 부름.

┗  파스 트리 구조:

- '루트 노드': 시작 비단말 기호
- '단말 노드': 단말 기호
- '단말 노드'를 '왼쪽'부터 '오른쪽'으로 차례로 나열하면 주어진 프로그램이 됨.

- 주어진 표현에 대한 파스 트리가 존재하면 구문에 부합하는 표현임.
- 주어진 표현에 대한 파스 트리가 존해하지 않으면 오류 있는 표현임.

 

💡 3. 모호성

[ 파스 트리와 모호성 ]

┗  주어진 표현에 대한 파스 트리가 존재하면 구문에 부합하는 표현임.

┗  하지만, '주어진 표현'에 대한 파스 트리가 여러 개 존재하는 경우 문제가 발생함.

- '구문론 관점': 파스 트리가 존재하므로 구문에는 부합 -> ( 부합하면 안되는데 부합함 )
- '의미론 관점': 주어진 표현이 서로 다른 의미로 해석될 수 있음

 

[ 모호한 문법 ]

┗  동일한 표현에 대해 서로 다른 파스 트리가 만들어지는 문법

┗  문제점:

- 하나의 프로그램이 서로 다른 결과를 도출할 수 있음
- 프로그래머의 의도와 다르게 해석되어 잘못된 결과를 도출하는 위험 내포

 

[ 모호성 제거 ]

┗  문법의 명확화:

- 의도하지 않은 의미로 해석되지 않도록 모호한 문법을 명확하게 변경
- 새로운 비단말 기호와 새로운 구문 규칙을 추가

┗  대표적인 예: 연산자 우선순위, 좌결합, 연산자, 중첩된 if문의 else

 

[ 연산자 우선순위 ]

┗  (낮음)덧셈과 뺄셈 < 곱셈과 나눗셈 < 괄호(높음)

┗  모호한 문법:

<exp> ::= <exp>+<exp> | <exp>-<exp> | <exp>*<exp>
        | <exp>/<exp> | (<exp>) | <digit>
        ;

<digit> ::= 0 | 1 | 2 | ... | 8 | 9
          ;

'[ 문제점 ]'
- 연산자 우선이 정해져 있지 않음 -> 같은 수식에 여러 결과가 도출됨.
- 예시: 2*3+1 -> 7, 8 두 개의 결과 도출'

┗  모호성 일부 제거된 문법:

<exp> ::= <exp>+<exp> | <exp>-<exp> | <term>
        ;

<term> ::= <term>*<term> | <term>/<term> | <factor>
         ;

<factor> ::= (<exp>) | <digit>
           ;

<digit> ::= 0 | 1 | 2 | ... | 8 | 9
          ;

- <exp> 규칙을 덧셈과 뺄셈, 곱셈과 나눗셈, 괄호를 표현하는 3개의 묶음으로 나눔.
- 우선순위가 낮은 덧셈과 뺄셈이 <exp> 규칙에 직접 표현됨
- 곱셈과 나눗셈이 <term> 규칙에 표현됨
- 괄호가 <factor> 규칙에 표현됨

┗  우선순위 계층화: 위의 모호성 제거된 문법을 나타냄.

- 연산자 우선순위에 따라 새로운 비단말 기호를 추가하고 관련 규칙을 우선순위에 따라 재조정하는 방법

 

[ 좌결합 연산자 ]

┗  우선순위가 동일한 연산자가 피연산자를 사이에 두고 연속된 경우, 왼쪽 연산자를 우선 고려함.

┗  모호한 문법:

<exp> ::= <exp>+<exp> | <exp>-<exp> | <term>
        ;

<term> ::= <term>*<term> | <term>/<term> | <factor>
         ;

┗  모호성이 제거된 문법:

<exp> ::= <exp>+<term> | <exp>-<term> | <term>
        ;

<term> ::= <term>*<factor> | <term>/<factor> | <factor>
         ;

- '오른쪽 피연산자'를 다음 높은 우선순위의 구문 규칙에서 정의하는 비단말 기호로 변경

┗  결합 방향 강제 방법:  위의 모호성이 제거된 문법을 나타냄.

- 좌결합이나 우결합 등 특정 방향으로 결합 방향을 강제하는 방법

 

[ 중첩된 if문의 else ]

- 중첩된 if문에서 else 문의 개수가 if문의 개수보다 적은 경우
-> 각 else 문을 어느 조건이 거짓일 때 수행해야 하는지 모호함.
- 예시: if x > 1 then if x < 5 then y = 1 else y = 2
-> 짝 읽은 else 문제: else의 짝이 어느 것인지 불분명한 문제임.

┗  모호한 문법:

<if문> ::= if <논리식> then <문장> else <문장>
         | if <논리식> then <문장>
         ;

<문장> ::= <if문> | <대입문> | ...
         ;

┗  모호성이 제거된 문법:

<if문> ::= if <논리식> then <문장2> else <문장>
         | if <논리식> then <문장>
         ;

<if문2> ::= if <논리식> then <문장2> else <문장2>
          ;

<문장> ::= <if문> | <문장2> | ...
         ;

<문장2> ::= <if문2> | <대입문> | ...
          ;

- 다른 else 문과 짝이 되지 않은 가장 가까운 if문과 짝이 되도록 정함
- 구문 규칙에서 else문 앞의 <문장>에는 if문과 else문이 짝인 경우만 가능하도록 변경