Sparse: Test Generation for Simple S-expression Language Parsers🔗 i

1.1Example🔗 i

Consider the following grammar for a simple language (dubbed PHYM4) which has conditionals, local variable binding, lambdas, function applications, numbers, strings, and identifiers:

Expr={ifExprExprExpr}

| {var {Id = Expr} ... Expr} |{lam{Id...}Expr}

| {Expr Expr ...} |Number

| String |Id

Here, Number, String, and Id are not to be taken literally, but rather as placeholders for literal numbers, strings, and identifiers. Additionally, if, var, lam, and = are to be forbidden as identifiers. Built-in operations, functions, and constants like +, *, <=, substring, or true are treated like any other identifier from the point of view of this language and so are not treated specially by the grammar. An example program from this language is

{{lam{xy}{if{<=xy}xy}}54}

which introduces a function to determine the minimum of two numbers, and then applies it to 5 and 4. Note, that we use braces as delimiters instead of parentheses to distinguish this tiny language from Racket. This language is very simple, and yet writing a suite of input programs to test students’ parsers would be tedious–and would likely fail to be comprehensive.

Sparse takes as input a description of the grammar which is not unlike the grammar shown above. It is worth noting here the largest limitation of Sparse. Sparse’s input grammar may only have one nonterminal. In this example, this is Expr. For languages whose grammars have more than one nonterminal, this can be worked around by only generating test cases for the core expression grammar, which is more likely to be able to be expressed as a grammar with one nonterminal, and leaving the full language to be tested with manually-written tests.

(definephym4-grammar

'([truefalsenull+-*/eq?<=substringarraynew-arrayarefaset!begin]

[lam=varif]

[Expr

{ifExprExprExpr}

{ExprExpr...}

{var{[id]=Expr}...Expr}

{lam{[id]...}Expr}

[id]

[string"Hello""World"""]

[number01-12.2-22/7]]))

The details of the format of the input grammar are described below. Using this grammar, one can call generate-valid-testcase to generate one large test case which will test to make sure the student’s parser accepts all valid programs. The following is produced for the grammar defined above:

{if{lam{}{lam{}{{lam{}{var{substring={lam{}{if{{{var{/={{if{var{-=

{var{+={if{iftrue{lam{truefalsenull+}false}{lam{-*/}"Hello"}}{null

{lam{eq?<=}0}{"World"{var{true=+}{1{if""{var{false="Hello"}{var{null

=-1}{if2.2{if{var""}-{{{{var/}-22/7}"World"}*}}{var0}}}}{if{var{lam

{substring}{if{if<=substring-1}1"World"}}}"Hello"eq?}}array}}new-arrayaref}

aset!begin}a}}b}}{*=c}d}ef}}}{eq?=g}{<==h}i}}}jk}}}{array=l}

{new-array=m}{aref=n}o}}}}}pq}

Additionally, one can call generate-invalid-testcases to generate a list of test cases which do *not* conform to the grammar to make sure that the student’s parser rejects all invalid programs. The following are produced for the grammar defined above.

{lamtruefalsenull}

{iflam"Hello""World"}

{if0lam1}

{if+-lam}

{}

{if}

{if""}

{if-1"Hello"}

{if0"Hello"eq?"World"}

{if<=1-1substring""}

{if"Hello"array2.2new-array"World"-22/7}

{=aref}

{""=}

{lam{true=e}f}

{var{lam=""}"World"}

{var{falselam1}1}

{var{null=var}j}

{var{}""}

{var{+}-1}

{var{-=}k}

{var{eq?=g"World"}l}

{var{<==2.2h""}"World"}

{var{substring=-22/7i"Hello"0}-22/7}

{var{array=m}if}

{var}

{var{new-array=""}}

{var{begin="World"}o""}

{var{a=-1}2.2p"Hello"}

{var{b=q}-22/7r"World"0}

{={true}s}

{lam{lam}""}

{lam{aref}=}

{lam}

{lam{aset!}}

{lam{b}2.2w}

{lam{c}"Hello"-22/7x}

{lam{d}"World"0y""}

lam

var

Since the "valid" test case produced is so large, it would likely not be very enlightening to a student trying to understand where exactly their parser is failing. To help alleviate this, Sparse includes a utility for producing minimal failing test cases for a student’s parser. For example, for one student’s parser, the following minimal failing test cases were identified:

{lam{truefalsenull+}false}

{lam{-*/}"Hello"}

{lam{eq?<=}1}

{lam{array}0}

{var{false="World"}x}

{var{+=0}x}

Here, the student’s mistake was forbidding the built-ins as parameter names; the language’s grammar and semantics allow redefining the names. It is worth noting that this student had actually passed all of the instructor’s original test cases. Since the instructor’s test cases only tried redefining a built-in once, a student whose submission was rejected the first time could simply special-case that one built-in and resubmit their assignment successfully. Manually writing test cases which redefine each built-in is rather tedious and requires a fair bit of foresight on the part of the instructor to know that that is an area where students might mistakes. By automating the generation of test cases, we can both reduce the tedium of writing test cases and make the test suite more comprehensive.

1.2Usage🔗 i

The first four of these functions take an S-expression representing the grammar for which to generate test cases. Several examples are provided in ‘example-grammars.rkt‘ Consider the example grammar from before:

(definephym4-grammar

;;ThefirstlistisforanylegalidentifiersyouwantSparsetouseexplicitly.

;;Thiscanbeusefulifyouthinkstudentsmightforbididentifiersthatarelegal.

'([truefalsenull+-*/eq?<=substringarraynew-arrayarefaset!begin]

;;Thesecondlistisforthesymbolsthatarenotlegalidentifiers

[lam=varif]

;;Thethirdlistisfortheproductionrulesofthegrammar.Thefirstelement

;;shouldbeasymbolforthegrammar'snonterminal.

;;Unfortunately,Sparsedoesnotsupportmorethanonenonterminal.

[Expr

;;Theproductionrules.Anynumbersandsymbolsotherthanthenameof

;;nonterminalaretreatedasliterals.

{ifExprExprExpr}

;;'...'meansthatthetermimmediatelytotheleftmayappearzeroormoretimes.

{ExprExpr...}

;;[id](or(id)or{id})referstovalididentifiers.Thiswillusethe

;;identifiersprovidedabove,aswellasthelettersofthealphabeta-z.

{var{[id]=Expr}...Expr}

{lam{[id]...}Expr}

[id]

;;Thisrepresentsanystring.Atleastoneexamplestringtousemustbeprovided.

[string"Hello""World"""]

;;Thisrepresentsanynumber.Atleastoneexamplenumbertousemustbeprovided

[number01-12.2-22/7]]))