《編譯原理第六章上機輔導(dǎo).ppt》由會員分享，可在線閱讀，更多相關(guān)《編譯原理第六章上機輔導(dǎo).ppt（52頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、1,編譯原理上機內(nèi)容,上機目的 題目與要求 參考解決方案 數(shù)據(jù)庫存儲結(jié)構(gòu) CREATE TABLE詞法語法分析 SELECT詞法語法分析,2,1 上機目的,通過做上機題加深對編譯原理和數(shù)據(jù)庫管理系統(tǒng)的理解，鞏固所學(xué)知識。 學(xué)會使用LEX// 類別 char char_var; char *yych; int yyint; ...... ; 4. SQL語言中記號的分類：關(guān)鍵字、標示符、數(shù)字、其它符號。,20,3.2 詞法分析器,SQL語句中的記號： 例 CREATE TABLE Student ( Sno CHAR(9), Sname CHAR(20), Ssex CHAR(2), S

2、age INT ); 上邊的SQL語句包括哪些記號？ 關(guān)鍵字：CREATE TABLE CHARINT 標示符：Student Sno Sname Ssex Sage 數(shù)字： 9，20，2 其他符號： ( ) , ; ,,LEX源程序基本結(jié)構(gòu)如下： 聲明 %% 翻譯規(guī)則 %% 用戶定義子程序,21,22,3.2 詞法分析器,用正則式識別記號 CREATE TABLE對應(yīng)的LEX源程序: CREATEreturn CREATE; TABLEreturn TABLE; CHARreturn CHAR; INTreturn INT; A-Za-zA-Za-z0-9_*yylval

3、.yych=(char *)malloc(strlen(yytext)+1); strcpy(yylval.yych,yytext); return IDENTIFIER;,23,3.2 詞法分析器,0-9+yylval.yych=(char *)malloc(strlen(yytext)+1); strcpy(yylval.yych,yytext); return NUMBER; ;| (| )| ,return yytext0; 經(jīng)過詞法分析，CREATE TABLE語句被識別為： CREATE TABLE IDENTIFIER1 (IDENTIFIER2 CHAR(NUMBER), ID

4、ENTIFIER3 CHAR(NUMBER), IDENTIFIER4 CHAR(NUMBER), IDENTIFIER5 INT);,24,3.3 語法分析器,語法分析器的任務(wù)：分析語言的結(jié)構(gòu) 為句子構(gòu)造語法樹； 檢查輸入序列中的錯誤。 主要工作： 設(shè)計SQL語言的文法； 設(shè)計語法樹的節(jié)點，用于存放表達式的語法樹； 利用YACC工具分析SQL語句，并構(gòu)造語句的語法樹； 設(shè)計測試程序和測試用例，檢驗分析器是否正確。,25,3.3 語法分析器,1. 設(shè)計CREATE TABLE語言的文法 statement createsql | selectsql | ...... createsql

5、 CREATE TABLE table ( fieldsdefinition ) ; table IDENTIFIER fieldsdefinition field_type | fieldsdefinition , field_type field_type field type field IDENTIFIER type CHAR ( NUMBER ) | INT,26,3.3 語法分析器,2. 設(shè)計CREATE TABLE語法樹的節(jié)點 typedef struct_createstruct/*create語法樹根節(jié)點*/ char*table; _createfieldsdef_ty

6、pe*fdef; _createstruct_type; typedef struct _createfieldsdef/*create語句中的字段定義*/ char*field; enum TYPE type; intlength; struct _createfieldsdef *next_fdef; _createfieldsdef_type; enum Type INT,CHAR;/*字段類型*/,27,YACC源程序基本結(jié)構(gòu)如下： 聲明 %% 翻譯規(guī)則 %% 用戶定義子程序 我們來看一個具體例子：,28,3.3 語法分析器,CREATE TABLE對應(yīng)的yacc源程序： %

7、 _createfieldsdef_type*cfdef_end; % %union/*定義yylval的格式*/ charchar_var; char*yych; intyyint; /*屬于create語法樹的類型*/ _createfieldsdef_type*cfdef_var; _createstruct_type*cs_var; ,29,3.3 語法分析器,%start statement %tokenCREATE TABLE CHAR INT %typeIDENTIFIERNUMBER %typetablefield %typetype %typefieldsdefinitio

8、nfield_type %typecreatesql %% --聲明部分,30,3.3 語法分析器,statement:selectsql |createsql create_table($1); | ......; createsql: CREATE TABLE table ( fieldsdefinition ) ; $$=(_createstruct_type *)malloc( sizeof(_createstruct_type)); $$-table=$3; $$-fdef=$5; ;,31,3.3 語法分析器,table

9、:IDENTIFIER $$=$1; ; fieldsdefinition:field_type $$=$1; cfdef_end=$1; |fieldsdefinition , field_type $$=$1; cfdef_end-next_fdef=$3; cfdef_end=$3; ;,32,3.3 語法分析器,field_type:field type $$=(_createfieldsdef_type *)malloc( sizeof(_createfieldsdef_type)); $$-field=$1; if (strlen($2)==0) /

10、*表示類型為int的時候，用INT表示類型，長度定為4*/ $$-type=INT; $$-length=4; $$-next_fdef=NULL; ,33,3.3 語法分析器,else/*類型為CHAR：用CHAR表示類型，長度定為$2*/ $$-type=CHAR; $$-length=atoi($2); $$-next_fdef=NULL; ; field:IDENTIFIER $$=$1; ; type:CHAR ( NUMBER ) $$=$3; |INT $$=0;;,34,3.4 SELECT 語句的實現(xiàn),詞法分析部分： SELECTreturn SELECT; FROMret

11、urn FROM; WHEREreturn WHERE; ANDreturn AND; ORreturn OR; ;| (| )| ,| | .| =| return yytext0;,35,3.4 SELECT 語句的實現(xiàn),1.設(shè)計SELECT語言文法 select 語句文法： statementselectsql| ...... selectsqlSELECT fields_star FROM tables ; | SELECT fields_star FROM tables WHERE conditions ; fields_startable_fields | * tablest

12、able | tables , table table_fieldstable_field | table_fields , table_field table_fieldfield | table . field table IDENTIFIER field IDENTIFIER,36,3.4 SELECT 語句的實現(xiàn),設(shè)計語法樹的節(jié)點，用于存放表達式的語法樹； typedefstruct_selectedfields/*select語句中選中的字段*/ char *table; char *field; struct _selectedfields*next_sf; _selectedfi

13、elds_type; typedef struct_selectedtables/*select語句中選中的表*/ char*table; struct_selectedtables*next_st; _selectedtables_type; typedef struct_selectstruct/*select語法樹的根節(jié)點*/ _selectedfields_type *sf; _selectedtables_type*st; _conditions_type*cons; _selectstruct_type;,37,3.4 SELECT 語句的實現(xiàn),typedef struct_con

14、ditions struct _conditions*left; struct _conditions*right; char comp_op;/*(a--and),(o--or), , = */ char type;/*2--是表的字段，1--是字符串型，0--是整型*/ char *table;/*不為NULL就存放表名*/ char *value;/*存放字段名，字符串或整數(shù)的值，要看type的值*/ intintval;/*用于以后計算的時候存儲結(jié)果*/ _conditions_type;,38,3.4 SELECT 語句的實現(xiàn),下邊是語法分析部分需要用到的中間變量 /*select語

15、句中選中的字段*/ _selectedfields_type*sf_var1,*sf_end; /*select語句中選中的表*/ _selectedtables_type*st_var1,*st_end;,39,3.4 SELECT 語句的實現(xiàn),%union/*定義yylval的格式*/ char char_var; char *yych; int yyint; /*屬于select語法樹的類型*/ _selectedfields_type*sf_var; _selectedtables_type*st_var; _selectstruct_type*ss_var; ,40,3.4 SELE

16、CT 語句的實現(xiàn),%token SELECTFROMWHERE %token IDENTIFIERNUMBER %typeselectsql %typefields_startable_fieldstable_field %typetables %typetablefield %left OR %leftAND %typeconditioncomp_leftcomp_right %typetable_field_conditions %typecomp_op,41,3.4 SELECT 語句的實現(xiàn),selectsql:SELECT fields_star FROM tables; $$=(_s

17、electstruct_type *)malloc(sizeof(_selectstruct_type)); $$-sf=$2; $$-st=$4; $$-cons=NULL; printf(SELECTSQLn); |SELECT fields_star FROM tables WHERE conditions ; $$=(_selectstruct_type *)malloc(sizeof(_selectstruct_type)); $$-sf=$2; $$-st=$4; $$-cons=$6;;,42,3.4 SELECT 語句的實現(xiàn),fields_star:table_fields/*

18、如果輸入了具體的字段名稱*/ $$=$1; printf(fields_starn); |*/*如果輸入了星號*/ $$=(_selectedfields_type *)malloc(sizeof(_selectedfields_type)); $$-table=NULL; $$-field=*; $$-next_sf=NULL; printf(fields_starn); ;,43,3.4 SELECT 語句的實現(xiàn),tables:table/*第一個表*/ $$=(_selectedtables_type *)malloc(sizeof(_selectedtables_type)); $$-

19、table=$1; $$-next_st=NULL; st_end=$$; printf(tables %s n,$1); |tables , table/*后面的表*/ $$=$1; st_var1=(_selectedtables_type *)malloc(sizeof(_selectedtables_type)); st_var1-table=$3; st_var1-next_st=NULL; st_end-next_st=st_var1;/*建立表名的連接*/ st_end=st_var1; printf(tablesn);;,44,3.4 SELECT 語句的實現(xiàn),table_fi

20、elds:table_field $$=$1; sf_end=$$;/*第一個字段名稱*/ printf(table_fieldsn); |table_fields , table_field/*后面的字段*/ $$=$1; sf_end-next_sf=$3;/*建立字段名的連接*/ sf_end=$3; printf(table_fieldsn); ;,45,3.4 SELECT 語句的實現(xiàn),table_field:field $$=(_selectedfields_type *)malloc(sizeof(_selectedfields_type)); $$-table=(char *)

21、malloc(sizeof(10));/*為以后填上表名預(yù)留空間*/ $$-table0=0; $$-field=$1; $$-next_sf=NULL; printf(table_field: %sn,$1); |table . field $$=(_selectedfields_type *)malloc(sizeof(_selectedfields_type));$$-table=$1; $$-field=$3; $$-next_sf=NULL; printf(table_fieldn);;,46,3.4 SELECT 語句的實現(xiàn),conditions:condition(文法還有問題，

22、原子條件必須加括號？) $$=$1; |( conditions ) AND ( conditions ) $$=(_conditions_type *)malloc(sizeof(_conditions_type)); $$-left=$2; $$-right=$6; $$-comp_op=a; |( conditions ) OR ( conditions ) $$=(_conditions_type *)malloc(sizeof(_conditions_type)); $$-left=$2; $$-right=$6; $$-comp_op=o;;,47,3.4 SELECT 語句的實現(xiàn)

23、,condition:comp_left comp_op comp_right $$=(_conditions_type *)malloc(sizeof(_conditions_type)); $$-left=$1; $$-comp_op=$2; $$-right=$3;; comp_left:table_field_ $$=$1; $$-comp_op=0; $$-type=2; $$-left=NULL; $$-right=NULL; ;,48,3.4 SELECT 語句的實現(xiàn),comp_right:table_field_ $$=$1; $$-comp_op=0; $$-type=2;

24、$$-left=NULL; $$-right=NULL; | IDENTIFIER $$=(_conditions_type *)malloc(sizeof(_conditions_type)); $$-left=NULL; $$-right=NULL; $$-comp_op=0; $$-type=1; $$-value=$2;,49,3.4 SELECT 語句的實現(xiàn),| NUMBER $$=(_conditions_type *)malloc(sizeof(_conditions_type)); $$-left=NULL; $$-right=NULL; $$-comp_op=0; $$-ty

25、pe=1; $$-value=$2; |NUMBER $$=(_conditions_type *)malloc(sizeof(_conditions_type)); $$-left=NULL; $$-right=NULL; $$-type=0; $$-value=$1; $$-intval=atoi($1);;,50,3.4 SELECT 語句的實現(xiàn),table_field_:field $$=(_conditions_type *)malloc(sizeof(_conditions_type)); $$-table=(char *)malloc(sizeof(10));/*為以后填上表名預(yù)

26、留空間*/ $$-table0=0; $$-value=$1; |table . field $$=(_conditions_type *)malloc(sizeof(_conditions_type)); $$-table=$1; $$-value=$3; ;,51,3.4 SELECT 語句的實現(xiàn),comp_op: $$=; |= $$==; ;,備注：,1.數(shù)據(jù)庫管理系統(tǒng)的重點在于物理結(jié)構(gòu)的設(shè)計。良好的物理結(jié)構(gòu)可以使數(shù)據(jù)存儲、查詢和刪除容易進行。 2.使用lex和yacc工具實現(xiàn)詞法和語法分析，可以去網(wǎng)上下載lex和yacc工具。此處建議使用集成的工具Parser Generator。注意配置Parser Generator和VC++。具體配置見word文檔。 3.若只進行詞法和語法分析，不用設(shè)計數(shù)據(jù)庫的物理結(jié)構(gòu)；若要實現(xiàn)DBMS的功能，則要設(shè)計物理結(jié)構(gòu)。 4.推薦書籍：數(shù)據(jù)庫系統(tǒng)實現(xiàn)，MySQL技術(shù)內(nèi)幕：Innodb存儲引擎，教材。,52,