Recursive-descent parsing(재귀적 하강 구문 분석)
Input string을 parsing하기 위해 recursive procedure를 사용한다.
- Nonterminal symbols에 대한 프로시저 및 Terminal symbols에 대한 프로시저를 각각 작성한 다음 이를 통합함으로써 구현한다.
- Terminal symbol에 대한 프로시저는 production rule에 있는 terminal symbol과 input symbol이 같은지 비교하여 같은 경우 다음 input symbol을 읽게 한다.
- Nonterminal symbol에 대한 프로시저는 현재의 input symbol를 생성할 수 있는 적절한 생성 규칙이 선택되도록 작성한다.
먼저 현재의 입력 기호를 보고 시작 기호에 대한 프로시저를 호출한다. 그리고 마지막에는 현재의 입력 기호가 입력의 끝을 나타내는 $이면 accept이고 그렇지 않으면 에러로 처리한다.
장점 : 구문 분석기를 쉽고 빠르게 구성할 수 있다.
단점 :
- 프로시저를 부르는 시간으로 인해 속도가 느리고 구문 분석기의 크기가 큼
- 결정적인 구문 분석이 되지 않아 역추적이 필요할 수 있음
- 생성 규칙이 바뀔 때마다 구문 분석기 전체를 다시 고쳐야 함
Example
1. 터미널 기호에 대한 프로시저
procedure pa;
begin
if nextsymbol = qa then get_nextsymbol
else error
end;
procedure pb;
begin
if nextsymbol = qb then get_nextsymbol
else error
end;
2. 논터미널 기호에 대한 프로시저
procedure PS;
begin
case nextsymbol of
qa : begin pa; PS end;
qb : pb;
otherwise : error
case
end
end;
3. 메인 프로그램에 대한 프로시저
begin
get_nextsymbol;
PS;
if nextsymbol = q$ then accept
else error
end;
3. Terminal & Nonterminal에 대한 프로시저를 통합한다.
procedure PS;
begin
if nextsymbol = qa then
begin get_nextsymbol; PA:
if nextsymbol = qb then get_nextsymbol
else error
end;
else error
end;
procedure PA;
begin
case nextsymbol of
qa : begin get_nextsymbol; PS end;
qb : get_nextsymbol;
otherwise : error
end
end;
begin
get_nextsymbol;
PS;
if nextsymbol = q$ then accept
else error
end;
Predictive Parsing
'3-2 > 기초컴파일러' 카테고리의 다른 글
| CLR parser (0) | 2021.11.07 |
|---|---|
| Bottom-up parsing (0) | 2021.11.06 |
| Syntax Analysis (0) | 2021.10.16 |
| Pushdown Automata (0) | 2021.10.16 |
| Grammar Conversion (0) | 2021.10.09 |