說明:
從形式語言的角度看,一個語言不過是字符串集.如果字符串集是有窮的,那么我們就可用枚舉的辦法來表示.但當集合為無窮時枚舉的辦法就不再適用.
文法是表示無窮字符串集的強有力的一種有限辦法.表示文法需要工具,其中最常用的工具是所謂的巴克斯范式(BNF).
這里的文法是用一種類似于巴克斯范式方式給出,但它又不是純粹的巴克斯范式.之所以表示成這種形式是在不影響其清晰性的前提下考慮到實現方便,具體地說這種文法能夠為下面要介紹的工具ACCENT所識別,而且表達比較簡捷.
該文法中大寫的單詞是終極符,小寫的單詞是非終極符,()號加*號表示重復0到多次,()號加號表示重復0到一次,''號中的是單字符終極符.
非終極符是指既可出現于產生式的左部,又可出現于產生式右部的符號;終極符是指只能出現于產生式右部的符號.在非終極符中有一個特殊符號,稱之為文法的初始符號,在SOOL文法中就是Program.
1.5 本文的主要工作
1,用巴克斯范式構造出模型語言SOOL;
2,建造SOOL的語法樹;
3,對程序進行信息流分析,從條件組合覆蓋策略和類覆蓋策略出發,依據SOOL的語法樹建造路徑二叉樹;
4,對路徑二叉樹上的條件表達式進行分類,化簡,對不同的情況采用各種辦法生成測試用例.
第二章 測試用例自動生成器的體系結構
2.1 使用工具介紹
2.1.1 ACCENT簡介
ACCENT是類似于YACC(Bison)的編譯器構造工具,是一個共享軟件,附有程序源代碼,它是在unix(linux)上開發的,其全稱為"A Compiler Compiler for the Entire Class of Context-Free Languages".其功能是能自動產生某個語言的語法分析器.使用時,按照ACCENT所要求的格式給出輸入文件,主要是指出語言的文法描述,ACCENT會自動產生出該語言的語法分析器yyparse().其網址為http://accent.compilertools.net.
2.1.2 ACCENT與YACC的比較
ACCENT對文法不加任何限制,能處理所有的上下文無關文法;YACC只能處理LALR(1)類文法.ACCENT在處理文法時不會產生任何沖突;YACC受所處理文法類的限制,可能會產生S/R或R/R沖突.ACCENT產生的語法分析器分析效率略低;由YACC生成的分析器分析效率高.
2.1.3 ACCENT輸入文件的格式
全局定義部分 token聲明部分 規則部分.
全局定義部分:用來定義一些函數,全局變量以及類型,這部分可空.
格式:%prelude { c_code }
用花括號括起來的部分為任意的C代碼,它會原封不動的復制到ACCENT產生的語法分析器文件的首部.
token聲明部分:用來聲明文法中出現的所有的終極符(稱為tokens),可空.
格式:%token tk1,tk2,…… ,tkn ;
ACCENT中的tokens分為兩種:
(1). 多字符終極符,這類token必須用"%token"關鍵字聲明
如:%token NUMBER,IF,THEN,ELSE,WHILE等;
(2). 單字符終極符,稱為"literal token",這類token不必聲明,用單引號引起來即可,可直接出現在產生式中.
如:statement:variable '=' exp
| IF exp THEN statement ELSE statement
| ……;
規則部分:文法中的產生式,應至少有一條規則.
格式:rule1 rule2 …… rulen
rulei: left_hand :right_hand ;
文法中的每個非終極符都用一條規則來定義,第一條規則的左部為整個文法的開始符.
2.1.4 詞法分析函數yylex
語法分析程序的輸入是經詞法分析后的token序列,而不是用戶直接寫的源程序,因此必須為ACCENT產生的語法分析器提供詞法分析函數,函數名固定為yylex.yylex可以自己編寫,也可以用Lex自動生成,其返回值為一個整數,表示所識別單詞的類別.
Lex生成一個C文件,里面有詞法分析函數yylex.
2.1.5 ACCENT中可以使用的文法描述手段
1).局部選擇(Local Alternatives)
格式:(alt_1 | …… | alt_n),可以避免引入新的非終極符.
如:signed_number:sign NUMBER;
sign :'+' | '-';
利用局部選擇可以寫成:signed_number:('+' | '-') NUMBER;
2).可選符(Optional Elements)
格式:(M_1 … M_n)
意義:括號中的 M_1 … M_n 可出現在輸入中,也可以不出現.
例如:integer:(sign) NUMBER;
則 123和 +123都是正確的輸入.
3). 星閉包(Repetitive Elements)
格式:(M_1 … M_n)*
意義:表示括號中項目的任意次重復(包括0次).
例如:number_list:NUMBER ( ',' NUMBER) * ;
則"12","12 , 24","12 ,32 , 4"都是合法的輸入.
2.1.6 ACCENT語義動作
ACCENT會根據文法產生語法分析程序來對用戶的源程序進行語法分析:它拒絕所有不符合文法的輸入.
為了對輸入進行語義處理,需要指定語義動作.語義動作可以嵌套在文法的任意位置,當指定的分支匹配時,對應的語義動作也被執行.語義動作為用花括號括起來的任意C代碼,這些C代碼將會被原文拷貝到語法分析程序的適當位置.
例如有如下文法:
N: {printf("1\n");} 'a' {printf("2\n");} 'b' {printf("3\n");} | {printf("x\n");} 'c' {printf("y\n");}
則對于輸入 "ab",語法分析程序會產生如下輸出:
1
2
3
2.1.7 ACCENT中非終極符的屬性
與程序設計語言中的函數類似,非終極符也可以有參數,這些參數可以在語義動作內訪問.參數有兩種模式:
1).in模式:是將信息從上下文傳遞到非終極符中,即繼承屬性.
2).out模式:將信息從非終極符傳遞到上下文中,稱作綜合屬性.
下面是產生式左,右部參數的格式和用法:
a.若規則左部的非終極符帶有參數,則其格式如下:
left_hand
left_hand
left_hand
left_hand
parameter_spec_list: 類型名 參數名,類型名 參數名,……
其中"類型名"可選,如果類型名不寫,則默認為YYSTYPE類型,YYSTYPE是一個宏,代表long類型,用戶可對其重定義.如果一個參數既不加%in修飾,也不加%out,則默認為是綜合屬性.
例: N:……;
b.產生式右部的非終極符如果有參數,則將其用尖括號""括起來跟在該非終極符的后面.
例:N
1).參數能在語義動作內訪問,輸入參數的值必須在語義動作內定義或者是其它文法符號的輸出參數.
2).若非終極符有綜合屬性,則其每個分支都要定義輸出參數并在語義動作內給其賦值.
3).在語義動作內使用左部非終極符的輸出參數,需用"*"操作符訪問.
4).參數變量均不需定義.
例如:
demo:
{actual_context=10;}
N
{printf("%d\n",actual_result);}
N:{*result=context+1;};
經ACCENT產生的語法分析程序如下:
demo()
{
int actual_context; /* 參數變量不需定義*/
int actual_result;
switch(yyselect()){
case 1:
{
actual_context=10; /* 輸入參數必須有值 */
N(actual_context, &actual_result); Printf("%d\n",actual_result);
}
break;
}
}
N(context,result)
int context;
int * result;
{
switch(yyselect()){
case 2:
{
*result=context+1; /* 輸出參數必須賦值 */
}
break;
}
}
2.1.8 ACCENT中Tokens的屬性
用%token語句聲明的token都有一個YYSTYPE類型的輸出參數,若要在規則的右部使用token,則可以為其指定一個實參來訪問其語義值.
例如: Value: NUMBER{printf("%d\n",n);}
這里n就表示NUMBER的數值(語義值),可以在語義動作內使用.
token語義值的計算:
一個token的語義值是在該token的詞法規則的語義動作內被計算的,其值必須賦給YYSTYPE類型的系統變量yylval.比如我們想訪問上例中的NUMBER的語義值,則相應LEX中的規則應改為:
[0-9]+ {yylval=atoi(yytext); return NUMBER}
變量yytext為當前匹配單詞的字符串值.atoi是標準的C函數,將一個字符串轉變成整數.
文章來源于領測軟件測試網 http://www.kjueaiud.com/
