解析表現文法による不完全なプログラムの構文解析手法の提案

構文が不完全なソースコードの補完やエラーメッセージの性能向上を図るなどの目的で，不完全なコードから構文を推論したい場合がある．発表者らのグループでは，そのような構文の推論を，もとの構文定義を「拡大文法」と呼ばれる文法に変換することによって行う手法を提案した．拡大文法は，Parsing Expression Grammar（PEG）で書かれた文法に変換を加えることで得られるもので，構文的に「欠け」がある入力に対しても構文解析を行うことを可能にした．PEGで書かれた文法を拡大文法へ変換するためには，任意の解析表現に「キーフレーズ」という各構文におけるユニークな非終端記号列の並びを定義し，それ以外の記号列を省略可能になるように変換を行う．この変換によってキーフレーズを手がかりに構文を正しく解釈することができるようになる．しかし，先行研究では拡大文法への変換方法やキーフレーズの定義が定式化されておらず不完全であり，文法定義者が手動で変換していたことと，構文解析が意図しない結果になることがある問題があった．そこで，本研究では拡大文法の正確な定義を試みる．これによって，構文解析において意図しない結果を導く問題の解消を図るとともに，もとの構文定義から拡大文法への変換手法を明らかにすることができる．本発表では，この変換アルゴリズムについても述べ，その実装について報告する．

In some cases, we may want to infer complete syntax from incomplete source codes for the purpose such as complementing incomplete source codes or improving readability of error messages. So our group suggested a method that converts original syntax description into an “extended grammar” to infer the correct syntax. The extended grammar is obtained from a syntax definition written in Parsing Expression Grammar (PEG) and its parser is able to parse input even if it is grammatically incorrect. To convert grammar written in PEG to the extended grammar, the language designer gives a unique string combination called “key phrase” for each rule, so that a fragment of the source code is accepted in case it contains the key phrase. With this conversion, the parser can recognize incomplete source code as complete one based on key phrases. However, our previous study did not resolve unexpected result of parsing, and did not show the algorithm of obtaining extended grammars. In this study, we will give more precise definition of extended grammars. This resolves the problem of having unexpected result in some case, and we can clarify the algorithm for obtaining the extended grammars from original syntax definitions. In this presentation, we describe this conversion algorithm and its implementation.