Mercurial > hg > Members > masakoha > seminar

comparison 2015/0512.html @ 25:ef709768b9cf

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add image
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Tue, 12 May 2015 19:06:48 +0900
parents 14d14dcb8219
children
comparison
equal deleted inserted replaced
24:14d14dcb8219 25:ef709768b9cf
100 </div> 100 </div>
101 </td> 101 </td>
102 </tr> 102 </tr>
103 <tr> 103 <tr>
104 <td><div align="right"> 104 <td><div align="right">
105 <name>Masataka Kohagura 5th, May , 2015</name> 105 <name>Masataka Kohagura 12th, May , 2015</name>
106 </div></td> 106 </div></td>
107 </tr> 107 </tr>
108 </tr> 108 </tr>
109 </table> 109 </table>
110 </div> 110 </div>
124 </li> 124 </li>
125 </ul> 125 </ul>
126 </div> 126 </div>
127 127
128 <div id="cover"> 128 <div id="cover">
129 <h1>今日の話題</h1>
130 <ul>
131 <li>
132 正規表現について
133 </li>
134 <li>
135 オートマトンについて
136 </li>
137 <li>
138 正規表現の基本三演算
139 </li>
140 <li>
141 正規表現の他の演算
142 </li>
143 </ul>
144 </div>
145
146 <div id="cover">
147 <h1>正規表現について</h1> 129 <h1>正規表現について</h1>
148 <ul> 130 <ul>
149 <li> 131 <li>
150 文字列の一部をパターン化して表現する手法 132 文字列の一部をパターン化して表現する手法
151 </li> 133 </li>
152 <li> 134 <li>
153 文章からあるパターン文字列を検索したいときに使用する <br> 135 文章からあるパターン文字列を検索したいときに使用する <br>
154 (e.g. 「ed」が末尾に含まれる英単語を検索する場合 : .*ed) 136 (e.g. 「ed」が末尾に含まれる英単語を検索する場合 : .*ed)<br>
155 </li> 137 . (ピリオド) : 改行コード以外の任意の1文字<br>
156 <li> 138 * : 直前の文字の 0 回以上の繰返し
157 正規表現は有限オートマトンで表現できる
158 </li> 139 </li>
159 </ul> 140 </ul>
160 </div> 141 </div>
161 142
162 <div id="cover"> 143 <div id="cover">
163 <h1>オートマトンについて</h1> 144 <h1>オートマトンについて</h1>
164 <ul> 145 <ul>
165 <li> 146 <li>
166 入力に対して内部の状況に応じた処理を行う結果を出力する仮想的な自動機械の概念 147 入力に対して内部の状況に応じた処理を行う結果を出力する仮想的な自動機械の概念
167 </li> 148 </li>
149 <li>
150 正規表現はオートマトンで表現することができる。
151 </li>
152 <li>
153 非決定性有限オートマトン NFA(Non-deterministic Finite Automaton)と、非決定性有限オートマトンDFA(Deterministic Finite Automaton)が存在する。
154 </li>
155 <li>
156 非決定性有限オートマトン : 1つの入力に対して複数の遷移先が存在する
157 </li>
158 <object data="images/vector/nfa.svg" type="image/svg+xml"></object>
159 <li>
160 決定性有限オートマトン : 1つの入力に対して遷移先が1つだけ
161 </li>
162 <object data="images/vector/dfa.svg" type="image/svg+xml"></object>
163
168 </ul> 164 </ul>
169 </div> 165 </div>
170 166
171 <div id="cover"> 167 <div id="cover">
172 <h1>正規表現の基本三演算</h1> 168 <h1>正規表現の基本三演算</h1>
173 <ul> 169 <ul>
174 <li> 170 <li>
175 正規表現は「連接」「選択」「繰返し」の演算が備えられている 171 正規表現は「連接」「選択」「繰返し」の演算が備えられている<br>
176 R,S という 2 つの正規表現が存在すると仮定する。<br> 172 R,S という 2 つの正規表現が存在すると仮定する。<br>
177 <b>連接 「RS」</b>: R の直後に S が続くパターン<br> 173 <b>連接 「RS」</b>: R の直後に S が続くパターン<br>
178 <ul>(e.g.) RS, RRS, RSS, RRSS, ...<br></ul> 174 <ul>(e.g.) RS, RRS, RSS, RRSS, ...<br></ul>
175 <object data="images/vector/rensetsu.svg" type="image/svg+xml"></object><br>
179 <b>選択 「R|S」</b>: R もしくは S が出現するパターン<br> 176 <b>選択 「R|S」</b>: R もしくは S が出現するパターン<br>
180 <ul>(e.g.) R, S, RS, ...<br></ul> 177 <ul>(e.g.) R, S, RS, ...<br></ul>
178 <object data="images/vector/sentaku.svg" type="image/svg+xml"></object><br>
181 <b>繰返し 「R*S」</b>: 「*」の直前(R)が 0 回以上出現するパターン<br> 179 <b>繰返し 「R*S」</b>: 「*」の直前(R)が 0 回以上出現するパターン<br>
182 <ul>(e.g.) S, RS, RRS, RRRS, ...</ul> 180 <ul>(e.g.) S, RS, RRS, RRRS, ...</ul><br>
181 <object data="images/vector/star.svg" type="image/svg+xml"></object><br>
183 </li> 182 </li>
184 <li> 183 <li>
185 基本三演算は結合順位が存在する<br> 184 基本三演算は結合順位が存在する<br>
186 <ul>繰返し &gt; 連接 &gt; 選択</ul> 185 <ul>繰返し &gt; 連接 &gt; 選択</ul>
187 </li> 186 </li>
200 <li> 199 <li>
201 <b>「R?S」</b>: 「?」の直前のパターンが 0 or 1 回出現するパターン<br> 200 <b>「R?S」</b>: 「?」の直前のパターンが 0 or 1 回出現するパターン<br>
202 <ul>(e.g.) S, RS</ul> 201 <ul>(e.g.) S, RS</ul>
203 </li> 202 </li>
204 <li> 203 <li>
205 <b>「R{1,3}」</b>: 「{}」の直前のパターンが 1 or 3 回出現するパターン<br> 204 <b>「R{1,3}」</b>: 「{}」の直前のパターンが 1 〜 3 回出現するパターン<br>
206 <ul>(e.g.) R, RR, RRR</ul> 205 <ul>(e.g.) R, RR, RRR</ul>
207 </li> 206 </li>
208 <li> 207 <li>
209 <b>「R{1,}」</b>: 「{}」の直前のパターンが 1 回以上出現するパターン<br> 208 <b>「R{1,}」</b>: 「{}」の直前のパターンが 1 回以上出現するパターン<br>
210 <ul>(e.g.) R, RR, RRR, ...</ul> 209 <ul>(e.g.) R, RR, RRR, ...</ul>
211 <ul>R+S ≡ R(R*)S ≡ R{1,}S</ul> 210 <ul>R+S ≡ R(R*)S ≡ R{1,}S</ul>
212 </li> 211 </li>
213 </ul> 212 </ul>
213 </div>
214
215 <div id="cover">
216 <h1>実装について</h1>
217 まずは基本三演算を実装していく。
218 <ul>
219 <li>
220 R*(T|S)U をオートマトンで表現してみる
221 </li>
222 <object data="images/vector/rtsu-automaton.svg" type="image/svg+xml"></object>
223 <li>
224 状態と入力に対する遷移先、遷移したかどうかフラグで管理する。
225 </li>
226 <pre>
227 <code>
228 typedef struct Automaton {
229 int state;
230 unsigned char input_char;
231 int next_state;
232 bool next_state;
233 };
234 </code>
235 </pre>
236 <object data="images/vector/rtsu-automatondata.svg" type="image/svg+xml"></object>
237 </ul>
214 </div> 238 </div>
215 239
216 <!-- 240 <!--
217 <div id="cover"> 241 <div id="cover">
218 <h1>prog</h1> 242 <h1>prog</h1>