Lec05. Syntax Analysis (1) - 6주차 1강

10월 7일 6주차 1강

* 개인 공부용으로 정리한 것입니다. 정확한 내용은 본인의 교재를 꼭 확인하시기 바랍니다.

 

1. Roadmap for Building a Parser

• Parser는 Token Stream을 입력받아 Syntax Analyzer로 Syntax Tree를 출력한다
• Specification: 문법을 어떻게 표현할 것인가? (1+3)은 올바르지만 (1+3는 오류를 발생한다
  • 문법을 정의하기 위해 CFG를 사용한다
• Parsing: 구문 분석: 주어진 토큰 시퀀스 s에서 s∈L(CFG)인지 확인하고, Syntax tree 생성하는 법
  • Top-down, Bottom-up 구문 분석 알고리즘 사용

2. Context-Free Grammer

• V: 유한한 variable의 집합. non terminal symbol
• T: 유한한 terminal symbol의 집합. tokens
• S∈V: 시작 기호. non terminal symbol 중 하나
• P: 유한한 생성규칙(Productions)의 집합. 생성 규칙은 x->y 형태. x는 non terminal symbol이고, y는 V랑 T가 섞여있음

3. Derivation

• 정의 (⇒: Derivation Relation – "한 단계에서 유도")
  • 문맥자유문법 G=(V,T,S,P)
  • αAβ는 A∈V, α,β∈(V∪T)∗
  • G의 생성 규칙 A→γ이 있다면 αAβ⇒αγβ로 유도될 수 있음
• ⇒*: Closure of ⇒ – "0단계 이상에서 유도"
  • base: 모든 terminal 기호와 non terminal 기호와 string α에 대해 α⇒∗α
  • Induction: α⇒∗β이고, β⇒γ라면, α⇒∗γ, =>*는 중간 단계를 생략하고 시작과 끝만 남김
  • non terminal symbol E에서 terminal symbol로만 구성된 id*(id+id)가 유도되는 과정을 =>*로 생략 가능

3.1. Language of Grammar

• 정의: Sentential lForm
  • 문맥자유문법 G=(V,T,S,P) S=>* α라면, 여기에서 α ∈(V∪T)∗일 때, α는 문장형식이라고 함
  • terminal symbol과 non termianl symbol이 섞여있음
• 정의: Sentence
  • non terminal symbol 없이 구성된 α 문자열
  • terminal symbol로만 구성된 문자열
• 정의: Language of Grammar
  • 모든 sentence의 집합을 grammar G라고 
  • L(G)={w∣S⇒∗w and w∈T∗}
  • 시작 기호 S에서 유도되는 모든 terminal symbol로 이뤄진 문자열의 집합

3.2. Parse Tree and Derivation

• parse tree(구문 트리)
  • 유도 과정을 트리 형태로 그래픽적으로 구현
  • L(G)는 parse tree를 생성할 수 있는 모든 문자열의 집합
• E⇒−E⇒−(E)⇒−(E+E)⇒−(id+E)⇒−(id+id)
• 각 내부 노드와 자식 노드는 Production의 적용을 나타냄
• 내부 노드는 production의 head, 자식 노드는 production의 body

• 구문 트리는 기호가 교체되는 순서를 무시함. 교체되는 순서에 상관 없이 규칙을 적용하면 동일한 구문 트리가 됨
• 유도 과정과 parse tree 간에는 one-to-many 관계가 존재할 수 있음
• 유도 과정이 동일한 규칙 세트를 사용하지만, 적용하는 순서가 다를 때 발생함

3.3. Derivation for Automatic Parsing

• Leftmost Deriviation
  • 각 문장 형식에서 가장 왼쪽 non terminal symbol을 선택해서 production을 적용함
  • α⇒β에서 α의 가장 왼쪽 non terminal 기호로 교체되는 경우, 이를 α ⇒l ​β로 표시함
  • E ⇒l​ −E ⇒l −(E) ⇒l​ −(E+E) ⇒l​ −(id+E) ⇒l​ −(id+id)
  • S ⇒l∗ ​α 인 경우 left sentential form이라고 함
• Rightmost Derivation
  • 각 문장 형식에서 가장 오른쪽 non terminal symbol을 선택해서 production을 적용함
  • α⇒β에서 α의 가장 오른쪽 non terminal symbol이 교체되는 경우, α ⇒r β
  • E ⇒r ​−E ⇒r​ −(E) ⇒r​ −(E+E) ⇒r ​−(E+id) ⇒r ​−(id+id)
  • S ⇒r∗ ​α 인 경우 right sentential form이라고 함
• 그러나 같은 derivation이 다른 parse tree를 유도하는 경우도 있음. ambiguity(무질서)

 

4. Ambiguity

• grammar가 ambiguous한 경우?
  • 어떤 sentence에 대해 1개 이상의 parse tree가 존재할 경우
  • 같은 문장에 대해 여러 multiple leftmost derivation 또는 multiple rightmost derivation이 유도되는 경우

• 예시: left most로 id+id*id를 유도하기
  
  • E->E+E에서 유도하는 방법과 E->E*E에서 유도하는 방법이 있음

5. Summary

• programmin의 syntax는 CFG에서 유도됨
• terminologies의 basic definition은 CGF, derivation, left/rightmost derivation, parse tree, ambiguity

 

정리 시작: 24.10.23. 14:39

정리 끝: 24.10.23. 15:17

노동요: 배너 Automatic, 피크타임 아낀다 러브킬라 무대