编译原理（清华大学出版社）-- 文法和语言 -- 文法和语言的形式定义

BuZhiDaoen

2020-01-10

形如 α→β 或 α::=β 的（α，β）有序对，其中α称为规则的左部，β称为规则的右部，这里的符号 →（::=）读作 "定义为"，例如A→a读作 “A定义为a”
文法 G定义为四元组（V_N，V_T，P，S）
其中V_N为非终结符集（语法实体或变量）；V_T终结符集；P为规则（α→β）的集合，α∈（V_N∪V_T）^* ，且至少包含一个非终结符，β∈（V_N∪V_T）^*，V_N，V_T和P都是非空有穷集
S称为识别符或者开始符，它是一个非终结符，至少要在一条规则中作为左部出现
V_N 和 V_T 不含公共的元素，即V_N ∩ V_T = Ø
通常用 V 表示 V_N ∪ V_T ，V称为文法G的字母表或词汇表

例2.1 有文法G=<V_N，V_T，P，S>，其中，V_N={S}，V_T={0，1}，P={S→0S1，S→01}，这里非终结符集中只含一个元素S，终结符号集由两个元素 0，1组成，有两条产生式，开始符是S

该例子也可以写成

G： S→0S1

S→01

或者

G[S]：S→0S1

S→01

例2.2 有文法G=（V_N，V_T，P，S），其中 V_N = {标识符，字母，数字}，V_T = {a，b，c，...，x，y，z，0，1，...，9}

P = { <标识符>→<字母>

<标识符>→<标识符><字母>

<标识符>→<标识符><数字>

<字母>→a

<字母>→b

...

<字母>→z

<数字>→0

<数字>→1

　　 ...

<数字>→9

}

S=<标识符>

为定义文法所产生的语言，还需要引入推导的概念，定义 V^* 中的符号之间的关系，直接推导=>，长度为n（n≥1）的推导编译原理（清华大学出版社）-- 文法和语言 -- 文法和语言的形式定义和长度为n（n≥0）的推导

设α→β是文法G=(V_N，V_T，P，S)的规则（或者是P中的一个产生式），γ 和 δ 是V^*中的任意符号
若有符号串 v、ω满足，v = γαδ，ω=γβδ，则说v（应用规则α→β）直接产生ω，或说ω是v的直接推导，或说ω直接归约到v，记作v=>ω

例如，对于例2.1的文法G，可以给出一些例子

对于例2.1的文法G，直接推导的例子如下

v=<标识符> ，ω=<标识符><字母>，直接推导：<标识符>=><标识符><字母>，使用的规则：<标识符>→<标识符><字母>，这里γ=δ=ε
v=<标识符><字母><数字>，ω=<字母><字母><数字>，直接推导：<标识符><字母><数字>=><字母><字母><数字>，使用的规则：<标识符>→<字母>，这里γ=ε，δ=<字母><数字>
v=abc<数字>，ω=abc5，直接推导：abc<数字>=>abc5，使用的规则：<数字>→5，这里γ=abc，δ=ε

如果存在直接推导的序列：v=ω₀ => ω₁ => ω₂ => ... => ω_n = ω （n>0）则称v推导出（产生）ω（推导长度为n），或称ω归约到v，记作v ω
若有 v ω，或 v = ω，则记作 v ω 对例2.1的文法，存在直接推导序列 v=S1 => 00S11 => 000S11 => 00001111 = ω，即 0S1 00001111，也可记作 0S1 00001111
对例2.2的文法，存在直接推导序列 v = <标识符> => <标识符><数字> => <字母><数字> => x<数字> => x1 = ω，即 <标识符> x1