Method and system for interactive computer science testing, anaylsis and feedback

• US 5,259,766 A
• Filed: 12/13/1991
• Issued: 11/09/1993
• Est. Priority Date: 12/13/1991
• Status: Expired due to Fees

• Current Assignee: Educational Testing Service
• Original Assignee: Educational Testing Service
• Inventors: Bennett, Randy E., Sack, Warren
• Primary Examiner(s): Apley, Richard J.
• Assistant Examiner(s): CHENG, JOE H
• Application Number:
  US07/807,008
• Time in Patent Office: 697 Days
• Field of Search: 434/322, 434/323, 434/327, 434/335, 434/336, 434/362, 434/353, 364/419, 364/191
• US Class Current: 434/362
• CPC Class Codes: G09B 19/0053 Computers, e.g. programming
• CPC Class Codes: G09B 7/04 characterised by modifying the teaching programme in response to a wrong answer, e.g. repeating the question, supplying a further explanation

Abstract

Disclosed is a method and system for administering to a student a problem in computer science for testing, analysis and feedback. The student is provided with an item pool of predetermined test problems to be selected by the student. The student inputs a solution in response to the problem selected, and the solution program is converted, by lexing and parsing, into an abstract syntax tree representation. Predetermined knowledge base patterns are selected from a knowledge base and compared against portions of the abstract syntax tree. Messages and a score are provided to the student which indicate the correctness or incorrectness of the solution program, as determined by the knowledge base patterns which were matched against the portions of the abstract syntax tree. The present method and system is especially qualified to analyze free-response test items.

Claims

1. A method of evaluating a solution program input to a computer in response to a computer science problem in which the solution program may contain a plurality of errors, said method comprising the steps of:

a) converting the solution program in response t the computer science problem into an abstract syntax tree representation;

b) comparing a first predetermined pattern against a first portion of the abstract syntax tree, said first portion representing certain nodes of the abstract syntax tree;

c) repeating step (b) against a plurality of portions of the abstract syntax tree until the first predetermined pattern matches a portion of the abstract syntax tree;

wherein the first predetermined pattern has been specified so as to match a range of abstract syntax tree portion; and

d) providing information correlated to the first predetermined pattern so matched;

wherein said information is a textual message indicative of the correctness of the solution program.

2. The method of claim 1 further comprising the steps of:

e) comparing a subsequent predetermined pattern against the first pattern the first portion of the abstract syntax tree;

f) repeating step (e) against a plurality of portions of the abstract syntax tree until the subsequent predetermined pattern matches a portion of the abstract syntax tree;

g) providing information correlated to the subsequent predetermined pattern so matched;

wherein said information is a textual message indicative of the correctness of the solution program; and

h) repeating steps (e), (f) and (g) for a plurality of sequent predetermined patterns.

3. The method of claim 2 in which the information provided further comprises a weighted score.

4. The method of claim 3 in which the converting step comprises the steps of:

(i) lexing the solution program into a list of tokens, each token being representative of a part of the solution program and its location within the solution program and

(ii) parsing the list of tokens into an abstract syntax tree representation.

5. The method of claim 4 wherein the lexing step and the parsing step are implemented in Prolog programs.

6. The method of claim 5 wherein the Prolog programs that implement the lexing step and parsing step comprises LEXER.ARI and PARSER.ARI programs.

7. The method of claim 6 in which the Prolog program that implements steps (b) and (c) of the method comprises ENGINE.ARI program.

8. The method of claim 1 in which the computer science problem is an open-ended problem.

9. The method of claim 1 in which the computer science problem is a completion problem.

10. The method of claim 1 in which the computer science problem is a faulty solution problem.

11. A method of administering to a student a problem in computer science for analysis and feedback comprising the steps of:

a) providing an item pool to the student, said item pool comprising a plurality of predetermined test problems in computer science to be selected by the student;

b) recording the student'"'"'s solution program to a particular test problem selected;

c) lexing the solution program into a list of tokens, each token being representative of a part of the solution program and its location within the solution program;

d) parsing the list of tokens into an abstract syntax tree representation;

e) comparing a predetermined pattern against a first portion of the abstract syntax tree;

f) repeating the comparison step with a plurality of portions of the abstract syntax tree until the predetermined pattern matches a portion of the abstract syntax tree;

g) repeating steps (e) and (f) for a plurality of predetermined patterns;

h) providing to the student text messages correlated to the predetermined patterns so matched;

whereby the student is automatically provided with information embodied in the text messages which is indicative of the correctness or incorrectness of the solution text entered by the student in response to the test problem selected.

12. A method of administering an examination in computer science to a student comprising the steps of:

a) providing to the student a predetermined test problem in computer science from an item pool comprising a plurality of different predetermined test problems;

b) recording the student'"'"'s solution program in computer science to the predetermined test problem so provided;

c) lexing the solution program into a list of tokens, each token being representative of a part of the solution program and its location within the solution program;

d) parsing the list of tokens into an abstract syntax tree representation;

e) comparing a predetermined pattern against a first portion of the abstract syntax tree;

f) repeating the comparison step with a plurality of portions of the abstract syntax tree until the predetermined pattern matches a portion of the abstract syntax tree;

g) repeating steps (e) and (f) for a plurality of predetermined patterns; and

h) storing a score correlated to the predetermined patterns so matched;

whereby the student'"'"'s solution program to the predetermined test problem is automatically evaluated and scored, the score being indicative of the correctness or incorrectness of the solution text entered by the student in response to the test problem provided.

13. The method of claim 12 further comprising the steps of:

i) eliminating from the item pool the predetermined test problem already provided to the student;

j) repeating steps (a) through (i) a predetermined number of times;

k) storing a cumulative score indicative of all the scores stored in step (h);

whereby the cumulative score is indicative of the student'"'"'s ability in computer science.

14. A computer system for administering a problem for analysis and feedback in a computer science programming language to a student, said system comprising:

a) a user interface comprising

i) an item pool comprising a plurality of predetermined test problems in computer science to be selected by the student;

ii) output means for providing to the student the particular test problem selected; and

iii) input means for providing communications from the student to the system;

iv) editor means for recording to student'"'"'s solution program in computer science to the particular test problem selected;

b) a knowledge base comprising a set of predetermined knowledge base patterns;

c) an analytic component comprising

i) means for converting the student'"'"'s solution program into an abstract syntax tree;

ii) means for comparing each of the predetermined knowledge base patterns against portions of the abstract syntax tree until matched successfully; and

d) means for providing to the output means of the user interface a text message correlated to the knowledge base patterns so matched;

whereby the student is automatically provided with information embodies in the text message which is indicative of the correctness of the solution text entered by the student in response to the test problem selected.

15. The computer system of claim 14 in which the converting means comprises:

A) means for system of claim 14 in which the converting means comprises;

A) means for lexing the student'"'"'s solution program into a list of tokens, each token being representative of a part of the solution program and its location within the solution program; and

B) means for parsing the list of tokens into an abstract syntax tree.

16. The computer system of claim 15 including means for implementing Prolog programs;

wherein the Prolog programs comprises LEXER.ARI, PARSER.ARI and ENGINE.ARI programs.

17. The computer system of claim 16 in which the means for lexing is implemented by the LEXER.ARI program, the means for parsing is implemented by the PARSER.ARI program, and the means for comparing is implemented by the ENGINE.ARI program.

18. An expert system for evaluating a solution program into to a computer in response to a computer science problem comprising:

a) interface means for providing communication to and from a user;

b) lexing means for converting said solution program into a list of tokens, each of said tokens being representative of a part of the solution program and its location within the solution program;

c) parsing means for converting the list of tokens produced by the lexing means into an abstract syntax tree representation of the solution program;

d) a knowledge base comprising a plurality of predetermined knowledge base patterns wherein each of said knowledge base patterns represent a certain part of a model solution program;

e) an inference engine comprising means for comparing each of said knowledge base patterns against portions of the abstract syntax tree until successfully matched; and

f) means for providing to the interface output messages correlated to the knowledge base patterns successfully matched.

19. The expert system of claim 18 including means for implementing Prolog programs;

wherein the Prolog programs comprise LEXER.ARI, PARSER.ARI and ENGINE.ARI programs;

and wherein the lexing means is implemented by the LEXER.ARI, the parsing means is implemented by the PARSER.ARI, and the inference engine is implemented by the ENGINE.ARI program.

20. A method for interactively compiling knowledge base patterns of computer science programs for matching against portions of abstract syntax tree representations of model solution programs in response to the computer science problems, said method comprising the steps of:

a) lexing a model program into a list of tokens, each of said tokens being representative of a part of the model program and its location within the model program;

b) parsing the list of tokens into an abstract syntax tree representation of the model program;

c) querying a user to select the part of the model program against which the knowledge base pattern will be used to compare; and

d) generating a knowledge base pattern in accordance with the user'"'"'s selection such that said knowledge base pattern will match against a portion of the abstract syntax tree correlated to the part of the model program selected by the user.

21. The method of claim 20 further comprising the steps of allowing the user to specify node relations of the knowledge base pattern in accordance with desired match criteria.

22. A method of administering to a student problems in computer science for analysis and feedback comprising the steps of:

a) providing an item pool to the student, said item pool comprising a plurality of predetermined test problems in computer science to be selected by the student;

b) recording the student'"'"'s solution program to a particular test problem selected;

c) lexing the solution program into a list of tokens, each token being representative of a part of the solution program and its location within the solution program;

d) parsing the list of tokens into an abstract syntax tree representation;

e) comparing a predetermined pattern against a first portion of the abstract syntax tree;

f) repeating the comparison step with a plurality of portions of the abstract syntax tree until the predetermined pattern matches a portion of the abstract syntax tree;

g) repeating steps (e) and (f) for a plurality of predetermined patterns;

h) providing to the student text messages correlated to the predetermined patterns so matched; and

i) storing a score correlated to the predetermined patterns so matched;

whereby the student is automatically provided with a score and information embodied in the text messages which is indicative of the correctness or incorrectness of the solution text entered by the student in response to the test problem selected.