【論文解説】N-gramでソースコードのバグを自動発見——初学者向け構文エラー修正支援手法の提案
tad論文情報
タイトル：N-gramによる確率モデルを用いた初学者向け構文エラー修正支援手法
著者：田中 慎之佑、嶋利 一真、福島 和希、石尾 隆、松本 健一（奈良先端科学技術大学院大学・公立はこだて未来大学）
掲載誌：情報処理学会論文誌 Vol.59 No.1（2018年1月）
研究の背景：初学者を悩ませる「構文エラー」
小学校・中学校・高校でプログラミング教育が必修化され、プログラミング未経験者が学習する機会が急増しています。しかし初学者がプログラミングを学ぶ際に大きな壁となるのが構文エラーです。
構文エラーとは、閉じ括弧の欠如やコロンの付け忘れなど、プログラミング言語の文法規則に違反した際に発生するエラーです。熟練者なら一目でわかるようなエラーでも、初学者は大量の時間を費やして修正を試みます。言語処理系（コンパイラ）が出力するエラーメッセージは初学者には難解なことが多く、「invalid syntax」と表示されるだけで、どこをどう直せばよいかまったくわからないケースも珍しくありません。
本研究はこの問題に対し、N-gramによる確率モデルを活用して「ソースコードのどこが不自然か」を自動検知し、修正の手がかりとなるトークン候補を提示する手法を提案しています。
N-gramとは何か
N-gramとは、テキストをN個の連続した単語（トークン）の列として捉える統計手法です。たとえば「for i in range ( 10 ) :」というコードは、N=3（3-gram）の場合、「for i in」「i in range」「in range (」…というように分割されます。
ポイントは、正しいコードのN-gramパターンは繰り返し出現しやすいという性質です。たとえばPythonのfor文は「for 変数 in range ( 数字 ) :」という形が頻繁に登場します。逆に「for if !=」のようなトークンの並びは正しいコードにはほぼ登場しない——つまり「不自然」です。この不自然さの検出こそが、本研究のバグ限局（バグのある場所を特定すること）の核心です。
提案手法の仕組み
提案手法は3つのステップで構成されています。
STEP 1：字句解析とトークン前処理
過去の授業で提出された正解ソースコードを字句解析し、トークン（プログラムの最小単位）に分解します。変数名や数値などは汎用トークン（IDENT、NUMなど）に統一し、頻出の識別子（str, int, print など）はそのまま扱います。これにより、コードの具体的な内容ではなく「構文的なパターン」を抽出できます。
STEP 2：N-gram辞書の作成
正解ソースコードから抽出したN-gramとその出現回数を「N-gram辞書」として記録します。出現頻度の低いN-gramは誤りと混同されやすいため、上位90%・80%の出現回数をカバーするN-gramだけを残した「90%辞書」「80%辞書」も作成し、ノイズを削減します。
STEP 3：確率モデルの適用とバグ限局・修正支援
構文エラーを含むソースコードに対してN-gram辞書を適用し、辞書に存在しない（または出現確率が極めて低い）N-gramを「不自然な箇所」としてフラグを立てます（バグ限局）。さらに、そのN-gramの末尾トークンを確率的に出現しやすいトークンに置き換えた候補を提示することで、修正の手がかりを与えます。
重要なのは、正解を直接提示するのではなく「手がかり」として候補を示す点です。学習者が自ら考えて修正する機会を残しながら、思考のきっかけを提供します。
実験と結果
奈良先端科学技術大学院大学の「プログラミング演習」（2022年度）で収集したデータを使用しました。正解ソースコード4,189件（55名分）でN-gram辞書を構築し、残り14名の正解ソースコード1,149件と構文エラーを含むソースコード846件に適用しました。
RQ1：構文エラーのあるコードは本当に「不自然」か？
N-gram辞書に存在しないN-gramの割合を正解コードとエラーコードで比較したところ、エラーコードの方が有意に高く（カイ二乗検定で有意差あり）、かつエラー行付近に不自然なN-gramが集中していることが確認されました。この結果は提案手法の理論的根拠を裏付けるものです。
RQ2：バグ限局の精度は？
| N-gram（N値） | 限局件数 / 全体 | 成功率 |
|---|---|---|
| 3-gram | 569件 / 846件 | 67.3% |
| 5-gram | 695件 / 846件 | 82.2% |
| 7-gram | 727件 / 846件 | 85.9% |
| 全体（和集合） | 731件 / 846件 | 86.4% |
Nの値を大きくするほど精度が向上し、80%辞書を使用した場合は最大745件（89.6%）でバグ限局に成功しました。
RQ3：修正支援の有用性は？
バグ限局できた745件のうち655件（87.9%）でトークン候補を提示できました。詳細分析として、候補が1種類だった203件を手動検証したところ：
- コンパイラのエラーメッセージのみで修正可能：26.6%
- 提案手法との併用で修正可能：49.8%（約2倍）
コンパイラだけでは「invalid syntax」としか表示されないケースでも、提案手法が具体的なトークン候補を提示できることが示されました。
成功例・失敗例
成功例
a = int(input())
if != 0: # ← if と != の間に変数が必要
print(1/a)
else:
print('Invalid Input')2行目の「if」の直後に変数「a」が欠落しているケースです。コンパイラは「invalid syntax」としか表示しませんが、提案手法は「ifの後には変数が来る」というパターンを学習しており、変数トークンを候補として提示できました。
失敗例
print('{} + {} = {}',.format(x, y, x+y))
# ↑ カンマの後に .format がくるパターンが学習データに少なく、誤った候補を提示文字列の後に「.format」でメソッドを呼ぶパターンは他の演習問題では少なく、N-gram辞書に十分なパターンが蓄積されていなかったため、誤った候補（変数の挿入）を提示してしまいました。学習データの偏りが失敗の原因です。
手法の限界と今後の展望
本手法にはいくつかの限界もあります。括弧の対応ミスのようにトークンが離れた位置に影響する誤りや、学習データにないパターンには対応が難しい点、また奈良先端大という特殊な学習環境（他言語経験者が多い）のデータを使用しているため汎用性に限界があることなどが挙げられています。
今後の展望として、実際のプログラミング演習にツールとして組み込み、学習効果を被験者実験で測定することや、学習データを工夫することでコーディングスタイルの改善（例：冗長な「else: if:」を「elif:」に促す）へと手法を拡張することが挙げられています。
まとめ
本研究は、N-gramという比較的シンプルな統計手法を使い、初学者のプログラミング学習を支援する実用的なアプローチを提示しています。深層学習ベースの手法と比べて軽量で、かつ「答えを教えすぎない」という教育的配慮が特徴的です。プログラミング必修化が進む今、こうした自動化された学習支援ツールの整備は、教員の負担軽減と学習者の自立的な問題解決能力の育成という両面から意義があります。
引用元：
田中 慎之佑、嶋利 一真、福島 和希、石尾 隆、松本 健一（2018）．N-gramによる確率モデルを用いた初学者向け構文エラー修正支援手法．情報処理学会論文誌，Vol.59, No.1, pp.1–11.
