Parsing Formal Languages using Natural Language Parsing Techniques

Jens Nilsson, Welf Löwe, Johan Hall, Joakim NivreIWPT 2009 · OpenReview

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:

  1. Robust: It must always produce a meaningful model (an Abstract Syntax Tree or Dependency Tree), even with incorrect input.
  2. 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.

Example of a dependency parse for a natural language sentence illustrating basic relations like ROOT, SUB, and OBJ.

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.

Dependency tree representation of a Java method declaration, illustrating the result of the AST-to-dependency conversion process.

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

BibTeX
@inproceedings{nilsson2009parsing,
  author = {Jens Nilsson and Welf Löwe and Johan Hall and Joakim Nivre},
  title = {{Parsing Formal Languages using Natural Language Parsing Techniques}},
  booktitle = {IWPT},
  year = {2009},
  url = {https://openreview.net/forum?id=tvwXLK3rU5N},
}

Loading related content...

Figure