6.2其它相关语法介绍 S是起始符,它是集合N中的一个成员R是一个产生式规则 集。每条产生式具有如下批式:a→b 其中a∈V+,b∈V,且a≠bV表式由V中的符号所构成 的全部符号串包括空符号串)的集合V+表示W中除中 以外的一切符号串的集合。 在一部短语结构语法中,基于运算就是把一个符号串重 写为另一个符号串。如果a→b是一条产生式就可以通过 用b来置换a,重写任何一个包含子串a的符号串,并用符号 "表示对符号串所作的这种运算。所以如果u∈V+, 有:uav→ubv 2021/2/23 第6章句法语法与语义理论及分析下近
2021/2/23 第6章句法(语法)与语义理论及分析 21 S是起始符, 它是集合N中的一个成员; P是一个产生式规则 集。每条产生式具有如下形式: a→b 其中, a∈V+, b∈V*, 且a≠b;V*表式由V中的符号所构成 的全部符号串(包括空符号串Φ)的集合,V+表示V*中除Φ 以外的一切符号串的集合。 在一部短语结构语法中, 基于运算就是把一个符号串重 写为另一个符号串。如果a→b是一条产生式, 就可以通过 用b来置换a, 重写任何一个包含子串a的符号串, 并用符号 " "表示对符号串所作的这种运算。所以, 如果u,v∈V+, 有：uav → ubv G 下页 6 . 2 其它相关语法介绍
6.2其它相关语法介绍 就说uav直接产生ubv或ubv是由uav直接推导出来 的。举例来说如果定义了一部语法G其中是起始 符且N={S} T=a, b, ch P={S→asC s→b} 于是从串S开始,应用第一条产生式可得到串aScn然后 应用第二条产生式得到串abc:S→aSC→abc G G 或者可以重复应用第一条产生式两次,然后再用第 二条产生式,得到S→aSc→ aaSc→ wabco G G G 2021/2/23 第6章句法语法与语义理论及分析下近
2021/2/23 第6章句法(语法)与语义理论及分析 22 就说uav直接产生ubv, 或ubv是由uav直接推导出来 的。举例来说, 如果定义了一部语法G, 其中S是起始 符, 且N={S} T={a,b,c} P={S → aSC, S→b} 于是从串S开始, 应用第一条产生式可得到串aSc, 然后 应用第二条产生式得到串abc: S → aSC → abc G G 或者可以重复应用第一条产生式两次, 然后再用第 二条产生式, 得到 S → aSc → aaScc → aabcc G G G 下页 6 . 2 其它相关语法介绍
6.2其它相关语法介绍 如果S1,S2,sn都是符号串,且 s1→s2→,,→Sn GG G 记作 s1→Sn 就是说S1产生Sn,或者说Sn是由S1推导出来的。因此 对于上面的简单语法有 s→abc G S→ aasc等等 2021/2/23 第6章句法语法与语义理论及分析下近
2021/2/23 第6章句法(语法)与语义理论及分析 23 如果S1, S2,…,Sn 都是符号串, 且 S1 → S2 → … → Sn G G G 记作 * S1 → Sn G 就是说S1产生Sn, 或者说Sn是由S1推导出来的。因此, 对于上面的简单语法有 * S → abc G * S → aaScc 等等。 下页 6 . 2 其它相关语法介绍
6.2其它相关语法介绍 通过以不同的顺序来应用这些产生式就可以从同一符 号产生许多不同的串。由一部短语结构语法是义的语言就 是可以从起始符S推导出来的全部终结符串的集合。可见 白上面这部简单语法所定义的语言是 b, abc aabcc. aaabccc,… 一个程序如果能根据一部特定的语法来确定一个句子的 推导,就称它为一个句法分析器。 2021/2/23 第6章句法语法与语义理论及分析下近
2021/2/23 第6章句法(语法)与语义理论及分析 24 通过以不同的顺序来应用这些产生式, 就可以从同一符 号产生许多不同的串。由一部短语结构语法定义的语言就 是可以从起始符S 推导出来的全部终结符串的集合。可见, 由上面这部简单语法所定义的语言是 b,abc,aabcc,aaabccc,… 一个程序如果能根据一部特定的语法来确定一个句子的 推导, 就称它为一个句法分析器。 下页 6 . 2 其它相关语法介绍
6.2其它相关语法介绍 一般来说如果把语法G定义的语言记作G则 L(G=WW|W∈T,且sW} 这条定义的意思是对于所有符号串W,如果W是由终结符 所组成的串,且用语法G可以从起始符S中推导出W那么符号 串W的集合就是语法G所生成的语言L(G)。 换言之,一个符号串要属于L(G)必须满足两个条件 (1)该符号串只包含终结符 2)该符号串能根据语法G从起始符S推导出来。 2021/2/23 第6章句法语法与语义理论及分析下近
2021/2/23 第6章句法(语法)与语义理论及分析 25 一般来说, 如果把语法G定义的语言记作L(G), 则 L(G)={W│W∈T*, 且S W} 这条定义的意思是, 对于所有符号串W, 如果W是由终结符 所组成的串, 且用语法G可以从起始符S中推导出W, 那么符号 串W的集合就是语法G 所生成的语言L(G)。 换言之, 一个符号串要属于L(G)必须满足两个条件: (1) 该符号串只包含终结符; (2) 该符号串能根据语法G从起始符S推导出来。 下页 6 . 2 其它相关语法介绍