Program understanding by integrated application of graph parsing and expectation-driven analysis

Abstract

Program understanding is an important part of the domain expertise required for programming language tutoring systems. However, understanding of student programs by computer is extremely difficult because of the tremendous variability in student solutions for nontrivial tasks. This dissertation aims to handle such variability and improve understanding performance by a integrated approach based on two complementary methods of graph-parsing and expectation-driven analysis. The graph parsing method by Wills is utilized to recognize the programming plans in the code. At the same time, a new expectation-driven analysis is devised to generate expectations about the program design by using such knowledges as the programming goals, plans, and information about the problem task. The analysis guides the plan recognition process through confirming, amending, or rejecting the expectations by checking them against the given code. Analysis by expectation on plan (plan-driven expectation analysis) handles the near-miss plan. The matching with the smallest cost to modify the partial recognition is selected for further analysis. Plan-driven expectation analysis can find errors that can be explained as a variation of a plan. This identification is achieved without separate buggy plan library, and it can be debugged automatically. Analysis by expectation on goal (goal-driven expectation analysis) is used for understanding programs which contain unseen plans not existing in the plan library. Also, it finds unknown goal-implementing plans by generating candidate subgraphs and checks them with test data. Automatically acquiring the new programming plan can be obtained for a specific goal by using simple initial goal specifications. It would widen the range of applicability of program understanding, especially for novice programs. The system presented in this thesis was implemented as a major component of the Intelligent Tutoring System for C programming tutoring for novice progr...