skyjump's blog

Left to right scanning, Right parse.
 
파싱테이블 : 스택의 top과 현재의 입력 심벌에 따라 구문 분석 행동을 결정.
LR 파서의 네가지 행동 : Shift, reduce, accept, error
shift: 현재 상태에서 입력 심벌을 본 행동이 shift S이면 입력 심벌을 스택으로 이동하고 다음 상태 S도 스택에 넣는다.
reduce: 현재 상태에서 입력 심벌을 본 행동이 reduce A->α이면 스택에서  α 2배만큼 제거하고 A를 스택에 넣는다. 그리고 A에 대한 다음 상태를 스택에 넣는다.
accept: 주어진 입력이 올바른 스트링이다.

LR 파싱 테이블 만드는 방법 : Simple LR(SLR), Canonical LR(CLR), Lookahead LR(LALR)
SLR
LR(0) 아이템과 FOLLOW 집합을 이용하여 만든다.
LR(0) 아이템은 생성 규칙의 rhs에 .이 있는 생성규칙이다.
점 심벌 다음의 심벌을 mark 심벌이라고 한다.
CLOSURE 함수는 한 상태에서 보아야 되는 모든 LR(0) 아이템을 구하는 것.
마크 심벌이 논터미널일 경우 이 논터미널 생성규칙들을 LR(0) 아이템으로 만들어서 현재 상태에 추가 한다.
GOTO 함수는 한 상태에서 다른 상태로 가기 위해 사용. 
상태 I와 GOTO함수들이 파싱테이블을 구성한다.
CLOSURE로 한 상태를 구하고 그 상태의 GOTO함수를 만든다. GOTO함수의 결과가 이전 상태들하고 일치하는 것이 없을 때 새로운 상태가 된다. 
reduce 아이템에 대하여 그 생성 규칙의 lhs의 follow 심벌을 보고 reduce행동을 한다.  <- SLR의 특징.
한 상태에서 마크 심벌과 reduce 아이템의 follow가 같을 때, shift를 해야 할지, reduce를 해야 할지 결정할 수 없다. shift-reduce충돌
한 상태에서 두개 이상의 reduce 아이템의 follow 심벌이 같다면  어느 것을 reduce해야 할지 결정할 수 없다.  reduce-reduce충돌
문법이 모호하기 때문에 이러한 충돌이 발생한다.

CLR
Lookahead : 한 상태에서 어떤 논터미널 심벌 다음에 나올 수 있는 터미널. 상태 의존적인 follow. Follow가 lookahead를 포함.
reduce 아이템에 대한 reduce행동을 lookahead 심벌에 대해서 만드는 방법이 CLR.
CLOSURE구할 때 lookahead를 구해서 첨가한다. 한 아이템의 마크 심벌 다음에 오는 심벌의 FIRST가 그 심벌의 lookahead가 된다.  
lookahead때문에 파싱 테이블이 커진다. 그래서 lookahead를 이용하지만 테이블 크기는 작게 구성하는 LALR을 많이 사용한다.

LALR
방법1
core(아이템에서 lookahead를 제외한 부분)가 같은 것들끼리 묶는다.
SLR의 상태수랑 같게 된다. shift-reduce충돌은 일어나지 않지만  reduce-reduce충돌은 일어날 수 있다. 왜냐하면 shift는 코어에 따라 결정되는 것이지 lookahead에 의해 결정되는 것이 아니기 때문.
방법2
방법1은 lookahead 때문에 상태수가 많아지고 시간이 오래걸린다.
그래서 SLR에서 follow대신에 lookahead를 계산해서 사용한다.

모호한 문법
모호한 문법은 LR 문법이 될 수 없다.
하지만 연산순위나 결합 법칙 정보를 이용해서 하나의 행동을 선택하도록 함으로써 shift-reduce 충돌이나 reduce-reduce충돌을 해결한다.

 

일반적인 top-down을 사용하면 backtracking이 생길 경우 느리니까, backtracking하지 않도록 결정적인 파싱 방법이 필요. 그러한 파싱 방법을 LL 파싱.

FIRST
논터미널 A로 부터 유도되어 첫번째로 나타날 수 있는 터미널의 집합.

nullable
논터미널 A가 ε를 유도할 수 있으면 A를 nullable하다. 

FOLLOW
생성규칙이 ε을 유도할 수 있으면 FIRST만 가지고는 생성 규칙을 결정적으로 선택할 수 없다.
논터미널 A 다음에 나오는 심벌에 따라 어느 생성 규칙으로 유도할 것인가를 결정한다. 

LL 조건
논터미널을 대치하기 위한 생성 규칙을 결정적으로 선택하기 위한 조건.
한 논터미널에 2개 이상의 생성규칙이 있을 때,
각 생성규칙의 FIRST가 달라야 하고,
한 생성 규칙이 ε을 유도할 수 있으면, 그 생성규칙의 FOLLOW와 다른 생성규칙의 FIRST가 달라야 한다.

LL방법을 실제로 사용하는 구문분석기
1) Recursive-descent
논터미널에 대한 유도를 각 논터미널별로 구현되어 있는 함수 호출로 처리.
논터미널에 적용할 생성 규칙을 정하기 위해 Lookahead를 조사. Lookahead는 각 생성규칙에서 첫번째로 유도될 수 있는 터미널들의 집합.
2) Predictive 파서
Recursive-descent파서는 생성규칙이 바뀔 때마다 프로그램을 다시 고쳐야 하는 단점이 있다.
Predictive파서는 파싱테이블만 수정하면 된다.
스택의 top과 현재 입력 심벌이 같을 경우 pop, 
expand : 스택의 top이 논터미널일 경우 생성규칙으로 바꿔서 역순으로 넣는다.
accept : 스택의 top과 입력이 모두 $인 경우, 파싱 성공
error

구문 분석의 결과는 파스트리.
파스트리 만드는 순서
1) top-down, 2) bottom-up
top-down은 시작 심벌로부터 생성 규칙을 적용하여 좌측 유도해 나가는 방법.
bottom-up은 주어진 스트링으로부터 시작 심벌로 축약되어 가는 과정. 우측 유도에서 적용된 생성 규칙 번호의 역순.

파스트리의 루트노드는 시작 심벌이고, 중간 노드는 비단말 심벌, 단말 노드는 단말 심벌.
top-down 방식은 루드노드부터 만들어 나가고, bottom-up 방식은 단말 노드부터 시작하여 서브트리를 만들어 나간다.

추상구문트리(Abstract Syntax Tree) : 파스 트리에서 꼭 필요한 의미 정보만을 갖는 트리.

Backtracking
top-down 시작 심벌로부터 좌측유도 하다가 생성 규칙이 잘못 적용되었으면 그 생성 규칙에서 보았던 스트링을 다시 입력으로 보내고 다른 생성 규칙을 적용하여 유도를 해본다.

top-down 할 때 left-recursion이 있으면 무한루프에 빠진다.

direct left-recursion 없애기.
A->Aα|β, it means A= βα*
it equals
A-> βA'
A' ->αA'|ε  

indirect left-recursion 없애기
direct left-recursion으로 만든다음 없앤다.
direct left-recursion으로 만드는 알고리즘 :
논터미널에 순서를 매기고
논터미널의 생성규칙에 앞선 논터미널이 있으면 앞선 논터미널의 생성규칙을 대입한다.  

left-factoring
같은 심벌들을 prefix로 갖는 두 개 이상의 생성 규칙이 있으면 어떤 생성 규칙을 적용해야 할지 결정 할 수 없다.
공통된 앞부분을 새로운 논터미날을 이용해서 표현한다.
A->αβ|αγ <=> A->α(β|γ) <=> A->αA', A'->β|γ

bottom-up의 reduce
구문 분석 중에 나타나는 문장 형태의 일부분이 정의된 생성 규칙의 rhs와 같을 때, 이 생성규칙의 lhs로 대체하는 것.
reduce되는 부분을 handle이라고 한다.

shift-reduce 구문 분석
bottom-up의 일종.
스택과 입력 버퍼가 있다. 스택에 handle을 찾을 때까지 문법 심벌들을 유지하고, 입력 버퍼는 주어진 스트링을 가지고 있다.
shift는 입력 심벌을 스택으로 이동하는 것. reduce는 스택 top의 핸들을 생성규칙으로 축약하는 것.
accept는 주어진 스트링이 문법적으로 맞다는 것.

트리생성
파싱하면서 트리 만들 수 있다.
시프트할때 단말 노드를 만들고 reduce할 때 서브트리를 만든다.

정규문법은 제약이 많아 구문 구조를 표현하기 어렵다.

leftmost derivation, rightmost derivation.

derivation tree (유도트리)
context-free grammar는 문장 유도과정을 트리로 표현할 수 있다.

ambiguous
문법이 어떤 문장에 대해 두개 이상의 유도 트리를 가질 때 그 문법이 모호하다라고 한다.

필요없는 생성 규칙 (useless production) 제거
터미널 심벌로 유도 될 수 없는 생성 규칙들은 제거한다.

ε 생성 규칙 제거해야 될 때도 있다.

A->B같은 simple production(단일 생성규칙) 제거.

CNF(Chomsky Normal Form) 촘스키 정규 형태.
모든 context-free grammar는 CNF로 바꿀 수 있다.
CFG를 나타내는데 필요한 표기법을 간소화 하는데 유용하다.

CFG 표기법
BNF(Backus-Naur Form)
EBNF(Extended BNF)
syntax diagram (문법 흐름도) : 언어의 구문 구조를 쉽게 이해할 수 있도록 문법을 도식화.

PDA (Push Down Automata)
유한오토마타에  지나간 입력에 대한 결과를 알 수 있도록 스택을 추가한 것.
입력스트링을 유지하는 입력테이프와 스택, 전체 행동을 제어하는 유한 상태 제어가 있다.
현재상태와 입력과 스택을 보고 다음 상태와 스택에 들어갈 값을 정한다.
 시작상태에서 입력스트링을 다 봤을 때의 상태가 종결 상태(final state)이면 입력스트링은 이 푸시다운 오토마타에 의해 인식(accept)되었다고 말한다. 푸시다운 오토마타 언어는 이 오토마타에 인식되는 스트링의 집합이다.

PDA언어로 CFG를 구성할 수 있고, CFG로 PDA를 구성할 수 있다.

top-down 구문분석방법 : 시작 심벌로부터 아래로 내려가면서 스트링을 만든다.
bottom-up 구문분석방법 : 생성규칙의 rhs(right hand side)가 스택 top 부분에 나타날때까지 shift하다가 rhs가 되면 reduce를 한다.
shift는 입력에 있는 터미널을 스택 top으로 옮기는 것이고 reduce는 스택 top부분에 있는 생성 규칙의 rhs를 lhs로 바꾸는 것이다.

정규언어는 토큰의 형태를 기술하는데 사용.
regular grammar(정규문법), regular expression(정규표현), finite automata(유한 오토마타)에 의해 표현한다.

정규문법 정의
A->aB 또는 A->a. A와 B는 논터미널, a는 터미널.
S ->ε이면 S가 다른 생성규칙의 오른쪽에 나타나지 않는다.
토큰의 구조를 표현하는데 사용. context-free문법으로도 만들 수 있지만 정규문법으로 더 쉽게 구현할 수 있다.
 
정규표현
기본 소자
Φ(공집합), ε(empty string을 나타내는 집합), terminal 심벌.  
union :  (e1)+(e2) 또는 (e1) | (e2)
concatenation : (e1)(e2)
closure : (e1)*

regular expression equation(정규표현식)
계수가 정규표현인 식.
정규문법을 정규표현식으로 나타낼 수 있고, 정규표현을 구할 수 있다.
정규문법과 정규표현은 같은 종류의 언어를 나타낸다.

유한오토마타
입력으로 스트링을 받아서 그 스트링이 그 언어의 문장이면 yes, 아니면 no을 답하는 인식기.
5개의 요소로 정의
유한개의 상태, 입력 심벌, 사상 함수(mapping function), 시작상태, 종결 상태(final state)
사상함수는 어떤 입력 a가 들어왔을 때, 상태 중에 하나를 결과(다음상태가 된다.)로 내보내는 함수. 전이함수라고 한다.

DFA(Deterministic FA)
전이 함수가 한 입력에 대한 다음 상태로 하나의 상태만을 갖는 경우. 

state transition diagram (상태 전이도)
유한 오토마타를 그림으로 나타낸것. 시작상태를 start, 각 상태는 노드,특히 종료 상태는 이중원인 노드. 입력에 대한 상태의 변화는 edges.

NFA (Non deterministic FA)
한 입력을 보고 다음 상태가 하나 이상 있을 수 있는 유한 오토마타.

NFA를 DFA로 바꿀 수 있다. NFA가 언어의 구조르 쉽게 표현할 수 있지만 프로그램으로 만들기는 어렵다. 그래서 DFA로 변환한다.
NFA에서 한 입력으로 갈 수 있는 노드들을 하나로 묶어서 하나의 상태로 본다.

ε-CLOSURE(s)
NFA에서 입력으로 ε을 가질 수 있을 때, 하나의 상태 s가 ε입력으로 갈 수 있는 모든 상태들의 집합.

DFA state minimization ( DFA 상태수 최소화)
종결상태와 종결아닌 상태로 나누고
각 그룹에서 할 일은 그룹에 있는 상태들이 각 입력에 대해 어느 그룹으로 가는지 조사하고 같은 그룹으로  가는 것들끼리 또 나누는 것.

정규문법을 유한 오토마타로 바꿀 수 있고,
유한 오토마타를 정규문법으로 바꿀 수 있다.

유한 오토마타가 인식하는 언어를 정규표현으로 나타낼 수 있다.
먼저 유한 오토마타로 정규문법을 구하고 그걸로 정규 표현을 얻는다.
또는 정규표현으로 유한 오토마타를 구할 수 있다.
정규 표현의 기본 소자(union, concatenation, closure 등)을 NFA로 표현하고, 간단화하고 DFA으로 변환한다.

펌핑 렘마
어떤 언어가 정규 언어가 아님을 증명하는데 사용.