CNUCOM
commented
1 year ago 좋은 질문입니다. 수업 중에 질문한 학생도 있어서 전체 확인을 해주었어야하는데 잊었습니다.
pair-wise 비교를 한다고 합니다. 즉 규칙을 두개씩, 두개씩 다 보고 교집합이 공집합인지 확인해야합니다.
모든 규칙의 lookahead를 한꺼번에 교집합하는 것은 공집합이 나올 가능성이 더 높습니다. 즉, 두개의 규칙의 lookahead가 서로 겹치는 바람에 결정적으로 파싱할 수 없는 경우라도, 3개의 규칙에 대해 교집합을 구해보면 공집합이 나오는 경우도 있습니다.
예) lookahead(A->X) = {a,b}, lookahead(A->Y) = {b,c} , lookahead(A->Z) = {a,c} {a,b} 교집합 {b,c} 교집합 {a,c} = 공집합 이지만 {a,b} 교집합 {b,c} ={b} != 공집합 {b,c} 교집합 {c,a} = {c} != 공집합 {a,b} 교집합 {c,a} = {a} != 공집합 입니다. 즉, 입력이 b일 때, A-X와 A->Y중 어느쪽을 골라야할지 결정적이지 않으므로 아무 쪽이나 선택해서 진행하다가 안되면 백트래킹 해야겠지요. LL(1)이 아닙니다.
글로 설명하다보니 부족한 것 같습니다. 혹시 이해가 잘 안되면 수업중에 한번더 질문 부탁합니다.
green-study
LL(1) 문법인지 확인하는 조건에서 A→a|b라는 규칙이 존재할때 LOOKAHEAD(A→a) 교집합 LOOKAHEAD(A→b) = 공집합 을 통하여 확인을 합니다.
그러면 A →a|b|c와 같이 3개 이상의 규칙이 존재한다면 LOOKAHEAD(A→a) 교집합 LOOKAHEAD(A→b) = 공집합 LOOKAHEAD(A→b) 교집합 LOOKAHEAD(A→c) = 공집합 LOOKAHEAD(A→a) 교집합 LOOKAHEAD(A→c) = 공집합 3가지 결과가 모두 공집합이여야 LL(1)문법을 만족하는 것인가요? 즉, 하나의 nonterminal에 대해 n개의 생성규칙이 존재한다면 nC2개의 교집합 결과가 공집합인지 확인해야하는 것인가요?
LOOKAHEAD(A→a) 교집합 LOOKAHEAD(A→b) 교집합 LOOKAHEAD(A→c)= 공집합 로 확인하는 방법은 잘못된 방법인지 궁금합니다.