オートマトン (6)

sys6.pdf sys.pdf sys-s.pdf 記事一覧

＜expr＞ の構文図

#65: 構文図

BNF や EBNF の構文は図で表わすと見やすくなります．上図は乗算を加算に優先して計算する式の構文図です．「式とは？」「項の和（や差）」＞「項とは？」「因子の積（や商）」＞「因子とは？」「数（定数，変数）または式を（ ）で囲ったもの」--- 式とは何か，と定義を辿っていくと定義の中に式自体が現れます．このような定義は再帰的であるといい，再帰的表現によって定義を簡潔に表現できます．
※ 上図では BNF との対応を分かりやすくするため ＜ ＞ や “ ” で囲っていますが，実際には省略します．

補足：(1) 再帰的な定義でも，スタックを用いることにより再帰のない関数でも処理できます．ただし，このためには再帰から有限回で脱出できる構文になっていることが必要です．上例で言えば「数（定数，変数）または式を（ ）で囲ったもの」の「数」の方に分岐することで脱出できます．
(2) if-then-else 文でも 「"else if"」の繰返し部分がループになります．構文解析の結果を木で表示できるのは，通常のプログラムでは適当なところで“脱出”しているためです．

[6-1] 記号処理・第 3 回 1 構文図
  http://www602.math.ryukoku.ac.jp/~nakano/Compiler/printed/part03.pdf
[6-2] Ⅲ プログラム言語の文法(構文図) -続き-
  http://user.numazu-ct.ac.jp/~fujio/personal/jp/kougi/progen/text/3-2.pdf
[6-3] BNF（形式言語）＜ハードウェアとソフトウェア＜Web教材＜木暮仁
  http://www.kogures.com/hitoshi/webtext/hs-bnf/index.html
[6-4] 前の問題 - 「情報処理試験.jp」平成15年 秋期 基本情報技術者 問題と ...
  http://情報処理試験.jp/FE15b-am/t11.html （ブラウザに貼り付けてください）

オートマトン (5)

sys6.pdf sys.pdf sys-s.pdf 記事一覧

逆ポーランド記法の式の表現

#64: メタ言語

言語仕様を記述する言語をメタ言語といいます．EBNF はプログラミング言語の構文の記述に広く用いられています．

補足：(1)「＜num＞::="a"|"b"」は非終端記号＜num＞は"a"または"b"で置き換えてよいことを示しています．EBNF では「num = "a", "b";」になります．
(2) Ｃ の if 文は EBNF では「if-statement = "if" "(" expression ")" statement ;」のようになります．末尾の「;」は ENBF の「;」で Ｃ で使う「;」とは関係ありません．
(3) Java の言語仕様では「IfThenStatement : if ( Expression ) Statement」のように非終端記号を斜体にしています．

[5-] メタ言語 - Wikipedia
  http://ja.wikipedia.org/wiki/%E3%83%A1%E3%82%BF%E8%A8%80%E8%AA%9E
[5-] バッカス・ナウア記法 - Wikipedia
  http://ja.wikipedia.org/wiki/%E3%83%90%E3%83%83%E3%82%AB%E3%82%B9%E3%83%BB%E3%83%8A%E3%82%A6%E3%82%A2%E8%A8%98%E6%B3%95
[5-] EBNF - メインページ - Wikipedia
  http://ja.wikipedia.org/wiki/EBNF
-------------------------
[5-] ISO-14977
  http://www.cl.cam.ac.uk/~mgk25/iso-14977.pdf
[5-] EBNF - School of Computer Science
  http://www.cs.cmu.edu/~pattis/misc/ebnf.pdf
[5-] The Java Language ...
  http://docs.oracle.com/javase/specs/jls/se5.0/html/j3TOC.html

オートマトン (4)

sys6.pdf sys.pdf sys-s.pdf 記事一覧

逆ポーランド記法の式の導出木

#63: 文脈自由文法

一般の句構造文法は複雑過ぎるので，正規表現の次に簡単な文脈自由言語を生成する文脈自由文法について説明しました．

補足：(1) 句構造文法を表わす 4-tuple に用いる記号は定まっていないようです．[0-1] では (N, T, P, S)，[4-1] では (N, Σ, P, S)，[4-3] では (V, Σ, R, S) です．1960年代に教わった [4-11] の (V, Σ, P, σ) のV は [4-3] の V と異なり N ∪ T でした．
(2) 逆ポーランド記法や文脈依存文法には言及しませんでした．
(3) 正規表現できなかった {aⁿ bⁿ ; n は自然数} は文脈自由言語です．なお，{aⁿ bⁿ cⁿ; n は自然数} は文脈自由文法で記述できない文脈依存言語です．
(4) 句構造文法の書き換え規則は [0-1] 第４章の式より [4-4] の式の方が正しいと思います --- (N ∪ T)⁺ でなく (N ∪ T)^* - T^*．

[4-1] 形式文法 - Wikipedia
  http://ja.wikipedia.org/wiki/%E5%BD%A2%E5%BC%8F%E6%96%87%E6%B3%95
[4-2] チョムスキー階層 - Wikipedia
  http://ja.wikipedia.org/wiki/%E3%83%81%E3%83%A7%E3%83%A0%E3%82%B9%E3%82%AD%E3%83%BC%E9%9A%8E%E5%B1%A4
[4-3] 文脈自由文法 - Wikipedia
  http://ja.wikipedia.org/wiki/%E6%96%87%E8%84%88%E8%87%AA%E7%94%B1%E6%96%87%E6%B3%95
[4-4] 11回目：句構造文法とチューリング機械
  http://www.enel.ucalgary.ca/People/far/Lectures/Automaton/PDF/11kaime.pdf
[4-5] 逆ポーランド記法 - Wikipedia
  http://ja.wikipedia.org/wiki/%E9%80%86%E3%83%9D%E3%83%BC%E3%83%A9%E3%83%B3%E3%83%89%E8%A8%98%E6%B3%95
-----------------------------------
[4-6] 形式言語 - Wikipedia
  http://ja.wikipedia.org/wiki/%E5%BD%A2%E5%BC%8F%E8%A8%80%E8%AA%9E
[4-7] 文脈依存文法
  http://ja.wikipedia.org/wiki/%E6%96%87%E8%84%88%E4%BE%9D%E5%AD%98%E6%96%87%E6%B3%95
[4-8] 生成文法 - Wikipedia
  http://ja.wikipedia.org/wiki/%E7%94%9F%E6%88%90%E6%96%87%E6%B3%95
[4-9] 一般化句構造文法 - Wikipedia
  http://ja.wikipedia.org/wiki/%E4%B8%80%E8%88%AC%E5%8C%96%E5%8F%A5%E6%A7%8B%E9%80%A0%E6%96%87%E6%B3%95
[4-10] 主辞駆動句構造文法 - Wikipedia
  http://ja.wikipedia.org/wiki/%E4%B8%BB%E8%BE%9E%E9%A7%86%E5%8B%95%E5%8F%A5%E6%A7%8B%E9%80%A0%E6%96%87%E6%B3%95
[4-11] The Mathematical Theory of Context-Free Languages
  http://dl.acm.org/citation.cfm?id=1102023

オートマトン (3)

sys6.pdf sys.pdf sys-s.pdf 記事一覧

記号列の集合の表現

#62: 正規表現

正規表現はエディタで語句を検索するときにも使用されていますが，定義は省略しました．正規表現で定義できる言語（記号列の集合の部分集合）は右線形文法（や左線形文法），有限状態のアクセプタでも定義できます．

補足：(1) 記号列の集合{aⁿ bⁿ ; n は自然数} は正規表現不能．
(2) 右線形文法は状態遷移図と直接的に対応しています．

[3-1] 正規表現 - Wikipedia
  http://ja.wikipedia.org/wiki/%E6%AD%A3%E8%A6%8F%E8%A1%A8%E7%8F%BE
[3-2] 正規言語 - Wikipedia
  http://ja.wikipedia.org/wiki/%E6%AD%A3%E8%A6%8F%E8%A8%80%E8%AA%9E
[3-3] 正規文法 - Wikipedia
  http://ja.wikipedia.org/wiki/%E6%AD%A3%E8%A6%8F%E6%96%87%E6%B3%95
[3-4] 3_4.pdf(115KB)
  http://ocw.kyushu-u.ac.jp/0005/0003/lecture/3_4.pdf
-------------------
[3-5] オートマトンと形式言語 正規表現
  http://kurt.scitec.kobe-u.ac.jp/~kikyo/lec/06/automaton/k5.pdf
[3-6] 2.5 正規表現と正規集合
  http://ocw.kyushu-u.ac.jp/0005/0003/lecture/2_5.pdf

オートマトン (2)

sys6.pdf sys.pdf sys-s.pdf 記事一覧

有限オートマトンのアクセプタ

#61: アクセプタ

記号列が所定の条件を満たしているか否かを識別する機械（アクセプタ）の例として，[#60] の順序回路の出力か否かを調べる機械の状態遷移図を上図に示しました．
※ (#60) の一部を付録（@60）にまわし，本文の内容を例題中心に変えました．(#) の内容もこれに連携しています．

補足：(1) 単に「有限オートマトン」というときは有限状態のアクセプタを指すことが多いようです．上図の式の説明は付録に回ってしまいましたので補足します．δは状態遷移関数，q_p は初期状態，{q_n, q_p} は最終状態の集合です．最終状態とは入力記号列を読み終わったときの状態ですが，「読み終わった」ことの意味はδの定義域を Q×Σ から Q×Σ^* に拡張した式で説明できます [0-1](第２章)．なお，δの定義域は Q×Σの部分集合でもよく，このときは遷移が未定義になったときも「読み終わった」と考えます（上図の状態遷移図で q_e を省いてもよい）．
(2) 非決定性有限オートマトンの説明は省きました．
(3) 文字列の連接を積と考えると，空列は単位元に相当しますが，逆元は考えません [2-3]．
(4) 文字列は終端記号の記号列，アルファベットは終端記号の集合．生成文法には非終端記号も現れます [2-4]．

[2-1] 有限オートマトン - Wikipedia
  http://ja.wikipedia.org/wiki/%E6%9C%89%E9%99%90%E3%82%AA%E3%83%BC%E3%83%88%E3%83%9E%E3%83%88%E3%83%B3
[2-2] 決定性有限オートマトンと非決定性有限オートマトンについて詳しくのって
  http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1380950358
[2-3] 半群 - Wikipedia
  http://ja.wikipedia.org/wiki/%E5%8D%8A%E7%BE%A4
[2-4] プログラミング言語論
  http://www.cck.dendai.ac.jp/~koyama/pl/m/2011-02syntax.pdf