🟡 研究语言的三个方面#

🟡 文法的作用#

语言是句子的集合，而句子是无穷的。文法就是一组有限的规则，用有穷的规则集去刻划无穷的句子集合。常用 BNF/EBNF 表示。

产生式（规则）#

α → β，其中 α∈V⁺（至少一个符号），β∈V*。V = V_N ∪ V_T，且 V_N ∩ V_T = ∅。

文法四元组#

G = (V_N, V_T, P, S)

• V_N：非终结符集（语法变量）。
• V_T：终结符集（单词、记号）。
• P：产生式集（规则集）。
• S：开始符号（识别符），S∈V_N，至少在一条规则左部出现。

🔴 Chomsky 文法分类（必背表）#

按表达能力由高到低（限制由松到严）分 0、1、2、3 型：

包含关系：3型 ⊂ 2型 ⊂ 1型 ⊂ 0型（限制越强、能力越弱、集合越小）。

记忆：0型最宽松（图灵机），3型最严格（有穷自动机）；型号越大限制越多。

推导#

• 直接推导 ⇒：若 v=γαδ，w=γβδ，且 α→β 是产生式，则 v ⇒ w（一步）。
• 推导 ⇒：存在 v ⇒ a₀ ⇒ a₁ ⇒ … ⇒ u，记 v ⇒ u（0 步或多步）。
• ⇒⁺：一步或多步推导。

最左 / 最右推导#

• 最左推导：每步都替换句型中最左的非终结符。
• 最右推导（=规范推导）：每步都替换最右的非终结符；所得句型叫规范句型。

句型 / 句子 / 语言#

• 句型：若 S ⇒* x，则 x 是文法的句型（可含非终结符）。
• 句子：若 x 是句型且 x∈V_T*（仅含终结符），则 x 是句子。
• 语言：L(G) = { x | S ⇒* x, x∈V_T* }（全部句子的集合）。

🟡 二义性#

若文法存在某个句子对应两棵不同的语法树（等价地：两个不同的最左推导或两个不同的最右推导），则该文法是二义的。

• 二义性不可判定（不存在通用算法判定任意文法是否二义）。
• 消除二义性：引入新非终结符、规定运算符优先级和结合性（如表达式文法、if-else 匹配规则）。

🧮 例题（务必练熟）#

文法 E→E+T|E-T，T→T*F|T/F，F→(E)|i，判断并分析句型 E+T*F：

证明是句型：E ⇒ E+T ⇒ E+T*F，故 E ⇒* E+T*F，是句型。 ✓

分析：

• 相对于 E 的短语：E+T*F（E ⇒⁺ E+T*F）
• 相对于 T 的短语：T*F（T ⇒ T*F）
• 直接短语：T*F（由 T→T*F 一步得到）
• 句柄：T*F（唯一/最左的直接短语）

🟡 句型分析两大类#

1. 自顶向下：从开始符出发向下建树，是逐步推导的过程。
2. 自底向上：从叶子向上归约，是逐步归约的过程，核心是找可归约串（句柄）。

🟢 文法实用性#

• 有害规则：形如 U→U 的规则。
• 多余规则：不可达规则（用不到）或不可终止规则（推不出终结符串）。
• ε 规则 A→ε：会使证明和讨论复杂，实用中限制使用。