Abstract: Jens Nilsson, Welf Löwe, Johan Hall, Joakim Nivre. Proceedings of the 11th International Conference on Parsing Technologies (IWPT’09).
2009.
Introduction
In software engineering, source code is typically treated as a rigid mathematical construct. However, for maintenance tools—such as those for code review, refactoring, or reverse engineering—source code is often "noisy." It may be incomplete, contain syntax errors, or follow non-standard dialects. Traditional compiler-style parsers, built on context-free grammars, are brittle and often fail entirely when encountering such irregularities.
This research proposes a shift in perspective: treating programming languages more like natural languages. By applying data-driven dependency parsing—techniques originally developed for analyzing human languages like English—the authors developed a robust and accurate parsing approach for Java, C++, and Python.
The Challenge of Brittle Parsers
Classical parsers (e.g., gcc or javac) expect perfect code. When they encounter an error, they may lose significant structural information or crash. For software maintenance, a parser needs to be:
- Robust: It must always produce a meaningful model (an Abstract Syntax Tree or Dependency Tree), even with incorrect input.
- Portable: It should not require a complex, hand-written grammar for every new language version or dialect.
Methodology: Adapting NLP Techniques
The researchers utilized MaltParser, a data-driven system employing Nivre’s arc-eager algorithm. Unlike grammar-based parsers, this system uses a machine-learning classifier (LIBSVM) to predict parsing actions (Shift, Reduce, etc.) based on the current state.
To adapt this to formal languages, the authors developed a pipeline to convert standard Abstract Syntax Trees (ASTs) into dependency trees. In this format, tokens are linked directly via directed relations. They discovered that the LEFT rule (designating the leftmost terminal as the head) was the most effective strategy for programming languages.
A key innovation was lexicalization. While compilers treat variable names as generic "Identifiers," this parser utilizes the actual text (e.g., equals or getName). These names often follow conventions that serve as "soft" grammatical cues for the machine learner.
Training Data
Training data was generated automatically by running existing compilers on large codebases, including the Java Recoder project (92k lines), the C/C++ Elsa benchmark (265k lines), and the Python NLTK library (65k lines).
Key Results and Insights
The parser achieved exceptional accuracy, significantly higher than typical NLP benchmarks:
- Java: Reached an F-score of 99.3% for unlabeled parsing and 97.7% for labeled parsing.
- C/C++: Achieved a 96.5% F-score, slightly lower due to the language's complex syntax.
The study revealed that variable names are powerful signals; lexical information significantly improved accuracy. Furthermore, because the parser is a classifier making step-by-step decisions, it is robust by design—it will always provide a "best guess" structure rather than failing on erroneous code.
Conclusion
While a 99% accuracy rate might be insufficient for a compiler, it is more than adequate for maintenance tools like code search engines or architecture recovery systems. The primary advantage is the parser's ability to handle "broken" code gracefully. Future research will focus on quantifying performance on truly "illegal" source code and validating the utility of these robust trees in downstream maintenance tasks.
Summary updated