Lec06. Syntax Analysis(2) - 7주차 1강/2강

10월 14일 7주차 1강 + 10월 16일 7주차 2강

* 개인 공부용으로 정리했습니다! 정확한 내용은 본인이 공부하는 자료를 참고해주세요.

 

오늘의 대주제: Top-Down Parsing

 

1. Top-Down Parsing

• Top-Down Parsing의 정의
  • 주어진 입력 문자열에 대해 parse tree를 구축하는 과정
  • parse tree의 root에서 시작해서 tree를 preorder로 순회(root-왼-오)하며 input 문자열과 일치하는 leaf까지 진행
  • input  문자열에 대한 leftmost derivation을 찾는 과정과 동일하게 볼 수 있음

• 모든 문법이 top-down parsing 알고리즘으로 분석될 수 있는 건 아님
• 분석할 수 있게 grammar를 재작성해야 함
  • Eliminating Ambiguity
  • Eliminating left-recursion

2. Eliminating Ambiguity

• Eliminating Ambiguity 제거
  • 예시 문법: E→E+E ∣ E∗E ∣ (E) ∣ id
  • 1 + 2*3은 (1+2)*3 또는 1+(2*3) 두 가지로 해석될 수 있음
  • 1+2+3은 (1+2)+3 또는 1+(2+3) 두 가지로 해석될 수 있음
• Precedece: 우선순위
  • *가 +보다 더 높은 우선순위를 갖도록 설정
  • 1+(2*3)으로 해석됨
• Associativity: *와 +f를 항상 left-associative로 설정. 왼쪽 결합성
  • 1+2+3은 항상 (1+2)+3으로 해석됨
• 모호성을 어떻게 없애냐..?  -> 없앨 수 있는 알고리즘은 없음 (?) 아래에서 계속

• 우리는 ambiguous grammar를 unambiguous 하게 바꾸고 싶음. 하지만....
  
  • 문맥 자유 문법 CFG에서 모호성을 제거할 수 있는 알고리즘은 없음
  • CFG가 Ambiguous 하다, 아니다? 판별할 수 있는 알고리즘 없음
  • 일부 CFG는 본질적으로 ambiguous하며, 모호성 제거가 불가능한 언어도 있음
• 우리는 unambiguous grammar를 디자인할 수 있음
  • 기존에 모호한 문법
    • E→E+E ∣ E∗E ∣ (E) ∣ id
  • 같은 의미의 모호하지 않은 문법
  • E→E+T ∣ T
  • T→T∗F ∣ F /* T를 추가해서 연산에 우선순위를 넣어 모호성을 제거*?
  • F→id ∣ (E)

 

• id + id + id: parse tree 그리기
  • E ⇒l E+T ⇒l E+T+T ⇒l T+T+T ⇒l .... =>l id+id+id
• id + id * id에 대한 parse tree 그리기
  • E ⇒l E+T ⇒l T+T ⇒l F+T ⇒l id+T ⇒l id+(T∗F) ⇒l id+(id∗id)

3. Eliminating Left-Recursion

• 어떤 non terminal A가 production의 우변에서 다시 등장하면 left-recursive하다고 말함
  • E -> E+T|T
• 하지만 left-recursive는 top-down parsing에서 무한 loop에 빠질 수 있음
  • T를 분석하기 위해 E->E+T가 계속 반복될 수 있음
• left-recursive 제거 방법: 변환 규칙을 사용해 non-left-recursive 생산
  • 기존 left-recursive production: A→Aα ∣ β
  • A→βA′, A′→αA′ ∣ ϵ 이렇게 바꿔서 제거할 수 있음
• 예시를 다시 변형해보자
  • 기존: E->E+T
  • 변환: E->TE', E'->+TE'| ϵ 

• 예시를 풀어보자
  • 기존: E->E+T|T, 변형: E->TE', E'->+TE'| ϵ 
  • 기존: T->T*F|F, 변형: T->FT', T'->*FT'| ϵ 
  • 기존: F->id|(E), (left-recursive 아니라서 안바꿔도 됨)

• 순차적으로 원본 grammar를 unambiguous하게 바꾸고, non-left recursive하게 바꾸는 방법
• 위에서 했던 예시를 한 슬라이드에 정리한 것 뿐임

• 최종적으로 unambiguous하게 디자인된 grammar에 따라 트리를 그리는 순서를 표현
• root-left-right 순서로 top-down parsing을 진행해 parse tree를 그린다

---

4. Key Problem of Top-down Parsing

• top-down parsing 에서는 leftmost nonterminal을 어떤 production의 우변으로 대체함.
  • Recursive-decent parsing: backtracking을 사용해 어떤 production을 선택할지 결정
• Predictive parsing: 백트래킹을 사용하지 않고, parsing table을 사용함
• LL(1) parsing: input symbol을 1개 미리 보고 예측하는 방식

4.1. Parsing Table

• predictive parser(예측 구문 분석기)는 입력 문자열을 미리 보기 위해 parsing table을 사용
• parsing table은 expression grammar에 대한 정보를 가지고 있음
  • 맨 왼쪽: non-terminal symbol
  • 맨 위: 다음에 input으로 들어올 symbol, 이를 look-ahead tokens(미리보기 토큰)라고 함
  • $: endmarker 입력 문자열의 끝을 표시
  • 만약 non terminal X가 주어지고, 다음 input symbol이 y라면 (X,y)에 있는 production 적용

4.2. Predictive Parsing

• predictive parsing 예시
  • stack: 현재 상태를 나타냄
  • input: 남은 입력 문자열
  • action: stack에서 어떤 규칙을 적용하는지, 혹은 일치하는지
• id+id*id$
  • 1단계: 맨 처음에 E로 시작, input은 id: 규칙 E->TE'
  • 2단계: 왼쪽부터, T랑 id: 규칙 T->FT' 적용하면 FT'E'가 됨
  • 3단계: 왼쪽부터, F랑 id: 규칙 F->id 적용하면 idT'E'가 됨. 이는 id+id*id$의 맨 왼쪽과 match함. pop, T'E'됨
  • 4단계: 왼쪽부터 T'랑 +: T'->입실론 적용하면 E'이 됨.
  • 5단계: 왼쪽부터 E'랑 +: 규칙 E'->+TE' 적용해서 +TE', +id*id$ 맨 왼쪽과 +가 match 됨. pop, TE'됨
  • 6단계: 왼쪽부터 T랑 id: 규칙 T->FT' 적용해서 FT'E' 됨.
  • 7단계: 왼쪽부터 F랑 id: F->id 적용. idT'E': id*id$ 맨 왼쪽과 일치. pop. T'E' 됨
  • 8단계: 왼쪽부터 T'랑 *: T'->*FT' 적용. *FT'E' 됨. *id$ 맨 왼쪽과 일치. pop FT'E'됨.
  • 9단계: 왼쪽부터 F랑 id: 규칙 F->id 적용. idT'E' 됨. id$ 맨 왼쪽과 일치. pop. T'E'됨.
  • 10단계: 왼쪽부터 T'랑 $: 규칙 T'->입실론 적용. E'됨
  • 11단계: 왼쪽부터 E'랑 $: 규칙 E'->입실론 적용. 끝! accept됨.

• w: 문자열, M: 문법 G에 대한 parsing table
• 단계
  • w의 첫 번째 symbol을 a로 설정
  • stack의 top 심볼을 X로 설정
  • X가 $일 때까지 반복
    • 만약 X랑 a가 같으면 top stack 제거하고, w의 다음 심볼을 a로 설정
    • 만약 X가 terminal이면 에러
    • 만약 M[X,a]이면 에러. X에서 a를 받아 갈 수 있는 production이 없다는 뜻
    • 만약 M[X,a]=X→Y1​Y2​…Yk​ 이면 해당 production rule 적용
      • top stack을 제거하고, production rule의 우변을 입력
    • X를 다시 top stack 심볼로 설정

4.3. FIRST and FOLLOW -> constructing parsing table

• Constructing Parsing Table: 구문 분석 테이블
• Predictive parser는 parsing table을 사용해 input symbol을 처리
  • parsing table은 어떻게 만드는가
  • FIRST, FOLLOW: 다음 1개의 symbol을 미리 보기 위해 사용
  • 이를 사용해 constructing parsing table 작성

• 정의: FIRST
  • 문자열 α: terminal, non-terminal symbol의 집합
  • FIRST( α): α로부터 파생될 수 있는 모든 문자열에서 시작할 수 있는 단말 기호들의 집합
  • α⇒∗cβ 라면, c∈FIRST(α)
  • 예외적으로 α⇒∗ϵ 라면, ϵ∈FIRST(α)
• 정의: FOLLOW
  • nonterminal symbol X에 대해, X의 바로 오른쪽에 올 수 있는 terminal symbol의 집합
  • S⇒∗αXaβ, a∈FOLLOW(X)
  • 예외적으로 S⇒∗αX일 경우, $∈FOLLOW(X)

• FIRST(E) =
  • FIRST(TE') = FIRST(FT'E') = FIRST(FT') = FIRST(F)
  • FIRST 집합은 문법 규칙에서 가장 처음으로 보이는 terminal symbol을 모은 것
  • (E)에서는 (, id에서는 id. 따라서 FIRST(E) = {(,id}
• FIRST(E')=
  • FIRST(+TE') and FIRST(입실론) = {+, 입실론}
• FIRST(T)=
  • FIRST(FT') = FIRST(F)
  • 여기에서 T'가 입실론으로 사라지는 이유는, T'이 F 뒤에 있어서 첫 번째 기호가 될 수 없음. FIRST 집합에 영향 없
  • FIRST(F) = {(,id)
• FIRST(T')=
  • FIRST(*FT') and FIRST(입실론) = {*,입실론)
  • FIRST(F) = FIRST((E)) and FIRST(id) = {(,id}
• FOLLOW(E)=
  • 아래 규칙에서 나올텐데, E가 start symbol이면 $  엔드마커를 추가한다
  • FOLLOW를 찾으려고 하는 nonterminal 심볼이 production 오른쪽에 있는 걸 찾는다
  • 그럼 E가 오른쪽에 있는 production? F->(E)|id를 살펴보자
  • production에서 내가 구하려고 하는 Nonterminal symbol 뒤에 있는 symbol의 FIRST를 추가. 그게 )임.
  • 그럼 {$,)} 가 정답이 된다
• FOLLOW(E')=
  • E'이 produciton 오른쪽에 있는 건? E->TE'임. 그럼 FOLLOW(E)값을 추가하자 {$,)}
  • 그 다음으로는 E'->+TE'가 있는데, E' 오른쪽에 아무것도 없움.
  • E' 뒤에 뭐가 없으니까 E->TE'의 E를 대신 추가함 {$,)} 근데 이건 이미 추가한 E값이랑 같음
  • 결론은 {$,)}
• FOLLOW(T) = 
  • T가 production 오른쪽에 있는거? E->TE'. FOLLOW(E) 추가 {$,)}
  • E->TE'에서 T 다음에 E'가 옴. E'은 입실론 또는 TE'로 이동함
    • E'->입실론인 경우, E->T입실론. E->T. 뒤에 아무것도 없으니까 FOLLOW(E) 추가 {$,)}로 동일
    • E'->+TE'인경우 T 뒤에 E'가 오는데, 규칙에 따라 FIRST(E')\{입}를 추가. 그럼 +가 됨
    • 결론적으로 {$,),+}
• FOLLOW(T')=
  • T'가 production의 오른쪽에 있는거? T->FT'임. 그럼 FOLLOW(T)를 추가. {$,),+}
  • 그 다음 production은 T'->*FT'임. T' 오른쪽에 아무것도 없음. 그럼 FOLLOW(T')추가. 같은 값이라 동일.
• FOLLOW(F)=
  • F가 production의 오른쪽에 있는거? T->FT'임. 그럼 Follow(T) 추가. {$,),+}
  • T->FT'에서 F 다음에 T'가 오는데, T'는 *FT' 또는 입실론으로 이동함
    • 입실론으로 이동하는 경우 T->F입실론, T->F가 됨. 그럼 T에 FOLLOW(T)
    • *FT'로 이동하는 경우, F 오른쪽에 T'이 있음. 그럼 FIRST(T')\{입}을 추가해야 함. *을 추가
    • 결론적으로 {$,),+,*}이 됨

 (1) FIRST

• 위에 설명에서 쓰였던 규칙을 다시 확실하게 정리해보자
• FIRST(X)에 대해 정의. 
  • X가 terminal symbol일 경우. FIRST(X)={X}
  • 만일 X가 nonterminal symbol이고, production X->Y1Y2Y3...Yk가 존재할 때
    • 아래 원칙에 따라 FIRST(X) = FIRST(Y1Y2...Yk)을 적용하자
      • FIRST(Y1)\{입실론}, 입실론을 제외한 FIRST(Y1)을 FIRST(X)에 추가
      • FIRST(Y2)\{입실론}, 만약 FIRST(Y1)에 입실론이 있다면, FIRST(Y2) 확인해서 입실론 제거하고 추가
      • ...FIRST(Yk)\{입실론}, 만약 FIRST(Y1)에서 FIRST(Yk)까지 모두 입실론이 있다면, FIRST(Yk)에서 입실론 제거하고 추가
      • 만약 모든 Y1...Yk가 입실론을 포함하고 있다면 FIRST(X)에 입실론을 추가
  • 만약 X->입실론인 규칙이 있다면, FIRST(X)에 입실론 추가
• 입실론 또는 termianl 심볼이 더 이상 추가될 수 없을 때까지 FIRST를 반복한다

 

(2) FOLLOW

 

• FOLLOW를 봅시다
• 파트1: interim FOLLOW(X) 계산
  • X가 start symbol인 경우? FOLLOW(X)에 $을 추가한다
  • 모든 production A에 대해 A→αXβ 형태인 경우, X 뒤에 나오는  β의 FIRST( β )에서 입실론을 제외한 모든 기호 추가
  • FOLLOW(X)←(FIRST(β)∖{ϵ})∪FOLLOW(X)
• 파트2: interim result를 전파
  • X→αA 형태의 규칙이 있을 때(A 옆에 뭐가 없을 때). FOLLOW(X)를 FOLLOW(A)에 추가.
    • A가 grammar의 마지막에 위치하면, X가 뒤따르는 모든 기호가 A를 따라야 한다
  • 입실론 포함 시 전파
    •  X→αAβ에서  β의 FIRST에 입실론이 포함되는 경우?
    • FOLLOW(X)도 FOLLOW(A)에 추가 됨.  β가 입실론을 생성할 수 있는 경우를 처리함

https://m.blog.naver.com/noma000/220902314630

first와 follow를 구해보자

 

이 분 블로그 정리 정말 잘해놓으셨음

같이 비교해가면서 공부하면 좋을 듯

 

(3) Construct Parsing Table

• 목표~
  • parsing table의 각 항목 M[A,a]를 채워넣는게 목적임
  • M은 predictive parsing table, A는 nonterminal, a는 terminal 또는 $
  • 입력 기호 알파에 대해 A->알파 production이 적절히 존재해야 table을 채울 수 있음
• 입력: G (CFG)
• 출력: M (predictive parsing table)
• 알고리듬 두둠칫
  • 각 production A->알파 에 대해 아래와 같이 적용한다
  • 1) 만약 FIRST(알파)에 대해 입실론이 존재하고, terminal b가 FOLLOW(A)에 들어있으면
    • A->알파를 M[A,b]에 추가
    • 알파가 입실론으로 파생될 수 있는 경우의 상황을 정리하는 과정
  • 2) 만약 FIRST(알파)에 입실론이 존재하고, FOLLOW(A)에 $가 들어있으면
    • A->알파를 M[A,$]에 추가한다.
    • $ 기호를 처리하는 방법
• Parsing table에 있는 각 항목이 하나의 규칙만을 포함한다면, 해당 문법은 LL(1) 문법에 속한다

 

(4) Example

• 이거 어케 풂?에 대한 설명
  • 일단 기본 문법을 가져옵니다
  • 그 기본 문법으로 FIRST와 FOLLOW을 구합니다
  • 기본 문법과 FIRST-FOLLOW를 보며 parsing table을 채웁니다!
  • 같이 해봅시다

• 주어진 문법

• FIRST 채우기(위에서 한거랑 같은 과정인데 좀 더 step by step으로 손으로 했어요)

• FOLLOW 채우기

• Parsing Table 채우기

 

끝~~~~~

 

5. 요약

 

 

• Top-down parsing: ambiguous grammar와 left recursion 제거해야 LL(1) 무한 루프 막을 수 있음
• LL(K) parsing: k는 predict를 위해 참고하는 next k개의 input symbol
• LL(1): 가장 단순한 LL parsing, k=1이므로 다음 한 개의 입력 기호만으로 규칙 적용 결정

 

진짜는 탑다운이 아니라 바텀업임

다음 렉처를 기대하십시오

 

---

정리 시작: 10.23. 15:20

정리 끝: 10.24. 15:48

하루종일 정리만 한건 아니고 밥도 먹고 잠도 자고 코테도 풀었어요 ^~^

 

노동요

배너 피크타임 경연곡 모음 무한 반복

스카이스크래퍼가 좋음!