[컴파일러 개론] LL 문법

앞서 Follow 와 First를 배운 이유 CFG가 임의의 생성 규칙에 대하여 만족해야할 조건을 이해함 

 

LL문법이란..

 

위의 조건에 의하면 CFG는 다음과 같이 나올 수 없다.

1. 모호성 2. left-factoring 3. left-recursive

 

모호성 해결방법(복습)

같은 언어를 생성하는 다른 문법을 사용함 

--연산자 우선주기 --결합법칙 사용

Left Factoring : 공통 앞부분

Left-Recursion: 좌측결합식이면 "무적권" 생김 

어떤식을 First구하든 똑같은것이 나올때..

1을 반복 ->컴퓨터에선 무한루프가 생김

 이 LR로 인한 무한루프를 어떻게 해결할것인가?  - > Right Recursion으로 해결하자! 아자아자! 화이팅!

 

직접 LR제거 방법 

nonterminal뒤에 무한반복되는것보단 앞에 무한반복되는 방향으로 가자 두과자

파란색의 변환과정을 기억해둘것

간접 LR팁 일정한 규칙 순서로 nonterminal을 순서화 

1번 규칙의 LHS가 두 번쨰 규칙의 RHS로 나온다면 이거 재귀의 가능성이 매우큼  바꿔줘야함 

ex

보는것과 같이 두번째 규칙에 1번쨰 lhs있음 이럼 안돼

 

 

2. LL파서 구현하기 

 

LL파서를 구현하기 위해선 두가지 방법이 있다.

1. Recursive descent parser 

- recursion 이용

-각 non-terminal 마다 한 개의 procedure를 둠 

-장점: 직관적, 쉽다 -단점: 생성규칙이 바뀌면 구문 분석기를 고쳐야함 

 

2. Predictive parser...

아직 배우진 않았지만.. 

-이론적으로 PDA(push down automata)에 기반 

-생성 규칙이 바뀌더라도 구문 분석기는 고치지 않음 

*단지 구문 분석기의 행동을 나타내는 파싱 테이블만 수정

 

Recursive Descent Parser 에 관하여 

 

모든 terminal 심볼 a에 대한 파서 코드가 존재

모든 non-terminal 심볼 A에 대한 파서 코드 존재

 

 

LL(1) 파서 구현 방법  2번째 - Predictive parser

전에 정규표현과 유한상태오토마타로는 못나타내는 범위들까지 구현 가능 

 

-테이블로 파싱하기 !

1.LL(1)은 lookahead 에 따라 적용할 생성규칙이 unique하게 결정되므로 주어진 문자열에 대해 기계적으로 파싱할 수 있다. 

파싱 테이블 만드는 방법 

테이블의 모호성에 대해서 

파싱테이블 한 cell에 두 개 이상의 생성규칙이 들어갈 수 있을 때 -> 이것은 LL(1)이 아니여~~~~~~~~

 

마지막으로 기계적인 파서 구조 

기계적 파서의 테이블을 이용한 처리 과정