컴퓨터과학[3-2]100 컴파일러구성 - [제11강] LALR 구문분석 컴파일러구성 - [제11강] LALR 구문분석 ·CLR 파싱표의 효율화 ·LR(0)에서 LALR파싱표 구성 컴파일러 용어정리 LALR LookAhead LR 방법으로 lookahead 정보를 이용하기 때문에 SLR 방법보다 훨씬 강력하고 파싱표의 크기는 CLR에서 core가 같은 항목들을 한데 묶음으로써 SLR과 같은 크기로 구성할 수 있다. 그러나 LR(0) 항목의 집합을 구한 후 파싱표를 만들기 위해 reduce 항목이 있는 각 상태에서 lookahead 기호를 구하는 데 상당한 시간과 노력이 소요된다.LR(0) 항목 LR(0) 항목은 다음과 같이 3종류로 나누어진다. 1) [A → α․β]에서 α≠ε 인 kernel 항목 2) [A → ․α]와 같은 closure 항목 3) [A → α․]와 같은 .. 2016. 7. 18. 컴파일러구성 - [제10강] CLR 구문분석 컴파일러구성 - [제10강] CLR 구문분석 SLR 충돌문제와 lookahead ·closure와 GOTO 함수 ·CLR 파싱표와 구문분석 컴파일러 용어정리 LR Left to right scanning and Right parseSLR 구문분석 Simple LR 구문분석은 LR 구문분석 방법 중 가장 간단하게 구현될 수 있는 방법이다. SLR 파싱표를 만드는 방법은 LR(0) 항목의 집합과 FOLLOW를 이용한다.CLR 구문분석 Canonical LR 구문분석은 SLR 의 충돌문제를 해결한 구문분석 방법이다. lookahead를 이용하는 방법인데, lookahead를 구해야 하므로 과정이 복잡하고 시간이 오래 걸리며 파싱표가 커진다.LR(1) LR(0)항목에서 lookahead 정보를 첨가한 것. LR.. 2016. 7. 18. 컴파일러구성 - [제9강] LR 구문분석 컴파일러구성 - [제9강] LR 구문분석 증가문법 ·closure와 GOTO 함수 ·SLR 파싱표 와 구문분석 컴파일러 용어정리 LR(k) 문법 모든 엔트리(entry)에 대해, 유일하게 정의되는 파싱표를 만들 수 있는 문법을 말한다. 여기서 k를 lookahead의 길이라고 하며, 이는 handle을 결정하는 데 k개의 입력기호에 이르기까지 조사하는 것LR(0) 항목 생성규칙의 오른쪽에 점기호(dot symbol)를 가진 생성규칙증가문법 G=(VN,VT,P,S)에서 G에 첨가된 문법 즉, 시작기호 {S'→S} 를 하나 더 추가한 문법이다..Closure 마크기호가 [A→ α․Bβ]와 같이 논터미널인 경우에 이 논터미널 B를 생성규칙의 왼쪽으로 갖는 LR(0) 항목을 구하는 것을 closure라고 한다... 2016. 7. 18. 컴파일러구성 - [제8강] 순위관계에 의한 구문분석 컴파일러구성 - [제8강] 순위관계에 의한 구문분석 여러가지 순위분석연산자 순위 구문분석 단순순위 구문분석 컴파일러의 용어정리 연산자 문법 : 연산자 문법은 ε-생성규칙을 갖지 않고, 생성규칙의 오른쪽에 2개 이상의 논터미널이 연속해서 나올 수 없음. 연산자 순위문법 : 연산자 문법이면서 두 개의 터미널 기호 사이에 많아야 한 개의 연산자 순위관계를 갖는 것을 말하고, 이 문법에 의해 정의된 언어를 연산자 순위언어라 함. 단순순위문법 : ε-생성규칙을 갖지 않고, 오른쪽 부분이 같은 생성규칙은 존재하지 않는다. 또한 기호 사이에 많아야 한 개의 Wirth-Weber 순위관계를 가짐. 순위문법의 종류 : 순위문법들에는 연산자 순위문법(operator precedence grammar), 단순 순위문법(si.. 2016. 7. 12. 컴파일러구성 - [제7장] 구문분석 개요 컴파일러구성 - [제7장] 구문분석 개요 bottom-up 구문분석 shift-reduce 구문분석, FIRST 와 FOLLOW 컴파일러 용어정리 핸들(handle) : Bottom-up 구문분석에서 reduce 되는 부분 reduce : 유도과정을 거꾸로 적용한 것. 즉, S ‗⇒ αAw ‗⇒ αβw의 유도과정이 존재할 때, 문장형태 αβw 에서 β를 A로 대체하는 것 Shift : 입력기호를 스택에 넣는 것 단일 생성규칙(single production) FOLLOW(A) ＝ {a ∈ VT ∪ {$} | S ‗⇒ αAaβ, α, β ∈ V＊} 즉, 어떤 문장형태에 있어서, 논터미널 A 다음에 나타나는 터미널 기호들의 집합이다. 여기에서 $기호는 입력 문자열의 끝을 나타내는 기호 FIRST : 문자열 .. 2016. 7. 12. 컴파일러구성 - [제6장] Context-free 문법의 효율화 컴파일러구성 - [제6장] Context-free 문법의 효율화 유도 트리 모호성 Context-free 문법의 효율화 푸시다운 오토마타 컴파일러 용어정리 푸시다운 오토마타 (push-down automata) : context-free 언어를 받아들이는 인식기 유도트리(derivation tree) : 구문분석을 하는 과정에서 문장이 유도되는 과정을 트리형태로 표현하는 것 모호성(ambiguous) : 문법 G에 의해 생성되는 어떤 문장이 두 개 이상의 유도트리를 갖은 경우 단일 생성규칙(single production) : 생성규칙들 중 생성규칙의 오른편이 단 한 개의 논터미널로 구성되어 있는 생성규칙이 존재하는 경우 backtracking : 문장을 유도하다가 일치하지 않아서 다른 문법 규칙을 적용.. 2016. 7. 12. 이전 1 ··· 10 11 12 13 14 15 16 17 다음
