--- title: "使用巴科斯範式(BNF/EBNF/ABNF)定義語言" description: "瞭解如何使用巴科斯範式及其擴展來定義語言" # image: https://hackmd.io/screenshot.png tags: BNF,EBNF,ABNF # robots: noindex, nofollow langs: zh-Hant --- # 前言 本筆記參考[The language of languages]的文章,來瞭解如何使用巴科斯範式及其擴展來定義語言。 # 使用巴科斯範式(BNF/EBNF)定義語言 語法定義了一種語言(A grammar defines a language)。 每種語言的背後都有一種語法,它決定了語言的結構。 上下文無關語法(context-free grammar)是在計算機科學中最常見的語法類型。 上下文無關語法能描述語言的遞歸語法結構。 ## 上下文無關語法語法的構成元件 一組規則(rules)是語法的核心組成部分。 規則都有兩個部分: 1. 名稱 2. 名稱的擴充。 定義英文名詞語法的規則: > **名詞片語(noun-phrase)** 可能擴充為 **文章名詞(article noun)**. - *dog*是名詞片語。 描述一種編程語言的規則: > **表達式(expression)** 可能擴充為 **表達式** + **表達式** 若以數學符號$\rightarrow$來表示「可以擴充為」: > noun-phrase $\rightarrow$ article noun expression $\rightarrow$ expression + expression 以下是經典的精確表達式語法, 由第2,3,4,6,7規則可以得出$3*7$是有效的表達式: - $\mathit{expr}$ : 表達式 - $\mathit{term}$ : 項 - $\mathit{factor}$ : 因子 - $\mathit{const}$ : 常數 - $\mathit{integer}$ : 整數 $$ \mathit{expr} \rightarrow \mathit{term}\; \mathtt{+}\; \mathit{expr} ~~ (1) \\ \mathit{expr} \rightarrow \mathit{term} ~~ (2) \\ \mathit{term} \rightarrow \mathit{term}\; \mathtt{*}\; \mathit{factor} ~~ (3) \\ \mathit{term} \rightarrow \mathit{factor} ~~ (4) \\ \mathit{factor} \rightarrow \mathtt{(}\;\mathit{expr}\;\mathtt{)} ~~ (5) \\ \mathit{factor} \rightarrow \mathit{const} ~~ (6) \\ \mathit{const} \rightarrow \mathit{integer} ~~ (7) $$ ## Backus-Naur Form (BNF) notation 在描述語言時,巴科斯範式(Backus-Naur Form)是正式表示法,應用於供人類消耗的編碼語法。 每個規則都具有以下結構: $$ \mathit{name} ::= \mathit{expansion} $$ - 符號 $::=$ 表示「可以擴充為」或「可以替換為」 - $\mathit{name}$ 也稱為**非終端符(non-terminal symbol)**。 - BNF的每個 $\mathit{name}$ 都用**尖括號**`<>`包圍,無論它出現在規則的左側還是右側。 - $\mathit{expansion}$ 是一個包含**終端符**和**非終端符**的表達式,通過排序和選擇將它們連接在一起。 - **終端符(terminal symbol)** 是像`"+"`或`"function"`或`integer`的文字 - 並置(juxtaposition)的表達式代表**檢測順序** - $\mathit{expansion} ::= \mathit{expansion}~ \mathit{expansion}$ - 豎條`|`代表**選擇(choice)**: - ` <expr> ::= <term> "+" <expr> | <term>` 將經典的精確表達式語法以BNF表示: ```bnf <expr> ::= <term> "+" <expr> | <term> <term> ::= <factor> "*" <term> | <factor> <factor> ::= "(" <expr> ")" | <const> <const> ::= integer ``` 自然地,我們可以為BNF中的規則定義語法: $$ \mathit{rule} \rightarrow \mathit{name} ::= \mathit{expansion} \\ \mathit{name} \rightarrow \mathit{<identifier>} \\ \mathit{expansion} \rightarrow \mathit{expansion} ~ \mathit{expansion} \\ \mathit{expansion} \rightarrow \mathit{expansion} ~|~\mathit{expansion} \\ \mathit{expansion} \rightarrow \mathit{name} \\ \mathit{expansion} \rightarrow \mathit{terminal} $$ - 我們可能使用正則表達式`[-A-Za-z_0-9] +`來定義標識符(identifier)。 - 終端可以是帶引號的文字(例如`"+"`,`"switch"`或`"<<="`),也可以是類別名稱的文字(例如`integer`)。 ## Extended BNF (EBNF) notation 擴展巴科斯範式(Extended BNF)是巴科斯範式的擴展集合。它允許在擴充中的附加操作。 ### 可選擇性的項目 在EBNF中,若方括號包圍著擴充`[expansion]`,表示此擴充是可選擇性的項目。 例如負數的規則如下: ``` <term> ::= [ "-" ] <factor> ``` ### 重複 在EBNF中,花括號`{}`表示該表達式可以重複零次或更多次。 例如常規逗號分隔參數列表的規則: ``` <args> ::= <arg> { "," <arg> } ``` ### 分組 為了表示優先順序,EBNF語法可以使用括號`()`明確定義擴充順序。 例如定義允許加法和減法的表達式規則: ``` <expr> ::= <term> ("+" | "-") <expr> ``` ### 串聯 在某些形式的EBNF中,運算符明確表示串聯(concatenation),而不是依靠並置(juxtaposition)。 ## Augmented BNF (ABNF) notation 協議規範通常使用增強巴科斯範式(Augmented BNF)。[RFC 5234]定義了ABNF。 從原則上講,ABNF與EBNF相似,不同之處在於ABNF的選擇(choice),可選擇項(option)和重複(repetition)表示法不同。 ABNF還提供了精確指定特定byte值的能力;詳細訊息在協議中至關重要。 在ABNF中: - 選擇的符號為`/` - 可選擇項為`[]` - 重複為前綴`*` - 重複n次或多次是前綴`n*` - 重複n到m次是前綴`n*m` - EBNF的`{expansion}`在ABNF中變為`*(expansion)` 範例可參考取自[RFC 5322 section-1.2]的日期和時間格式的定義。 # BNF的正則擴展 在語法中通常會找到[類似正則表達式]的操作。 在這些語法中: - 後綴`*`表示"重複0次或多次" - 後綴`+`表示"已重複1次或多次” - 後綴`?`表示"0或1次" Python中浮點文字的定義是一個很好的例子: ```bnf floatnumber ::= pointfloat | exponentfloat pointfloat ::= [intpart] fraction | intpart "." exponentfloat ::= (intpart | pointfloat) exponent intpart ::= digit+ fraction ::= "." digit+ exponent ::= ("e" | "E") ["+" | "-"] digit+ ``` ## 數學文法 參閱[translating math into code] ## 在上下文無關語法以外 正則表達式(Regular expression)在描述能力上位於上下文無關語法的下方:您可以將任何正則表達式重寫為表示該表達式匹配的形式的語法。但是,事實並非如此:並非所有語法都可以轉換為等效的正則表達式。 為了超越上下文無關文法的表達能力,需要在語法中允許一定程度的上下文敏感性。 上下文敏感性(context-sensitivity)意味著終端符也可能出現在規則的左側。 範例: ```bnf <top> ::= <a> ")" <a> ::= "(" <exp> "(" <exp> ")" ::= 7 ``` - `<top>`可以擴展為`<a> ")"` - 其可以擴展為`"(" <exp> ")"` - 其可以擴展為`7` 就其可描述的語言而言,它使語法等效於圖靈機。 通過限制規則,使左側的符號嚴格少於右側的所有擴展,上下文相關語法等同於(可確定的)[線性有界自動機(Linear bounded automaton)]。 即使某些語言是上下文相關的,上下文相關的語法也很少用於描述計算機語言。 例如,由於C處理標識符和類型的方式,C有點上下文敏感性,但是這種上下文敏感性是通過特殊約定解決的,而不是通過在語法中引入上下文敏感性來解決的。 # 解析 本文介紹了解釋語法和常用符號的過程。一個密切相關的主題是解析(Parsing)。 解析採用語法和字符串,並回答兩個問題: 1. 該字符串是語法語言嗎? 2. 該字符串相對於語法的結構是什麼? 參閱[Parsing Techniques: A Practical Guide] [The language of languages]: http://matt.might.net/articles/grammars-bnf-ebnf/ [RFC 5234]: http://tools.ietf.org/html/rfc5234 [RFC 5322 section-1.2]: http://tools.ietf.org/html/rfc5322#section-1. [類似正則表達式]: http://matt.might.net/articles/sculpting-text/ [translating math into code]: http://matt.might.net/articles/discrete-math-and-code/ [線性有界自動機(Linear bounded automaton)]: https://zh.wikipedia.org/zh-tw/%E7%BA%BF%E6%80%A7%E6%9C%89%E7%95%8C%E8%87%AA%E5%8A%A8%E6%9C%BA [Parsing Techniques: A Practical Guide]: https://www.tenlong.com.tw/products/9781441919014
×
Sign in
Email
Password
Forgot password
or
By clicking below, you agree to our
terms of service
.
Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Wallet (
)
Connect another wallet
New to HackMD?
Sign up