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

通信プロトコルコンパイラPreccsにおける正規表現パターンマッチングの高速化

N/A
N/A
Protected

Academic year: 2021

シェア "通信プロトコルコンパイラPreccsにおける正規表現パターンマッチングの高速化"

Copied!
1
0
0

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

全文

(1)Vol. 48. No. SIG 4(PRO 32). Mar. 2007. 情報処理学会論文誌:プログラミング. 発表概要. 通信プロトコルコンパイラ Preccs における 正規表現パターンマッチングの高速化 服. 部. 健. 太†,†† 平. 木. 敬††. Preccs は通信プロトコルの記述に特化したプログラミング言語であり,拡張した正規表現によっ てメッセージ形式を定義し,並行プロセス計算に基づいてメッセージの送受信手順を記述する.本発 表では,正規表現パターンマッチングを高速に行うために Preccs コンパイラが用いている 2 つの手 法について説明する.1 つ目は DFA によるパターンマッチングである.Preccs では正規表現を拡張 し,マッチしたフィールドの参照や,参照した値による繰返しマッチをサポートしているため,DFA を用いたパターンマッチングの手法は自明ではない.2 つ目はパターンマッチングのスキップである. ある正規表現とマッチしたメッセージに対して,さらに狭いパターンと再度マッチングを行う場合, すでにマッチ済みの事実を利用して,2 度目のマッチング処理の一部を省略することが可能になる.. Optimization Techniques for Regular Expression Pattern Matching in the Preccs Compiler Kenta Hattori†,†† and Kei Hiraki†† Preccs is a programming language for communication protocols. Message formats are defined with extended regular expression and rules for message sequences are defined with notation based on a concurrent process calculus. In this presentation, we describe two optimization techniques for regular expression pattern matching. The first is use of a DFA engine. It is not trivial to develop DFA for pattern matching, because regular expression is extended such that a part of matching pattern can be referred as value and iterative matching by the referred value is supported. The second is to skip matching characters. When trying to match again with a narrower pattern to a message matching with a ceratain pettern, it is possible to skip to a part of the process using the informations about the previous matching.. (平成 18 年 7 月 31 日発表). † 株式会社システム計画研究所 Research Institute of Systems Planning, Inc. †† 東京大学大学院情報理工学系研究科 Graduate School of Information Science and Technology, The University of Tokyo. 73.

(2)

参照

関連したドキュメント

「エピステーメー」 ( )にある。これはコンテキストに依存しない「正

 仮定2.癌の進行が信頼を持ってモニターできる

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

張力を適正にする アライメントを再調整する 正規のプーリに取り替える 正規のプーリに取り替える

本論文での分析は、叙述関係の Subject であれば、 Predicate に対して分配される ことが可能というものである。そして o

第2条第1項第3号の2に掲げる物(第3条の規定による改正前の特定化学物質予防規

各テーマ領域ではすべての変数につきできるだけ連続変量に表現してある。そのため

EC における電気通信規制の法と政策(‑!‑...