说明:
从形式语言的角度看,一个语言不过是字符串集.如果字符串集是有穷的,那么我们就可用枚举的办法来表示.但当集合为无穷时枚举的办法就不再适用.
文法是表示无穷字符串集的强有力的一种有限办法.表示文法需要工具,其中最常用的工具是所谓的巴克斯范式(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函数,将一个字符串转变成整数.
文章来源于领测软件测试网 https://www.ltesting.net/
