基礎理論 - 1.基礎理論 - 3.情報に関する理論 - 5.形式言語

Last Update : January 02 2021 16:00:16

     

a. 形式言語

プログラム言語のように、厳格な文法によって生成された言語を形式言語といいます。

文脈自由文法
定義が必要なもの(数式、演算子、数字など)を非終端記号といい、0 や 7 など定義を伴わないもの(それ以上分解できないもの)を終端記号といいます。そして、数値を「-1.25」とか数式を「-3+2.16×5」というように、非終端記号は最終的には終端記号の並びで表現できます。
 「文脈自由」という用語は、前後関係に依存せずに非終端記号を終端記号に置換できることを意味しています。そして、文脈自由文法によって生成される形式言語を文脈自由言語といいます。
例えば
 「数式とは数字列と演算子からなる」
 「数字列とは、符号、数字の並び、小数点、数字の連続からなる」
 「数字とは、0、1、…、9のいずれかである」
などと定義することにより、 数式の表現方法を厳密に定義できる。また、ある文字列が数式として正しいかどうかを判断できる。

文脈自由文法の代表的な記法として、「BNF」 がある。 図法にしたものに「構文図」がある。  

逆ポーランド記法
「数式をコンピュータで処理しやすいように変換したもの」。後置記法 (Postfix Notation) とも言う。
演算子を被演算子の後ろに記述する方法。括弧を使わずに記述できる。


30 - 2 * 10 + 5 を計算させる式を
30 2 10 * - 5 + と表記する。

これは、日本語の表現の『30から2と10を掛けた値を引き、それに5を加算する』と言う表現に適合する。
式中の演算対象の値を括弧で囲み、演算子を括弧の外側の右に置き、最後に括弧とカンマを消すと得られる。
f = a - b ÷ ( c + d )
f = a - b ÷ ( c , d ) +
f = a - ( b ÷ ( c ,d ) + )
f = a - ( b , ( c , d ) + ) ÷
f = ( a - ( b , ( c , d ) + ) ÷ )
f = ( a , ( b , ( c , d ) + ) ÷  ) -
(
f = ( a , ( b , ( c , d ) + ) ÷  ) - )
( f , ( a , ( b , ( c , d ) + ) ÷  ) - ) =
これから、括弧とカンマをはずす
f a b c d + ÷ - =
 
 この表記順に式が並べられる時、単純なスタック操作で演算結果を求めることができる。
それは、『数値や変数ならスタックに入れ、演算子ならスタックから2つ取り出して、演算結果をスタックに入れる
を繰り返せばよい。これで、最終演算結果がスタックに残る。
先ほどの f = 30 - 2 * 10 + 5  →  f 30 2 10 * - 5 + =


変数 数字 数字 数字 演算子 演算子 数字 演算子 演算子
f 30 2 10 2 * 10 30 - 20 5 10 + 5 f = 15
 
      10          
    2 2 20   5    
  30 30 30 30 10 10 15  
f f f f f f f f  

※ポーランド記法(前置記法)
演算子(オペレータ)を被演算子(オペランド)の前(左)に記述する。


b. BNF バッカス・ナウア記法(Backus-Naur Form)

「BNF」とは、「プログラム言語の文法を厳密に表現する」もので、すべて文字のみで表現します。表現方法には、「順次」「選択」「反復」があります。
●順次
<x>::=<a><b>
ここで、「::=」は定義するという意味です。この場合、「x」という構文はaとbの並びであるという意味です。
●反復
<x>::=<a>・・・
これは、「x」という構文は、「a」という文字の繰り返しの意味です。
●選択
<x>::=<a | b>
これは、「x」という構文は、aかまたはbであるという意味です。
<x>::=[<a>]
これは、「x」という構文は、aか空であるという意味です。


<>・・・括弧<>の中の文字列は1つのメタ変数である。
  <>で囲まれているものは非終端記号。<>で囲まれていないものは終端記号
::=・・・左辺が右辺のように定義されているという意味である。
| ・・・または(or)

「<○○> ::= △△」は、「○○とは△△の構成になる」という意味です。
「○○|△△」は、「○○または△△のどちらかを選択せよ」の意味です。
「<数字列> ::= <数字>|<数字列><数字>」
数字列を3、数字を9とすれば、「<数字列> ::= <数字列><数字>」ですから、39は数字列です。

[例]
<数字> ::= ("0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9")
<数字列> ::= <数字> | <数字> <数字列>
<式> ::= <数字列> | <数字列> ("+" | "×" | "-" | "÷") <式> | "(" <式> ")"


c. 正規表現

正規表現とは、文字列のパターンを示す表現方法。
パターンを表現するための特別な文字をメタ文字と言い以下の文字が使用される。


メタ文字 意味 記述例 記述例の意味
. 任意の一文字 A .. D Aで始まり、Dで終わる4文字の文字列
(文字列) 文字列を1つのパターンとして扱う (ABCD)  
+ 直前の文字やパターンの1回以上の繰り返し ABX+ ABとXの1回以上の繰り返し
ABX , ABXX , ABXXX
(AB)+ パターンABの一回以上の繰り返し
AB , ABAB , ABABAB
* 直前の文字やパターンの0回以上の繰り返し ABX* ABとXの0回以上の繰り返し
AB , ABX , ABXX , ABXXX
? 直前の文字やパターンの0または1回の繰り返し ABCD? ABCまたはABCD
次に続く文字またはメタ文字ではなく、文字そのものとして扱う AB¥* 文字列AB*
| 文字やパターンの選択 A | B AまたはB
(AB)|(CDE) パターンABまたはCDE
[ ] [ ]の中のどれか一文字 [1-9] 1から9までのいずれか一文字
[ABCD] A,B,C,Dいずれか一文字
[A-D]
^ 行頭 ^A 行の先頭がAで始まる
$ 行末 Z$ 行の終わりがZのもの


整数・・・[+-]?[0-9]+ 整数値は先頭が符号(+,-)がないか一文字あり、符号に続いて1文字以上の0から9までの数字が並ぶ
小数・・・[+-]?[0-9]+¥.[0-9]+ 小数は整数に小数点と小数部の数値を付加する
浮動小数点数・・・[+-]?[0-9]+¥.[0-9]+e[+-]?[0-9]+ 小数に対して指数部を追加したもの +1.34×103 = +1.34e3
郵便番号・・・^[0-9]{3}-[0-9]{4}$


d. 構文図

構文図(Syntax Chart)とは、BNF と同じような内容を視覚的に図式化するための図法です。
下の図は、数値を定義した構造図です。数値とは数字を繰り返したものと定義しています。


  [ 例題 ] 
  1. 平成26年度秋期 問04  後置記法 逆ポーランド記法
  2. 平成25年度春期 問06  逆ポーランド記法
  3. 平成23年度秋期 問04  BNF
  4. 平成22年度春期 問03  逆ポーランド記法
  5. 平成21年度秋期 問03  逆ポーランド記法
  6. 平成20年度春期 問11  BNF
  7. 平成18年度春期 問10  後置表記法
  8. 平成18年度秋期 問12  後置記法
  9. 平成17年度秋期 問10  正規表現
  10. 平成15年度春期 問11  BNF


     

www.it-shikaku.jp