03 聽說你們計科編譯原理要寫一個詞法分析器

來自專欄 goldfish同學4 人贊了文章

COOL語言詞法分析器

一、COOL語言的語法結構

Cool語言是一個面向對象程序設計語言。雖然它很小巧，但仍包含了許多現代語言的特性，如對象、強制類型和自動化內存管理。一個Cool語言程序由一個或多個類組成, 類內部有函數和屬性,他們之間更詳細的語法規則如下所示:

①、program ::= [[class; ]]+ //程序由一個或多個類組成②、class ::= class TYPE [inherits TYPE] { [[feature;]]? } //類定義(繼承可選)③、feature ::= ID( [ formal [[, formal]]? ] ) : TYPE { expr } //特徵由函數和屬性組成| ID : TYPE [ <- expr ] ④、formal ::= ID : TYPE //參數表一項⑤、expr ::= ID <- expr // 表達式賦值 | expr[@TYPE].ID( [ expr [[, expr]]? ] ) //函數動態調用 | ID( [ expr [[, expr]]? ] ) //函數靜態調用 | if expr then expr else expr fi //if-else | while expr loop expr pool //while | { [[expr; ]]+} //block塊 | let ID : TYPE [ <- expr ] [[,ID : TYPE [ <- expr ]]]? in expr //let表達式 | case expr of [[ID : TYPE => expr; ]]+esac //case分支 | new TYPE //申請新類 | isvoid expr //判斷是否為VOID | expr + expr | expr ? expr | expr ? expr | expr / expr | ?expr | expr < expr | expr <= expr | expr = expr | not expr | (expr) | ID | integer | string | true | false ── 摘自COOL手冊(其中[]、[[]]內部內容為可選部分,[[]]常與正則表達式符號+,*搭配使用)

二、COOL語言的詞法單元

由第一部分總結可知,COOL語言詞法單元只包含INT(整數)、OBJECT_ID(對象標識符)、TYPE_ID(類型標識符) 、SPECIAL_NOTAION(特殊符號) 、STRINGS(字元串) 、COMMENTS(注釋)、KEYWORDS(關鍵字) 和 WHITE_SPACE(空格符號)

2.1 整數

整數是非空的0-9的數字串

正則表達式:[0-9]+

2.2 標識符

標識符是字母開頭的,由字母、數字和下劃線組成的非空串,注意他不能是關鍵保留字

其中類型標識符有大寫字母開頭,

正則表達式:[A-Z][_0-9A-Za-z]*

對象標識符由小寫字母開頭

正則表達式:[a-z][_0-9A-Za-z]*

2.3 字元串

字元串由一對雙引號和引號內部任意多字元組成

字元串識別有些複雜,因為有些字元串不合法,不能匹配不合法的字元串,所以在詞法分析這一階段就要處理字元串的錯誤

字元串的錯誤有:

(1).字元串太長

(2).字元串包含非轉義字元
(
前有一個字元則允許換行)

(3).字元串包含非法結束字元

(4).字元串包含EOF(end of file)標記

字元串要準確識別出這些錯誤場景並報錯,並繼續在新位置繼續詞法分析

詞法分析字元串簡易步驟:

1.識別雙引號,更新一個flag值,表示進入字元串識別狀態,分析下一個字元

2.如果識別到錯誤字元(
||||EOF),則中斷詞法分析,返回一個ERROR錯誤標籤

3.字元串有一個字元個數計數器,當達到限度還未結束字元串則返回字元串長度過長的錯誤

4.[.] 任意字元跳過(計數器正常工作)

5.再次識別到雙引號時,結束,返回一個STRING的標籤,和作為標籤屬性的該字元串

2.4注釋

注釋有兩種類型

一種是行注釋: --......

另一種是跨行注釋: (*......*)

第一種很好處理,在識別到"--" 時直接忽略後面即可

值得注意的是第二種注釋,識別的時候需要考慮嵌套注釋

(* XXX (*

XXX *) XXX *)

不能一遇到右括弧就立刻結束分析注釋

這個時候就需要一個棧裝填(*和*),就可以解決了

或者用一個計數器也行

當然,因為是匹配結構,也需要錯誤分析處理

注釋2錯誤有:

(1).在注釋外遇見"*)"

(2).遇見"*)"前遇見EOF標記

注釋1分析:

(1).遇到"--"就忽略該行,直接跳到下一行

注釋2分析:

(1-1).掃到"(*"時建立flag表示進入注釋2分析,括弧計數器初始化為1,掃描下一個字元

(2).當掃到EOF是,報錯

(3).當再次掃到"(*",括弧計數器加1

(4).忽略其他字元

(5).當掃描到"*)"時如果括弧計數器為1,結束注釋掃描

(6).否則,計數器減1,繼續掃描,直到結束

(1-2).當掃描到"*)" 報錯

2.5 COOL語言關鍵字

classelsefalsefiifininheritsisvoidletlooppoolthenwhilecaseesacnewofnottrue

共19個

注意:關鍵字除了true和flase外其他大小寫不敏感,true和false首字母必須小寫,其他位任意大小寫

當掃描到關鍵字時直接返回屬性為他本身的標籤

2.6空格符號

包括:
、f、
、 和 v

掃描時直接忽略

2.7特殊符號

";"","":""("")""{""}""<-""=>""+""-""*""/""~""=""<""<="

直接返回值為符號本身的標籤

三.FLEX程序設計

FLEX是C++語言的LEX詞法分析生成器,使用它能快速高效生成詞法分析器.

FLEX主要由四部分組成

%{聲明部分%}定義部分%%規則部分%%用戶子程序部分

1.在定義部分主要給一些正則表達式起名,方便規則部分調用

INT [0-9]+TYPEID [A-Z][_a-zA-Z0-9]*OBJECTID [a-z][_a-zA-Z0-9]*SEMICOLON ";"COMMA ","COLON ":"LEFTPARENTHESE "("RIGHTPARENTHESE")"LEFTBRACE "{"RIGHTBRACE "}"INIT "<-"DARROW "=>"ADD "+"MIN "-"MUL "*"DIV "/"FEI "~"ET "="LT "<"LE "<="WHITESPACE [ f
v]CLASS[Cc][Ll][Aa][Ss][Ss]ELSE[Ee][Ll][Ss][Ee]FI [Ff][Ii]IF [Ii][Ff]IN [Ii][Nn]INHERITS[Ii][Nn][Hh][Ee][Rr][Ii][Tt][Ss]ISVOID[Ii][Ss][Vv][Oo][Ii][Dd]LET[Ll][Ee][Tt]LOOP [Ll][Oo][Oo][Pp]POOL[Pp][Oo][Oo][Ll]THEN[Tt][Hh][Ee][Nn]WHILE[Ww][Hh][Ii][Ll][Ee]CASE[Cc][Aa][Ss][Ee]ESAC[Ee][Ss][Aa][Cc]NEW[Nn][Ee][Ww]OF [Oo][Ff]NOT[Nn][Oo][Tt]FALSE[f][Aa][Ll][Ss][Ee]TRUE[t][Rr][Uu][Ee]

2.規則部分是LEX程序的邏輯部分,是整個程序的核心

遵循:

正則表達式 匹配成功後操作

"*)" {yylval.error_msg= "Unmatched *)";returnERROR;}"(*" {BEGIN(COMMENT);}<COMMENT><<EOF>> {yylval.error_msg= "EOF in comment";returnERROR;}<COMMENT>
{curr_lineno++;}<COMMENT>. {}<COMMENT>"(*" {RECUR++;}<COMMENT>"*)" { if(RECUR)RECUR--; elseBEGIN(INITIAL); }--.*
{curr_lineno++;}" {BEGIN(STRING);string_buf_ptr= string_buf; }<STRING>" {BEGIN(INITIAL);if(string_long_check()){ cool_yylval.error_msg = "Stringconstant too long"; ERR = true; return ERROR;}*string_buf_ptr= ;string_buf_ptr++;if(!ERR)cool_yylval.symbol= stringtable.add_string(string_buf);elseERR= false; returnSTR_CONST;}<STRING> {cool_yylval.error_msg= "String contains null character";ERR= true;returnERROR;}<STRING>
{yylval.error_msg= "Unterminated string constant";BEGIN(INITIAL);curr_lineno++;returnERROR;}<STRING>\
{if(string_long_check()){ yylval.error_msg = "String constanttoo long"; ERR = true; return ERROR;}*string_buf_ptr=
;string_buf_ptr++;curr_lineno++;}<STRING>\n {if(string_long_check()){ yylval.error_msg = "String constanttoo long"; ERR = true; return ERROR;}*string_buf_ptr=
; string_buf_ptr++;}<STRING>\b {if(string_long_check()){ yylval.error_msg = "String constanttoo long"; ERR = true; return ERROR;}*string_buf_ptr=;string_buf_ptr++;}<STRING>\t {if(string_long_check()){ cool_yylval.error_msg = "Stringconstant too long"; ERR = true; return ERROR;}*string_buf_ptr= ;string_buf_ptr++;}<STRING>\f {if(string_long_check()){ cool_yylval.error_msg = "Stringconstant too long"; ERR = true; return ERROR;}*string_buf_ptr= f;string_buf_ptr++;}<STRING>\[^nbtf] {if(string_long_check()){ cool_yylval.error_msg = "Stringconstant too long"; ERR = true; return ERROR;}*string_buf_ptr= yytext[1];string_buf_ptr++;}<STRING>. {if(string_long_check()){ cool_yylval.error_msg = "Stringconstant too long"; ERR = true; return ERROR;}*string_buf_ptr= yytext[0];string_buf_ptr++;}<STRING><<EOF>> {cool_yylval.error_msg= "EOF in string control";BEGIN(INITIAL);returnERROR;}{CLASS} {return(CLASS);} {ELSE} {return(ELSE);}{FI} {return(FI);}{IF} {return(IF);}{IN} {return(IN);}{INHERITS} {return(INHERITS);}{ISVOID} {return(ISVOID);}{LET} {return(LET);}{LOOP} {return(LOOP);}{POOL} {return(POOL);}{THEN} {return(THEN);}{WHILE} {return(WHILE);}{CASE} {return(CASE);}{ESAC} {return(ESAC);}{NEW} {return(NEW);}{OF} {return(OF);}{NOT} {return(NOT);}{TRUE} {yylval.boolean= true; return(BOOL_CONST); } {FALSE} {yylval.boolean= false; return(BOOL_CONST); }{DARROW} {return (DARROW); }{INIT} {return (ASSIGN);}{LE} {return (LE);}{SEMICOLON} {return (;);}{COMMA} { return (,);}{COLON} {return (:);}{LEFTPARENTHESE} {return (();}{RIGHTPARENTHESE} {return ());}{LEFTBRACE} {return ({);}{RIGHTBRACE} {return (});}{ADD} {return (+);}{MIN} {return (-);}{MUL} {return (*);}{DIV} {return (/);}{FEI} {return (~);}{ET} {return (=);}{LT} {return (<);}"." {return (.);}"@" {return (@);}{INT} {cool_yylval.symbol= inttable.add_string(yytext); return(INT_CONST);} {TYPEID} {cool_yylval.symbol= idtable.add_string(yytext);return(TYPEID);}{OBJECTID} {cool_yylval.symbol= idtable.add_string(yytext);return(OBJECTID); }
{curr_lineno++;}{WHITESPACE} {} /* remain */. {cool_yylval.error_msg= strdup(yytext);returnERROR;}

3.第四部分是用戶子程序部分,包含第三部分頻繁使用的函數,方便調用

bool string_long_check(){ if(string_buf_ptr - string_buf + 1 > MAX_STR_CONST){ return true;} else return false;}

四.詞法分析器實例操作

Hello_world.cl

class Main inherits IO { main():SELF_TYPE { out_string("HELLO WORLD!!") };};

其實我設計的這個詞法分析器不魯棒:63個測試點拿了55分(orz)

有一個EOF的bug一直沒解決,暫時放著

源代碼待上傳...

推薦閱讀：