上下文無關文法

定義:
??上下文無關文法G是一個四元組，\(G=(V_T,V_N,S,P)\)，其中
??\(V_T\)：終結符（Terminal）非空集合
??\(V_N\)：非終結（Nonterminal）非空集合，且\(V_T \cap V_N=\oslash\)
??S：文法的開始符號，\(S\subset V_N\)
??P：產生式有限集合，每個產生式形式為

??且文法開始符號S必須在某個產生式的左部出現一次。

巴科斯范式（BNF）

“→”用“::=”表示，小寫字母為終結符，大寫字母為非終結符。
約定：

可縮寫為

其中，“|”讀成“或”，稱\(\alpha_i\)為P的一個候選式，表示一個文法時，通常只給出一個開始符號和產生式

文法生成語言

直接推導

定義：
?? 稱\(\alpha A \beta\)直接推出\(\alpha \gamma \beta\)，即

??僅當\(A \to \gamma\)是一個產生式，且\(\alpha,\beta \in(V_T \cup V_N)^*\)。
??如果\(\alpha_1 \implies \alpha_2 \implies ... \implies \alpha_n\)，則稱這個序列是從\(\alpha_1\)到\(\alpha_n\)的一個推導。若存在一個從\(\alpha_1\)到\(\alpha_n\)的推導，則稱\(\alpha_1\)可以推導出\(\alpha_n\)。
??\(\alpha_1 \overset{*}{\implies} \alpha_n\)，從\(\alpha_1\)出發，經過\({\color{red}0}\)步或者若干步推出\(\alpha_n\)。
??\(\alpha_1 \overset{+}{\implies} \alpha_n\)，從\(\alpha_1\)出發，經過\({\color{red}1}\)步或者若干步推出\(\alpha_n\)。
??\(\alpha \overset{*}{\implies} \beta \iff \alpha = \beta 或 \alpha \overset{+}{\implies}\beta\)

句型

定義
??假定G是一個文法，S是它的開始符號，如果

??則稱\(\alpha\)是一個\(\color{red}{句型}\)。

句子

定義：僅含終結符的句型是一個\(\alpha\)是一個\(\color{red}{句子}\)。

語言

定義：文法G所產生的句子的全體是一個\(\color{red}{語言}\)，記為：\(\color{red}L(G)\)。

??概述為把語言定義為句子的全體，也就是說，你如果掌握了一個語言所有的句子，就等于你掌握了這一門語言！