데이터베이스 만 들 기: SQL 명령 해석 기 구현 (1)

데이터베이스 작업 이 ddl 에 도착 합 니 다.데이터베이스 의 두 개의 최상 위 모듈 인 시스템 관리 모듈 과 명령 해석 모듈 을 실현 하기 위해 서 는 먼저 SQL 문장의 명령 해석 기 가 필요 합 니 다.명령 해석 기 모듈 은 Lex + Yacc 를 사용 합 니 다.사실 이 두 도 구 는 컴 파일 원리 수업 의 PA 에서 이미 사용 되 었 지만 PA 에 서 는 프레임 워 크 를 주 었 습 니 다. 프레임 워 크 의 모양 에 따라 수정 하고 베 끼 기만 하면 됩 니 다. 데이터 뱅 크 의 명령 해석 기 는 처음부터 써 야 합 니 다.다행히 SQL 의 문법 은 컴 파일 원리 PA 의 문법 보다 훨씬 간단 하 다.
Lex, Yacc 및 Memphis 와 함께 인 터 프 리터 작성 하기
이 글 은 Lex, Yacc, Memphis 로 이 루어 진 목표 언어 에 대한 해석 기 를 제공 합 니 다.목표 언어 예 는 다음 과 같다.

x := 8;
y := 12;
WHILE x != y DO
   IF x > y THEN x := x-y
   ELSE y := y-x
   FI
OD;
PRINT x

우 리 는 다음 두 단계 로 문법 해석 기 를 완성 할 것 이다.

Task 1 (the analizer) 소스 코드 읽 기 및 코드 구조 분석

Task 2 (the tree walker) 처리 코드

The Analizer
이 부분 에서 우 리 는 두 단계 로 나 누 어 코드 구 조 를 분석 하 는 임 무 를 완성 할 것 이다. 그것 이 바로 품사 분석 과 문법 분석 이다.
품사 분석 Lex
품사 분석 은 목표 텍스트 를 token, 빈 칸, 빈 줄, 주석 으로 구 성 된 서열 로 분해 합 니 다.예 를 들 어 대상 텍스트 가

x:=   // multiply x
x*100 // by hundred

그러면 이 는 token x, :=, x, *, 100 로 구 성 된 서열 로 분 해 될 것 이다.모든 token 은 하나의 클래스 에 속 합 니 다. 예 를 들 어 := 는 클래스 ASSIGN 에 속 하고 100 은 클래스 Number 에 속 합 니 다.Number 와 같은 클래스 에 대해 서 는 정규 표현 식 [0-9]+ 을 사용 하여 표시 할 수 있 습 니 다.어법 분석 은 yylex() 함 수 를 통 해 이 루어 진다.yylex() 먼저 목표 문자열 에서 다음 token 을 읽 은 다음 에 이 token 이 어떤 종류 에 속 하 는 지 되 돌려 주 고 이 token 의 의미 값 을 전역 변수 yylval 에 전달 합 니 다.이 절 차 를 완성 하기 위해 서, 우 리 는 lex 에 다음 문장 을 입력 해 야 한다. 그리고 lex 는 이 문장 에 따라 상기 yylex() 과정 을 자동 으로 생 성 할 것 이다.

 regular-expression {action}

예 를 들 면

  [0-9]+ { yylval=atoi(yytext); return NUMBER; }

다음 token 이 정규 표현 식 [0-9]+ 과 일치 하면 yylval 이 token 이 표시 하 는 숫자 이 고 이 token 의 유형 은 NUMBER 입 니 다.완전한 lex 입력 코드 는 다음 과 같 습 니 다:

 %{
   #include "y.tab.h"
   extern int yylval;
   %}
   %%
   "="      { return EQ; }
   "!="     { return NE; }
   ""      { return GT; }
   ">="     { return GE; }
   "+"      { return PLUS; }
   "-"      { return MINUS; }
   "*"      { return MULT; }
   "/"      { return DIVIDE; }
   ")"      { return RPAREN; }
   "("      { return LPAREN; }
   ":="     { return ASSIGN; }
   ";"      { return SEMICOLON; }
   "IF"     { return IF; }
   "THEN"   { return THEN; }
   "ELSE"   { return ELSE; }
   "FI"     { return FI; }
   "WHILE"  { return WHILE; }
   "DO"     { return DO; }
   "OD"     { return OD; }
   "PRINT"  { return PRINT; }
   [0-9]+   { yylval = atoi(yytext); return NUMBER; }
   [a-z]    { yylval = yytext[0] - 'a'; return NAME; }   
   \        { ; }
   
       { nextline(); }
   \t       { ; }
   "//".*
 { nextline(); }
   .        { yyerror("illegal token"); }
   %%
   #ifndef yywrap
   yywrap() { return 1; }
   #endif

문법 분석
문법 분석 에 서 는 문맥 과 무관 한 문법 으로 문법 구조의 매 칭 을 실현 할 것 이다.이전 단계 에서 우 리 는 모든 token 을 식별 했다. 따라서 이 부분 에서 우 리 는 모든 token 을 그들의 유형 으로 대체 할 수 있다. 예 를 들 어 100 즉 NUMBER 이 고 := 즉 ASSIGN 이 며 x 즉 designator 이 므 로 분석 x:=x*100 은 분석 designator ASSIGN designator MULT NUMBER 이 되 었 다.그 다음 에 우 리 는 문맥 과 무관 한 문법 으로 목표 언어의 문법 규칙 을 정의 할 수 있다.Ycc 에서 코드 세 션 은 다음 과 같 습 니 다:

statement:
   designator ASSIGN expression {$$ = assignment($1, $3);} 
 | PRINT expression {$$ = print($2);} 
 | IF expression THEN stmtseq ELSE stmtseq FI
     {$$ = ifstmt($2, $4, $6);}
 | IF expression THEN stmtseq FI
     {$$ = ifstmt($2, $4, empty());}
 | WHILE expression DO stmtseq OD {$$ = whilestmt($2, $4);}
 ;

The Glue
문법 분석 과 어법 분석 을 다 쓰 고 나 면 우 리 는 문맥 에 관 계 없 이 문법 정의 와 일치 하 는 규칙 을 알 게 될 것 이다.대상 코드 를 입력 한 후 위 에서 정 의 된 규칙 분석 을 통 해 문법 분석 트 리 를 얻어 야 합 니 다.문법 분석 트 리 를 얻 기 위해 서 는 Ycc 의 트 리 규칙 에 추상 적 인 종 류 를 정의 해 야 합 니 다. 예 를 들 어 Ycc 중국어 법의 첫 번 째 규칙 Statement : designator ASSIGN expression {$$ = assignment($1, $3)} 은 assignment 방법 으로 designator 와 expression 의 매개 변 수 를 전달 하여 Statement 노드 를 구성 해 야 합 니 다.이렇게 하면 우 리 는 Statement 유형의 노드 를 얻 은 후에 다른 부분 코드 에서 이 문법 분석 트 리 의 노드 를 사용 할 수 있다.완전한 정 의 는 다음 과 같다.

domain Statement {

      assignment (Expression lhs, Expression rhs)
      print (Expression x)
      ifstmt (Expression cond, Statement thenpart, Statement elsepart)   
      whilestmt (Expression cond, Statement body)
      seq (Statement s1, Statement s2)
      empty ()

 }

domain Expression {

      eq (Expression x, Expression y)
      ne (Expression x, Expression y)
      lt (Expression x, Expression y)
      le (Expression x, Expression y)
      gt (Expression x, Expression y)
      ge (Expression x, Expression y)
      plus (Expression x, Expression y)
      minus (Expression x, Expression y)
      mult (Expression x, Expression y)
      divide (Expression x, Expression y)
      neg (Expression x)
      number (int x)
      name (int location)

}

The Tree Walker
이제 우 리 는 문법 분석 트 리 를 사용 할 수 있다. 원문 에서 두 함수 evaluate(Expression e) 와 execute(Statement) 를 정의 했다. 만약 에 문법 분석 트 리 의 한 노드 가 Expression 유형 이 라면 evaluate 방법 을 호출 하고 표현 식 e 의 값 을 계산한다. 만약 에 분석 트 리 중의 한 노드 의 유형 이 Statement 이 라면 execute 방법 으로 이 문 구 를 집행 한다.이 부분의 코드 는 수요 와 밀접 한 관 계 를 가지 기 때문에 우 리 는 SQL 문법 을 분석 하고 실행 문 에 있 는 목표 언어 를 분석 하 는 것 이 아니 라 데이터 베 이 스 를 실행 하 는 것 을 가 져 와 야 하기 때문에 이 부분 은 여기 서 상세 하 게 설명 하지 않 습 니 다.
다음은 SQL 명령 해석 기 를 만 들 수 있 습 니 다.