摘要：遵循特定規(guī)則，利用操作符，終止節(jié)點和其他非終止節(jié)點，構(gòu)造新的字符串非終結(jié)符是表示字符串的樹的內(nèi)部節(jié)點。語法中的生產(chǎn)具有這種形式非終結(jié)符終結(jié)，非終結(jié)符和運算符的表達式語法的非終結(jié)點之一被指定為根。

基于狀態(tài)的構(gòu)建

基于自動機的編程

設(shè)計模式：Memento提供了將對象恢復(fù)到之前狀態(tài)的功能（撤消）。

設(shè)計模式：狀態(tài)允許對象在其內(nèi)部狀態(tài)改變時改變其行為。

表驅(qū)動結(jié)構(gòu)*

基于語法的構(gòu)建

語法和解析器

正則表達式（regexp）

設(shè)計模式：解釋器實現(xiàn)一種專門的語言。

基于狀態(tài)的編程是一種編程技術(shù)，它使用有限狀態(tài)機（FSM）來描述程序行為，即使用“狀態(tài)”來控制程序的流程。

使用有限狀態(tài)機來定義程序的行為，使用狀態(tài)來控制程序的執(zhí)行

例如，在電梯的情況下，可能會停止，向上移動，向下移動，停止，關(guān)閉門并打開門。

這些都被認為是一個狀態(tài)，接下來發(fā)生的事情是由電梯的當(dāng)前狀態(tài)決定的。
根據(jù)當(dāng)前狀態(tài)，決定下一步要執(zhí)行什么操作，執(zhí)行操作之后要轉(zhuǎn)移到什么新的狀態(tài)

如果電梯剛剛關(guān)好，接下來會發(fā)生什么情況？ 它可以停止，向上移動或向下移動。

當(dāng)電梯停下時，你預(yù)計下一個動作是門打開，向上移動或向下移動。

基于自動機的編程是一種編程模式，其中程序或其一部分被認為是有限狀態(tài)機（FSM）或任何其他形式自動機的模型。

將程序視為有限自動機。

每臺自動機可以一次接受一個“步驟”，程序的執(zhí)行分解為多帶帶的步驟。

這些步驟通過改變代表“狀態(tài)”的變量的值來相互溝通。

程序的控制流程由該變量的值決定。

應(yīng)用程序設(shè)計方法應(yīng)與控制系統(tǒng)（Automata System）的設(shè)計類似。
核心思想：將程序看作是一個有限狀態(tài)自動機，側(cè)重于對“狀態(tài)”和“狀態(tài)轉(zhuǎn)換”的抽象和編程

程序的執(zhí)行被分解為一組自動執(zhí)行的步驟

每個步驟實際上是一個代碼段的執(zhí)行（所有步驟都相同），它有一個入口點。 這樣的部分可以是功能或其他例程，或者只是一個循環(huán)體。

各步驟之間的通訊通過“狀態(tài)變量”進行

在任何兩個步驟之間，程序不能有其狀態(tài)的隱式分量，例如本地（堆棧）變量值，返回地址，當(dāng)前指令指針等。

在進入自動機步驟的任何兩個時刻取得的整個程序的狀態(tài)只能在被認為是自動機狀態(tài)的變量值中有所不同。

如何實施？

基于自動機的代碼的整個執(zhí)行過程都是自動機步驟的一個（可能是顯式的）循環(huán)。

“狀態(tài)”變量可以是簡單的枚舉數(shù)據(jù)類型，但可以使用更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。

一種常見的技術(shù)是創(chuàng)建一個狀態(tài)轉(zhuǎn)換表，一個包含表示每種可能狀態(tài)的行的二維數(shù)組，以及表示輸入?yún)?shù)的列。

行和列滿足的表格的值是在符合兩個條件的情況下機器應(yīng)轉(zhuǎn)換到的下一個狀態(tài)。

應(yīng)用領(lǐng)域

高可靠性系統(tǒng)

軍事應(yīng)用

航空航天工業(yè)

汽車行業(yè)

嵌入式系統(tǒng)
移動系統(tǒng)
可視化系統(tǒng)
Web應(yīng)用程序
客戶端服務(wù)器應(yīng)用程序

狀態(tài)模式 (behavioral pattern)

假設(shè)一個對象總是處于幾個已知狀態(tài)之一
對象所處的狀態(tài)決定了幾種方法的行為
可以在每種方法中使用if / case語句
更好的解決方案：狀態(tài)模式
有一個狀態(tài)對象的引用

通常，狀態(tài)對象不包含任何字段

更改狀態(tài)：更改狀態(tài)對象

方法委托給狀態(tài)對象

狀態(tài)模式注釋
可以為每個狀態(tài)類的實例使用單例

狀態(tài)對象不封裝狀態(tài)，所以可以共享 - 不可變

輕松添加新的狀態(tài)

新狀態(tài)可以擴展其他狀態(tài)

僅覆蓋選定的功能

備忘錄模式 (behavioral)

意圖

在不違反封裝的情況下，捕獲并外部化對象的內(nèi)部狀態(tài)，以便稍后可以將對象返回到此狀態(tài)。

封裝“檢查點”功能的魔術(shù)餅干（cookie）。

促進撤消或回滾到完整的對象狀態(tài)。

問題：需要將對象恢復(fù)到以前的狀態(tài)（例如“撤銷”或“回滾”操作）。
記住對象的歷史狀態(tài)，以便于“回滾”

備忘錄設(shè)計模式定義了三種不同的角色：

發(fā)起者 - 知道如何保存自己的對象。需要“備忘”的類

看守者 - 知道發(fā)起者需要保存和恢復(fù)的原因和時間的對象。添加發(fā)起者的備忘記錄和恢復(fù)

備忘錄 - 由發(fā)起人撰寫和閱讀的鎖盒，由看守人管理。備忘錄，記錄發(fā)起者對象的歷史狀態(tài)

什么是“表驅(qū)動”？

表驅(qū)動方法是一種使用表來查詢信息而不是使用邏輯語句（例如if-else和switch-case）的模式。
在簡單情況下，使用邏輯語句更快更容易，但隨著邏輯鏈變得更復(fù)雜，表驅(qū)動的代碼：

比復(fù)雜的邏輯簡單

更容易修改

更高效

表驅(qū)動編程的核心思想：將代碼中復(fù)雜的if-else和switch-case語句從代碼中分離出來，通過“查表”的方式完成，從而提高可維護性

查找東西的方法

? 直接訪問
? 索引訪問
? 階梯訪問

選擇其中之一取決于數(shù)據(jù)的性質(zhì)以及數(shù)據(jù)域的大小。

簡單

您只是通過一個或多個索引“查找事物”。

與所有查找表一樣，直接訪問表取代了更復(fù)雜的邏輯控制結(jié)構(gòu)。

他們是“直接進入”的，因為你不必跳過任何復(fù)雜的循環(huán)來找到你想要的信息。

有時直接索引是一個問題，特別是如果可能的值域很大。
例如，如果您想使用產(chǎn)品ID（8位數(shù)字），并制作一張映射200個產(chǎn)品的表格。

查找索引與直接索引

索引元素很小（整數(shù)），值可以有效地大（只有你需要的那么多），比如字符串（名字，描述，錯誤信息等）。
多個索引可以訪問相同的數(shù)據(jù)（員工信息可以按名稱，聘用日期，出售等進行映射）
可維護 - 從應(yīng)用程序界面隔離查找方法。

表格中的條目對數(shù)據(jù)范圍有效，而不適用于不同的數(shù)據(jù)點

關(guān)鍵點

表格提供了復(fù)雜邏輯和繼承結(jié)構(gòu)的替代方案。 如果您發(fā)現(xiàn)程序的邏輯或繼承樹讓您感到困惑，那么問問自己是否可以通過查找表進行簡化。

使用表格的一個關(guān)鍵考慮因素是決定如何訪問表格。 您可以通過直接訪問，索引訪問或階梯訪問來訪問表。

使用表格的另一個關(guān)鍵考慮因素是決定放入表格的具體內(nèi)容。

基于語法的構(gòu)建目標(biāo)

理解語法生成和正則表達式操作符的思想
能夠讀取語法或正則表達式，并確定它是否匹配一系列字符
能夠編寫語法或正則表達式來匹配一組字符序列并將其解析為數(shù)據(jù)結(jié)構(gòu)

基于字符串/流的I / O

某些程序模塊以字節(jié)序列或字符序列的形式輸入或輸出輸出，當(dāng)它存儲在內(nèi)存中時稱為字符串，或者在流入或流出模塊時稱為字符串。 有一類應(yīng)用，從外部讀取文本數(shù)據(jù)，在應(yīng)用中做進一步處理。

具體來說，一個字節(jié)或字符序列可能是：

磁盤上的文件，這種情況下，規(guī)范稱為文件格式，程序需讀取文件并從中抽取正確的內(nèi)容

通過網(wǎng)絡(luò)發(fā)送的消息，在這種情況下，規(guī)范是有線協(xié)議從網(wǎng)絡(luò)上傳輸過來的消息，遵循特定的協(xié)議

用戶在控制臺上鍵入的命令，在這種情況下，規(guī)范是命令行界面，用戶在命令行輸入的指令，遵循特定的格式

存儲在內(nèi)存中的字符串，也有格式需要

語法的概念

對于這些類型的序列，語法的概念是設(shè)計的一個好選擇：

它不僅可以幫助區(qū)分合法序列和非法序列，還可以將序列解析為程序可以使用的數(shù)據(jù)結(jié)構(gòu)。 使用語法判斷字符串是否合法，并解析成程序里使用的數(shù)據(jù)結(jié)構(gòu)

從語法產(chǎn)生的數(shù)據(jù)結(jié)構(gòu)通常是遞歸數(shù)據(jù)類型。通常是遞歸的數(shù)據(jù)結(jié)構(gòu)

正則表達式

這是一個廣泛使用的工具，用于許多字符串處理任務(wù)，需要反匯編字符串，從中提取信息或進行轉(zhuǎn)換。

解析器生成器是一種將語法自動轉(zhuǎn)換為該語法的解析器的工具。 根據(jù)語法生成它的解析器，用于后續(xù)的解析

終結(jié)：語法中的文字串

為了描述一串符號，無論它們是字節(jié)，字符還是其他類型的從固定集合中抽取的符號，我們都使用稱為語法的緊湊表示法。

語法定義了一組字符串。用語法定義一個“字符串”

例如，URL的語法將指定HTTP協(xié)議中合法URL的一組字符串。

文法中的文字被稱為終結(jié)節(jié)點，葉節(jié)點

它們被稱為終結(jié)，因為它們是代表字符串結(jié)構(gòu)的解析樹的葉子。語法解析樹的葉子節(jié)點

他們沒有孩子，不能再進一步擴大。 無法再往下擴展

我們通常用引號將終結(jié)寫入，如"http"或"："。 通常表示為字符串

語法中的非終結(jié)者與生產(chǎn)者

一個語法由一組產(chǎn)品描述，每個產(chǎn)品定義一個非終結(jié)非終止節(jié)點

非終結(jié)符就像一個變量，它表示一組字符串，而生成則表示該變量根據(jù)其他變量（非終結(jié)符），運算符和常量（終結(jié)）的定義。 遵循特定規(guī)則，利用操作符，終止節(jié)點和其他非終止節(jié)點，構(gòu)造新的字符串

非終結(jié)符是表示字符串的樹的內(nèi)部節(jié)點。

語法中的生產(chǎn)具有這種形式

非終結(jié)符:: =終結(jié)，非終結(jié)符和運算符的表達式

語法的非終結(jié)點之一被指定為根。

語法識別的字符串集合是匹配根非終結(jié)符的字符串。

這個非終結(jié)者通常被稱為root或start。根節(jié)點

三個基本的語法運算符

生產(chǎn)表達中最重要的三個操作是：

連接，不是由一個符號表示，而是一個空格：x :: = y z an x是一個y，后跟一個z

重復(fù)，用表示：x :: = y x是零或更多y

聯(lián)合，也稱為選擇，由|：x :: = y |表示 z an x是y或z

正則語法

正則語法有一個特殊的性質(zhì)：通過用右端代替每個非終結(jié)符（除了根結(jié)尾之外），可以將它縮減為單根生成，只有終結(jié)和操作符在右側(cè)。
正則語法：簡化之后可以表達為一個產(chǎn)生式而不包含任何非終止節(jié)點

正則表達式（正則表達式）

終結(jié)和操作符的簡化表達式可以用更緊湊的形式寫成，稱為正則表達式。
正則表達式避免了終結(jié)周圍的引號以及終結(jié)和運算符之間的空格，因此它只包含終結(jié)字符，用于分組的括號和運算符字符。去除引號和空格，從而表達更簡潔（更難懂）

正則表達式比原始語法的可讀性要低得多，因為它缺少記錄每個子表達式意義的非終結(jié)符名稱。

但是一個正則表達式的實現(xiàn)很快，并且有很多支持正則表達式的編程語言的庫。

正則表達式中的一些特殊運算符

. 任何單個字符
d任意數(shù)字，與[0-9]相同
是任何空格字符，包括空格，制表符，換行符
w任何單詞字符，包括字母和數(shù)字
，（，）， *， +，...轉(zhuǎn)義一個操作符或特殊字符，以便它按字面順序匹配

上下文無關(guān)文法

通常，可以用我們的語法系統(tǒng)表達的語言稱為上下文無關(guān)的。

并非所有的上下文無關(guān)語言也是正則的; 也就是說，有些語法不能簡化為單一的非遞歸生成。

HTML語法是上下文無關(guān)的，但不是正則的。

大多數(shù)編程語言的語法也是無上下文的。
一般來說，任何具有嵌套結(jié)構(gòu)的語言（如嵌套括號或大括號）都是上下文無關(guān)的，但不是正則的。

語法，解析器和解析器生成器
目標(biāo)：

能夠?qū)⒄Z法與解析器生成器結(jié)合使用，將字符序列解析為解析樹

能夠?qū)⒎治鰳滢D(zhuǎn)換為有用的數(shù)據(jù)類型

解析器將輸入文本轉(zhuǎn)為解析樹

解析器需要一系列字符并嘗試將該序列與語法進行匹配。 解析器：輸入一段文本，與特定的語法規(guī)則建立匹配，輸出結(jié)果
解析器通常會生成一個解析樹，該解析樹顯示如何將語法生成擴展為與字符序列匹配的句子。 解析器：將文本轉(zhuǎn)化為解析樹

解析樹的根是語法的起始非終結(jié)符。

解析樹的每個節(jié)點都擴展為語法的一個生成。

解析的最后一步是對這個分析樹做一些有用的工作。 利用產(chǎn)生的分析樹，進行下一步的處理
表示語言表達式的遞歸抽象數(shù)據(jù)類型稱為抽象語法樹（AST）。

解析器生成器根據(jù)語法定義生成解析器

解析器生成器是一種讀取語法規(guī)范并將其轉(zhuǎn)換為可識別語法匹配的Java程序的工具。
更廣泛地：

解析器生成器是一種編程工具，它根據(jù)某種形式的語言形式描述創(chuàng)建解析器，解釋器或編譯器。

輸入可能是一個文本文件，其中包含用BNF或EBNF編寫的定義編程語言語法的語法。 - 輸出是語法分析器的一些源代碼。

Backus Normal Form（BNF）巴克斯范式

1959年6月，Backus Normal Form（BNF）首次提出，以遞歸形式描述語言的各種成分，凡遵守其規(guī)則的程序就可保證語法上的正確性。

經(jīng)過Peter Naur的改進與完善以及Niklaus Wirth的擴充，形成了EBNF（擴展BNF），也就是目前使用的BNF。

經(jīng)Donald Knuth的建議，BNF中的N變成了Naur（Backus-Naur Form）。

Grammar定義語法規(guī)則（BNF格式的文本），Parser generator根據(jù) 語法規(guī)則產(chǎn)生一個parser，用戶利用parser來解析文本，看其是否符 合語法定義并對其做各種處理（例如轉(zhuǎn)成parse tree）

用于正則表達式處理的java.util.regex

java.util.regex包主要由三個類組成：

一個Pattern對象是一個正則表達式的編譯后的表示。 Pattern類不提供公共構(gòu)造函數(shù)。 要創(chuàng)建一個模式，你必須首先調(diào)用其公共靜態(tài)編譯方法之一，然后返回一個Pattern對象。 這些方法接受一個正則表達式作為第一個參數(shù)。模式是對正則表達式的正則表達式進行編譯之后得到的結(jié)果

匹配對象是解釋模式并對輸入字符串執(zhí)行匹配操作的引擎。 像Pattern類一樣，Matcher沒有定義公共構(gòu)造函數(shù)。 您通過調(diào)用Pattern對象上的匹配器方法來獲得Matcher對象。 Matcher：利用Pattern對輸入字符串進行解析

PatternSyntaxException對象是指示正則表達式模式中的語法錯誤的未經(jīng)檢查的異常。

正則表達式在編程語言中非常有用。

在Java中，可以使用正則表達式來處理字符串（例如String.split，String.matches，java.util.regex.Pattern）。

它們作為現(xiàn)代腳本語言（如Python，Ruby和Javascript）的一流功能而內(nèi)置，您可以在許多文本編輯器中將它們用于查找和替換。

解釋器模式

解釋器模式提供了評估語言語法或表達的方法。
意圖

給定一種語言，為其語法定義一個表示法，以及一個使用表示法來解釋語言句子的解釋器。 給定一種語法，定義該語法的程序內(nèi)部表示，形成該語法的解釋器，將遵循語法規(guī)則的文本解釋成程序內(nèi)部的表示（例如一組對象）

將一個領(lǐng)域映射到一種語言，將語言映射到一種語法，將語法映射為一種等級面向?qū)ο笤O(shè)計。解釋語法的“引擎”：遵循語法的文本?OO表示

用于定義語法，標(biāo)記輸入并存儲它。

實施

它使用復(fù)合模式來表示語法。

因為語法通常形成樹結(jié)構(gòu)，故使用復(fù)合模式來表達遵循語法的內(nèi)容。

它定義了行為，而復(fù)合只定義了結(jié)構(gòu)。

針對該層次化樹形結(jié)構(gòu)，定義了一組行為來處理結(jié)構(gòu)中的不同類型節(jié)點

解釋器與語法+解析器
語法+解析器

語法由BNF等形式定義

解析器讀取用戶輸入的待解析的文本，判定其是否與語法匹配，并轉(zhuǎn)為符合語法的解析樹，交給其他功能做后續(xù)處理 - 可用于高度復(fù)雜的語法規(guī)則

解釋器模式

語法由程序員手工定義為一組接口/類及其之間的關(guān)系，對語法的解釋（即解析器）由此組的類的內(nèi)部操作（Interpret（））負責(zé)

每條語法規(guī)則（生產(chǎn)）都要定義相應(yīng)的類 - 相當(dāng)于開發(fā)一個簡單的解析器 - 用戶使用的時候，調(diào)用這個類類完成對輸入文本的解釋（這里的“解釋”，其實相當(dāng)于 “翻譯”） - 只適用于簡單的語法規(guī)則，過于復(fù)雜的語法就需要引入大量的類

機器處理的文本語言在計算機科學(xué)中無處不在。
語法是描述這種語言的最流行的形式
正則表達式是語法的一個重要子類，可以在不遞歸的情況下表達。

減少錯誤保證安全

語法和正則表達式是字符串和流的聲明性規(guī)范，可以由庫和工具直接使用。

這些規(guī)范通常比手工分析代碼更簡單，更直接，更不容易出錯。

容易明白

語法以比手寫解析代碼更易于理解的形式捕獲序列的形狀。

正則表達式，唉，往往不易理解，因為它們是可能是一個更容易理解的正則語法的簡化形式。

準(zhǔn)備好改變

語法可以很容易地編輯，但不幸的是，正則表達式很難改變，因為復(fù)雜的正則表達式是神秘而難以理解的。