编译原理-第3章 文法和语言

第3章:文法和语言的概念和表示3.0

概述3.1

形式语言基础3.2文法的直观理解3.3文法和语言的定义3.4

文法的类型3.5

语法树与二义性3.6

句型的分析3.0概述用高级语言编程比用低级语言方便，但要解决两个问题：(1)计算机怎样懂得高级语言程序，这就需要一个翻译程序实现从源程序到目标程序的转换。(2)用什么方法来精确定义高级语言，即怎样精确描述高级语言。

要构造一个编译程序，应深刻理解被编译的源语言的结构（即词法和语法）及其含义（即语义），同时要弄清源语言的语法规则和语义规则是采用什么理论或什么方法来描述的。

本章目的为语言的语法描述寻求工具，该工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读）形式工具--形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。语言概述语言是由句子组成的集合，或说是由一组符号串所构成的集合。汉语——所有符合汉语语法的句子的全体英语——所有符合英语语法的句子的全体程序设计语言——所有该语言的程序的全体每个句子构成的规律研究语言每个句子的含义每个句子和使用者的关系研究程序设计语言每个程序构成的规律每个程序的含义每个程序和使用者的关系语言研究的三个方面语法Syntax

语义Semantics

语用Pragmatics语法——表示构成语言句子的各个记号之间的组合规律。语义——表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）语用——表示在各个记号所出现的行为中，它们的来源、使用和影响。

每种语言具有两个可开始的特性，即语言的形式和该形式相关联的意义。语言的实例若在语法上是正确的，其相关联的意义可以从两个观点来看，其一是该句子的创立者所想要表示的意义，另一是接收者所检验到的意义。这两个意义并非总是一样的，前者称为语言的语义，后者是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。

如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。

任何语言均可看作一个集合。这个集合中的每个元素都是在一定符号集（字母表）上的一个符号串。

对于自然语言来说，它们是定义在某个字母表上的句子的集合。对于程序语言来说，它们也是定义在某个字母表上的句子的集合。这里的句子，就是一个源程序。

通常，源程序是由关键字、标识符、常数、运算符以及一些界限符组成。这些语法成分统称为单词或单词符号。单词符号是语言中具有独立意义的最基本单位。语言的单词符号是由词法规则所确定的，即词法规则规定了单词符号的形成规则。

当我们表述一种语言时，无非是要说明这种语言的句子，如果语言只含有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，就存在着如何给出它的有穷表示的问题。以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语。“我是大学生”。是汉语的一个句子用语法来描述：〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词〉｜〈名词〉〈代词〉∷=我｜你｜他〈名词〉∷=王明｜大学生｜工人｜英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是｜学习〈直接宾语〉∷=〈代词〉｜〈名词〉

有了一组规则以后，按照如下方式用它们导出句子：开始去找∷=左端的带有〈句子〉的规则并把它由∷=右端的符号串代替，这个动作表示成：〈句子〉〈主语〉〈谓语〉，然后在得到的串〈主语〉〈谓语〉中，选取〈主语〉或〈谓语〉，再用相应规则的∷=右端代替之。比如，选取了〈主语〉，并采用规则〈主语〉∷=〈代词〉，那么得到：〈主语〉〈谓语〉〈代词〉〈谓语〉，重复做下去，句子：“我是大学生”的全部动作过程是：〈句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉我〈谓语〉我〈动词〉〈直接宾语〉

我是〈直接宾语〉我是〈名词〉我是大学生“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。3.1形式语言基础基本概念:一、字母表和符号串1.字母表：符号的非空有限集合例：={a，b，c}2.符号：字母表中的元素例：a，b，c3.符号串：符号的有穷序列例：a,aa,ac,abc，..

特别地,空符号串：无任何符号的符号串(ε)

符号串的形式定义

有字母表，定义：（1）ε是上的符号串；（2）若x是上的符号串，且a，则ax或xa是上的符号串；（3）y是上的符号串，iff（当且仅当）y可由（1）和（2）产生。

4.符号串集合：由符号串构成的集合。二、符号串和符号串集合的运算

5.符号串相等：若x、y是集合上的两个符号串，则x＝yiff（当且仅当）组成x的每一个符号和组成y的每一个符号依次相等。

6.符号串的长度：x为符号串，其长度|x|等于组成该符号串的符号个数。例：x＝STV，|x|=3

特别地,|ε|=0例：A＝{a,b},B={c,d},AB=？8.符号串集合的乘积运算：令A、B为符号串集合，定义

AB＝{xy|x∈A，y∈B}

{ac，ad，bc，bd}

因为εx＝xε＝x，所以{ε}A=A{ε}=A7.符号串的联接：若x、y是定义在Σ是上的符号串，且x＝XY，y＝YX，则x和y的联接xy＝XYYX也是Σ上的符号串。注意：一般xy≠yx，而εx＝xε＝x9.方幂运算：符号串集合的方幂符号串的方幂有任一符号串集合A，定义:有任一符号串X，定义:A0={ε},X0=εA1=A,X1=XA2=AA,X2=XXA3=AAA,X3=XXX

…

…

An＝An-1A=AAn-1Xn=XX…X

＝AA…An个

n个其中:n≥010.符号串集合的闭包运算：设A是符号串集合，定义

A＋=A1∪A2∪A3∪……∪An∪……

称为集合A的正则闭包。

A*=A0∪A1∪A2∪A3∪……∪An∪……=A0∪A＋

称为集合A的星闭包。例：A={x,y}A＋＝？

A*＝？{x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,……}

A1

A2

A3{ε,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,……}

A0A1

A2

A3

为什么对符号、符号串、符号串集合以及它们的运算感兴趣？若A为某语言的基本字符集

A＝{a,b,……z,0,1,……,9,+,－,×,_/,(,),=……}B为单词集

B={begin,end,if,then,else,for,……,<标识符>,<常量>,……}

则BA*

。语言的句子是定义在B上的符号串。若令C为句子集合，则CB*,程序C3.2文法的直观理解1.什么是文法：

文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文法”（或称为“语法”）。

例：有一句子：“我是大学生”。这是一个在语法、语义上都正确定句子，该句子的结构（称为语法结构）是由它的语法决定的。在本例中它为“主谓结构”。如何定义句子的合法性？有穷语言无穷语言

2.语法规则：

我们通过建立一组规则（产生式），来描述句子的语法结构。规定用“::=”表示“由……组成”。<句子>::=<主语><谓语><主语>::=<代词>|<名词><代词>::=你|我|他<名词>::=

王民|大学生|工人|英语<谓语>::=<动词><直接宾语><动词>::=是|学习<直接宾语>::=<代词>|<名词>由产生式推导句子：

<句子>=><主语><谓语><主语><谓语>=><代词><谓语>

……

……这种推导一直进行下去，直到所有带<>的符号都由终结符号替代为止。

有了一组产生式之后，可以按照一定的方式用它们去推导或产生句子。

推导方法：从一个要开始的符号开始推导，即用相应产生式的右部来替代产生式的左部，每次仅用一条产生式去进行推导。<句子>

<主语><谓语>

<代词><谓语>

我<谓语>

我<动词><直接宾语>

我是<直接宾语>

我是<名词>

我是大学生<句子>::=<主语><谓语><主语>::=<代词>|<名词><代词>::=你|我|他<名词>::=

王民|大学生|工人|英语<谓语>::=<动词><直接宾语><动词>::=是|学习<直接宾语>::=<代词>|<名词>推导方法：从一个要开始的符号开始推导，即用相应产生式的右部来替代产生式的左部，每次仅用一条产生式去进行推导。例：给定一组语法规则，考察一个句子：“我是大学生”的推导过程。例：有一英语句子：Thebigelephantatethepeanut.<句子>::=<主语><谓语><主语>::=<冠词><形容词><名词><冠词>::=the<形容词>::=big<名词>::=elephant<谓语>::=<动词><宾语><动词>::=ate<宾语>::=<冠词><名词><名词>::=peanut<句子>=><主语><谓语>=><冠词><形容词><名词><谓语>=>the<形容词><名词><谓语>=>thebig<名词><谓语>=>thebigelephant<谓语>=>thebigelephant<动词><宾语>=>thebigelephantate<宾语>=>thebigelephantate<冠词><名词>=>thebigelephantatethe<名词>=>thebigelephantatethepeanut<句子>::=<主语><谓语><主语>::=<冠词><形容词><名词><冠词>::=the<形容词>::=big<名词>::=elephant|peanut<谓语>::=<动词><宾语><动词>::=ate<宾语>::=<冠词><名词>Thebigelephantatethepeanut.上述推导可写成<句子>=>thebigelephantatethepeanut+说明：

(1)有若干语法成分同时存在时，我们总是从最左的语法成分进行推导，这称之为最左推导，类似的有最右推导（一般推导）。

(2)从一组产生式可推出不同的句子，如以上产生式还可推出“大象吃象”、“大花生吃象”、“大花生吃花生”等句子，它们在语法上都正确，但在语义上都不正确。

所谓文法是在形式上对句子结构的定义与描述，而未涉及语义问题。4.语法树：我们用语法树来描述一个句子的语法结构。<句子><主语><谓语><冠词><形容词><名词><动词><宾语><冠词><名词>Thebigelephantatethepeanut语法成分（在形式语言中又称“非终结符”）单词符号（在形式语言中又称“终结符号”)3.3.1文法的定义3.3文法和语言的形式定义

定义1:文法G=（VN，VT，P，Z）

VN

：非终结符号集

VT

：终结符号集

P：产生式或规则的集合

Z：开始符号（识别符号）Z∈VNV＝VN∪VT称为文法的字汇表产生式：U::xU∈VN,x∈V*其中:①产生式：产生式是一个有序对(U,x),通常写为:U::x或Ux；|U|=1|x|0②非终结符号：出现在产生式的左部,且能推出符号或符号串的那些符号。其全体构成非终结符号集，记为VN

。③终结符号：不出现在产生式的左部,且不能推出符号或符号串的那些符号。其全体构成终结符号集，记为VT

。P={<无符号整数>→<数字串>；

<数字串>→<数字串><数字>；

<数字串>→<数字>；

<数字>→0；

<数字>→1；

…………

<数字>→9；

}Z=<无符号整数>；例：无符号整数的文法：

G[<无符号整数>]=（VN，VT，P，Z）

VN＝{<无符号整数>,<数字串>,<数字>} VT={0,1,2,3,……9}几点说明：产生式左边符号构成集合VN，且Z∈VN有些产生式具有相同的左部，可以合在一起例、<无符号整数>→<数字串>；

<数字串>→<数字串><数字>|<数字>；

<数字>→0|1|2|3|……|9

文法的BNF表示给定一个文法，实际只需给出产生式集合，并指定开始符号例、G[<无符号整数>]<无符号整数>→<数字串>；

<数字串>→<数字串><数字>|<数字>；

<数字>→0|1|2|3|……|93.3.2推导与归约

定义2：直接推导：文法G：v＝xUy，w＝xuy,

其中x、y∈V*

，U∈VN,u∈V*,

若U::u∈P，则vw，即xUyxuy。若x＝y＝ε，有U::u，则Uu

换句话说，x和y是符号串，若使用一次产生式可以从x变换出y，则称x直接推导出y(或者说y是x的直接推导），记为xy。

当符号串已没有非终结符号时，推导就必须终止。因为终结符不可能出现在产生式左部，所以将在产生式左部出现的符号称为非终结符号。例如：G[N]：

N→ND|DD→0|1|2|3|4|5|6|7|8|9NNDNDDND9N09D09109

(6)==>==>(1)==>(3)(4)==>==>(2)(5)==>

＋N==>109定义3：+推导：x和y是符号串，若使用若干次产生式可以从x变换出y，则称x推导出y(或者说y是x的推导），记为xy。＋NNDNDDND9N09D09109

(6)==>==>(1)==>(3)(4)==>==>(2)(5)==>例：则有：

定义4：

*推导：x和y是符号串，若使用0次或若干次产生式可以从x变换出y，则称x*推导出y(或者说y是x的*推导），记为xy。**N==>109则有：*N==>N或者说：若有直接推导序列：x=U0==>U1==>U2==>……==>Un=y,则x==>y。+直观意义：规范推导＝最右推导

定义5：最右推导：若符号串α中有两个以上的非终结符时，对推导的每一步坚持把α中的最右非终结符进行替换，称为最右推导。最左推导：若符号串α中有两个以上的非终结符时，对推导的每一步坚持把α中的最左非终结符进行替换，称为最左推导。

定义6：推导的逆过程称之为归约。例：x==>y,可称为x直接推导出y，也可称为y直接归约出x。

＋x==>y,可称为x推导出y，也可称为y归约出x。3.3.3语言的形式定义文法G[Z]所产生的所有句子的集合

定义7：文法G[Z]

（1）句型：x是句型

Zx,且x∈V*；**（2）句子：x是句子

Zx,且x∈VT*；*（3）语言：L（G[Z]）={x|Zx，x∈VT*}；即：句型是由文法开始符号推导出来的由终结符和非终结符组成的符号串。即：句子是由文法开始符号推导出来的由终结符组成的符号串。例：{abna|n≥1},构造其文法

G1[Z]：Z→aBa, B→b|bBG2[Z]：Z→aBa, B→b|Bb

定义8:G和G'是两个不同的文法，若L(G)=L(G'),

则G和G’为等价文法。编译感兴趣的问题是:给定x,G,求xL(G)?x算法1算法2xL(G)?Gyn出错处理停机3.3.4递归文法1.递归产生式：产生式右部有与左部相同的符号 对于U::=xUy

若x=ε,即U::=Uy，左递归； 若y=ε,即U::=xU，右递归；2.递归文法：文法G，存在U

∈VNifU==>…U…,则G为递归文法；

ifU==>U…,则G为左递归文法；

ifU==>…U,则G为右递归文法；+++4.递归文法的优点：可用有穷条产生式，定义无穷语言

例：对于前面给出的无符号整数的文法是有递归文法，用13条产生式就可以定义出所有的无符号整数。若不用递归文法，那将要用多少条产生式呢？!3.左递归文法的缺点：不能用自顶向下的方法来进行语法分析会造成死循环（后面将详细论述）3.4文法分类

形式语言：用文法和自动机所描述的没有语义的语言。

文法定义：乔姆斯基将所有文法都定义为一个四元组：

G=（VN，VT，P，Z）

VN：非终结符号集

VT：终结符号集

P：产生式或规则的集合

Z：开始符号（开始符号）Z∈VN

语言定义：

L（G[Z]）={x|Z==>x,x∈VT*,}*

文法和语言分类：0型、1型、2型、3型这几类文法的差别在于对产生式施加不同的限制。定义9：0型文法：P：u::=v

其中u∈V*

，v∈V* 0型语言：L0这种语言可以用图灵机(Turing)接受. 0型文法称为短语结构文法。产生式的左部和右部都可以是符号串，一个短语可以产生另一个短语。定义10：

1型文法：P：xUy::=xuy ︱其中U∈VN，x、y、u∈V*1型语言：L1这种语言可以由一种线性界限自动机接受.

称为上下文敏感或上下文有关。也即只有在x、y这样的上下文中才能把U改写为u定义10：

1型文法：P：u::=v ︱u︱≥︱v︱u,v∈V*定义11：2型文法：P：U::=u

其中U∈VN，u∈V*2型语言：L2这种语言可以由下推自动机接受.

称为上下文无关文法。也即把U改写为u时，不必考虑上下文。注意：2型文法与BNF表示相等价。（右线性）

P：U::=t

或U::=tW

其中U、W∈VNt∈VT3型语言：L3又称正则语言、正则集合 这种语言可以由有穷自动机接受.3型文法又被称为正则文法。它是对2型文法进行进一步限制。（左线性）

P：U::=t

或U::=Wt

其中U、W∈VNt∈VT定义12：

3型文法：根据上述讨论，L0L1L2L30型文法可以产生L0、L1、L2、L3，但2型文法只能产生L2，不能产生L1。∪∪∪3.5语法树与二义性文法3.5.1推导与语法树（1）语法树：句子结构的图示表示法，它是一种有向图，由结点和有向边组成。

结点：符号 根结点：开始符号 中间结点：非终结符 叶结点：终结符或非终结符

有向边：表示结点间的派生关系。

ZUVabcd

注意一个重要事实：文法所能产生的句子，可以用不同的推导原则（使用产生式顺序不同）将其推导出来。语法树的生成规律不同，但最终生成的语法树形状完全相同。某些文法有此性质，而某些文法不具此性质。(2)句型的推导及语法树的生成（自顶向下）给定G[Z]，句型w：可建立推导序列，Zw

可建立语法树，以Z为树根结点，每步推导生成语法树的一层分支，最终可生成句型的语法树。*

<无符号整数><数字串><数字串><数字><数字>1(1)(2)(3)(5)(4)0一般推导：(3)子树与简单子树

子树：语法树中的某个结点（子树的根）连同它向下派生的部分所组成。简单子树：只有单层分枝的子树称为简单子树。

<无符号整数><数字串><数字串><数字><数字>1(1)(2)(3)(5)(4)0(4)树与推导句型推导过程

句型语法树的生长过程

由推导构造语法树1从开始符号开始，自左向右建立推导序列。由根结点开始，自上而下建立语法树。例：给定文法G[<无符号整数>]和句型10,考察语法树与推导过程。规范推导[<无符号整数>]<无符号整数><数字串><数字串>R<数字串><数字><数字串><数字>R<数字串>0R0<数字><数字>0R110R

由语法树构造归约2自下而上地修剪子树的末端结点，直至把整棵树剪掉（留根），每剪一次对应一次归约。从句型开始，自右向左地逐步进行归约，建立归约序列。规范归约与规范推导互为逆过程[<无符号整数>]<数字串><数字串><数字>0<数字>1<无符号整数><数字串>R<数字串><数字>R<数字串>0R<数字>0R10R定义14：通过规范推导或规范归约所得到的句型称为规范句型。不是规范推导

在上例中，<数字><数字>就不是规范句型，因为：<无符号整数><数字串> <数字串><数字>

<数字><数字>RR3.5.2文法的二义性

定义14.1：若对于一个文法的某一句子存在两棵不同的语法树，则该文法是二义性文法，否则是无二义性文法。

换而言之，无二义性文法的句子只有一棵语法树，尽管推导过程可以不同。下面举一个二义性文法的例子：

G[E]: E:=E+E|E*E|(E)|i

VN

={E}

VT={+,*,(,),i}对于句子S＝i＋i*i∈L（G[E]

），存在不同的规范推导：EEE+EE*iiiEEE*EE+iii这两种不同的推导对应了两种不同的语法树(1)EE+EE+E*EE+E*iE+i*ii＋i*iRRRRR(2)

EE*EE*iE+E*iE+i*ii＋i*iRRRRRG[E]: E:=E+E|E*E|(E)|i

定义14.2：若一个文法的某句子存在两个不同的规范推导，则该文法是二义性的，否则是无二义性的。

以上是自顶向下来看文法的二义性，我们还可以自底向上来看文法的二义性。上例中，规范句型E+E*i

是由i＋i*i通过两步规范规约得到的，但对于同一个句型E+E*i，它有两个不同的句柄（对应上述两棵不同的语法树）：i和E＋E。因此语法的二义性意味着句型的句柄不唯一。EEE+EE*iEEE*EE+i句柄：i句柄：E＋E

若文法是二义性的，则在编译时就会产生不确定性，遗憾的是在理论上已经证明：文法的二义性是不可判定的，即不可能构造出一个算法，通过有限步骤来判定任一文法是否有二义性。

现在的解决办法是：提出一些限制条件，称为无二义性的充分条件，当文法满足这些条件时，就可以判定文法是无二义性的。

由于无二义性文法比较简单，我们也可以采用另一种解决办法：即不改变二义性文法，而是确定一种编译算法，使该算法满足无二义性充分条件。

定义14.3若一个文法的某规范句型的句柄不唯一，则该文法是二义性的，否则是无二义性的。例:算术表达式的文法：E::=E+E|E*E|(E)|iE::=E+T|TT::=T*F|FF::=(E)|i例:Pascal语言条件语句的文法<条件语句>::=If<布尔表达式>then<语句>|If<布尔表达式>then<语句>else<语句><语句>::=<条件语句>|<非条件语句>|…….3.6句型的分析

任务：给定G[Z]:S∈VT*,判定是否有S

L(G[E])?

这是词法分析和语法分析所要做的工作，将在第三、四章中详细介绍。3.6.1句型的短语、简单短语和句柄*定义15:

给定文法G[Z],w=xuy∈V+，为该文法的句型,

若ZxUy,且U

u,则u是句型w相对于U的短语；其中U∈VN，u∈V+，x,y∈V*＋

直观理解：短语是前面句型中的某个非终结符所能推出的符号串。或短语定义:

设G[Z]是给定文法,w=xuy∈V+，为该文法的句型,如果满足下面两个条件:①ZxUy；②Uu；则称句型xuy中的子串u是句型xuy的短语。*＋定义17.

任一句型的最左简单短语称为该句型的句柄。

给定句型找句柄的步骤： 短语 简单短语句柄

注意：短语、简单短语是相对于句型而言，一个句型可能有多个短语、简单短语，句柄只能有一个。定义16:

给定文法G[Z],w=xuy∈V+，为该文法的句型,

若ZxUy,且U

u,则u是句型w相对于U的简单短语。其中U∈VN，u∈V+，x,y∈V**例：给定文法G：

E→T|E+T|E－TT→F|T*F|T／FF→i|(E)符号串（T+i）*i－F是文法G的一个句型，求其短语、简单短语和句柄。E

E－T

T－T

T*F－T

F*F－T(E)*F－T(T+T)*F－T(T+F)*F－T(T+i)*F－T(T+i)*i－T(T+i)*i－T解：短语有8个：1.E

E，E（T+i）*i－F则有：（T+i）*i－F2.E

T－F，T（T+i）*i则有：（T+i）*i3.E

T*i－F，T（T+i）则有：（T+i）4.E(E)*i－F，ET+i则有：T+i5.E(E+i)*i－F，ET则有：T6.E(T+F)*i－F，Fi

则有：第一个i7.E(T+i)*F－F，Fi

则有：第二个i8.E(T+i)*F－T，TF

则有：F*+*+*+*+*+*+*+*+定义:

给定文法G[Z],w=xuy∈V+，为该文法的句型,

若ZxUy,且U

u,则u是句型w相对于U的短语；若ZxUy,且U

u,则u是句型w相对于U的简单短语。其中U∈VN，u∈V+，x,y∈V***＋U其简单短语有4个：1.E

(E+i)*i－F,ET则有：T2.E

(T+F)*i－F,Fi

则有：第一个i3.E

(T+i)*F－F,Fi

则有：第二个i4.E

(T+i)*F－T,TF

则有：F句柄有1个：

TEE－TTT*FF(E)FiE+TTFi用语法树求短语、简单短语和句柄的方法：1）每个句型都有一棵语法树；2）每棵语法树的叶（从左到右）组成一句型；3）每个子树的叶（从左到右）组成一短语；4）每个简单子树的叶（从左到右）组成一简单短语；5）最左简单子树的叶（从左到右）组成一句柄。只需画出句型的语法树，然后根据子树找短语→简单短语→句柄。3.7有关文法的实用限制

若文法中有如U::=U的产生式，则这就是有害产生式，它会引起二义性。

例如存在U::=U，U::=a|b,则有两棵语法树：UaUUa

多余产生式：（1）在推导文法的所有句子中，始终用不到的产生式。即该产生式的左部非终结符不出现在任何句型中。（2）在推导句子的过程中，一旦使用了该产生式，将推不出任何终结符号串。即该产生式中含有推不出任何终结符号串的非终结符。

例如给定G[Z]，若其中关于U的产生式只有如下一条：

U::=xUy

该产生式是多余产生式。若还有U::=a，则此产生式并非多余若某文法中无有害产生式或多余产生式，则称该文法是压缩过的。小结掌握符号串和符号串集合的运算、文法、句型、句子和语言的定义几个重要概念：推导、归约、递归、短语、简单短语和句柄、语法树、文法的二义性、文法的实用限制等。掌握文法的表示：BNF、扩充的BNF范式、语法图。了解文法分类。本章作业48页：3题，4题，5题，7题，11题MagneticResonanceImaging磁共振成像发生事件作者或公司磁共振发展史1946发现磁共振现象BlochPurcell1971发现肿瘤的T1、T2时间长Damadian1973做出两个充水试管MR图像Lauterbur1974活鼠的MR图像Lauterbur等1976人体胸部的MR图像Damadian1977初期的全身MR图像

Mallard1980磁共振装置商品化1989

0.15T永磁商用磁共振设备中国安科

2003诺贝尔奖金LauterburMansfierd时间MR成像基本原理实现人体磁共振成像的条件:人体内氢原子核是人体内最多的物质。最易受外加磁场的影响而发生磁共振现象(没有核辐射)有一个稳定的静磁场（磁体）梯度场和射频场：前者用于空间编码和选层，后者施加特定频率的射频脉冲，使之形成磁共振现象信号接收装置：各种线圈计算机系统：完成信号采集、传输、图像重建、后处理等

人体内的H核子可看作是自旋状态下的小星球。自然状态下，H核进动杂乱无章，磁性相互抵消zMyx进入静磁场后，H核磁矩发生规律性排列（正负方向），正负方向的磁矢量相互抵消后，少数正向排列（低能态）的H核合成总磁化矢量M，即为MR信号基础ZZYYXB0XMZMXYA:施加90度RF脉冲前的磁化矢量MzB:施加90度RF脉冲后的磁化矢量Mxy.并以Larmor频率横向施进C:90度脉冲对磁化矢量的作用。即M以螺旋运动的形式倾倒到横向平面ABC在这一过程中，产生能量

三、弛豫（Relaxation）回复“自由”的过程

1.

纵向弛豫（T1弛豫）：

M0（MZ）的恢复，“量变”高能态1H→低能态1H自旋—晶格弛豫、热弛豫

吸收RF光子能量（共振）低能态1H高能态1H

放出能量（光子，MRS）T1弛豫时间：

MZ恢复到M0的2/3所需的时间

T1愈小、M0恢复愈快T2弛豫时间：MXY丧失2/3所需的时间；T2愈大、同相位时间长MXY持续时间愈长MXY与ST1加权成像、T2加权成像

所谓的加权就是“突出”的意思

T1加权成像（T1WI）----突出组织T1弛豫（纵向弛豫）差别

T2加权成像（T2WI）----突出组织T2弛豫（横向弛豫）差别。

磁共振诊断基于此两种标准图像磁共振常规h检查必扫这两种标准图像.T1的长度在数百至数千毫秒（ms）范围T2值的长度在数十至数千毫秒（ms）范围

在同一个驰豫过程中,T2比T1短得多

如何观看MR图像：首先我们要分清图像上的各种标示。分清扫描序列、扫描部位、扫描层面。正常或异常的所在部位---即在同一层面观察、分析T1、T2加权像上信号改变。绝大部分病变T1WI是低信号、T2WI是高信号改变。只要熟悉扫描部位正常组织结构的信号表现，通常病变与正常组织不会混淆。一般的规律是T1WI看解剖,T2WI看病变。磁共振成像技术－－图像空间分辨力，对比分辨力一、如何确定MRI的来源（一）层面的选择1.MXY产生（1H共振）条件

RF=ω=γB02.梯度磁场Z（GZ）

GZ→B0→ω

不同频率的RF

特定层面1H激励、共振

3.层厚的影响因素

RF的带宽↓

GZ的强度↑层厚↓〈二〉体素信号的确定1、频率编码2、相位编码

M0↑--GZ、RF→相应层面MXY----------GY→沿Y方向1H有不同ω

各1H同相位MXY旋进速度不同同频率一定时间后→→GX→沿X方向1H有不同ω沿Y方向不同1H的MXYMXY旋进频率不同位置不同（相位不同）〈三〉空间定位及傅立叶转换

GZ----某一层面产生MXYGX----MXY旋进频率不同

GY----MXY旋进相位不同（不影响MXY大小）

↓某一层面不同的体素，有不同频率、相位

MRS（FID）第三节、磁共振检查技术检查技术产生图像的序列名产生图像的脉冲序列技术名TRA、COR、SAGT1WT2WSETR、TE…….梯度回波FFE快速自旋回波FSE压脂压水MRA短TR短TE－－T1W长TR长TE－－T2W增强MR最常用的技术是：多层、多回波的SE（spinecho，自旋回波）技术磁共振扫描时间参数：TR、TE磁共振扫描还有许多其他参数：层厚、层距、层数、矩阵等序列常规序列自旋回波（SE）,快速自旋回波（FSE）梯度回波（FE）反转恢复（IR），脂肪抑制（STIR）、水抑制（FLAIR）高级序列水成像（MRCP,MRU,MRM）血管造影（MRA,TOF2D/3D）三维成像（SPGR）弥散成像（DWI）关节运动分析是一种成像技术而非扫描序列自旋回波（SE）必扫序列图像清晰显示解剖结构目前只用于T1加权像快速自旋回波（FSE）必扫序列成像速度快多用于T2加权像梯度回波（GE）成像速度快对出血敏感T2加权像水抑制反转恢复（IR）水抑制（FLAIR）抑制自由水梗塞灶显示清晰判断病灶成份脂肪抑制反转恢复（IR）脂肪抑制（STIR）抑制脂肪信号判断病灶成分其它组织显示更清晰血管造影（MRA）无需造影剂TOF法PC法MIP投影动静脉分开显示水成像（MRCP，MRU，MRM）含水管道系统成像胆道MRCP泌尿路MRU椎管MRM主要用于诊断梗阻扩张超高空间分辨率扫描任意方位重建窄间距重建技术大大提高对小器官、小病灶的诊断能力三维梯度回波（SPGR） 早期诊断脑梗塞

弥散成像MRI的设备一、信号的产生、探测接受1.磁体（Magnet）:静磁场B0（Tesla,T）→组织净磁矩M0

永磁型（permanentmagnet）常导型（resistivemagnet）超导型（superconductingmagnet）磁体屏蔽（magnetshielding）2.梯度线圈（gradientcoil）:

形成X、Y、Z轴的磁场梯度功率、切换率3.射频系统（radio-frequencesystem，RF）

MR信号接收二、信号的处理和图象显示数模转换、计算机，等等；MRI技术的优势1、软组织分辨力强（判断组织特性）2、多方位成像3、流空效应（显示血管）4、无骨骼伪影5、无电离辐射，无碘过敏6、不断有新的成像技术MRI技术的禁忌证和限度1.禁忌证

体内弹片、金属异物各种金属置入：固定假牙、起搏器、血管夹、人造关节、支架等危重病人的生命监护系统、维持系统不能合作病人，早期妊娠，高热及散热障碍2.其他钙化显示相对较差空间分辨较差（体部，较同等CT）费用昂贵多数MR机检查时间较长1.病人必须去除一切金属物品，最好更衣，以免金属物被吸入磁体而影响磁场均匀度，甚或伤及病人。2.扫描过程中病人身体（皮肤）不要直接触碰磁体内壁及各种导线，防止病人灼伤。3.纹身（纹眉）、化妆品、染发等应事先去掉，因其可能会引起灼伤。4.病人应带耳塞，以防听力损伤。扫描注意事项颅脑MRI适应症颅内良恶性占位病变脑血管性疾病梗死、出血、动脉瘤、动静脉畸形（AVM）等颅脑外伤性疾病脑挫裂伤、外伤性颅内血肿等感染性疾病脑脓肿、化脓性脑膜炎、病毒性脑炎、结核等脱髓鞘性或变性类疾病多发性硬化（MS）等先天性畸形胼胝体发育不良、小脑扁桃体下疝畸形等脊柱和脊髓MRI适应证1.肿瘤性病变椎管类肿瘤（髓内、髓外硬膜内、硬膜外），椎骨肿瘤（转移性、原发性）2.炎症性疾病脊椎结核、骨髓炎、椎间盘感染、硬膜外脓肿、蛛网膜炎、脊髓炎等3.外伤骨折、脱位、椎间盘突出、椎管内血肿、脊髓损伤等4.脊柱退行性变和椎管狭窄症椎间盘变性、膨隆、突出、游离，各种原因椎管狭窄，术后改变，5.脊髓血管畸形和血管瘤6.脊髓脱髓鞘疾病（如MS），脊髓萎缩7.先天性畸形胸部MRI适应证呼吸系统对纵隔及肺门区病变显示良好，对肺部结构显示不如CT。胸廓入口病变及其上下比邻关系纵隔肿瘤和囊肿及其与大血管的关系其他较CT无明显优越性心脏及大血管大血管病变各类动脉瘤、腔静脉血栓等心脏及心包肿瘤，心包其他病变其他（如先心、各种心肌病等）较超声心动图无优势，应用不广腹部MRI适应证主要用于部分实质性器官的肿瘤性病变肝肿瘤性病变，提供鉴别信息胰腺肿瘤，有利小胰癌、胰岛细胞癌显示宫颈、宫体良恶性肿瘤及分期等，先天畸形肿瘤的定位（脏器上下缘附近）、分期胆道、尿路梗阻和肿瘤，MRCP，MRU直肠肿瘤骨与关节MRI适应证X线及CT的后续检查手段－－钙质显示差和空间分辨力部分情况可作首选：1.累及骨髓改变的骨病（早期骨缺血性坏死，早期骨髓炎、骨髓肿瘤或侵犯骨髓的肿瘤）2.结构复杂关节的损伤（膝、髋关节）3.形状复杂部位的检查（脊柱、骨盆等）软件登录界面软件扫描界面图像浏览界面胶片打印界面报告界面报告界面2合理应用抗菌药物预防手术部位感染概述外科手术部位感染的2/3发生在切口医疗费用的增加病人满意度下降导致感染、止血和疼痛一直是外科的三大挑战，止血和疼痛目前已较好解决感染仍是外科医生面临的重大问题，处理不当，将产生严重后果外科手术部位感染占院内感染的14%～16%，仅次于呼吸道感染和泌尿道感染，居院内感染第3位严重手术部位的感染——病人的灾难，医生的梦魇

预防手术部位感染（surgicalsiteinfection,SSI)

手术部位感染的40%–60%可以预防围手术期使用抗菌药物的目的外科医生的困惑★围手术期应用抗生素是预防什么感染？★哪些情况需要抗生素预防？★怎样选择抗生素？★什么时候开始用药？★抗生素要用多长时间？定义：指发生在切口或手术深部器官或腔隙的感染分类：切口浅部感染切口深部感染器官／腔隙感染一、SSI定义和分类二、SSI诊断标准——切口浅部感染

指术后30天内发生、仅累及皮肤及皮下组织的感染，并至少具备下述情况之一者：

1．切口浅层有脓性分泌物

2．切口浅层分泌物培养出细菌

3．具有下列症状体征之一：红热，肿胀，疼痛或压痛，因而医师将切口开放者（如培养阴性则不算感染）

4．由外科医师诊断为切口浅部SSI

注意：缝线脓点及戳孔周围感染不列为手术部位感染二、SSI诊断标准——切口深部感染

指术后30天内（如有人工植入物则为术后1年内）发生、累及切口深部筋膜及肌层的感染，并至少具备下述情况之一者：

1.切口深部流出脓液

2.切口深部自行裂开或由医师主动打开，且具备下列症状体征之一：①体温＞38℃；②局部疼痛或压痛

3.临床或经手术或病理组织学或影像学诊断，发现切口深部有脓肿

4.外科医师诊断为切口深部感染

注意：感染同时累及切口浅部及深部者，应列为深部感染

二、SSI诊断标准—器官／腔隙感染

指术后30天内（如有人工植入物★则术后1年内）、发生在手术曾涉及部位的器官或腔隙的感染，通过手术打开或其他手术处理，并至少具备以下情况之一者：

1.放置于器官/腔隙的引流管有脓性引流物

2.器官/腔隙的液体或组织培养有致病菌

3.经手术或病理组织学或影像学诊断器官/腔隙有脓肿

4.外科医师诊断为器官/腔隙感染

★人工植入物：指人工心脏瓣膜、人工血管、人工关节等二、SSI诊断标准—器官／腔隙感染

不同种类手术部位的器官/腔隙感染有：

腹部：腹腔内感染（腹膜炎，腹腔脓肿）生殖道：子宫内膜炎、盆腔炎、盆腔脓肿血管：静脉或动脉感染三、SSI的发生率美国1986年～1996年593344例手术中，发生SSI15523次，占2.62%英国1997年～2001年152所医院报告在74734例手术中，发生SSI3151例，占4.22%中国？SSI占院内感染的14～16%，仅次于呼吸道感染和泌尿道感染三、SSI的发生率SSI与部位：非腹部手术为2%～5%腹部手术可高达20%SSI与病人：入住ICU的机会增加60%再次入院的机会是未感染者的5倍SSI与切口类型：清洁伤口 1%～2%清洁有植入物 ＜5%可染伤口＜10%手术类别手术数SSI数感染率(%)小肠手术6466610.2大肠手术7116919.7子宫切除术71271722.4肝、胆管、胰手术1201512.5胆囊切除术8222.4不同种类手术的SSI发生率：三、SSI的发生率手术类别SSI数SSI类别（%）切口浅部切口深部器官/腔隙小肠手术6652.335.412.3大肠手术69158.426.315.3子宫切除术17278.813.57.6骨折开放复位12379.712.28.1不同种类手术的SSI类别：三、SSI的发生率延迟愈合疝内脏膨出脓肿，瘘形成。需要进一步处理这里感染将导致:延迟愈合疝内脏膨出脓肿、瘘形成需进一步处理四、SSI的后果四、SSI的后果在一些重大手术，器官/腔隙感染可占到1/3。SSI病人死亡的77%与感染有关，其中90%是器官/腔隙严重感染

——InfectControlandHospEpidemiol,1999,20(40:247-280SSI的死亡率是未感染者的2倍五、导致SSI的危险因素（1）病人因素：高龄、营养不良、糖尿病、肥胖、吸烟、其他部位有感染灶、已有细菌定植、免疫低下、低氧血症五、导致SSI的危险因素（2）术前因素：术前住院时间过长用剃刀剃毛、剃毛过早手术野卫生状况差（术前未很好沐浴）对有指征者未用抗生素预防五、导致SSI的危险因素（3）手术因素：手术时间长、术中发生明显污染置入人工材料、组织创伤大止血不彻底、局部积血积液存在死腔和/或失活组织留置引流术中低血压、大量输血刷手不彻底、消毒液使用不当器械敷料灭菌不彻底等手术特定时间是指在大量同种手术中处于第75百分位的手术持续时间其因手术种类不同而存在差异超过T越多，SSI机会越大五、导致SSI的危险因素（4）SSI危险指数（美国国家医院感染监测系统制定）：病人术前已有≥3种危险因素污染或污秽的手术切口手术持续时间超过该类手术的特定时间（T）

（或一般手术＞2h)六、预防SSI干预方法根据指南使用预防性抗菌药物正确脱毛方法缩短术前住院时间维持手术患者的正常体温血糖控制氧疗抗菌素的预防/治疗预防

在污染细菌接触宿主手术部位前给药治疗

在污染细菌接触宿主手术部位后给药

防患于未然六、预防SSI干预方法

——抗菌药物的应用132预防和治疗性抗菌素使用目的：清洁手术：防止可能的外源污染可染手术：减少粘膜定植细菌的数量污染手术：清除已经污染宿主的细菌六、预防SSI干预方法

——抗菌药物的应用133需植入假体，心脏手术、神外手术、血管外科手术等六、预防SSI干预方法

——抗菌药物的应用预防性抗菌素使用指征：可染伤口(Clean-contaminatedwound)污染伤口（Contaminatedwound）清洁伤口（Cleanwound）但存在感染风险六、预防SSI干预方法

——抗菌药物的应用外科预防性抗生素的应用：预防性抗生素对哪些病人有用?什么时候开始用药?抗生素种类选择?使用单次还是多次?采用怎样的给药途径？六、预防SSI干预方法

——抗菌药物的应用预防性抗菌素显示有效的手术有：妇产科手术胃肠道手术(包括阑尾炎)口咽部手术腹部和肢体血管手术心脏手术骨科假体植入术开颅手术某些“清洁”手术六、预防SSI干预方法

——抗菌药物的应用外科预防性抗生素的应用：预防性抗生素对哪些病人有用?什么时候开始用药?抗生素种类选择?使用单次还是多次?采用怎样的给药途径？六、预防SSI干预方法

——抗菌药物的应用

理想的给药时间？目前还没有明确的证据表明最佳的给药时机研究显示：切皮前45～75min给药，SSI发生率最低，且不建议在切皮前30min内给药影响给药时间的因素:所选药物的代谢动力学特性手术中污染发生的可能时间病人的循环动力学状态止血带的使用剖宫产细菌在手术伤口接种后的生长动力学

手术过程

012345671hr2hrs6hrs1day3-5days细菌数logCFU/ml六、预防SSI干预方法

——抗菌药物的应用139术后给药，细菌在手术伤口接种的生长动力学无改变

手术过程抗生素血肿血浆六、预防SSI干预方法

——抗菌药物的应用Antibioticsinclot

手术过程

血浆中抗生素予以抗生素血块中抗生素血浆术前给药，可以有效抑制细菌在手术伤口的生长六、预防SSI干预方法

——抗菌药物的应用141ClassenDC,etal..NEnglJMed1992;326:281切开前时间切开后时间予以抗生素切开六、预防SSI干预方法

——抗菌药物的应用不同给药时间，手术伤口的感染率不同NEJM1992;326:281-6投药时间感染数（%）相对危险度(95%CI)早期（切皮前2-24h）36914(3.8%)6.7(2.9-14.7)4.3手术前（切皮前45-75min)170810(0.9%)1.0围手术期（切皮后3h内）2824(1.4%)2.4(0.9-7.9) 2.1手术后（切皮3h以上）48816(3.3%)5.8(2.6-12.3)

5.8全部284744(