귀속 하강 문법 분석기 실현 과정

어법 분석기에 비해 문법 분석기를 구성하는 방법은 매우 많은데 그 중에서 손으로 쓰기에 가장 간단한 것은 자연히 귀속적으로 떨어지는 방법이다.

문법

언어의 분석기를 실현하려면 먼저 이런 언어의 상하문은 문법과 무관하다(Context-free grammer)를 써야 한다. 나는 언어의 문법을 다음과 같이 선택한다.

P -> S $

S -> S ; S
S -> id = EXP
S -> print ( EXPS )

EXPS -> EXP
EXPS -> EXPS , EXP

EXP -> int
EXP -> id
EXP -> EXP OP EXP
EXP -> ( EXP )

OP -> +
OP -> -
OP -> *
OP -> /

여기서 대문자 단어는 비종결자를 나타내고, 소문자와 기호는 종결자를 나타낸다.

문법을 처리하다

귀속 하강 분석기의 구조 방법은 매우 간단하다. 간단하게 말하면 모든 비종결자를 위해 귀속 함수를 쓴다. 함수에서 이 종결자가 변환될 수 있는 모든 상황에 대한 첫 번째 token을 판단하고 대응하는 처리를 한다. 예를 들어 S의 함수 형식은 다음과 같다. (주의해야 할 것은 이 함수가 틀린 것이다. 단지 형식을 표현하기 위해서이다. 다음은 설명할 것이다.)

void S(){
  switch(current_token){
    case S: 
      S(); eat(';'); S(); break;
    case id: 
      eat(id); eat('='); EXP(); break;
    case print:
      eat(print); eat('('); EXPS(); eat(')'); break;
    default:
      error_exit();
  }
}

쉬워 보이죠?그러나 위의 함수는 문제가 있습니다. 함수는caseS의 상황만 실행하고 무한덕을 귀속합니다. 이를 좌귀속이라고 합니다.이것은 우리 방법의 문제가 아니라 문법 양식의 문제이다. 귀속 하강 방법은 왼쪽 귀속과 왼쪽 인자가 없는 문법만 처리할 수 있기 때문에 우리는 그것을 없애야 한다.

왼쪽 반복 제거

유사하다

E -> E + T
E -> T

의 문법은 왼쪽으로 귀속된다. 우리는 새로운 비종결자를 도입하여 그것을 없앨 수 있다. 결과는 다음과 같다.

E -> T E'
E' -> + T
E' ->

위에서 보여준 것은 하나의 틀이 아니라 사상이다. 우리의 문법에서 비종결자 EXP, S에서도 왼쪽 귀속의 상황이 나타났다. 그러나 훨씬 복잡하다. 왼쪽 귀속의 사상을 없애고 해결해야 한다는 것을 이해해야 한다.

왼쪽 계수 추출

문법 중의 EXPS를 고려하면, 우리는 그 전환의 첫 번째 기호에 근거하여 다음에 무엇을 해야 할지 판단할 수 없다는 것을 발견하였다.종결자가 아닌 다른 변환의 앞의 몇 개의 기호가 같은 기호일 때, 이런 경우에도 왼쪽 귀속과 유사한 문제가 발생할 수 있으니, 우리는 왼쪽 인자를 추출하는 방법을 통해 그것을 없애야 한다.유사하다

S -> E + E
S -> E

의 문법은 문제가 있습니다. 여전히 새로운 비종결자를 도입하는 것입니다.

S -> E S'
S' -> + E
S' ->

최종 문법

EXP와 S의 왼쪽 귀속을 제거하고 EXPS의 왼쪽 인자를 추출한 후 다음 문법을 사용합니다.

P -> S $

S -> id = EXP S'
S -> print ( EXP S ) S'
S' -> ; S
S' -> 

EXPS -> EXP EXPS'
EXPS' -> , EXPS
EXPS' ->

EXP -> ( EXP )
EXP -> int EXP' 
EXP -> id EXP'
EXP' -> OP EXP
EXP' ->

OP -> +
OP -> -
OP -> *
OP -> /

구성 분석기

이제 우리는 언어에서 결과로 우리의 코드를 구성합시다.

문법 분석 (myrdp.l)

우선, 우리는 문자열 형식의 언어를 token 문자열로 전환해야 한다. 이 단계에서 우리는 어법 분석기가 필요하다. 나는flex를 사용하여 이 작업을 완성했다. 분석 과정에서 모든 token의 유형과 값을 저장하고 저장 유형의 구체적인 정의는 아래의 myrdp를 참조한다.h 파일 코드, 코드는 다음과 같습니다.

%{
#include "myrdp.h"
#include 
#include 
#include 
using namespace myrdp;
%}

%%
;       tokens.push_back(Token(SEMICOLON));
=       tokens.push_back(Token(ASSIGN));
\(      tokens.push_back(Token(LPAREN));
\)      tokens.push_back(Token(RPAREN));
,       tokens.push_back(Token(COMMA));
\+      tokens.push_back(Token(PLUS));
-       tokens.push_back(Token(MINUS));
\*      tokens.push_back(Token(TIMES));
\/      tokens.push_back(Token(DIV));
print   tokens.push_back(Token(PRINT));
[0-9]+  tokens.push_back(Token(INT,atoi(yytext)));
[a-zA-Z]+[a-zA-Z0-9]* {
  tokens.push_back(Token(ID,std::string(yytext)));
}
[ \t
] ;
.       std::cout<

문법 분석(myrdp.h myrdp.cpp)

현재 우리는 Token을 저장한vector를 얻었다. 우리는 위에서 말한 구축 방법에 따라 처음부터 끝까지 귀속적인 방식으로vector를 한 번 훑어보면 결과를 얻을 수 있다. 코드는 간단하니 코드를 직접 보자.프로그램의 입구 구조, 즉main 함수에 쓰인 부분

yyin = fopen(argv[1],"r");
yylex();
prog();

관건적인 구조의 정의와 함수 설명은 myrdp를 보십시오.h
myrdp.h

#pragma once

#include 
#include 
#include 

구체적인 함수와 변수의 정의
myrdp.cpp

#include 
#include 
#include 
#include