컴파일러 원리 - 귀속 하강 분석기

컴파일링 원리 - 간단한 귀속 하강 문법 분석기 LL(1)

인터넷에서 귀속 하강 분석기에 관한 많은 블로그를 보았지만 모두 만족스럽지 못했다. 첫째, 쓴 프로그램이 틀렸고, 둘째, 해석이 분명하지 않았다.그래서 자기가 한 편 쓰는 김에 배운 것을 총결해 보려고 합니다.

역귀하강 분석법

귀속하강분석법의 원리는 함수 간의 귀속조를 이용하여 문법 트리의 위에서 아래로의 구축 과정을 모의하는 것이다.뿌리 노드에서 출발하여 입력 열에서 가장 왼쪽 일치하는 서열을 찾아 문법 트리를 만듭니다.왼쪽 귀속과 모든 비종결자를 포함하지 않는 모든 후보 종결 첫 번째 문자 집합이 서로 교차하지 않는 조건에서 우리는 거슬러 올라가지 않는 자정향하의 분석 프로그램을 구성할 수 있다. 이 분석 프로그램은 하나의 귀속 과정(또는 함수)으로 구성되고 모든 과정(또는 함수)은 문법에 대응하는 비종결부호가 아니다.

지식을 준비하다

문법의 모든 비종결자에 대해Fisrt 집합,Follow 집합,Select 집합을 계산합니다.책의 정의는 정말 이해하기 어려울 것 같다. 다음은 정의와 수학 기호를 붙이지 않고 블로거 개인의 이해만 붙인다.
4

First 세트 계산 1.끝 문자의 First 집합은 그 자체입니다.2. 종결부 A가 아니면 종결부로 시작하는 열을 내놓을 수 있다면 이 종결부는Fisrt(A)에 속한다.만약 A가 빈 문자열을 유도할 수 있다면ε,그렇게εFirst에 속함(A);3. A->B... 생성식이고 B는 비종결부호이며First(B)에서 빈 문자열을 제거합니다εFirst(A)4. A가 비종결부일 경우;B1, B2,..., Bi도 비종결부호이고 생성식 A->B1 B2...Bn이 있다.B1, B2... Bn-1도 유도할 수 있어요.εFirst(B1), FIRST(B2),..., First(Bn-1)의 모든 비공식 요소와 First(Bn)가 First(A)에 포함됩니다.5. 4에서 B1, B2... Bn을 모두 밀어낼 수 있음εFirst(B1), FIRST(B2),..., First(Bn)의 모든 비어 있지 않은 요소가 First(A)에 포함되고εFirst 에 속합니다 (A)

4

Follow 집합 Follow 집합을 계산하는 것은 말 그대로 문법 기호 뒤에 따라갈 수 있는 종결부호의 집합(공렬 포함하지 않음)이다.ε).Follow 세트는 시비 종결자를 대상으로 합니다.1. 먼저 S를 문법에서 시작하는 기호로 설정하고 {#}을Follow(S)에 넣는다.2. 만약에 A->αBβ First(β)의 비어 있지 않은 요소가 Follow(B)에 포함됩니다.하면, 만약, 만약...β유도할 수 있다εFollow (A) 도 Follow (B) 에 넣어서 유추합니다

4

계산 Select 집합은 상하문에 문법과 무관한 생성식 A->α,A는 종결부가 아닙니다.α유도할 수 없다ε,그러면 Select(A->α)=First(α); 하면, 만약, 만약...α유도할 수 있다ε,Select(A->α)=(First(α) –{ε})∪Follow(A).

예제

문법G: E->TE'E'->+E|ε T->FT’ T’->T|ε F->PF’ F’->*F’|ε P->(E)|a|b|v 계산된 Select 집합: Select(E->TE') = {(,a,b,v}Select(E'->+E) = {(,+}Select(E'->ε) = {(,#} Select(T->FT’) = {(,a,b,v} Select(T’->T) = {(,a,b,v} Select(T’->ε) = {+,),#} Select(F->PF’) = {(,a,b,v} Select(F’->*F’) = {*} Select(F’->ε) = {(,a,b,v,),+,#} Select(P->(E)) = {(} Select(P->a) = {a} Select(P->b) = {b} Select(P->v) = {v}

프로그램 구현

4

모든 비종결부호는 하나의 함수(서브프로세스)에 대응한다

4

비종결부호에 대응하는 오른쪽 생성식은 함수체이다

4

종결자를 만날 때마다 입력한 문자가 일치하는지 판단해야 한다. 일치하면 다음 문자를 읽고 일치하지 않으면 오류 처리를 한다

C 언어 코드

#include
#include
#include

#define LEN 100

char str[LEN];
int i;
bool flag=true;

void E();
void E1();
void T();
void T1();
void F();
void F1();
void P();

int main(){
    int m;
    printf(" :");
    scanf("%d",&m);
    while(m--){
        printf(" ( # ):");
        scanf("%s",&str);
        i=0;
        E();
        if(flag==true){
            printf("%s !
",str);
        }else{
            printf("%s !
",str);
        }
        strcpy(str,"");
    }
} 

void E(){
    if(flag){
        if(str[i]=='('||str[i]=='a'||str[i]=='b'||str[i]=='v'){
            T();
            E1();
        }else{
            flag=false;
        }
    }
}

void E1(){
    if(flag){
        if(str[i]=='+'){
            i++;
            E();
        }else if(str[i]!='#'&&str[i]!=')'){
            flag=false;
        }
    }
}

void T(){
    if(flag){
        if(str[i]=='('||str[i]=='a'||str[i]=='b'||str[i]=='v'){
            F();
            T1();
        }else{
            flag=false;
        }
    }
}

void T1(){
    if(flag){
        if(str[i]=='('||str[i]=='a'||str[i]=='b'||str[i]=='v'){
            T();
        }else if(str[i]!='+'&&str[i]!=')'&& str[i]!='#'){
            flag = false;
        }
    }
}

void F(){
    if(flag){ 
        if(str[i]=='('||str[i]=='a'||str[i]=='b'||str[i]=='v'){
            P();
            F1();
        }else{
            flag=false;
        }
    }   
}

void F1(){
    if(flag){
        if(str[i]=='*'){
            i++;
            F1();
        }else if(str[i]!='('&&str[i]!='a'&&str[i]!='b'&&str[i]!='v'&&str[i]!='+'&&str[i]!=')'&&str[i]!='#'){
            flag = false;
        }
    }
}

void P(){
    if(flag){
        if(str[i]=='('){
            i++;
            E();
            if(str[i]==')'){
                i++;
            }
        }else if(str[i]=='a'){
            i++;
        }else if(str[i]=='b'){
            i++;
        }else if(str[i]=='v'){
            i++;
        }else{
            flag=false;
        }
    }
}