컴파일러 설계-구문 분석 유형

구문 분석기는 문맥없는 문법으로 정의 된 생산 규칙을 ​​따릅니다. 생산 규칙이 구현 (파생)되는 방식은 파싱을 하향식 파싱과 상향식 파싱의 두 가지 유형으로 나눕니다.

하향식 구문 분석

파서가 시작 기호에서 구문 분석 트리를 구성하기 시작한 다음 시작 기호를 입력으로 변환하려고 할 때이를 하향식 구문 분석이라고합니다.

• Recursive descent parsing: 하향식 구문 분석의 일반적인 형태입니다. 재귀 프로 시저를 사용하여 입력을 처리하므로 재귀라고합니다. 재귀 적 하강 파싱은 역 추적을 겪습니다.

• Backtracking: 하나의 생산물 파생이 실패하면 구문 분석기가 동일한 생산의 다른 규칙을 사용하여 프로세스를 다시 시작 함을 의미합니다. 이 기술은 올바른 생산을 결정하기 위해 입력 문자열을 두 번 이상 처리 할 수 ​​있습니다.

상향식 파싱

이름에서 알 수 있듯이 상향식 구문 분석은 입력 기호로 시작하여 시작 기호까지 구문 분석 트리를 구성하려고합니다.

Example:

입력 문자열 : a + b * c

생산 규칙 :

S → E
E → E + T
E → E * T
E → T
T → id

상향식 파싱을 시작하겠습니다.

a + b * c

입력을 읽고 생산이 입력과 일치하는지 확인하십시오.

a + b * c
T + b * c
E + b * c
E + T * c
E * c
E * T
E
S