如何测试解析器

Question

我有一个解析器，可以将表达式解析成语法树。示例表达式如下

1+2-3*4/5
add(1,2,3)+(4*5-6*(7-8))

有效令牌为：

num + - * / ( ) add avg max min

函数add、avg、max和mix可以接受一个或多个参数。每个参数都可以是一个表达式。例如：

max(1, 4*add(1,2,3))

1+2*3的示例语法树

   +
/    \
1    *
   /   \
   2   3

如何设计测试用例，以用最少的用例达到最大的复盖率？

Answer 1

功能测试的核心概念是划分和组合。

确定给定参数的测试值。

确定参数维度的覆盖范围。

所以这个问题是因为如何识别解析器的测试参数。一旦我们确定了测试参数，我们就可以通过分区和组合来构造测试用例。

我对这个问题的回答是使用上下文无关文法( Context Free Grammars，CFG)来描述所讨论的解析器。

EXPR -> NUM | FX | (EXPR) | EXPR' | NUM BOP1 EXPR' | FX BOP1 EXPR' | (EXPR) BOP1 EXPR'
EXPR' -> NUM | FX | (EXPR) | NUM BOP2 EXPR | FX BOP2 EXPR | (EXPR) BOP2 EXPR
BOP1 -> + | -
BOP2 -> * | /
FX -> FN(ARGS)
FN -> add | avg | max | min
ARGS -> EXPR | EXPR , ARGS | ε

然后，您可以设计测试用例来测试CFG中的每个产品。例如，在产品"FX -> FN( ARGS )“中，有两个测试参数: FN和ARGS。FN的有效值是add，avg，max，min，ARGS的有效值是"EXPR"，"EXPR，EXPR"，"EXPR，...EXPR“。

如果我们使用1-wise组合。那么表达式"add(1,2)“、"avg(1,2)”、"max(1,2)“、"min(1,2)”是等价的。这样，我们应该只测试其中的一个，以实现类似的覆盖率。