제 4 장 구문 분석.

Slides:



Advertisements
Similar presentations
취업정보 알리미 (job.inha.ac.kr) 취업정보 홈페이지 (job.inha.ac.kr) 취업진로지원팀 페이스북 안내 ※ 종합인력개발센터 취업진로지원팀 페이스북에서 취업추천 및 취업관련 프로그램 등 취업 정보를 실시간으로 받아보세요 ! ★ 페이스북 검색창에서 검색★
Advertisements

열왕기 상하는 중요하다 ! 왜 ? 시가 3 권 예언서 12 원 열왕기 상하는 중요하다 ! 대라느스 단겔학슥말.
3 학년 문제가 남느냐, 내가 남느냐 1. ( 아씨방 일곱 동무 ) 아씨의 방에는 바느질을 위한 친구가 몇 명이 있었나요 ? 정답은 ? 일곱.
 수학 10- 나  1 학년 2 학기  Ⅰ. 도형의 방정식 1. 평면좌표 (1/24) 두 점 사이의 거리 수업 계획 수업 활동.
아름다운 지역공동체를 만들어가는.  목적 본관은 풍부한 인적, 물적 자원을 동원하여 소외계층에게 보호서비스의 제공, 자립능력 배양을 위한 교육훈련, 가족기능강화, 나아가 주민상호간 연대감조성 등 전문적, 종합적 사회복지서비스를 제공함으로써 소외계층과 지역주민이 더 불어.
실시간 개인방송 서비스 아프리카. 서비스 개요 방송놀이 신대륙 afreeca 실시간 멀티미디어 개인방송을 지원하는 신 개념의 개인미디어 어원 afreeca : a free casting ■ 실감나는 방송을 누구나 자유롭게 즐길 수 있습니다 ■ 아프리카의 거친, 미지의,
제 5 강 근대수학의 여명 무리수 (Irrational number) 인도, 아라비아 (0 과 음수 ) 데카르트 - 해석기하학.
C-aC-bA-bB-aB-bB-cA-aA-c A. Head Section. A-b B-a B-b B-c C A-a A-c Top page.
생활 속의 확률과 진실성 하안북중 1학년 서동조.
2014전망&쟁점.
언어와 문법 (languages, grammar)
지적기초측량 경일대학교/부동산지적학과.
(2) 고대 국가의 성립  1) 고대 국가의 성격    ① 중앙 집권 체제      - 국왕의 지위 강화, 부족장 세력의 통합,
프로젝트 학습 중간 보고서 군포초등학교부설 지역공동 영재학급 용호초등학교5학년 이창민.
1. 비정규노동이란 2. 비정규노동의 확대 원인 3. 비정규노동자의 삶 4. 비정규노동의 문제
컴파일러 입문 제 5 장 Context-Free 문법.
변비 재활전문센터 재활 간호사 김은화.
2015 담당 강사 : 정세진 중국 명문 감상 2015 담당 강사 : 정세진
Compiler Lecture Note, Inroduction to FL theory
Compiler Lecture Note, Inroduction to FL theory
해시 함수.
우리나라 수출농업의 현황과 문제점 김자경.
암 보다 더 무서운 당뇨 2010년 [아시아경제 강경훈 기자 ].
Q & A (사실상 혼인·이혼) Q. 사실상 혼인·이혼 관계를 어떻게 처리해야 하나요?   사실 혼인·이혼은 부부 모두 동의 여부를 확인하고, 자녀, 이·통·반장으로부터 「사실(이)혼 확인서」를 징구해야 합니다. 만약 어느 한쪽이 동의하지 않는 경우는.
전산회계1급 기출 50회 신성대학교 세무부동산과 김상진.
4장 구문(Syntax).
2. 형식언어 (Formal Language)
문법과 언어.
3장 (2) 구문과 의미론 순천향대학교 컴퓨터공학과 하상호.
오일석, C와 ALPS, 장. 논리적으로 생각하기 © 오일석, 전북대학교 컴퓨터공학.
형식언어와 유한상태기계.
수학 I 2. 방정식과 부등식.
DS020 오토마타형식언어 Chapter 6. Simplification of Context-Free Grammars and Normal Forms Exercises October 16, 2003.
제 5장. Context-Free Languages
관능검사 기법.
인류의 분산 언어의 대 혼잡시기 창조,타락 홍수 바벨탑사건 아브라함 모세 BC 고조선 하/은/주 (창 11:7,9) 『[7] 자, 우리가.
에너지 운동량 방법: 일과 에너지법칙 1. 상자들이 초기속도 vo로 컨베이어 벨트로 운반되어 A에서 미끄러져서 B에서 떨어진다. μk= 0.40이고, 상자가 2.4m/s로 B점에서 떨어질 때 컨베이어 벨트의 속도를 구하라.
도덕 1학년 1학기 2. 개성신장과 인격 도야:인물학습 석가모니 인물학습 -석가모니.
주요 내용 형식 언어와 문법 정규식과 정규 집합 유한 상태 기계 정규 문법과 유한 상태 기계와 정규집합.
제 11장 교락법과 일부실시법.
작업장에서 불의의사고로 절단사고가 발생했다면
1.고객맞이 상황 응대자세 화법 중점사항 매장 밖 에 서 도보 고객 고객 방향 쪽으로 바른 자세를 취한다
이재상 기본 논리회로와 불의 대수 이재상
2. 형식언어 (Formal Language)
제주닷컴 매뉴얼 (실시간 예약시스템) 2013년 10월.
우리생활속의 확률 이용사례탐구 한림초등학교영재학급 6학년 김수민.
7. LL 구문 분석 7-1. 결정적 구문 분석 7-2. Recursive-descent 파서 7-3. Predictive 파서 7-4. Predictive 파싱 테이블의 구성 7-5. Strong LL(k) 문법과 LL(k)문법.
서울 2008: 재정분석결과.
김포 한강베네치아 상가분양 3층~5층 오피스텔 226세대 1층~2층 상가 분양문의 : 이효철( )
학습 주제 p 역학적 에너지는 보존될까?(2).
Ⅶ. 원 의 성 질 1. 원 과 직 선 2. 원 주 각 3. 원 과 비 례.
우리는 부모를 닮지만, 왜 똑같지는 않을까? 유전적 다양성 독립 연관과 교차 무작위 수정.
도구를 사용할 때의 일(2) 도구를 사용해도 마찬가지야. 지레 지레를 사용할 때의 일.
쿰란 쿰란 와디 항공촬영 .
3. 정규 언어(Regular Language)
인천공항 스카이 허브라운지 상세페이지  배송비 부분에서 B2B, B2C 두가지 버전이 필요하며,
평 면 도 형 도형의 작도 삼각형의 작도와 결정조건 도형의 합동 작도와 삼각형의 합동 학습내용을 로 선택하세요
마음의 성전이 더 아름다운 조촌교회.
기술가정 1학년 4. 제도의 기초 > 1) 물체를 나타내는 방법 ( / ) 평 면 도 법 수업계획 수업활동.
1.비 사업용(자가용 및 관용) 차 종 적 용 상 의 구 분 승합 자동차 (버스) 1 종
Chapter 5. Context-Free Language Exercises
2. 기초 집단유전학 천안연암대학 주종철 본 교재는 故 정흥교수의 강의 교재를 기반으로 일부 편집하여 작성한 것입니다.
제 6 장  상향식 파싱.
(생각열기) 횡파와 종파를 구분하는 기준은 무엇인가?? 답 : 진동하는 방법의 차이
진리 나무 Truth-tree  ∧ ∨ → ↔  =.
잘 살기 생산물류팀.
엔화 대환/대출 자금용도 대상 이자 차액 효과 (A,B,C) 환율 리스크 헷징 (A,B) 엔화의 평균환율 (A,B,C)
2012년 9월 16일 바벨탑 사건과 셈의 후손들의 족보 ▣말씀:창세기 11:1-32 예 수 복 된 교 회.
논증의 타당성/부당성 검증 Verification/Falsification
표준화 이론 표준형 구조나무 표준화 정리  ∧ ∨ → ↔  =.
Presentation transcript:

제 4 장 구문 분석

4.1 구문 분석 개념 그림 4.1 구문 분석기의 위치와 기능 어휘 분석기 구문 중간 코드 심볼 테이블 원시프로그램 토큰 파스트리 중간 코드 심볼 테이블 그림 4.1 구문 분석기의 위치와 기능

유도과정과 파스 트리 파스트리는 프로그램의 각 문장이 문법에서 만들어지는 언어인지를 검사하는 유도 과정이다. 이러한 유도 과정을 파스 트리라 한다. 문장 구조가 올바른지 아닌지를 알기 위해 입력 토큰 스트림과 문법을 비교한다.

신택스 트리와 중간코드 구문 분석에 의하여 생성되는 것은 중간 코드의 신택스 트리 중간 코드는 기계어 인스트럭션을 만들 수 있는 가장 작은 동작으로 컴퓨터의 주소로 되어 있는 피연산자를 포함한다. = x + * y 1.873 - 78 a 그림 4.2  x = (a - 78) * 1.873 + y; 의 신택스 트리

4.2 문법과 언어 컴파일러의 구문 분석 단계를 이해하기 위하여 형식 언어의 이론과 개념을 살펴보자!

4.2.1 문법 정의 4.1 문법(G)은 알파벳, 입력 심볼, 터미널 심볼 문자의 유한 집합에 대하여, G = (VN, VT, P, S)와 같이 구성한다. 여기에서 각 구성요소는 아래와 같다. VN 은 넌터미널 심볼의 유한 집합이다. VT 은 터미널 심볼의 유한 집합으로 VN ∩VT =∅, VN∪VT = V 이다. V 는 알파벳 집합이다. P 는 생성규칙의 유한 집합으로 아래의 형식을 가지는데 α 는 널이 아니다. α →β (α ∈V+, β∈V* ) S 는 시작 심볼이나 문장 심볼로서 S ∈VN 이다.

예 4.1 문법 G1 = ({S, T}, {t, r}, P, S)을 살펴보자. 이 문법의 각 원소는 아래와 같다.              4. 생성 규칙 P : S →tTS                                     S →t                                T →SrT                                     T →rt                                    T →SS

유도 정의 4.2 유도는 생성규칙에서 문장을 생성하는 과정으로 시작 심볼에서 생성규칙의 정의 기호(→)의 오른쪽에 있는 심볼들로 대치한다. S는 시작 넌터미널, α,β,γ는 터미널이나 넌터미널 스트링, x는 터미널 스트링이면 유도(⇒)는 아래와 같이 쓴다.             S ⇒ α ⇒ β ⇒ γ ⇒ .... ⇒ x

예 아래의 문법이 있으면 스트링 baaa을 S ⇒ Sa ⇒ Saa ⇒ Saaa ⇒ baaa와 같이 유도한다. P : S → S a       S → b       S → ε 스트링 baaa을 S ⇒ Sa ⇒ Saa ⇒ Saaa ⇒ baaa와 같이 유도한다.

정의 4.3 언어는 시작 넌터미널 심볼 S로 시작하는 문법 G 에서 ⇒+를 적용하여 문법 G에서 생성되어지는 언어  L(G)로 표기한다. 언어 L(G)안에 있는 스트링은 아래와 같이 G의 터미널 심볼만으로 구성된다.                L(G)  = {ω| S ⇒+ω, ω∈VT*}

예 4. 2 문법 G2 = ({S}, {t}, P, S)을 살펴보자 예 4.2 문법 G2 = ({S}, {t}, P, S)을 살펴보자. 이 문법의 생성 규칙이 P : S →tS |t이면 유도에 의하여 아래의 언어가 생성될 수 있다.     S ⇒t                     t ∈L(G2)     S ⇒tS ⇒tt          tt∈L(G2)     S ⇒tS⇒ttS⇒ttt       ttt∈L(G2)                        ......

예 4.3 문법 G3 = ({S}, {0,1}, P, S) 이고, 생성 규칙이 아래와 같을 때 이 문법에서 언어를 유도해 보자.      P : S → 0S0 | 1S1 | 0 | 1 이 문법에서 한 언어를 유도하면 아래와 같다.        S ⇒ 0S0 ⇒ 00S00 ⇒ 001S100 ⇒ 0010100

문장과 문장형식 정의 4.4 S ⇒* α이고 α ∈V * 이면 α를 문법 G 의 문장형식이라 하고, S ⇒* α이고 α ∈VT* 이면 α는 문법 G 의 문장이라 한다.

예 4.4 문법 G4 = ({S, A, B}, {0, 1, ε}, P, S) 이고, 생성 규칙이 아래와 같을 때 문장 0110를 유도하는 과정에서 문장 형식을 알아보자.        P : S →0A|1B|ε             A →1S             B →0S

이 문법에서 0110를 유도하는 과정은 아래와 같다.           S ⇒0A (생성규칙 S →0A)              ⇒01S        (생성규칙 A →1S)              ⇒011B      (생성규칙 S →1B)              ⇒0110S    (생성규칙 B →0S)              ⇒0110      (생성규칙 S →ε) 유도 과정에서 생성되는 S, 0A, 01S, 011B, 0110S는 문장형식이고, 터미널 스트링만으로 구성된 0110 은 문장이다.

실습 4. 1 생성 규칙이 아래와 같은 문법 G5 = ({S}, {0,1}, P, S)가 있다               P : S → 0S0 S → 1S1 S → 0 S → 1

예 4.5 아래 생성 규칙이 있는 문법 G6 = ({S, A, B}, {a, b, ε}, P, S)에서 문장 aabb를 유도해 보자.        P : S →ASB S →ε             A →a             B →b

이 문법은 문장 aabb를 유도할 수 있다. S ⇒ ASB (생성규칙 S →ASB)              ⇒ AASBB    (생성규칙 S →ASB)              ⇒ AaSBB    (생성규칙 A →a)              ⇒ AaBb     (생성규칙 S →ε)              ⇒ Aabb      (생성규칙 B →b)                 ⇒ aabb      (생성규칙 A →a)

실습 4.2 문법 G = ({S, A, B}, {1,0}, P, S) 이고, 생성 규칙이 아래와 같을 때 이 문법에서 생성할 수 있는 여러 개의 유도과정을 보이시오. P : S → 1SA|BA    A → 10    B → 0A 어떤 스트링을 생성하는데 두 개 이상 여러 개의 유도가 있을 수 있다는 것을 알 수 있다.

4.2.2 문법의 분류 무제한 문법 문맥-민감 문법 문맥-자유 문법 우-선형 문법 그림 4.3 문법의 분류 무제한 문법

촘스키의 문법 분류 타입 0 문법: 무제한 문법은 타입 0 문법이라고도 하며 생성규칙에 제한이 없는 문법이다. 각 생성규칙은 화살표 → 의 양쪽(왼쪽과 오른쪽)에 임의의 터미널과 넌터미널 스트링으로 구성된다. 단 ε 는 화살표의 오른쪽에만 올 수 있다.                         AaB → bA|ε

타입 1 문법: 문맥-민감 문법은 타입 1 문법이라고도 하며 아래와 같은 생성규칙으로 구성된다 타입 1 문법: 문맥-민감 문법은 타입 1 문법이라고도 하며 아래와 같은 생성규칙으로 구성된다. 문맥-민감 문법은 컴파일러에서 실제로는 사용할 수 없다. |α|≤|β|로 β의 길이가 α의 길이보다 더 길다.                           α → β             1.   A → aABCc             2.   A → ε             3.   aB → ab             4.   bB → bb 5.   cB → cb             6.   bC → ac             7.   C → Cc

교재를 수정해야함 A → aABCc 를 A → aABC 로 문맥-민감 문법에서 생성한 언어의 예 A ⇒ aABC ⇒ aaABCBC ⇒ aaBCBC ⇒ aabCBC ⇒ aabCcBC ⇒ aabCcbC ⇒ aabCccbC ⇒ aabCccbCc ⇒ aaacccbCc ⇒ aaacccacc

타입 2 문법: 문맥-자유 문법은 타입 2 문법이라고도 하며, 문맥에 제한되지 않고 자유롭기 때문에 아래와 같은 생성규칙으로 구성된다.                       A → α, |A|=1, |A|≤| α | 생성한 언어 예     S →aAS                       S →a                       A →SbA                       A →ba                       A →SS

타입 3 문법: 우-선형 문법은 타입 3 문법이라고도 하며 아래와 같은 생성규칙으로 구성된다.               A → aB  또는 A → a

실습 4.3 아래의 문법 생성 규칙에서 촘스키의 분류에 따라 무제한, 문맥-민감, 문맥-자유, 우-선형 문법을 고르시오. 1.   aSb → aAbBc         2.   A → bB         3.   Ab → b         4.   b → AB         5.   S → aAbc         6.   AB → BAC

실습 4. 4 어떤 언어 L(G) = {ε, abc, aabbcc, aaabbbccc, 실습 4.4 어떤 언어 L(G) = {ε, abc, aabbcc, aaabbbccc, ...} = {anbncn}, n≥0는 a뒤에는 b가, b뒤에는 c가 오지만, a, b, c 각각의 갯 수가 반드시 같은 스트링의 집합이다. 이 언어를 생성하는 문맥-민감 언어를 구성해 보자.

4.2.3 문맥-자유 문법과 표현 문맥-자유 문법은 반복 구조로 프로그래밍 언어의 문장이나 구조 조건 문장을 만드는 아래의 규칙을 정규 수식으로 표현할 수 있는지?? 「S1과 S2이 각각 문장이고 E 가 수식이면 "if (E ) S1  else S2;" 는 문장이다」 제한된 방법으로 표현하기 어려운 언어 구조도 문맥-자유 문법으로는 표현하기 쉽다. 정규 수식으로 이러한 조건 문장을 표현하기는 어렵다.

예 4.6 수식 a + a + a + a + a 와 같이 더하기 연산을 반복하는 문법 G = ({E, OP}, {a, +}, P, E)를 구성해 보자. 이 수식에서 터미널 심볼은 a와 연산자 + 이고 더하기 연산만 반복한다. 그러므로 이 수식을 표현하려면 터미널 심볼 a는 넌터미널 E에서 유도되고, 터미널 심볼 +는 넌터미널 OP에서 생성되도록 아래와 같이 반복하여 유도하도록 한다.     E ⇒E  OP E ⇒*E  OP E  OP E  OP E  OP E ⇒* a + a + a + a + a 다음과 같은 생성 규칙을 구성할 수 있다.       P :  E → E  OP E            E →  a          OP → +

이 생성 규칙에 의하여 아래와 같이 유도할 수 있다. 밑줄 친 넌터미널 심볼이 대치된다.          E ⇒ E  OP E              ⇒ E  OP E  OP E              ⇒ E  OP E   OP E  OP E              ⇒ E  OP E  OP E   OP E  OP E              ⇒ a  OP E  OP E   OP E  OP E              ⇒ a + E  OP E   OP E  OP E              ⇒ a + a  OP E   OP E  OP E              ⇒ a + a + E   OP E  OP E ⇒ a + a + a OP E  OP E              ⇒ a + a + a + E  OP E              ⇒ a + a + a + a OP E              ⇒ a + a + a + a + E              ⇒ a + a + a + a +a

예 4. 7 수식 a + a - a. a / a 와 같이 사칙 연산을 하는 문법 G = ({E, OP}, {a, +, -, 예 4.7 수식 a + a - a * a / a 와 같이 사칙 연산을 하는 문법 G = ({E, OP}, {a, +, -, *, /}, P, E)를 구성해 보자. 이 수식에서 보듯이 터미널 심볼은 a와 연산자 +, -, *, / 이다. E ⇒ E  OP E ⇒*E  OP E  OP E  OP E  OP E ⇒* a + a – a * a / a 다음과 같은 생성 규칙을 구성할 수 있다.      P :  E → E  OP E             E →  a             OP → +             OP → -             OP → *             OP → /

이 생성 규칙에 의하여 아래와 같이 유도할 수 있다. 밑줄 친 넌터미널 심볼이 대치된다.           E ⇒ E  OP E              ⇒ E  OP E  OP E              ⇒ E  OP E   OP E  OP E              ⇒ E  OP E  OP E  OP E  OP E              ⇒ a  OP E  OP E  OP E  OP E              ⇒ a + E  OP E  OP E  OP E              ⇒ a + a  OP E  OP E  OP E ⇒ a + a - E  OP E  OP E              ⇒ a + a - a OP E  OP E              ⇒ a + a - a * E  OP E              ⇒ a + a - a * a OP E              ⇒ a + a - a * a / E              ⇒ a + a - a * a / a

정의 4.6 문맥-자유 문법(CFG:Context-Free Grammar)은 CFG = (VN, VT, P, S)와 같이 구성한다. VT 은 터미널 심볼의 유한 집합으로 VN∩VT =∅, VN ∪VT = V 이다. V 는 알파벳 집합이다. P 는 생성규칙의 유한 집합으로 아래의 형식을 가진다. A→ α, (A∈VN, α ∈V *, |A|=1 이고  |A|≤|α|) S 는 시작 심볼로서 S ∈VN 이다.

예 4. 8 문맥-자유 문법의 정의에 따라 괄호와 음수를 포함하는 산술 연산 수식을 생성하는 문법을 구성해 보자 예 4.8 문맥-자유 문법의 정의에 따라 괄호와 음수를 포함하는 산술 연산 수식을 생성하는 문법을 구성해 보자. 연산에 사용할 연산자 터미널 심볼은 VT  = {a,+,-,*,/,(,)}이며, 넌터미널 심볼은 VN  = {E, OP}이다. 그러므로 문맥-자유 문법 G6 = ({E, OP}, {a,+,-,*,/,(,)}, P, E)의 생성 규칙은 아래와 같다.       P :  E → E  OP E             E →  (E )             E →  -E             E →  a OP →  +             OP →  -             OP →  *             OP →  /

실습 4. 5 문맥-자유 문법 G = ({E, OP}, {a,+,-, 실습 4.5 문맥-자유 문법 G = ({E, OP}, {a,+,-,*,/,(,)}, P, E)에서 아래의 각각을 생성하는 유도 과정을 보이시오.       P :  E → E  OP E |(E )|-E | a             OP →  +|-|*|/ (a) a * a * a (b) a -(-a) - a (c) a + a * a (d) a * a - a (e) a - a / (a +a)

BNF(Backus-Naur Form) <S> ::= a <S> b | ε

4.2.4 유도 트리 문맥-자유 문법 CFG = (VN, VT, P, S) 이고, ω∈VT* 일 때 유도 트리는 다음과 같이 그린다. 각 노드는 알파벳 V(VN∪VT)의 모든 심볼이다. 루트 노드는 시작 심볼 S 이다. N∈VN 이면, N 노드에는 서브 트리가 적어도 하나는 있다. N →N1N2  ... Nn ∈ P 이면,  N 노드를 루트로 하고 N1, N2, ..., Nn를 N 노드의 서브 트리로 한다. 서브트리는 가장 왼쪽부터 N1, N2, ..., Nn 의 순서로 구성한다.

S N1 N2 ... Nn 그림 4.4 유도 트리 구성하기

예 4.9 아래의 문맥-자유 문법 G8 이 있다.            G8 = ({E, OP }, {a,+,-,*,/,(,)}, P, E )        P :  E → E  OP E |(E )|-E | a               OP →  +|-|*|/

E ⇒ E OP E a * E OP E + 그림 4.5 산술수식 a + a * a 의 유도 트리

우단 유도와 좌단유도 아래는 우단 유도 과정이다. 아래는 좌단 유도 과정이다. E ⇒ E  OP E ⇒ E  OP E  OP E ⇒ E  OP E  OP a ⇒ E  OP E  * a ⇒ E  OP a * a ⇒ E  + a * a ⇒ a + a * a 아래는 좌단 유도 과정이다. E ⇒ E  OP E ⇒ E  OP E  OP E ⇒ a OP E  OP E ⇒ a +E  OP E ⇒ a + a  OP E ⇒ a + a * E  ⇒ a + a * a

4.3 문법의 불명확성 이와 같이 문맥-자유 문법에서 어느 스트링에 대하여 여러 개의 유도 트리를 만들 수 있으면 그 문법을 불명확하다고 한다. 예를 들어 그림 4.5의 유도 트리는 수식 a + a * a를 a + (a * a)와 같은 의미로 유도한 트리이다.

4.3.1 불명확한 문법을 명확한 문법으로 재구성하기 아래의 산술 연산 수식에 대한 문법을 살펴보자.   G8 = ({E }, {+, *, (, ), a}, P, E )        P :  E → E +E              E → E * E              E → (E )              E →  a

재구성한 문법 G8' = ({E', T, F }, {+, *, (, ), a}, P', E' ) P' : E' → E' +T               T → T * F               T → F               F → (E' )               F → a

E' T + T * F F a 그림 4.7 스트링 a + a * a 를 재구성한 명확한 문법(G8' )으로 유도한 유도트리

실습 4.6 아래와 같은 G8' 문법에서 유도되는 트리는 오직 하나만 존재한다는 것과 이 문법이 명확한 문법이라는 것을 증명하시오.   G8' = ({E', T, F }, {+, *, (, ), a}, P', E' )        P' :  E' → E' +T               E' → T               T → T * F               T → F               F → (E' )               F → a

실습 4.7 아래 문법 G9에서 스트링 a + a + a를 좌단 유도와 우단 유도 과정을 보이고 각 경우의 유도 트리를 그리시오. 또한 유도 트리에서 연산자 우선순위를 비교하시오. 이때 연산자 결합법칙을 비교한다.     G = ({E }, {+, *, (, ), id}, P, E )        P :  E → E +E              E → E *E              E → (E )              E →  id

실습 4. 8 문법 G9에서 스트링 a + a. a를 유도하는 과정에서 E + E 를 먼저 선택하는 경우와 E 실습 4.8 문법 G9에서 스트링 a + a * a를 유도하는 과정에서 E + E 를 먼저 선택하는 경우와 E * E 를 먼저 선택하는 경우의 유도 트리를 그리시오. 그리고 연산자 우선순위를 비교하시오.     G9 = ({E }, {+, *, (, ), id}, P, E )        P :  E → E +E              E → E * E              E → (E )              E →  id

4.3.2 불명확한 if 문 구조 연산 수식에 대한 문법 뿐 만 아니라, 조건 문장에서도 불명확성을 발견할 수 있다.    G10 = ({Stmt, Ifstmt, CondEp, Compstmt, Assignstmt },{if, else}, P, Stmt )        P :  Stmt → Compstmt              Stmt → Assignstmt                   Stmt → Ifstmt              Ifstmt → if CondEp Stmt              Ifstmt → if CondEp Stmt  else Stmt

if E1 S1 else if E2 S2 else S3 의 유도 트리 Stmt if CondEp else E1 S1 E2 S2 S3 그림 4.10 문법 G10에서 유도한 조건문 if E1  S1 else if E2   S2 else S3 의 유도 트리

그림 4.11 조건문 if E1 if E2 S1 else S2 에 대한 두 개의 유도 트리 stmt if CondEp else E2 S1 S2 E1 stmt if CondEp else S2 S1 E1 E2 그림 4.11 조건문 if E1  if E2   S1 else S2 에 대한 두 개의 유도 트리

변환된 if 문의 문법  G9 = ({Stmt, Ifstmt, CondEp, Matched_Stmt, Unmatched_Stmt}, {if, else}, P, Stmt )      P :  Stmt → Ifstmt            Ifstmt → Matched_Stmt            Ifstmt → Unmatched_Stmt            Matched_Stmt → if CondEp Matched_Stmt else Matched_Stmt            Matched_Stmt → OtherStmt            Unmatched_Stmt → if CondEp  Ifstmt            Unmatched_Stmt → if CondEp  Matched_Stmt else Unmatched_Stmt

그림 4.12 블명확성을 제거한 if 문의 유도트리 Stmt Ifstmt Unmatched_Stmt if CondEp Stmt if CondEp Matched_stmt else Mached_Stmt OtherStmt OtherStmt 그림 4.12 블명확성을 제거한 if 문의 유도트리

4.4 푸쉬다운 기계와 번역기 푸쉬다운 기계는 문맥-자유 문법을 인식한다.

4.4.1 푸쉬다운 기계 정의 4.7 입력 심볼 T에 대한 푸쉬다운 기계(M)는 M=(S, T, z , q, s0, Q, F)와 같이 7 개의 요소로 구성되는 시스템이다. 여기에서 각 요소는 아래와 같다. S: 상태의 유한 집합(빈상태는 없음) T: 입력되는 알파벳의 유한 집합 z: 스택 알파벳의 유한 집합 q: 현재의 상태에서 입력된 새 알파벳에 따라 다른 상태로 전이하는 상태 전이 함수, S×(T∪{λ})×z →S×z*의 부분집합 Q ∈z : 스택의 시작 심볼 s0: 시작 상태로, s0∈S F : 수락 상태의 유한 집합으로, F⊆S

# 푸쉬다운 기계 구성과 전이함수 테이블 X2 X1 ai ai+1 … an ↲ 푸쉬다운기계 읽기헤드 입력 스트링 전이함수 (테이블) ai ai+1 … an ↲ # X1 X2 읽기헤드 s (상태) 입력 심볼 a1 a2 ... an ↲ 스택 심볼 X 내용 # 그림 4.13 스택을 사용하는 푸쉬다운 기계 구성과 전이함수 테이블

그림 4.14는 아래 문법의 푸시다운 기계의 동작을 테이블로 나타낸 예이다.                   S → ASB                   S → ε                   A → a                   B → b s1 a b ↲ X s1, 푸시(X) s2, 팝 거부 # 수락 s2 a b ↲ X 거부 s2, 팝 # 수락 그림 4.14 푸쉬다운 기계의 상태전이 테이블 예

그림 4.14의 상태 전이 테이블을 이용하여 입력 스트링 aabb을 인식 ____________________________________________     스택              입력                     액션                 (#               aabb↲)               (s1, 푸시(X))       (#X              abb↲)               (s1, 푸시(X))       (#XX             bb↲)                (s2, 팝)       (#X              b↲)                (s12, 팝)      (#                ↲)               (수락)           

실습 4. 9 수식에서는 왼쪽 괄호의 수와 오른쪽 괄호의 수가 같도록 한다. 즉, (a-b-c). ((d/4 s1 ( ) ↲ X s1, 푸시(X) s1, 팝 거부 # 수락

4.4.2 언어의 등급과 인식 기계 문 법 언 어 인식기 무제한 문법(타입 0) 반복 나열 집합 튜링 기계  언 어  인식기 무제한 문법(타입 0) 반복 나열 집합 튜링 기계 문맥-민감 문법(타입 1) 문맥-민감 언어 선형 기계 문맥-자유 문법(타입 2) 문맥-자유 언어 푸쉬다운 기계 정규 문법(타입 3) 정규 언어 유한 상태 기계

제 4 장 끝