공부/컴파일러2011. 8. 20. 16:42


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

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로 바꾸는 것이다.

'공부 > 컴파일러' 카테고리의 다른 글

LL 구문 분석  (0) 2011.08.22
구문 분석 (syntax analysis)  (0) 2011.08.22
regular language  (0) 2011.08.20
formal language  (0) 2011.08.20
3장 context-free grammars & parsing  (0) 2011.07.27


Posted by skyjumps