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

Packrat Parsingを用いたRubyの構文解析

N/A
N/A
Protected

Academic year: 2021

シェア "Packrat Parsingを用いたRubyの構文解析"

Copied!
1
0
0

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

全文

(1)情報処理学会論文誌. プログラミング. Vol.5 No.3 63 (Aug. 2012). 発表概要. Packrat Parsing を用いた Ruby の構文解析 山口 大貴1,a). 前田 敦司1. 山口 喜教1. 2012年1月24日発表. 多くのスクリプト言語同様,Ruby は C や Java といった従来の言語と比較して非常に複雑な文法を持っ ている.そのため,構文解析器の作成において現在主流となっている,yacc(または bison)と lex を用 いて構文解析器と字句解析器を生成しそれらを組み合わせる手法では,文法の記述や実装が困難であっ たり実装が複雑化しメンテナンスが困難となってしまったりする場合がある.たとえば Ruby では,文 字列リテラルに任意の式を埋め込み可能な文法を実現するため等の理由で,手書きの字句解析器を含め て 8000 行以上にもおよぶ巨大な文法定義を行っている.これは,現在用いられている構文解析アルゴリ ズムが字句解析をベースとしているために,字句解析器に状態を付加する等のアドホックな実装を行わ なければこのような文法を実現することができないためである.そこで本研究では,Parsing Expression Grammar(PEG)をベースとした,強力な解析力を持つ構文解析アルゴリズム Packrat Parsing を Ruby 処理系(JRuby)に導入することを提案する.Packrat Parsing を実際に Ruby 処理系に用いることで,従 来の構文解析アルゴリズムで問題となっていた部分を改善し,文法定義の保守性を向上させることが本研 究の目標である.本研究の構文解析器の実装は,PEG をベースとした文法定義を Packrat Parser 生成系 Rats! に与えることで行い,その文法定義は従来の文法定義を変換することで作成する.また提案手法に よる処理系と従来手法による処理系に対して実際のスクリプトを使用した比較評価を行い,その結果とし て,提案手法によって文法定義の保守性が向上することを示す.. A Packrat Parser for Ruby Daiki Yamaguchi1,a). Atsushi Maeda1. Yoshinori Yamaguchi1. Presented: January 24, 2012. Like many other scripting languages, Ruby programming language has relatively complex grammar when compared with more conventional languages such as Java or C. This complex grammar makes traditional parser implementation using yacc (or bison) and lex difficult, complicated, or hard to maintain. For example, in Ruby, over 8000 lines of grammar rule definition (including hand-written scanner) is used to implement complex token syntax such as string literals that can embed Ruby expressions. Since traditional parsers are based on token lookahead, they need some ad-hoc implementation technique such as stateful scanners. In this presentation, we propose a Ruby parser using Packrat Parsing, a powerful parsing algorithm based on Parsing Expression Grammar (PEG). We also show that it is possible to resolve the problems in traditional methods and increase maintainability of the grammar rule definition. We rewrite the definition of the grammar into PEG-based style from existing yacc-style one, and generate Packrat Parser by Rats!, a Packrat Parser generator. We also perform evaluation of our parser in comparison with existing Ruby parser using real programs. As a result, we show that our grammar rule definition is better than existing one in terms of maintainability.. 1. a). 筑波大学大学院システム情報工学研究科 Graduate School of Systems and Information Engineering, University of Tsukuba, Tsukuba, Ibaraki 305–8573, Japan [email protected]. c 2012 Information Processing Society of Japan . 63.

(2)

参照

関連したドキュメント

Birdwhistell)は、カメラフィル ムを使用した研究を行い、キネシクス(Kinesics 動作学)と非言語コミュニケーションにつ いて研究を行いました。 1952 年に「Introduction

この見方とは異なり,飯田隆は,「絵とその絵

この 文書 はコンピューターによって 英語 から 自動的 に 翻訳 されているため、 言語 が 不明瞭 になる 可能性 があります。.. このドキュメントは、 元 のドキュメントに 比 べて

2021] .さらに対応するプログラミング言語も作

日本語で書かれた解説がほとんどないので , 専門用 語の訳出を独自に試みた ( たとえば variety を「多様クラス」と訳したり , subdirect

解析の教科書にある Lagrange の未定乗数法の証明では,

しかし,物質報酬群と言語報酬群に分けてみると,言語報酬群については,言語報酬を与

しかし , 特性関数 を使った証明には複素解析や Fourier 解析の知識が多少必要となってくるため , ここではより初等的な道 具のみで証明を実行できる Stein の方法