計算理論：巴科斯正規化

試卷 1 - ⇑ 計算理論 ⇑
← 正則表示式	巴科斯正規化	演算法分類 →

巴科斯正規化（也稱為巴科斯正規化 (BNF) 或簡稱BNF）是一種用於表達計算機語言語法的符號技術。表示式被放在列表中，可用於檢查所寫語法的有效性。

結構和佈局

符號

BNF 使用以下符號表示

 ::=   'is defined as'
 |     'or'
 <>    category names

這些符號的佈局方式如下

 <Parent Expression> ::= <Child Expression 1> | <Child Expression 2>

簡單來說，上面的表示式表示“父表示式定義為子表示式 1 或子表示式 2”。這意味著要構成父表示式，它必須包含一個子表示式，而子表示式又是由其他東西組成的。

示例

在本例中，BNF 結構正在分解語法以建立

家庭住址的巴科斯正規化分解

 <Address> ::= <House Number> <Street Name> <Town Name> <City Name> <Country> <Postcode> | <House Number> <Street Name> <City Name> <Country> <Post Code>

 <Postcode> ::= <Area Code> <Street Code>
 <Area Code> ::= <City Prefix> <digit> | <City Prefix> <digit> <digit>
 <Street Name> ::= <Name> <Street Type>
 <Flat Number> ::= <character> | <digit>
 <House Number> ::= <number> | <digit> <number>
 <number>::= <digit> | <digit> <number>
 <Name> ::= <string>
 <Street Type> ::= <string>
 <City Prefix> ::= <string>
 <Street Code> ::= <string>
 <Town Name> ::= <string>
 <City Name> ::= <string>
 <Country> ::= <string>
 <string> ::= <character> | <character><string>
 <character> ::= A|B|C|D|E|F|G|H|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z
 <digit> ::= 0|1|2|3|4|5|6|7|8|9

練習題

使用上面關於地址的示例中的 BNF，說明每個輸入是否有效輸入。

15 Jubilee Lane Blackpool England FY98 5ER

答案

否

15 Jubilee Lane Blackpool England FY423 5ER

答案

否

32 Parkstone Road Syston England Leicester LE7 3ZY

答案

否