[PL] Syntax Analysis

👑 Syntax Analysis

앞선 설명처럼 소스코드를 처리하는 과정의 front-end 단에서는 소스코드를 AST로 변환하고,

문법에 맞지 않는 경우 에러를 발생시킨다. AST (Abstract Syntax Tree)란 프로그램의 구조를 요약한

트리이며, 추상적이라는 것은 실제 구문의 모든 세세한 정보를 나타내지 않는다는 것을 의미한다.

Lexical Analysis 에서의 토큰들은 regular expression을 이용하여 표현되었지만, 대부분의

프로그래밍 언어는 regular language가 아니다. regular expression으로는 프로그래밍 언어의

구문들을 모두 표현할 수가 없기에, Context-free language, 즉 문맥 자유 언어로 정의한다.

• 언어 정의

  • Regular Expression : 어휘목록 정의
  • Context-free Grammar : 구문구조 정의

💡 Context-free grammar (CFG)

문맥 자유 언어는 Chomsky 계층에서 정규 언어보다 상위에 있는 언어로 정규 표현식이 표현할 수 있는

모든 언어를 표현할 수 있다. 즉, 문맥 자유 문법으로 정규 언어를 정의할 수 있다.

CFG는 문맥을 고려하지 않고 항상 동일한 문자열을 표현하는 문법으로 다음과 같이 구성된다.

• Terminal : 기초 기호 (literal)
• Nonterminal : Production에 의해 최종적으로 Terminal로 치환되는 기호
• Production (or rule) : Nonterminal을 치환하는 규칙

🚩 Definition CFG

G = (∑, N, P, S)

  ◻ ∑ : terminal의 유한 집합
  ◻ N : nonterminal의 유한 집합
  ◻ P : production의 집합
  ◻ S : 시작 nonterminal

e.g.

< S > → a < A > c
< A > → a < A >
      | b
      | ϵ

G = (∑, N, P, S)

  ◻ ∑ = {a, b, c}
  ◻ N = {< S >, < A >}
  ◻ P = {< S > → a < A > c, < A > → a < A >, < A > → b, < A > → ϵ}
  ◻ S = < S >

  ⇒ L(G) = {ac, aac, abc, aaac, ...}

🚩 Backus-Naur Form (BNF)

Context free grammar를 기술하기 위한 표기법으로, John Backus와 Peter Naur의

이름을 따서 부른다. BNF는 기본적으로 다음의 문법을 사용한다.

<기호> ::= <표현식>

위의 예시를 BNF로 표기하면 다음과 같다. (<>는 생략함)

S ::= aAc
A ::= aA
    | b
    | ϵ

🚩 Derivation & parsing

CFG로부터 문자열을 생성하려면 다음과 같은 과정을 거치는데 이를 derivation이라 한다.

• 시작 nonterminal로부터 production 적용 (LHS를 RHS로 치환)

• 모든 nonterminal에 대해 production 반복 적용 (terminal만 남으면 완료)

      e.g. S ::= 1S | 0
  
          - S ⇒ 0
          - S ⇒ 1S ⇒ 10
          - S ⇒ 1S ⇒ 11S ⇒ 110
          ⋮
  

그렇다면 문자열 s가 언어 L(G)에 속하는지 여부는 어떻게 확인할 수 있을까

derivation의 반대로 production을 역으로 적용하면 확인할 수 있으며, 이를 parsing이라 한다.

e.g. S ::= 1S | 0

    - 0 ⇒ S
    - 10 ⇒ 1S ⇒ S
    - 110 ⇒ 11S ⇒ 1S ⇒ S
    ⋮

문자열의 parse 과정을 트리로 나타낼 수 있는데, 이를 Parse tree or Derivation tree 라 한다.

트리의 각 노드는 terminal 또는 nonterminal 이며 부모, 자식 관계는 production에 의한 치환 관계이다.

leaf node를 왼쪽부터 오른쪽으로 나열하면 대상 문자열이 나오게 된다.

derivation은 Leftmost derivation과 Rightmost derivation의 두가지 방향을 가지고 있다.

모호한 문법 (Ambiguous grammar)은 하나의 문자열을 여러가지 다른 방식으로 파싱한다.
→ Parse tree가 여러개

💡 정리

• AST란 프로그램의 추상 구조를 나타내는 트리 형태의 자료구조이다.

• Parse tree는 문법으로부터의 유도과정을 모두 포함하는 반면, AST는 필요한 구조만을 포함한다.

• Lexer 와 Parser 는 소스코드를 입력으로 받아 AST를 생성한다.

  • Parse tree는 개념적인 것. parser의 산출물이 아님!!

• 컴파일러는 소스코드를 AST로 변환하고, 다양한 분석과 최적화를 수행한다.

  • 중간언어 (Intermediate representation, IR)로 변환하여 수행하기도 한다.

• 인터프리터는 소스코드를 AST로 변환하고, 실행한다.

  • 마찬가지로 IR로 변환하여 실행하기도 함.