Lec08. Syntax Analysis (4) - 10주차 1강

11월 4일 10주차 1강

* 개인 공부를 위해 정리한 것입니다. 정확한 내용은 꼭 본인이 공부하는 교재를 참고하시기 바랍니다.

 

LR Parsing with Ambiguous Grammars

---

1. LR Parsing with Ambiguous Grammars

• LR 파싱은 LL 파서보다 더 복잡한 문법 구조를 처리할 수 있음. LR>>LL
• Ambiguous 문법의 문제
  • LR 기술을 적용하려면 ambiguity를 제거해야 함 
  • E→E+E∣E∗E∣(E)∣id 이와 같은 문법은 
  • E→E+T∣T, T→T∗F∣F, F→(E)∣id 이와 같이 바꿔야 함
• unambiguous 하게 문법을 작성하는 건 어렵고, 불가능한 경우도 있음
• LR 기술은 disambiguating rules 를 바탕으로 ambiguous grammer에 적용될 수 있음

2. Conflict due to the Ambiguity

2.1 LR(0) items에서 shift/reduce가 conflict되는 부분은?

• 각 item에서 shift가 가능한 항목과 reduce가 가능한 항목이 동시에 존재하면 conflict임
• 예를 들어 I7 item을 보면
  • E->E+E.은 dot이 맨 마지막에 있기 때문에 reduce 항목임
  • 하지만, 나머지 E->E.+E와 E->E.*E는 dot 뒤에 expression이 남아있기 때문에 shift 항목임

2.2 SLR parsing table에서 conflict를 grammar 변형 없이 어떻게 해결해야 할까?

 

• I7에서는 E->E+E. (rule 1)이 종료되었고, I8에서는 E->E*E. (rule 2) 이 종료되었음
• 따라서 Follow(E)를 고려해서, I7에는 r1을, I8에는 r2를 추가해야 함.
• 그리고 Follow(E)에는 +와 *가 포함되어 있기 때문에 해당 부분에 추가함. 그럼 conflict가 발생함
• Conflict를 어떻게 해결할까?
  • 1번 규칙: *는 +보다 높은 우선순위를 가진다
  • 2번 규칙: +와 *는 모두 left-associative하다.
    • (왼->오 로 그룹화함, 오->왼으로 그룹화하는건 음수부호 같은 게 있음 -8 이런거)

3. [1번 규칙] Resolving Conflicts with Precedence (우선순위)

• 마지막 부분에서 s5와 r1 중 어떤 걸 선택해야 할까?

왼: shift5 선택한 경우, 오: reduce 1 선택한 경우

• 여기서 차이점은, shift5일 경우 *가 먼저 처리되며, reduce1일 경우 +가 먼저 처리된다.
• 하지만 우리는 처음에 *가 +보다 높은 우선순위를 가지고 있다고 정의했다. 그렇다면?

• 따라서, s5를 선택해야 *가 +에 대해 우선순위를 가질 수 있다.

4. [2번 규칙] Resolving Conflict with Associativity

• 이번에는 id+id+id input에 대해 살펴보자. s4와 r1 conflict에 대해 무엇을 선택해야 할까?

왼: s4 선택, 오: r1 선택

• 여기에서 주목할 것은, Symbols를 봤을 때 s4는 오른쪽부터 처리되고, r1은 왼쪽부터 처리된다는 걸 알 수 있다
• 그런데 우리는 규칙 2에 의해 +는 left-associative 하다는 것을 알고 있다. 그럼 결과는?

• 따라서, +는 left-associative 하기 때문에 r1을 선택하게 된다.

5. Resolving Conflicts in the "Dangling-Else" Grammar

• 어떤 예시 문법을 살펴보자
  • stmt (statement, 문장)은 조건문과 기타 문장(other)으로 정의
    • stmt → if expr then stmt
    • stmt → if expr then stmt else stmt
    • stmt → other
• 이 grammar는 ambiguous한가?
  • ambiguous하다. 예를 들어 if E1 then if E2 then E2 then S1 else S2 라는 경우를 보자
    • if E1 then if E2 then E2 then S1 else S2 : E1이 참일 때, E2가 참이면 S1을 실행, 아니면 S2
    • if E1 then if E2 then E2 then S1 else S2: E1이 참이면 E2가 참일 때만 S1실행, E1이 거짓이면 S2 실행
    • if-else가 각각 어떻게 매칭되는지에 따라 의미가 달라짐
    • 대부분 첫 번째 해석을 더 많이 받아들임.
    • 각 else는 가장 가까운 짝이 없는 then과 매칭한다는 rule이 있기 때문
• Dangling-else 문제
  • 중첩된 조건문에서 else 절이 ambiguous 해지는 문제
  • 각 else가 정확히 어떤 then에 속하는지 지정되지 않았기 때문에 발생하는 문제

• dangling-else를 해결하기 위해 ambiguous 문법을 unambiguous 하게 바꾸는 방법
  • stmt → matched_stmt | open_stmt
  • matched_stmt → if expr then matched_stmt else matched_stmt | other
  • open_stmt → if expr then stmt | if expr then matched_stmt else open_stmt
• 아이디어: then과 else 사이 내부 문장이 open then(else와 match 되지 않은) 상태로 끝나지 않게 만들기
  • 간단한 해결책: disambiguating rules를 추가하기
• 예시로 확인하기 
  • S′→S
  • S→ i S e S ∣ i S ∣ a
  • i는 if expr then을 의미하고, S는 smtm, e는 else, a는 other를 의미한다.

• 위  ambiguous grammar를 바탕으로 LR(0) items를 만든다
  • conflict가 발생하는 부분은 I4

• 4번 state에서 e가 들어왔을 때 reduce(S->iS.)랑 shift(S->iS.eS)가 동시에 발생함.
• state 4에서 S->iS. 발생, FOLLOW(S)에 포함된 e와 $에 r2를 추가한다. 여기에서 (4,e)에 s5와 r1 conflict 발생
• 어떤 게 맞는 선택인가?
  
  • shift랑 reduce가 겹치면 보통 shift 선택함.

 

• Ocaml yacc(Ocaml parser 생성기) 기본적으로 shift 선택해서 충돌 해결
  • 연산자 precedence 규칙을 따르지 않는 기본적인 경우에 shfit를 선택해서 해결한다

Conflict 해결 예시

• if x then if y then win (); else lose; 에서 else lose;가 어떤 if와 연결되냐 에 따라 해석이 달라짐
• 1번: shift를 선택하는 경우 - 기본적으로 else를 가장 가까운 if와 연결
  • parser가 else를 만나면 shift를 해서 else를 가장 가까운 if와 연결한다
  • else lose;는 가장 안쪽의 if y then win();과 연결한다

if x then {
  if y then {
    win ();
  } else {
    lose;
  }
}

• 2번: reduce를 선택하는 경우 - 가장 바깥쪽 if와 연결
  • parse가 else 바깥쪽 if와 연결
  • else lose;는 가장 바깥 if x then과 연결

if x then {
  if y then {
    win ();
  }
} else {
  lose;
}

 

 

작성 시작: 24.11.05. 20:45

작성 종료: 24.11.05. 21:50

 

노동요: 유튜브 썰풀이 영상