PEGに基づいた構文解析器の実装
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/27 02:27 UTC 版)
「Parsing Expression Grammar」の記事における「PEGに基づいた構文解析器の実装」の解説
PEGはそのまま再帰下降構文解析の構文解析器に変換可能である。ただしそれをナイーブに実装すると最悪の場合、最後まで先読みして失敗し、また最初から繰返すことにより指数時間かかる可能性がある構文解析器になってしまう。 しかし、PEGが21世紀に入って以降に見直される傾向となったのは、再帰下降構文解析の途中結果をメモ化し、各構文解析関数が同じ入力位置について高々1回までしか呼ばれないようにするPackrat Parserの実用性が確認されたためである。メモ化のためにメモリ領域を必要とすることと引き換えに、理論的には常に線形時間で動作する。遅延評価の言語では自然に実装できることもこれを後押しした。 ただし実際のプログラミング言語などでは、典型的にはC言語においてtypedefで「型の名前」として扱われるべき名前が追加されることによる大域的な文脈依存性などで、再度の解析が必要となる場合があるが、そういったものも含め、たいていは実用的な範疇である。
※この「PEGに基づいた構文解析器の実装」の解説は、「Parsing Expression Grammar」の解説の一部です。
「PEGに基づいた構文解析器の実装」を含む「Parsing Expression Grammar」の記事については、「Parsing Expression Grammar」の概要を参照ください。
ウィキペディア小見出し辞書の「PEGに基づいた構文解析器の実装」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- PEGに基づいた構文解析器の実装のページへのリンク
