푸시 다운 자동화 및 구문 분석
구문 분석은 문법의 생산 규칙을 사용하여 문자열을 파생하는 데 사용됩니다. 문자열의 허용 여부를 확인하는 데 사용됩니다. 컴파일러는 문자열의 구문이 올바른지 여부를 확인하는 데 사용됩니다. 파서는 입력을 받아 파스 트리를 만듭니다.
파서는 두 가지 유형이 될 수 있습니다.
Top-Down Parser − 하향식 구문 분석은 시작 기호가있는 맨 위에서 시작하여 구문 분석 트리를 사용하여 문자열을 파생합니다.
Bottom-Up Parser − 상향식 구문 분석은 문자열이있는 맨 아래부터 시작하여 구문 분석 트리를 사용하여 시작 기호에 도달합니다.
하향식 파서 설계
하향식 구문 분석의 경우 PDA에는 다음 네 가지 유형의 전환이 있습니다.
스택 맨 위에있는 프로덕션의 왼쪽에있는 비 터미널을 팝하고 오른쪽 스트링을 누릅니다.
스택의 맨 위 기호가 읽고있는 입력 기호와 일치하면 팝하십시오.
시작 기호 'S'를 스택에 밀어 넣습니다.
입력 문자열을 완전히 읽고 스택이 비어 있으면 최종 상태 'F'로 이동합니다.
예
다음 생산 규칙을 사용하여 문법 G에 대한 "x + y * z"표현식에 대한 하향식 파서를 설계합니다.
P : S → S + X | X, X → X * Y | Y, Y → (S) | 신분증
Solution
PDA가 (Q, ∑, S, δ, q 0 , I, F)이면 하향식 파싱은 다음과 같습니다.
(x + y * z, I) ⊢ (x + y * z, SI) ⊢ (x + y * z, S + XI) ⊢ (x + y * z, X + XI)
⊢ (x + y * z, Y + XI) ⊢ (x + y * z, x + XI) ⊢ (+ y * z, + XI) ⊢ (y * z, XI)
⊢ (y * z, X * YI) ⊢ (y * z, y * YI) ⊢ (* z, * YI) ⊢ (z, YI) ⊢ (z, zI) ⊢ (ε, I)
상향식 파서 설계
상향식 구문 분석의 경우 PDA에는 다음 네 가지 유형의 전환이 있습니다.
현재 입력 기호를 스택에 넣습니다.
스택 맨 위에있는 프로덕션의 오른쪽을 왼쪽으로 바꿉니다.
스택 요소의 맨 위가 현재 입력 기호와 일치하면 팝하십시오.
입력 문자열을 완전히 읽고 시작 기호 'S'가 스택에 남아있는 경우에만 해당 문자열을 팝하고 최종 상태 'F'로 이동합니다.
예
다음 생산 규칙을 사용하여 문법 G에 대한 "x + y * z"표현식에 대한 하향식 파서를 설계합니다.
P : S → S + X | X, X → X * Y | Y, Y → (S) | 신분증
Solution
PDA가 (Q, ∑, S, δ, q 0 , I, F)이면 상향식 파싱은 다음과 같습니다.
(x + y * z, I) ⊢ (+ y * z, xI) ⊢ (+ y * z, YI) ⊢ (+ y * z, XI) ⊢ (+ y * z, SI)
⊢ (y * z, + SI) ⊢ (* z, y + SI) ⊢ (* z, Y + SI) ⊢ (* z, X + SI) ⊢ (z, * X + SI)
⊢ (ε, z * X + SI) ⊢ (ε, Y * X + SI) ⊢ (ε, X + SI) ⊢ (ε, SI)