Lec07. Syntax Analysis (3) - 8주차 1강/2강

10월 21일 8주차 1강 + 10월 23일 8주차 2강

 

1. Bottom-Up Parsing

• Bottom up parsing: 입력된 문자열에서 시작해 점차 상위로 올라가며 parse tree를 구성하는 과정
  • leaf에서 시작해서 root로 작업이 진행됨
  • 문자열 w를 start symbol을 사용해서 점점 reducing하는 과정
• Reduction: production rule를 역방향으로 적용. production의 body를 head로 교체함
• id*id 예시에서, id*id가 순차적으로 축소되어 최종적으로 시작 기호 E로 변환 됨.
• Rightmost Derivation의 역순으로 구성됨. production rule을 역으로 적용해서 최종적으로 start symbol로 도달함.

• Expression Grammar: E→E+E ∣ E∗E ∣ (E) ∣ id
• 위 문법을 unambiguous하면서 left-recursive(우측에 자기자신 포함)한 버전으로 바꾸면
  • E→E+T
  • E→T
  • T→T∗F
  • T→F
  • F→(E)
  • F→id
• top-down parsing: left-recursive grammar 처리에 부적합
• bottom-up parsing(지금 배우는거): parse tree를 재귀적으로, 무한적으로 확장하지 않는 방식이기 때문에 left-recursvie grammar를 처리할 수 있음

 

2. Handle

• bottom-up parsing의 포인트: 언제 reduce할 것인가, 어떤 production을 적용할 것인가가 주요 결정 포인트
  • 예를 들어 주어진 T*id에서 id를 F로 치환해서 E로 축소할 수 있도록 prodcution을 적용함. 만일 T를 E로 치환한다면 id*id를 accept할 수 없음. 어떤 prodcution을 어떤 문자에 적용할지 결정하는 것 중요함
• bottom-up parsing: handle을 선택하고 reduce하는 과정
  • handle: 이란 무엇인가?
    • production의 body(우변)과 일치하는 substring, 축소하면 right-sentential form으로 reduction 됨

3. LR Parsing

• LR Parsing: 가장 선호되는 bottom-up parsing
• LR(k)
  • L: input을 왼-오로 스캔
  • R: rightmost-derivation을 역순으로 적용
  • k: 최대 k token을 미리 내다봄
• 일반적으로 널리 사용된 이유
  • LL(k) ⊆ LR(k): LR 메서드를 사용해 구문 분석할 수 있는 grammar class가 LL 메서드 사용할 때보다 넓음
    • LR이 LL보다 더 복잡한 문법을 처리할 수 있음
  • 대부분의 parse는 LR parsing을 기반으로 만들어짐

 

3.1. LR Parsing Overview

• LR parse는 현재 stack state와 next input symbol에 의거해 아래 두 가지 작업을 수행함
• Reduce
  • stack의 맨 위가 handle일 때 수행 됨
  • 예를 들어 X->ABC가 선택되면, stack에서 C,B,A를 pop하고 X를 push한다
• Shift
  • input에서 stack으로 token을 이동시키는 작업
  • stack의 맨 위가 handle이 아닐 때 수행하는 작업

 

 

3.2. Recognizing Handles

• Handle 결정하는 법
  • DFA pasing table을 기반으로 expression grammar를 관리함
  • input token을 읽으면서 handle을 인식하고 축소할지, 아니면 더 많은 토큰을 shift할 지 결정함
• s: shift, r: reduce, g: goto
• 맨 윗줄: 왼쪽-state, 가운데-terminal symbol, 오른쪽-non termnial symbol

3.3. LR Parsing Process

3.4. LR Parsing Algorithm

• LR 파싱 알고리즘
  • top stack과 input symbol을 확인하고 action을 고른다
  • 만약 actions이
    • shift(n)이라면 input에서 token을 하나 가져오고, 이와 대응하는 상태 n을 stack에 push 한다
    • reduce(k)라면
      • reduce는 파싱 규칙을 적용해 스택이 여러 상태와 기호들을 하나의 nonterminal symbol로 축소하는 과정
      • reduce(k)는 다음을 수행
        • pop stack: 해당 파싱 규칙의 우변에 있는 기호들의 개수만큼 stack에서 state를 제거한다
        • X는 rule k의 좌변이라고 하자
        • X에 대해 goto 테이블을 참조해 state를 확인한다 (goto n)
        • n를 top stack에 push한다

 

4. LR(0)

4.1. LR(0) and SLR Parser Generation

• grammar를 파싱하기 위해 parsing table을 만들어야 한다

• 그 parsing table은 LR(0) Automaton 으로부터 만들어진다.
• 일단 LR(0) Automaton을 어떻게 구하는지 아래에서 살펴보자

4.2. LR(0) Items

• LR(0) Items
  • item: dot(점)이 production의 body에 어디에 있는지를 기준으로 표현됨
  • 문법 규칙이 A->XYZ라면, 점 위치에 따라 여러 표현이 가능함
    • .XYZ X.YZ XY.Z XYZ.
    • 점 앞에 있는 건 이미 처리된거, 점 뒤에 있는 건 처리해야 할거
  • 만약 규칙이 A → ε이라면 A → . 으로 표현함.
  • A → XYZ. 는 파서가 XYZ를 전부 처리했으므로, A로 reduce할 준비가 되었다는 것임

5. Parse Mechanism

5.1. The Initial Parse State

• 가장 처음에 파서는 empty stack에서 시작함
• 그리고 파서는 완전한 E-문장을 파싱하고 싶기 때문에 E'->.E를 초기상태로 정의함
• initial item에서 어떤 input token 없이 도달할 수 있는 모든 항목을 수집하자
  • parsign 진행 과정에서 virtually equivalent한 항목을 모두 모아야 함
  • 예를 들어, E->.E+T이면, E와 관련된 다른 규칙들도 파싱에 포함될 수 있음
  • 입력을 아직 처리하지 않은 상태에서 해당 규칙과 관련된 모든 항목을 한번에 모아서 시작상태 정의

5.2. Closure of Item Sets

• 초기상태: 모든 item I를 CLOSURE(I)에 추가함
• 만약 A → α . B β 가 CLOSURE(I)에 있고, B-> γ 가 production이라면, B->. γ를 CLOSURE(I)에 추가함
  • 더이상 새로운 item이 CLOSURE(I)에 추가되지 않을 때까지 계속 추가함

5.3. Construction of LR(0) Automaton

• 예시로 I1을 만드는 법을 알려줌
  • 예를 들어 I0인 상태에서 input으로 E가 들어왔다고 해보자
  •  A → α . B β 형태에서 B를 E로 치환함.  A → α . E β
  • 위 형태에 해당하는 rule을 모두 고르자
    • E' → .E, E → .E + T
  • 해당 rule에서 .을 E 뒤로 하나씩 옮기자
    • • E' → E., E → E. + T

• 예를 들어 "("가 들어왔다고 가정하자
• (I 순서는 크게 의미는 없는데, 지금 ppt에 나오는 도식도를 기준으로 해서 번호가 정해짐)
• A → α . B β 에서 (로 바꾸면 A → α . ( β 
  • 해당하는 형태는 F->.(E) 이거고, 점 위치 옮기면 A → α  ( .  β  이 된다.
  • 그럼 F->(.E)가 되는데, . 뒤에 non-terminal symbol인 E가 있다.
  • 그럼 E에 대한 Closure도 구해서 적용해야 한다.
• E에 대한 closure
  • E->.E+T, E->.T
  • 엇 . 뒤에 T가 또 있다 그럼 얘도 Closure를 구하자
    • T->.T*F, T->.F
    • 엇 점 뒤에 F가 있다.. 그럼 또 Closure를 구하자
      • F->.(E), F->.id
      • 이런 논리로 I0의 state가 다 추가됨

 

5.4. GOTO

• I: item의 집합. X:는 grammar symbol(terminal or nonterminal)
• GOTO(I,X): stateI에서 X를 읽었을 때 정의하는 새로운 state
  • I의 A → α . X β 를 A → α X . β  로 바꿔서 모든 set을 Closure에 추가하게 됨
• 알고리즘
  • GOTO(I,X)에서
    • J는 빈 집합
    • 모든 A → α . X β item(in I)에 대해 A → α X . β 를 J에 추가함
    • Closure (J)를 반환함    

 

5.5. Construction of LR(0) Automaton

• LR(0) Automaton  만들기
  • T: state 집합
  • E: edge 집합
    • T를 Closure((S'->S})로 초기화
    • E를 빈 집합으로 초기화
    • 반복문
      • T에 존재하는 각 state I에 대해
        • I에 있는 각 item  A → α . X β
          • J를 GOTO(I,X)라고 했을 때
          • 집합에 J를 추가
          • E에 I에서 X를 통해 J로 가는 관계 추가
      • E와 T가 변하지 않을 때까지 계속

 

6. LR(0) Automaton to LR(0) Parsing Table

• 노가다를 통해 만들어진 Automaton 테이블
• 제가 직접 해보겠습니다 (근데 이거 슬라이드에서 8에서 + 받으면 6으로 가는게 맞는거 아닌가

 

• 각 state를 다 정의했으면 하나의 table로 edge를 통해 이어봅시다

 

• LR(0) Automaton 에서 LR(0) Parsing Table 만들기
• 알고리즘
  • 각 state I가 S'->S. 를 포함하고 있으면  acception action (I,$)를 추가
    • .이 끝까지 이동해서 더 이상 파싱할 게 없으니까 accept이 가능하다는 뜻
  • 각 edge I---X--->J에 대해
    • 만약 X가 terminal이면, shift J action을 (I,X)에 집어넣는다
    • 만약 X가 nonterminal이면, (I,X)에 goto J를 집어넣는다
  • 각 state가 item A-> γ. ( dot이 끝까지 이동한 production n)을 포함하는 경우
    • 모든 token Y에 대해 (I,Y)에 reduce n을 추가함
• 위에 직접 만든 table을 바탕으로 LR(0) parsing table을 만들어봅시다

6.1. Conflicts

• 한 state에 multiple action이 가능한 경우 문제가 발생할 수 있음

• parsing table에서 발생할 수 있는 두 가지 충돌
  • Shift/Reduce 충돌: parser는 둘 중 무러 해야할 지 모호함
  • Reduce/Reduce: 어떤 reduction을 수행해야할지 모름
• LR(0) parsing table의 grammar가 conflict가 없으면, LR(0) grammar에 해당된다고 할 수 잇음
• Shift/Reduce conflict를 위에서 어떻게 해결할 수 있을까?

6.2. From LR(0) Automaton to SLR Parsing Table

 

• LR(0) Automaton to SLR Parsing Table
  • 각 state I에서 S'->S. 를 포함하면, accept action (I,$)를 집어넣음
  • 각 edge I----X--->J
    • 만약 X terminal이면, (I,X)에 shift J 집어넣음
    • 만약 X가 nonterminal, (I,X)에 goto J에 집어넣음
  • A-> γ. (점이 끝에 있는 production n)를 포함하는 state에 대해
    • FOLLOW(A)에 속하는 모든 Y에 대해 (I,Y)에 reduce n 집어넣음

6.3. SLR Parsing Table

• 아까와 다르게 중첩되는 게 없어졌당
• 여기에서 FOLLOW 구하는 게 조금 헷갈림
  • top-down parsing에서도 follow를 구했는데 그거랑 결과가 다름
  • 왜냐면 그때는 grammar를 left-recursive가 아닌 형태로 바꾸고, 그 상태에서 follow를 구했기 때문
  • top-down parsing은 left-recursive가 허용되기 때문에, grammar를 수정하지 않고 그대로 follow를 구해야됨
  • 자세한 건 제 필기를 참고하십시요 (이거 이해하는데 개오래걸림ㅠㅠ ㅎㅎ)

6.4. More Powerful LR Parsers

• 각 parser의 포함관계를 설명하는 그림

 

 

와~~~~ 드디어 끝났다

 

정리 시작: 24.10.24. 정확하진 않은데 저녁 먹기 전후로 시작했음

정리 종료: 24.10.25. 오후 8시 23분

그 사이에 있었던 일: 배너 피크타임 노래 다 듣고 오토매틱 듣고 타이틀곡 따라가면서 듣다가 자컨이랑 예능 보고 결국 버블 구독함...