• 検索結果がありません。

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

N/A
N/A
Protected

Academic year: 2021

シェア "PEGのパラメタ付き拡張Macro PEGの提案"

Copied!
1
0
0

読み込み中.... (全文を見る)

全文

(1)情報処理学会論文誌. プログラミング. Vol.10 No.2 1 (Feb. 2017). 発表概要. PEG のパラメタ付き拡張 Macro PEG の提案 水島 宏太1,a) 2016年8月10日発表. PEG は,2004 年に Ford によって発表された解析的形式的文法の 1 つである.PEG は非常にシンプル であるにもかかわらず,広い範囲の文法を解析することができる(一部の文脈依存言語を含む).また, Packrat Parsing という構文解析アルゴリズムによって,PEG で表現可能な任意の言語は線形時間で解析 できるという好ましい性質を持っている.PEG の解析木は必ず一意に定まるため,プログラミング言語の 構文解析器など,非自然言語の構文解析に向いている.PEG はその強力さにもかかわらず,いくつかの問 題がある.まず,PEG の規則は再利用性が低い.また,現実のプログラミング言語の文法要素を扱うため には必ずしも十分な能力を持っていない.たとえば,複数の修飾子が順不同で出現するというパターンを 認識するためには,通常の PEG ではすべてのパターンを書き下す必要があり,修飾子の数が増えると文 法の規模が爆発的に増加してしまう.本発表では,Macro Grammar を参考に,PEG がパラメタを取れる ように拡張した Macro PEG を提案する.Macro PEG では,先ほどあげたような文法を簡潔に記述する ことができる.また,本発表では,Macro PEG とパーザコンビネータとの関係について考察する.パー ザコンビネータとは,主に関数型プログラミング言語で用いられる手法であり,関数合成によってパーザ を組み立てる.最後に,本発表では,Macro PEG がどのような計算能力を持つのかについて考察を行う.. Macro PEG: PEG with Macro-like Rules Kota Mizushima1,a) Presented: August 10, 2016. 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.. 1 a). 株式会社ドワンゴ DWANGO Co., Ltd., Chuo, Tokyo 104–0061, Japan kota [email protected]. c 2017 Information Processing Society of Japan . 1.

(2)

参照

関連したドキュメント

行列の標準形に関する研究は、既に多数発表されているが、行列の標準形と標準形への変 換行列の構成的算法に関しては、 Jordan

そのため本研究では,数理的解析手法の一つである サポートベクタマシン 2) (Support Vector

外声の前述した譜諺的なパセージをより効果的 に表出せんがための考えによるものと解釈でき

 オランダ連合東インド会社による 1758 年の注文書 には、図案付きでチョコレートカップ 10,000 個の注 文が見られる

それでは,従来一般的であった見方はどのように正されるべきか。焦点を

これらの定義でも分かるように, Impairment に関しては解剖学的または生理学的な異常 としてほぼ続一されているが, disability と

析の視角について付言しておくことが必要であろう︒各国の状況に対する比較法的視点からの分析は︑直ちに国際法

  支払の完了していない株式についての配当はその買手にとって非課税とされるべ きである。