Yayacc－自動エラーリカバリ機構付きパーサジェネレータ

IPSJ Web Site

Bibliographic Information

Other Title
  • Yayacc ジドウ エラーリカバリ キコウ ツキ パーサジェネレータ
  • Yayacc - A Parser Generator with Automatic Error Recovery

Search this article

Description

本発表では，自動エラーリカバリ機構を持つパーサジェネレータ yayacc の設計と実装を述べる．yacc や bison をはじめとして，現在広く使われているパーサジェネレータでは，文法中に特殊なエラーリカバリ動作を指示するトークンを手動で挿入させることで，エラーリカバリパーサを生成している．この古典的な手法は本来の文法定義を変えてしまうことに起因する深刻な問題があり，正しいエラーリカバリを行うパーサを生成させるには，多くの勘と経験が必要とされる．一方，yayacc ではエラーリカバリのために，文法を修正するというこがいっさい不要であり，生成されるパーサは従来の error トークン手動挿入によるパーサでは理論的に不可能な優れたエラーリカバリを自動的に行う．さらに yayacc では意味動作の Undo も自動で行うことが可能である．これは先行研究における自動エラーリカバリパーサでは扱われていないが，字句解析が完全に分離できない文法，たとえば C 言語に対しても自動的なエラーリカバリを行う場合に必要となる重要な機能である．yayacc は筆者らが開発している SCK コンパイラキットのツールの 1 つとして作成されたものである．現在 ANSI C言語，および小規模な関数型言語のパーサは yayacc により自動生成されたものを使っており，きわめて優れたエラーリカバリが行われている．

In this presentation, we describe the design and implementation of a parser generator named yayacc, which generates parsers with automatic error recovery. Widely used parser generators, such as yacc and bison, require parser writers to insert by hand special tokens indicating error recovery actions for generating error recovery parsers. This antique method involves serious problems due to the fact that the method actually modifies the original definition of given grammar. As a consequence, much of experience and inspirations are needed to generate parsers which can truly recover from errors. On the other hand, yayacc ruquires no such ad hoc modification of grammars for error recovery, yet the generated parsers do excellent error recoveries which could not theoretically be achieved by the antique method. Undoing semantic actions are also possible in yayacc. Previous studies and their experimental parser generators did not implement this feature, but it is indispensable to generate error recovery parsers for certain languages where a parser must semantically interact with its lexical analyzer to parse input programs, such as C language. We have developed yayacc as a tool of SCK compiler kit. Currently, parsers of ANSI C and a small functional language in SCK are yayacc generated ones and demonstrate excellent error recoveries.

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top