PEGのパラメタ付き拡張Macro PEGの提案

情報処理学会

書誌事項

タイトル別名
  • Macro PEG: PEG with Macro-like Rules

この論文をさがす

抄録

PEGは，2004年にFordによって発表された解析的形式的文法の1つである．PEGは非常にシンプルであるにもかかわらず，広い範囲の文法を解析することができる（一部の文脈依存言語を含む）．また，Packrat Parsingという構文解析アルゴリズムによって，PEGで表現可能な任意の言語は線形時間で解析できるという好ましい性質を持っている．PEGの解析木は必ず一意に定まるため，プログラミング言語の構文解析器など，非自然言語の構文解析に向いている．PEGはその強力さにもかかわらず，いくつかの問題がある．まず，PEGの規則は再利用性が低い．また，現実のプログラミング言語の文法要素を扱うためには必ずしも十分な能力を持っていない．たとえば，複数の修飾子が順不同で出現するというパターンを認識するためには，通常のPEGではすべてのパターンを書き下す必要があり，修飾子の数が増えると文法の規模が爆発的に増加してしまう．本発表では，Macro Grammarを参考に，PEGがパラメタを取れるように拡張したMacro PEGを提案する．Macro PEGでは，先ほどあげたような文法を簡潔に記述することができる．また，本発表では，Macro PEGとパーザコンビネータとの関係について考察する．パーザコンビネータとは，主に関数型プログラミング言語で用いられる手法であり，関数合成によってパーザを組み立てる．最後に，本発表では，Macro PEGがどのような計算能力を持つのかについて考察を行う．

PEGs are analytic formal grammars invented by Ford in 2004. Despite of its simplicity, PEGs can recognize wide-ranged grammars, including some context sensitive languages. Also, packrat parsing enables linear time parsing for any language expressed by PEGs. Since PEGs don't have ambiguity, they are well suited for non-natural language parsing, especially programming language's parsing. Although PEGs are powerful, they have some problems. At first, rules of PEG have low reusability. And they don't have enable power to handle all pratical programming langauges. Considering so-called “modifiers” in several programming languages: there is a sequence of modifiers and each modifier occurs only once in the sequence. To recognize such modifier sequences, the size of the grammar may increase explosively. In this presentation, I propose Macro PEG, inspired by Macro grammar. Macro PEGs can express `permutation languages' concisely comparison with traditional PEGs. Also, I consider the relation between Macro PEGs and parser combinators. Parser combinators are a technique that build parsers by composing smaller parsers. At the last, I consider about Macro PEGs' expressiveness.

収録刊行物

キーワード

詳細情報 詳細情報について

  • CRID
    1050282812885044608
  • NII論文ID
    170000148434
  • NII書誌ID
    AA11464814
  • ISSN
    18827802
  • Web Site
    http://id.nii.ac.jp/1001/00177612/
  • 本文言語コード
    ja
  • 資料種別
    article
  • データソース種別
    • IRDB
    • CiNii Articles

問題の指摘

ページトップへ