文法和语言是密切相关的， 文法所定义的任一句型和句子, 都可以根据文法推导出来。 我们提出一个问题：
这种推导过程是否唯一？
同一个句型(句子)可以通过不 同的推导序列推导出来，这是因为 在推导过程中与所选择非终结符的 次序有关。
例如，设有文法G[N1] N1→N N→ND | D D→0 | 1 | 2 句子12有下列三种不同的推导序列: ① N1N ND N2 D2 12 ② N1N ND DD 1D12 ③ N1N ND DD D212
E (E) (E+E)(E*E+E) (i*E+E)
(i*i+E) (i*i+i) * 即有 E(i*i+i), 所以符号串(i+i*i)是文法 G[E]的一个句子。
2.3.2 语言的形式定义
5．语言
文法G[S]产生的所有句子的集合称为文 法G所定义的语言,记为L(G[S])：
* x且x∈V *} L(G[S])={x|S T 由语言定义可知： （1）当文法给定，语言也就确定。 （2）L(G)是VT* 的子集。即属于VT* 的符 号串 x 不一定属于L(G)。
语法树与二义性
用一张图表示一个句型的推导,称为语法树。 (i*i+i)的语法树 G(E)： E i | E+E | E*E | (E)
(i*i+i)
E (E) (E+E) (E*E+E) (i*E+E) (i*i+E) (i*i+i)
E (E) (E+E) (E+i) (E*E+i) (E*i+i) (i*i+i)
四种类型描述能力比较
0型
1型 2型 3型
L5={anbn|n1} 不能由正规文法产生，但 可由上下文无关文法产生： G5(S)： S aSb| ab L6={anbncn|n1}不能由上下文无关文法产 生，但可由上下文有关文法产生： G6(S)： S aSBC| aBC CB BC aB ab bB bb bC bc cC cc
2.3.2 语言的形式定义
3．广义推导
* 0n表示从0出发，经0步或若干步， 可推导出n。 * 意味着 + 或者 = 。 也就是说
0 n 0 n 0 n
对上例 E→E+T | T T→T*F | F F→(E) | i *E * i+i*i 我们有： E E
2.3.2 语言的形式定义
例2 设有文法G[E]： E→E+E | E*E | (E) | i 试证明符号串 (i*i+i) 是文法G[E]的一 个句子。 分析 只要证明符号串 (i*i+i) 对文法 G 存在一个推导，就可证明符号串 (i*i+i) 是文法G[E]的一个句子。
2.3.2 语言的形式定义
E→E+E | E*E | (E) | i
2.3.1 文法的形式定义
L={ aa, aba, abba, …… }
所以定义语言的文法为：
G=( {A, B}, {a, b}, P, A )
P={ A→aBa B→Bb | ε }
2.3.1 文法的形式定义
设字母表∑={ (, ) } ,试设计一个文法描 述语言 L={ (n )n | n≥0} 分析 该语言中串的结构特征是 当n=0 L={ ε } 注: (0 )0= ε 当n=1 L={ ( ) } 当n=2 L={ (( )) } …… L={ ε, ( ), (( )), ((( ))), … }
其中P为：E→i | E+E | E*E | (E)
2.3.1 文法的形式定义
P为：E→i | E+E | E*E | (E) { i, i+i, i*i, i+i*i, (i+i), … }
注意：是符号 串的集合
2.3.1 文法的形式定义
设字母表 Σ={ a, b } , 试设计一个文法， 描述语言 L={ abna | n≥0 } 分析 该语言中串的结构特征是 当n＝0 L={ aa } (b0=ε) 当n＝1 L={ aba } 当n＝2 L={ abba } …… L={ aa, aba, abba, …… }
• 一棵语法树是不同推导过程的共性抽象。
如果使用最左(右)推导，则一个最左(右) 推导与语法树一一对应。 一个句型是否只对应唯一一棵语法树？
E ( E E i E + E i * E i )
E ( E i E * E i E +E i )
定义：如果一个文法存在某个句子对应两颗不同 的语法树，则说这个文法是二义的。即：如果一 个文法存在某个句子，它有两个不同的最左（最 右）推导， 则说这个文法是二义的 G(E)： E i|E+E|E*E|(E) 是二义文法。 语言的二义性：一个语言是二义性的，如果对它 不存在无二义性的文法。
对文法G(E)： E i | E+E | E*E | (E)
E (E) (E+E) (i+E) (i+i)
2.3.2 语言的形式定义
2 ．推导 如果存在一个直接推导序列： α0 α1 α2 … αn
则我们称这个序列是一个从0至 n的长度为n的推导，记为 + αα
即表示从0 出发，经 一步或若干 步 或者说 使用若干次规则可推导 出 。
2.3.2 语言的形式定义
例1 设有文法G[S]：S→01 | 0S1 我们有:
* 01 S * 0S1 S * 00S11 S * 000111 S 显然，符号串01、0S1、00S11和 000111 都是文法G[S]的句型，而01和 000111又是文法G[S]的句子。
2.3.2 语言的形式定义
第二章
语法描述
2.3.1 文法的形式定义
用文法定义一个含＋、*的算术 表达式，定义用下述自然语言描 述： 变量是一个表达式； 若 E1和 E2是算术表达式, 则 E1＋E2、E1*E2、(E1) 也是算术 表达式。
2.3.1 文法的形式定义
分析 算术表达式的定义用自然 语言描述，这是对算术表达式的非 形式定义，题意用文法来定义算术 表达式，即是用形式化的方法定义 表达式。定义算术表达式的文法为： G=({E},{ i, +, *, (, ) }, P, E )
可能存在G和G’，一个为二义的，一个为无二义的。 但L(G)=L(G’)
二义性问题是不可判定问题，即不存在一个算法， 它能在有限步骤内，确切地判定一个文法是否是 二义的。 可以找到一组无二义文法的充分条件。
二义文法： G(E)： E i|E+E|E*E|(E) 无二义文法：
G(E)：E T | E+T T F | T*F F (E) | i 表达式 项|表达式+项 项 因子 | 项*因子 因子 (表达式) | i
由该文法所确定的语言为 L(G[S])={ε, 0, 1, 00, 01, 10, 11, …} ={ x | x∈{0,1}* }
2.3.2 语言的形式定义
例5 设有文法G[A]： A→yB B →xB | x 该文法所定义的语言是什么？ 分析 从文法开始符号A出发可推导 出以y开头后面跟一个或多个x结尾的 符号串，所以该文法定义的语言为
0
n
2.3.2 语言的形式定义
设有文法G[E]=({E,T,F},{i,+,*,(,)},P,E) 其中P为：E→E+T | T T→T*F | F F→(E) | i 对 i+i*i 有如下直接推导序列: E E+T T+T F+Ti+T i+T*F i+F*F i+i*Fi+i*i + 我们可记为 Ei+i*i
最左(最右)推导，是指对于 一个推导序列中的每一步直接推 导 αβ , 都是对α 中的最左(最右) 非终结符进行替换。 最右推导也称为规范推导， 用规范推导推导出的句型称为规 范句型。
例 设有文法G[S]: S→AB A→A0 | 1B B→0 | S1 请给出句子101001的最右、最左推导。 分析 最右推导是指在推导过程 中任何一步αβ (α和β是句型)，都是 对α中的最右非终结符进行替换。
S→AB A→A0 | 1B B→0 | S1 句子101001的最右推导为: S AB AS1AAB1AA01A1B01 A10011B1001101001
最左推导是指在推导过程中任何 一步αβ (α和β是句型), 都是对α的最 左非终结符进行替换。 S→AB A→A0 | 1B B→0 | S1 句子101001的最左推导为： S AB 1BB10B 10S110AB1 101BB11010B1101001
*
*
r V
* T
2.3.3
形式语言鸟瞰
Chomsky于1956年建立形式语言 体系，他把文法分成四种类型：0， 1，2，3型。 与上下文无关文法一样，它们都由 四部分组成，但对产生式的限制有 所不同。
0型(短语文法，图灵机)：
产生式形如： 其中： (VT VN)*且至少含有一个非终结 符； (VT VN)* 0型文法又叫短语文法，记为PSG。0型文法 相应的语言称为0型语言或称递归可枚举集， 它的识别系统是图灵（Turing）机。
我们应用第二个规则n－1次，然 后再应用第一个规则1次，有： S 0S100S11…0n-1S1n-10n1n * 即S0n1n
可见，此文法定义的语言为 L(G[S])={ 0n1n | n≥1}
2.3.2 语言的形式定义
例4 设有文法G[S]：S→0S | 1S |ε 该文法所定义的语言是什么？
L(G[A])={ yxn | n≥1}
2.3.2 语言的形式定义