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

基于狀態的構建

基于自動機的編程

設計模式：Memento提供了將對象恢復到之前狀態的功能（撤消）。

設計模式：狀態允許對象在其內部狀態改變時改變其行為。

表驅動結構*

基于語法的構建

語法和解析器

正則表達式（regexp）

設計模式：解釋器實現一種專門的語言。

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

使用有限狀態機來定義程序的行為，使用狀態來控制程序的執行

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

這些都被認為是一個狀態，接下來發生的事情是由電梯的當前狀態決定的。
根據當前狀態，決定下一步要執行什么操作，執行操作之后要轉移到什么新的狀態

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

當電梯停下時，你預計下一個動作是門打開，向上移動或向下移動。

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

將程序視為有限自動機。

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

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

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

應用程序設計方法應與控制系統（Automata System）的設計類似。
核心思想：將程序看作是一個有限狀態自動機，側重于對“狀態”和“狀態轉換”的抽象和編程

程序的執行被分解為一組自動執行的步驟

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

各步驟之間的通訊通過“狀態變量”進行

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

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

如何實施？

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

“狀態”變量可以是簡單的枚舉數據類型，但可以使用更復雜的數據結構。

一種常見的技術是創建一個狀態轉換表，一個包含表示每種可能狀態的行的二維數組，以及表示輸入參數的列。

行和列滿足的表格的值是在符合兩個條件的情況下機器應轉換到的下一個狀態。

應用領域

高可靠性系統

軍事應用

航空航天工業

汽車行業

嵌入式系統
移動系統
可視化系統
Web應用程序
客戶端服務器應用程序

狀態模式 (behavioral pattern)

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

通常，狀態對象不包含任何字段

更改狀態：更改狀態對象

方法委托給狀態對象

狀態模式注釋
可以為每個狀態類的實例使用單例

狀態對象不封裝狀態，所以可以共享 - 不可變

輕松添加新的狀態

新狀態可以擴展其他狀態

僅覆蓋選定的功能

備忘錄模式 (behavioral)

意圖

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

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

促進撤消或回滾到完整的對象狀態。

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

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

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

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

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

什么是“表驅動”？

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

比復雜的邏輯簡單

更容易修改

更高效

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

查找東西的方法

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

選擇其中之一取決于數據的性質以及數據域的大小。

簡單

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

與所有查找表一樣，直接訪問表取代了更復雜的邏輯控制結構。

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

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

查找索引與直接索引

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

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

關鍵點

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

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

使用表格的另一個關鍵考慮因素是決定放入表格的具體內容。

基于語法的構建目標

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

基于字符串/流的I / O

某些程序模塊以字節序列或字符序列的形式輸入或輸出輸出，當它存儲在內存中時稱為字符串，或者在流入或流出模塊時稱為字符串。 有一類應用，從外部讀取文本數據，在應用中做進一步處理。

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

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

通過網絡發送的消息，在這種情況下，規范是有線協議從網絡上傳輸過來的消息，遵循特定的協議

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

存儲在內存中的字符串，也有格式需要

語法的概念

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

它不僅可以幫助區分合法序列和非法序列，還可以將序列解析為程序可以使用的數據結構。 使用語法判斷字符串是否合法，并解析成程序里使用的數據結構

從語法產生的數據結構通常是遞歸數據類型。通常是遞歸的數據結構

正則表達式

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

解析器生成器是一種將語法自動轉換為該語法的解析器的工具。 根據語法生成它的解析器，用于后續的解析

終結：語法中的文字串

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

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

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

文法中的文字被稱為終結節點，葉節點

它們被稱為終結，因為它們是代表字符串結構的解析樹的葉子。語法解析樹的葉子節點

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

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

語法中的非終結者與生產者

一個語法由一組產品描述，每個產品定義一個非終結非終止節點

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

非終結符是表示字符串的樹的內部節點。

語法中的生產具有這種形式

非終結符:: =終結，非終結符和運算符的表達式

語法的非終結點之一被指定為根。

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

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

三個基本的語法運算符

生產表達中最重要的三個操作是：

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

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

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

正則語法

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

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

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

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

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

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

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

上下文無關文法

通常，可以用我們的語法系統表達的語言稱為上下文無關的。

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

HTML語法是上下文無關的，但不是正則的。

大多數編程語言的語法也是無上下文的。
一般來說，任何具有嵌套結構的語言（如嵌套括號或大括號）都是上下文無關的，但不是正則的。

語法，解析器和解析器生成器
目標：

能夠將語法與解析器生成器結合使用，將字符序列解析為解析樹

能夠將分析樹轉換為有用的數據類型

解析器將輸入文本轉為解析樹

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

解析樹的根是語法的起始非終結符。

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

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

解析器生成器根據語法定義生成解析器

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

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

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

Backus Normal Form（BNF）巴克斯范式

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

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

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

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

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

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

一個Pattern對象是一個正則表達式的編譯后的表示。 Pattern類不提供公共構造函數。 要創建一個模式，你必須首先調用其公共靜態編譯方法之一，然后返回一個Pattern對象。 這些方法接受一個正則表達式作為第一個參數。模式是對正則表達式的正則表達式進行編譯之后得到的結果

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

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

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

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

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

解釋器模式

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

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

將一個領域映射到一種語言，將語言映射到一種語法，將語法映射為一種等級面向對象設計。解釋語法的“引擎”：遵循語法的文本?OO表示

用于定義語法，標記輸入并存儲它。

實施

它使用復合模式來表示語法。

因為語法通常形成樹結構，故使用復合模式來表達遵循語法的內容。

它定義了行為，而復合只定義了結構。

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

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

語法由BNF等形式定義

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

解釋器模式

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

每條語法規則（生產）都要定義相應的類 - 相當于開發一個簡單的解析器 - 用戶使用的時候，調用這個類類完成對輸入文本的解釋（這里的“解釋”，其實相當于 “翻譯”） - 只適用于簡單的語法規則，過于復雜的語法就需要引入大量的類

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

減少錯誤保證安全

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

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

容易明白

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

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

準備好改變

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