1．1 オートマトンと状態遷移図

２．３形式言語のモデル化
（１）メタ言語（metalanguage）
■言語を定義する言語＝メタ言語
①バッカス記法、BN記法（Buckus-naur Form）, BNF
②構文図（syntax diagram）
③COBOL記法
④正規表現
（２）バッカス記法
■数字が０～９、英字がA～Z, a～z
<数字>::=0|1|2|3|4|5|6|7|8|9
<英字>::=A|B|C|D|E|F|G|H|I|J|K|L|M|
N|O|P|Q|R|S|T|U|V|W|X|Y|Z|
a|b|c|d|e|f|g|h|i|j|k|l|m|
n|o|p|q|r|s|t|u|v|w|x|y|z
バッカス記法その他の例（その１）
■識別子（変数名や関数名）
<識別子>::=<英字>|<英字><英数字列>
<英数字>::=<英字>|<数字>
<英数字列>::=<英数字>| <英数字> <英数字列>
【識別子の例】
A B x z <英字>
AA Ab AZ <英字><英数字列>→<英字><英数字>→<英字><英数字>
C2 Z3 X6 <英字><英数字列>→<英字><英数字>→<英字><数字>
AB1 MY8
<英字><英数字列>→<英字><英数字><英数字列>
→<英字><英字><英数字列>→<英字><英字><英数字>
→<英字><英字><数字>
バッカス記法その他の例（その２）
■if文（C）
<if文>::=if(論理式）<ブロック>|
if(論理式）<ブロック>else <ブロック>
<複文>::=<文>|<文><複文>
<ブロック>::=<文>|｛<複文>}
バッカス記法の論理式としての解釈
■識別子（Prolog表現）
識別子([A]):=英字(A).
識別子([A|LL]:=英字(A),英数字列(LL).
英数字(A):=英字(A).
英数字(A):=数字(A).
英数字列([A]):=英数字(A).
英数字列([A|LL]):=英数字(A),英数字列(LL)
数字(‘0’).
数字(‘1’).
・
・
・
数字(‘9’).
数字(‘A’).
数字(‘B’).
・
・
・
数字(‘Z’).
数字(‘a’).
数字(‘b’).
・
・
・
数字(‘z’).
バッカス記法の特徴
【長所】
言語仕様を厳密に定義するのに適している。
【短所】
右辺に同じような表現が多数出てくる場合が
あり、見づらくなることがある。
（３）構文図
■文法を図式的に表現する
識別子
英字
英字
数字
■If文
構文図の例
If文
if(
式
）
else
文
文
（４）正規表現
記号（Symbol）
: アルファベットの各記号aについて文字aだけを含
む言語
選択（Alternation） : ２つの正規表現AとBが与えられたとき、A | B は
「AまたはB」を表す。
連接（Concatenation） : ２つの正規表現AとBが与えられたとき、A・B は
「AとBが連続する」ことを表す。
空（ε）
：正規表現εは「空の文字列」だけを含むことを表
す。
反復（Repetition）
: 正規表現A*は「Aのゼロ個以上の連接からなる
文字列。正規表現A+は「Aの１個以上の連接か
らなる文字列
すなわち A*=(A+|ε)
また、{ 0|1|2|3|4|5|6|7|8|9 } をA=[0-9]のように表記することもある。
正規表現のあいまいさの排除
■最長一致（Longest Match）
正規表現に一致する入力の部分文字列のうち最長の文字
列を次のトークンにする
■優先規則（Rule Priority）
最長部分文字列のうち最初に一致する表現がそのトークン
を決定する。
【例】 if5 : 最長一致により識別子、
if : 優先規則により予約語

Download Report