flex詞法分析器

flex詞法分析器

flex詞法分析器是替代lex的免費開源軟體。它是一個生成詞法分析器(也稱為“掃瞄器”或“詞法分析器”)的電腦程式。它經常在BSD派生的作業系統上與Berkeley Yacc解析器生成器一起用作lex實現(因為lex和yacc都是POSIX的一部分),或者與GNU bison(一個版本的 yacc)在* BSD連線埠[8]和Linux發行版中。 與Bison不同,flex不是GNU項目的一部分,也不是根據GNU通用公共許可證發布的。

基本介紹

  • 中文名:flex詞法分析器
  • 外文名:fast lexical analyzer generator
  • 提出時間:1987
  • 作者:Vern Paxson
  • 本質:是一個生成詞法分析器
歷史,實例,內部,相關問題,時間複雜度,重入,非Unix環境下的使用,使用其他語言的flex,Flex++,

歷史

Vern Paxson於1987年以C語言寫作了flex。他引用了Jef Poskanzer為Ratfor寫作的詞法分析器。

實例

這是用於指令程式語言PL / 0的Flex掃描器的示例。
識別的標記是:'+',' - ','*','/','=','(',')',',',';','。',':=', '<','<=','<>','>','> ='; 數字:0-9 {0-9};
標識符:a-zA-Z {a-zA-Z0-9}
關鍵字:begin,call,const,do,end,if,odd,procedure,then,var,while。
%{#include "y.tab.h"%} digit         [0-9]letter        [a-zA-Z] %%"+"                  { return PLUS;       }"-"                  { return MINUS;      }"*"                  { return TIMES;      }"/"                  { return SLASH;      }"("                  { return LPAREN;     }")"                  { return RPAREN;     }";"                  { return SEMICOLON;  }","                  { return COMMA;      }"."                  { return PERIOD;     }":="                 { return BECOMES;    }"="                  { return EQL;        }"<>"                 { return NEQ;        }"<"                  { return LSS;        }">"                  { return GTR;        }"<="                 { return LEQ;        }">="                 { return GEQ;        }"begin"              { return BEGINSYM;   }"call"               { return CALLSYM;    }"const"              { return CONSTSYM;   }"do"                 { return DOSYM;      }"end"                { return ENDSYM;     }"if"                 { return IFSYM;      }"odd"                { return ODDSYM;     }"procedure"          { return PROCSYM;    }"then"               { return THENSYM;    }"var"                { return VARSYM;     }"while"              { return WHILESYM;   }{letter}({letter}|{digit})* {                       yylval.id = strdup(yytext);                       return IDENT;      }{digit}+             { yylval.num = atoi(yytext);                       return NUMBER;     }[ \t\n\r]            /* skip whitespace */.                    { printf("Unknown character [%c]\n",yytext[0]);                       return UNKNOWN;    }%% int yywrap(void){return 1;}

內部

這些程式通過使用確定性有限自動機(DFA)執行字元解析和標記化。 DFA是接受常規語言的理論機器。 這些機器是圖靈機系列的一部分。 DFA相當於唯讀右移圖靈機。 語法基於正則表達式的使用。 另見非確定性有限自動機。

相關問題

時間複雜度

Flex詞法分析器通常在輸入的長度上具有時間複雜度{\ displaystyle O(n)} O(n)。也就是說,它對每個輸入符號執行恆定數量的操作。此常量非常低:GCC為DFA匹配循環生成12條指令。[需要引用]請注意,常量與令牌的長度,正則表達式的長度和DFA的大小無關。
但是,在具有匹配極長令牌的掃瞄器中使用REJECT宏可能會導致Flex生成具有非線性性能的掃瞄器。此功能是可選的。在這種情況下,程式設計師已明確告訴Flex在已經匹配某些輸入之後“返回並重試”。這將導致DFA回溯以找到其他接受狀態。默認情況下不啟用REJECT功能,並且由於其性能影響,在Flex手冊中不鼓勵使用它。[11]

重入

默認情況下,Flex生成的掃描程式不可重入。對於從不同執行緒使用生成的掃描程式的程式,這可能會導致嚴重問題。為了解決這個問題,Flex提供了一些選項以實現重入。有關這些選項的詳細說明,請參閱Flex手冊。[12]

非Unix環境下的使用

通常,生成的掃描程式包含對Unix特定的unistd.h頭檔案的引用。為避免生成包含unistd.h的代碼,應使用%option nounistd。另一個問題是調用isatty(一個Unix庫函式),它可以在生成的代碼中找到。 %選項從不互動強制flex生成不使用isatty的代碼。

使用其他語言的flex

Flex只能為C和C ++生成代碼。要使用flex從其他語言生成的掃描程式代碼,可以使用SWIG等語言綁定工具。

Flex++

flex ++是一個類似於C ++的詞法掃描程式,它作為flex包的一部分包含在內。 生成的代碼不依賴於任何運行時或外部庫,除了記憶體分配器(malloc或用戶提供的替代),除非輸入也依賴於它。 這在傳統作業系統或C運行時設施可能不可用的嵌入式和類似情況下非常有用。
flex ++生成的C ++掃描程式包含頭檔案FlexLexer.h,它定義了兩個C ++生成的類的接口。

相關詞條

熱門詞條

聯絡我們