长春工业大学计算机科学与工程学院2011春 长春工业大学计算机科学与工程学院2011春 2011
Principle of Compiling
例3.2写一文法，使其语言是奇数集合，但不允许出现以0打 写一文法，使其语言是奇数集合，但不允许出现以 打 写一文法 头的奇数。 头的奇数。
M B DD … D A
长春工业大学计算机科学与工程学院2011春 长春工业大学计算机科学与工程学院2011春 2011
Principle of Compiling
0型文法 型文法
0型文法的产生式：α → β， 型文法的产生式： 型文法的产生式 ， α∈ （VN∪VT）+且至少含一 N ∈ 且至少含一V β ∈ （VN∪VT）* 相应语言称为0型语言，又称为递归可枚举集合。 相应语言称为 型语言，又称为递归可枚举集合。 型语言
长春工业大学计算机科学与工程学院2011春 长春工业大学计算机科学与工程学院2011春 2011
Principle of Compiling
文法和语言的分类
Chomsky对文法层次化划分，分为四类： 对文法层次化划分，分为四类： 对文法层次化划分 0型:无约束文法 型 无约束文法 1型:上下文有关文法 型 上下文有关文法 2型:上下文无关文法 型 上下文无关文法 3型:正规文法 型 正规文法
长春工业大学计算机科学与工程学院2011春 长春工业大学计算机科nciple of Compiling
句型、 句型、句子
对于文法G[S]: 对于文法 * 如果： 称为G的一个句型， 如果： S ⇒ α ，则α称为 的一个句型， 称为 的一个句型 开始符号是最简单的句型。 开始符号是最简单的句型。 如果：α是 G[S]的一个句型 且α∈VT* ， 的一个句型, 如果： 是 的一个句型 ∈ 被称为G[S]的一个句子， 的一个句子 则 α被称为 被称为 的一个句子， 也就是说句子是全部由终结符号组成的句型。 终结符号组成的句型 也就是说句子是全部由终结符号组成的句型。
长春工业大学计算机科学与工程学院2011春 长春工业大学计算机科学与工程学院2011春 2011
Principle of Compiling
习题
• 已知文法 已知文法G[Z]=({Z},{a,b},Z,P) P:Z→ aZb | ab 求该文法确定的语言。 求该文法确定的语言。 • 已知语言为 L(G)={abna | n ≥ 1}，构造产生该语言的 已知语言为: ， 文法。 文法。
长春工业大学计算机科学与工程学院2011春 长春工业大学计算机科学与工程学院2011春 2011
Principle of Compiling
1型文法 型文法
1型文法的产生式：γ1Aγ2 →γ1δγ2 ， 型文法的产生式： 型文法的产生式 其中A 其中 ∈ VN ， γ1, γ2∈ (VN∪VT)* δ ∈ (VN∪VT)+ γ1, γ2为上下文 1型文法也可以定义为： 型文法也可以定义为： 型文法也可以定义为 所有规则的右部都比左部长。 所有规则的右部都比左部长。
长春工业大学计算机科学与工程学院2011春 长春工业大学计算机科学与工程学院2011春 2011
Principle of Compiling
文法的语言
文法的语言：定义为： 文法的语言 定义为： 定义为
L(G[S]) = {α | S ⇒α 并且 α ∈ VT*} 一个文法的语言就是该文法的所有的句子的集合。 一个文法的语言就是该文法的所有的句子的集合。 文法的语言是所有终结符号串所组成的集合的子集， 文法的语言是所有终结符号串所组成的集合的子集，一般是真 子集。 子集。
长春工业大学计算机科学与工程学院2011春 长春工业大学计算机科学与工程学院2011春 2011
Principle of Compiling
2型文法 型文法
2型文法的产生式： 型文法的产生式： 型文法的产生式 A→ δ ，其中A ∈ VN , δ ∈ （VN∪VT）* 。 其中 2型文法又称为上下文无关文法。 型文法又称为上下文无关文法。 型文法又称为上下文无关文法 一般的程序设计语言的语法都使用2型文法描述。 一般的程序设计语言的语法都使用 型文法描述。 型文法描述 2型文法的例子：S →ab|aSb 型文法的例子： 型文法的例子
+
文法和语言有如下关系： 文法和语言有如下关系：
– 给定一个文法 就能从结构上唯一的确定其语言,即: G→L(G) 给定一个文法,就能从结构上唯一的确定其语言 即 就能从结构上唯一的确定其语言 – 给定一种语言 能确定其文法,但不唯一，即: L→G1 或G2 或…。 给定一种语言,能确定其文法 但不唯一 能确定其文法 但不唯一， 。 – 若文法G1和文法 所产生的语言相同，即L(G1) = L(G2)，则 若文法 和文法G2所产生的语言相同， ， 和文法 所产生的语言相同 称文法G1和文法 等价。 和文法G2等价 称文法 和文法 等价。
长春工业大学计算机科学与工程学院2011春 长春工业大学计算机科学与工程学院2011春 2011
Principle of Compiling
文法与语言举例
描述语言L={ban | n>=1}的文法： 的文法： 描述语言 的文法 G=({S,A},{a,b},S,P) P:S →bA P:S →AB A →aA | a B →bB | b描述的语言是： 描述的语言是： 描述的语言是 文法G =({S,A,B},{a,b},S,P) 文法 A →aA | a L={anbm | m，n>=1} ，
长春工业大学计算机科学与工程学院2011春 长春工业大学计算机科学与工程学院2011春 2011
Principle of Compiling
3型文法 型文法/RG 型文法
文法产生式：（ ） 或者A→aB 文法产生式：（1） A→a或者 ：（ 或者 或者A→Ba （2） A→a或者 ） 或者 其中A， ∈ 其中 ，B∈ VN，a∈VT。 ∈ 3型文法又称为右（左）线性文法，正则文法，其 型文法又称为右（ 型文法又称为右 线性文法，正则文法， 语言也称为正则语言。 语言也称为正则语言。 3型文法的例子：S →0|1|1A|2B 型文法的例子： 型文法的例子 A →1A|0B B →0|1|0B
长春工业大学计算机科学与工程学院2011春 长春工业大学计算机科学与工程学院2011春 2011
Principle of Compiling
例: G = ({E}, {i, +, *, (, ) } , P , E) P： E → E + E | E * E | ( E ) | i ： 表达式(i)和 的推导： 表达式 和(i+i)*i的推导： 的推导
长春工业大学计算机科学与工程学院2011春 长春工业大学计算机科学与工程学院2011春 2011
Principle of Compiling 产生标识符的文法。 例:产生标识符的文法。 产生标识符的文法 L:“字母”类非终结符, L→a∣b∣…∣z; “字母”类非终结符 ∣ ∣ D:“数字”类非终结符, D→0∣1∣…∣9; “数字”类非终结符 ∣ ∣ T:“字母或数字”类非终结符，则有：T→L∣D； “字母或数字”类非终结符，则有： ∣ ； S:“字母数字串”类，S→T∣ST； “字母数字串” ∣ ； I:“标识符”，I→L∣LS； “标识符” G=({a,b,…,z,0,…,9},{I,S,T,L,D},I,P) … … P:I→L∣LS ∣ S→T∣ST ∣ T→L∣D ∣ L→a∣b∣…∣z ∣ ∣ D→0∣1∣…∣9 ∣ ∣
Principle of Compiling
第3章 语法分析 章
3.1 文法和语言 3.2 推导与语法树 3.3 自上而下分析方法 3.4 自下而上分析方法 3.5 LR分析法 分析法
长春工业大学计算机科学与工程学院2011春 长春工业大学计算机科学与工程学院2011春 2011
Principle of Compiling
3.1 文 法 和 语 言
文法是程序语言的生成系统; 文法是程序语言的生成系统 自动机则是程序语言的识别系统 用文法可以精确地定义一个语言，并依据该文法构 造出识别这个语言的自动机。 程序语言的词法可用正规文法描述; 语法可用上下文无关文法描述; 语义则要借助于上下文有关文法描述。
长春工业大学计算机科学与工程学院2011春 长春工业大学计算机科学与工程学院2011春 2011
中中位 最 高 位
长春工业大学计算机科学与工程学院2011春 长春工业大学计算机科学与工程学院2011春 2011
最 低 位
Principle of Compiling 最高位允许出现 ～ ，用非终结符B表示 表示； 最高位允许出现1～9，用非终结符 表示； 允许出现 中间部分可出现任意多位数字0～ ，每一位用非终结符D表示 表示； 中间部分可出现任意多位数字 ～9，每一位用非终结符 表示； 最低位只允许出现 、 、 、 、 等奇数 等奇数， 表示。 最低位只允许出现1、3、5、7、9等奇数，用A表示。 只允许出现 表示 由于中间部分可出现任意位，引入了一个非终结符M， 由于中间部分可出现任意位，引入了一个非终结符 ，它包括最 高位和中间位部分。 高位和中间位部分。 文法为： 文法为： G=({0,1,…,9},{N,A,M,B,D},N,P) … P:N→A∣MA ∣ M→B∣MD ∣ /*一位数字 多位数字 一位数字│多位数字 一位数字 多位数字*/ /*仅两位数字 无中间位 多于两位数字 仅两位数字(无中间位 多于两位数字*/ 仅两位数字 无中间位)│多于两位数字
Principle of Compiling
文法
文法通常表示成四元组G=(VT，VN，S，P)，其中： 文法通常表示成四元组G=(V P)，其中： 为终结符号集， 这是一个非空有限集， (1)VT 为终结符号集 ， 这是一个非空有限集 ， 它的每个 元素称为终结符号； 元素称为终结符号； 为非终结符集， 它也是一个非空有限集， (2)VN 为非终结符集 ， 它也是一个非空有限集 ， 其每个 元素称为非终结符号，且有VT∩VN=Φ； =Φ； 元素称为非终结符号，且有V 为一文法开始符， (3)S为一文法开始符 ， 是一个特殊的非终结符号 ， 即 )S 为一文法开始符 是一个特殊的非终结符号， S∈VN； (4) P是产生式的非空有限集， 其中每个产生式 或称规 是产生式的非空有限集，其中每个产生式(或称规 是产生式的非空有限集 是一序偶(α， ，通常写作α→β或α::=β, α∈(VT∪VN)+ 则)是一序偶 ，β)，通常写作 是一序偶 或 ∈ 且至少有一个非终结符，而β∈(VT∪VN)* 且至少有一个非终结符， ∈