8. LR 구문 분석 8-1. LR 파서 8-2. LR(0) 아이템의 집합 8-3. SLR 파싱 테이블 구성 방법

Slides:



Advertisements
Similar presentations
CHAPTER 5 TOP-DOWN PARSING SUNG-DONG KIM, DEPT. OF COMPUTER ENGINEERING, HANSUNG UNIVERSITY.
Advertisements

10-7 부동소수점 (Floating-Point) 계산  컴퓨터에서 숫자를 표기하는 방법  가수 (Fraction) : 부호화된 고정소수점 숫자 지수 (Exponent) : 소수점의 위치를 표시 ( 예 )10 진수 를 표기하면 Fraction Exponent.
Chapter 12. 배열. 배열  동일한 항목들이 동일한 크기로 연속적으로 메모리에 저장되는 구조  동일한 자료 유형이 여러 개 필요한 경우에 이용할 수 있는 자료 구조.
6 장. printf 와 scanf 함수에 대한 고찰 printf 함수 이야기 printf 는 문자열을 출력하는 함수이다. – 예제 printf1.c 참조 printf 는 특수 문자 출력이 가능하다. 특수 문자의 미 \a 경고음 소리 발생 \b 백스페이스 (backspace)
1 08 배열. 한국대학교 객체지향연구소 2 C 로 배우는 프로그래밍 기초 2 nd Edition 배열  동일한 자료유형의 여러 변수를 일괄 선언  연속적인 항목들이 동일한 크기로 메모리에 저장되는 구조  동일한 자료 유형이 여러 개 필요한 경우에 이용할 수 있는.
1. 2 차원 배열  배열은 동일한 데이터 유형으로 여러 개의 변수를 사용할 경우 같은 이 름으로 지정하여 간편하게 사용할 수 있도록 하는 것으로서 앞에서 1 차원 배열을 공부하였습니다.  2 차원 배열은 바둑판을 생각하면 되며, 1 차원 배열에서 사용하는 첨자를 2.
제3장제3장 제3장제3장 이산균등분포  확률질량함수 :  평균 :  분산 : 공정한 주사위를 한 번 던지는 경우 나온 눈의 수를 확률변수 : X 확률질량함수 : 평균 : 분산 :
제 5 장 구문 정의  프로그래밍 언어의 기본 문자 집합  Alphabet 문자 (A-Z) 26 개 + 아라비아 숫자 (0 - 9) 10 개  예 ) Fortran : 기본 문자 집합 + 13 개의 특수문자 (=+ - * / ( ),. $ ‘ : 공백 ) Algol60.
컴퓨터와 인터넷.
컴파일러 입문 제 7 장 LL 구문 분석.
적분방법의 연속방정식으로부터 Q=AV 방정식을 도출하라.
2장. 프로그램의 기본 구성. 2장. 프로그램의 기본 구성 2-1"Hello, World!" 들여다 보기 /* Hello.c */ #include int main(void) { printf("Hello, World! \n"); return 0;
컴퓨터프로그래밍 1주차실습자료 Visual Studio 2005 사용법 익히기.
제 7 장  LR 파서.
Report #5 - due: 4/13 다음 10*5의 희소 행렬 A, B를 고려하라.
수치해석 6장 예제문제 환경공학과 천대길.
Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라.
제3장 스택과 큐.
P150 문제를 프로그래밍 할 것 Source file (헤더파일포함), 실행화면 (학번_이름_1.txt)
6. 구문 분석 (syntax analysis)
11장. 포인터 01_ 포인터의 기본 02_ 포인터와 Const.
학습목표 학습목차 다른 홈페이지의 HTML 파일 코드를 보는 방법에 대해 알아봅니다.
6장. printf와 scanf 함수에 대한 고찰
2007 1학기 11 프로젝트 기초 실습.
602 LAB FDTD 를 이용한 Acoustic Simulation 지도: 이형원 교수님 차진형.
3. 정규 언어(Regular Language)
11장. 1차원 배열.
JA A V W. 03.
프로그래밍 개요
5. Context-free 문법 5-1. 서 론 5-2. 유도와 유도 트리 5-3. CFG표기법.
박성진 컴퓨터 프로그래밍 기초 [09] 배열 part 1 박성진
이메일 자동 포워딩 방법 (Outlook/OWA)
Report #3 - due: 4/6 100*100의 2개의 희소 행렬 A, B를 전달 받아서 이들의 덧셈을 구하고, 그 결과의 행렬 C를 반환하는 add_sparse_matrix(A, B, C)를 다음과 같이 작성하라. 희소 행렬은 sparse_matrix 타입으로 표현된다.
Quiz #7 다음 수들을 합병 정렬과 퀵 정렬 알고리즘을 이용하여 오름 차순으로 정렬하였을 때, 데이터 이동 회수를 각각 구하라. 여러분은 정렬 과정을 단계별로 보이면서 이동 회수를 추적해야 한다. 단, 퀵 정렬시에 피봇으로 배열의 왼쪽 첫 번째 원소를 선택한다. 5.
Term Projects 다음에 주어진 2개중에서 한 개를 선택하여 문제를 해결하시오. 기한: 중간 보고서: 5/30 (5)
연산자 (Operator).
컴퓨터 프로그래밍 기초 - 10th : 포인터 및 구조체 -
8. LR 구문 분석 8-1. LR 파서 8-2. LR(0) 아이템의 집합 8-3. SLR 파싱 테이블 구성 방법 8-4. CLR 파싱 테이블 구성 방법 8-5. LALR 파싱 테이블 구성 방법 8-6. 모호한 문법 8-7. 구문 분석기의 작성.
합집합과 교집합이란 무엇인가? 01 합집합 두 집합 A, B에 대하여 A에 속하거나 B에 속하는 모든 원소로 이루어진 집합을 A와 B의 합집합이라고 하며, 기호 A∪B로 나타낸다. A∪B ={x | x∈A 또는 x∈B}
컴퓨터 프로그래밍 기초 - 8th : 함수와 변수 / 배열 -
9강. 클래스 실전 학사 관리 프로그램 만들기 프로그래밍이란 결국 데이터를 효율적으로 관리하기 위한 공구
빌드 성공.
CHAP 21. 전화, SMS, 주소록.
균형이진탐색트리 이진 탐색(binary search)과 이진 탐색 트리(binary search tree)와의 차이점
ITQ 정보기술자격 국가공인 Excel 2007 Ⅱ 함수- 15회차 강사 : 박영민.
약식 진리표를 이용한 타당성 증명 진리표 그리기 방법의 한계
에어 PHP 입문.
4장. 데이터 표현 방식의 이해. 4장. 데이터 표현 방식의 이해 4-1 컴퓨터의 데이터 표현 진법에 대한 이해 n 진수 표현 방식 : n개의 문자를 이용해서 데이터를 표현 그림 4-1.
Chapter 1 단위, 물리량, 벡터.
[INA240] Data Structures and Practice
쉽게 배우는 알고리즘 2장. 점화식과 점근적 복잡도 분석
논리회로 설계 및 실험 4주차.
Chapter 10 데이터 검색1.
12 그리드 시스템.
11장 배열 1. 배열이란? 1.1 배열의 개요 1.2 배열의 선언과 사용.
ITQ 정보기술자격 국가공인 Excel 2007 Ⅱ 함수- 12회차 강사 : 박영민.
상관계수.
7장 연습 문제 풀이 학번 : 이름 :조 재한.
Numerical Analysis Programming using NRs
3장 (2) 구문과 의미론 순천향대학교 컴퓨터공학과 하상호.
제 4 장 Record.
수치해석 ch3 환경공학과 김지숙.
제 29 강 스트링(string) 다루기 s a i s . s T i h t g r i n.
개정판 누구나 즐기는 C언어 콘서트 제13장 동적 메모리 출처: pixabay.
버스와 메모리 전송 버스 시스템 레지스터와 레지스터들 사이의 정보 전송을 위한 경로
교착 상태 해결 : 교착 상태 탐지 교착 상태 탐지(Deadlock Detection)
Visual Basic .NET 기초문법.
2학기 2학기 7월 26일(금) 14시에 덕성포탈에 로그인 하시면 합격/불합격/대기 여부를 확인하실 수 있습니다. 2학기
피보나치수열에 대하여 한림초 5학년 신동오.
2019 2학기 9장 배열과 포인터 1. 주소, 주소연산자(&) 2. 포인터, 역참조연산자(*) 3. 배열과 포인터.
Presentation transcript:

8. LR 구문 분석 8-1. LR 파서 8-2. LR(0) 아이템의 집합 8-3. SLR 파싱 테이블 구성 방법 8-4. CLR 파싱 테이블 구성 방법 8-5. LALR 파싱 테이블 구성 방법 8-6. 모호한 문법 8-7. LR 파싱 테이블의 구현 8-8. 구문 분석기의 작성

8-1. LR 파서 LR 구문분석 정의 결정적인 bottom-up방법으로 LR는 입력 스트링을 왼쪽에서 오른쪽으로 읽어가며(Left to right scanner)출력으로 우파스 (Right parse)를 생성하기 때문에 붙여진 이름이다.

정의 a1 a2 … an$ Sn . LR방법으로 주어진 스트링을 구문 분석하는 구문 분석기를 말한다. 입력 파싱테이블 출력 구문분석기 스택 스택 : S0X1S1 … XmSm (Si: 상태, XiV : 문법기호) 버퍼 : a1a2…an$

Parser 정의 shift reduce (S0X1S1XmSm, aiai+1…an$) ACTION[Sm,ai] = shift S (다음상태) (S0X1S1…XmSmaiS, ai+1…an$) 입력심벌을 스택에 넣고 다음 상태를 S로 만들기 위해 S도 역시 스택 에 push한다는 의미 reduce ACTION[Sm, ai] = reduce A  | | = r 2*r 만큼 pop off (S0X1…Sm-rAS, ai+1…an$) 새로운 S GoTo(Sn-r,A) = S

Accept Error ACTION[Sm, ai] = accept 올바른 스트링이라는 의미이며 파싱을 끝낸다. Error ACTION[Sm, ai] = error Sm상태에서 입력 심벌 ai를 본 행동이 error라면 입력 스트링이 틀린 스트링이라는 의미이며 그 에 따른 작업을 하게 된다. 일반적으로 오류복구 루틴을 불러 오류를 처리한다.

 예제 1. LISTLIST, ELEMENT 2. LISTELEMENT 3. ELEMENTa 파싱테이블: 파싱 과정: (0 , a, a$) (0 a 3 , , a$) (0 ELEMENT 2 , , a$) (0 LIST 1 , , a$) (0 LIST 1, 4 , a$) (0 LIST 1, 4 a 3 , $) (0 LIST 1, 4 ELEMENT 5 , $) (0 LIST 1 , $) r3GOTO2 r2GOTO1 s4 r3GOTO5 s3 r1GOTO1 accept

8-2. LR(0) 아이템의 집합 정의  예제 LR(0) 아이템은 생성 규칙의 오른쪽에 점 심벌을 가진 생성 규칙이다.  예제 생성 규칙의 형태가 AXYZ일 때, [A.XYZ], [AX.YZ], [AXY.Z], 그리고 [AXYZ.]등은 모두 LR(0)아이템이다.

8-3. SLR파싱 테이블 구성 방법 SLR이란 Simple LR C0와 FOLLOW 정보를 이용하여 파싱 테이블을 구성하는 방법 C0 = { I0, I1, , In }

SLR 파싱 테이블을 작성하는 방법 만일 LR(0) 아이템 [A.a]가 상태 I에 있고 a가 terminal심벌 이면 shift행동이므로, I 상태에서 마크 심벌 a를 보고 j 상태로 가 는 GOTO함수가 존재한다면, ACTION 테이블의 상태 I와 심벌 a 가 만나는 곳에 상태 번호 j를 적는다. if [A.a]Ii and GOTO(Ii, a) = Ii then M[i, a]:= shift j 아이템 [Aa.]가 상태 I에 있다면, reduce 행동이므로 nonterminal A의 FOLLOW를 구하여 ACTION테이블의 상태 I와 FOLLOW 심벌이 만나는 곳에 reduce 생성 규칙 번호를 적는다. if[A.]Ii then for each aFOLLOW(A) do M[i,a]:=reduce A

상태 I에 LR(0) 아이템 [S’S.]가 있다면 accept 행동이므로 ACTION 테이블의 상태 I와 $심벌이 만나는 곳에 accept를 적는다. if [S’S.]Ii then M[i, $] := accept 만일 LR(0)아이템[A.B]가 상태 I에 있고 B가 nonterminal 심벌일 때, 상태 I에서 마크 심벌 B를 보고 상태 j로 가는 GOTO 함수가 존재한다면 GOTO테이블의 상태 I와 nonterminal심벌 B가 만나는 곳에 상태 번호 j를 적는다. if[A.B]Ii and GOTO(Ii, B) = Ii then M[i, B] := j.

이렇게 해서 정의되지 않은 파싱 테이블의 엔트리는 모두 error가 되며 첨가된 생성 규칙의 LR(0) 아이템 [S’S]를 포함하는 상태 가 초기 상태가 된다. 예제 1. E  E + T 2. E  T 3. T  T * F 4. T  F 5. F  (E) 6. F  id (1) 첨가된 생성 규칙 : 0. S’  E 1. E E + T 2. E  T 3. T  T * F 4. T  F 5. F  (E) 6. F  id

[S’  .E] [E.E+T] [E.T] [T.T*F] [T.F] [F.(E) [F.id] [S’E.] [EE.+T] [ET.] [TT.*F] [TF.] [EE+.T] [F.(E)] [EE+T.] [TT*.F] [TT*F.] [F (.E) [E .E+T] [E .T] [T .T*F] [T .F] [F .(E)] [F .id] [Fid.] [F(E.)] [F(E). I0 I11 I8 I5 I4 I7 I3 I2 I9 I6 I1 I10 E + T * F ( ) id (2) C0 및 GOTO그래프

(3) FOLLOW의 계산 FOLLOW(E) = {$, +, )} FOLLOW(T) = {*, +, ), $} FOLLOW(F) = {*, +, ), $} (4) 파싱 테이블

(5) 스트링 a*a+a를 위한 구문 분석 과정

8-4. CLR 파싱 테이블 구성 방법 정의 LR(0)아이템에 lookahead정보를 첨가 한 것이 LR(1)아이템 이라고 한다. LR(1)아이템은 [A., a]의 형태를 이루며 여기서 AP 이고 aVT{$}이다. 첫번째 부분 A.를 core라고 부르며 LR(0) 아이템과 같은 의미 를 갖는다. 두 번째 부분 a를 아이템의 lookahead라 부르며, reduce 아이템 일 때 그 심벌에 대하여 reduce 행동을 하는 것을 뜻한다.

CLR파싱 테이블 작성 방법 I가 LR(1) 아이템의 집합이라면, CLOSURE(I) = I  {[B., b] | [A.B, a]CLOSURE(I), BP, bFIRST(a)}이다. CLR파싱 테이블 작성 방법 만일 LR(1) 아이템 [A.a, u]가 상태 i에 있고 terminal이면 shift 행동이므로, i상태에서 마크 심벌 a를 보고 j상태로 가는 GOTO함수가 존재한다면 ACTION 테이블의 상태 I와 심벌 a가 만나는 곳에 상태 번호 j를 적는다. if [A.a, u]Ii and GOTO(Ii, a) = Ij then M[i, a] := shift j.

만일 LR(1)아이템[A., u]가 상태 I에 있다면 reduce 행동 이므로 ACTION테이블의 상태 I와 lookahead 심벌 u가 만나는 곳에 reduce 생성 규칙 번호를 적는다. if [A., u]Ii then M[i, u] := reduce A. 만일 LR(1) 아이템[S’S.,$]가 상태 i에 있다면 accept 행동 이므로 ACTION 테이블의 상태 I와 $심벌이 만나는 곳에accept를 적는다. if [S’S.,$]Ii then M[I, $] := accept. 만일 LR(1) 아이템 [A.B, u]가 상태 I에 있고 B가 nonterminal일 때, i 상태에서 마크 심벌 B를 보고 j 상태로 가는 GOTO 함수가 존재한다면 GOTO 테이블의 상태 i와 심벌 B가 만나는 곳에 상태 번호 j를 적는다. if [A.B, u]Ii and GOTO(Ii, B)=Ii then M[i,B] := j.

8-5. LALR 파싱 테이블 구성 방법 정의 LookAhead LR 방법으로 아이템의 lookahead 정보를 이용하기 때문에 SLR방법보고 훨씬 강력하고 파싱 테이블의 크기는 CLR 에서 core가 같은 아이템들을 한 데 묶음으로써 SLR와 같은 크기 로 구성가능 모호하지 않은 context-free문법으로 표현된 거의 모든 언어를 인식할 수 있기 때문에 요사이 대부분의 파서 제작 시스템에서 사용된다.

테이블 작성방법 [A.,a] [A.,b] … … [A.,a/b] … C1에서 작성하는 방법 Ii Ij Iij 같은 core를 가진 LR(1) 아이템 집합들을 한 개의 LR(0)아이템 집합 으로 만들고 각 아이템의 lookahead는 이들 LR(1)아이템의lookahead 의 합집합으로 구성하는 방법 예를 들면 C1의 Ii와 Ij와 같은 core를 갖고 있다면, Iij상태로 통합되어 한 개의 상태로 된다. 이때, lookahead는 두 아이템이 갖고 있는 lookahead의 합집합이 된다. Ii Ij [A.,a] … [A.,b] … Iij [A.,a/b] …

C1에서 같은 core를 갖는 상태들을 모두 통합하면, C0과 같은 상태수를 갖게 된다. 따라서 LALR 파싱 테이블의 크기는 항상 SLR와 같게 된다. 공통 core를 갖는 상태를 합침으로써 원래의 상태들에서 존재 하지 않았던 shift-reduce충돌은 야기할 수 있다. 다시 말해서, CLR방법에서 shift-reduce충돌이 일어나지 않으면, LALR방법 에서도 shift-reduce 충돌이 일어나지 않는다. 왜냐하면 shift 행동은 core에 따라 결정되는 것이지 lookahead에 따라 결정 되는 것이 아니기 때문이다. C1로부터 구하는 것은 이론적으로 쉽게 설명할 수 있으나 실질 적으로 C1을 작성하는 데는 lookahead에 따라 상태수가 매우 커지고 시간이 오래 걸려 실제적인 프로그래밍 언어의 파싱 테이 블 구성하는 방법으로는 사용하지 않는다.

정의 C0를 이용하는 방법 상태 p에서 LR(0) 아이템 [A.]의 lookahead는 SLR방법과 유사 주어진 문법의 C0을 구성 파싱 테이블의 shift와 accept 그리고 GOTO 행동은 SLR와 같고 reduce행동은 각 reduce 아이템의 lookahead에 의해 결정된다. LALR 방법은 C0으로부터 reduce 아이템의 lookahead를 구하는 것이 주된 이론 정의 상태 p에서 LR(0) 아이템 [A.]의 lookahead는 LA(p, [A.])로 표기하며 p 상태에서 A 다음에 나올 수 있는 terminal의 집합이다. LA(p, [A.]) = {a | aFIRST(), S’A ,  accesses p}. *

상태 p의 전 상태, PRED(p)의 의미는 다음과 같다. p,qC0이고 XV, 그리고 V*일 때, GOTO(q, ) = q 이고 GOTO(q, X) = GOTO(GOTO(q,X), )이다. 그리고 PRED(p, a) = {q | pGOTO(q, a)}이다. LR(k)문법은 고정된 k에 대하여 두 개의 우측 유도과정이 존재할 때마다 다음을 만족한다. S’     와 S’  y의 유도 과정이 있을 때 FIRSTk() = FIRSTk(y)이면 a = , A = B, 그리고 x = y이다. * *

8-6. 모호한 문법 정의 모호한 문법에서 구문 분석 행동의 순위 모든 모호한 문법은 LR문법이 될 수 없다. 파싱테이블 작성시 항상 shift-reduce충돌이나 reduce-reduce 충돌을 야기 모호한 문법에서 구문 분석 행동의 순위 shift-reduce 충돌인 경우 reduce되는 생성 규칙과 입력 심벌의 순위를 비교하여 결정하는데 생성 규칙의 순위가 높으면 reduce를, 그렇지 않으면 shift를 선택하는 것이 일반적이다. 같은 순위인 경우에는 결합 법칙을 이용하는데 좌측 결합을 만족하면 reduce를, 우측 결합을 만족하면 shift를 선택한다.

Reduce-reduce충돌인 경우 reduce되는 생성 규칙들의 순위를 비교하여 어느 생성 규칙을 생성 규칙의 순위는 그 생성 규칙 내에 있는 terminal심벌로 결정할 수 있으며, 또는 YACC에서와 같이 특별히 명시하는 방법이 있다. PGS의 입력 명세서에서 먼저 기술되는 생성 규칙이 순위가 높도록 정할 수 있다.

8-7. LR파싱 테이블의 구현 파싱테이블의 구성 ACTION테이블과 GOTO테이블로 구성 ACTION테이블 GOTO테이블 terminal심벌에 대해나 구문 분석 행동을 나타낸다 GOTO테이블 reduce시에 nonterminal에 대한 다음 상태를 나타낸다.

파싱테이블 구현 시 문제점 ACTION 테이블의 기억공간 축소 실제 프로그래밍의 경우에 파싱테이블이 상태수와 문법 심벌의 개수에 따라 방대하게 커져 기억 공간을 매우 많이 차지하여 기억 공간의 낭비가 심하고 또한 테이블을 구하는 데도 상당한 시간과 노력이 소요된다 ACTION 테이블의 기억공간 축소 같은 구문 분석 행동을 갖는 상태의 경우 한 상태만 표시하고 나머지 상태에서는 그 구문 분석 행동을 갖는 상태에 포인터만 갖게 함으로써 중복되는 구문 분석 행동으로 인한 기억 공간의 낭비를 줄일 수 있다. 각 상태에서 terminal 심벌 중 구문 분석 행동이 정의된 것만 표현 하고 나머지는 별도로 한데 묶어 나타내어 기억 공간을 줄이는 방법

GOTO테이블의 기억공간 축소 각 nonterminal에 대한 짝을 만들어 내는 것 기억 장소를 줄임으로써 테이블을 참조하는 데 걸리는 시간이 증가 파싱테이블을 위한 기억 장소의 배정은 동적 기억 장소를 이용 하는 것이 바람직하다. 왜냐하면, 파싱테이블은 단지 구문분석 시에만 필요로 하기 때문에 구문분석이 끝났을 때 시스템에 기 억 장소를 되돌려 줌으로써 주기억 장치를 효율적으로 운영할 수 있다.

8-8. 구문 분석기의 작성 기본구성 파싱 테이블과 파싱 테이블을 참조하여 구문분석을 수행하는 실행 루틴으로 구성 파싱 테이블은 2차원 배열로 행은 terminal 심벌과 nonterminal 심벌이며, 열은 상태 번호가 된다. 구문 분석기의 행동은 행과 열이 만나는 곳에 정의되는데 shift되는 상태는 양의 정수 값으로, reduce 되는 생성 규칙 번호는 음의 정수 값으로 나타낸다. 그리고 accept는 최대 번호보다 큰 생성 규칙으로 reduce될 때 이며, error는 0으로 표시된다.