当前位置：文档之家 › 第四章_语法分析(4)

第四章_语法分析(4)

  • 格式：ppt
  • 大小：621.55 KB
  • 文档页数：77

下载文档原格式

  / 77

合集下载

第四章语法分析

第四章语法分析




最右推导
E rm E rm (E) rm (E + E) rm (E + id) rm (id + id)
4.1 上下文无关文法
4.1.3 分析树 例 E E + E | E E | (E ) | E | id
E

E
( E ) E + E id
id
4.1 上下文无关文法

4.2 语言和文法
4.2.7 提左因子

有左因子的文法 A b1 | b2 提左因子 A A A b 1 | b 2

4.2 语言和文法

例 悬空else的文法 stmt if expr then stmt else stmt | if expr then stmt | other 提左因子

无二义的文法
stmt matched _stmt | unmatched_stmt matched_stmt if expr then matched_stmt else matched_stmt | other unmatched_stmt if expr then stmt | if expr then matched_stmt else unmatched_stmt
句型 文法G的开始符为S，S *， 可能含有非终结符， 则叫做文法G的句型。
4.1 上下文无关文法

例 E E + E | E E | (E ) | E | id 最左推导
E lm E lm (E) lm (E + E) lm (id + E) lm (id + id)

按串长进行归纳：配对括号串可由S推出
现代汉语语法第四章

现代汉语语法第四章


3.两类短语的语法性质和句法功能
• 状心和心补短语一般以动词和形容词为核心构件，是动词短语 或形容词短语。 • 就七八个人 • 多年夫妻 • 夫妻多年 • 状心短语有时以名词、数量词或数量名结构为核心构件，心补 短语有时以名词为核心构件，是特殊的名词短语
• 句法功能上，状心短语或心补短语带上特定语气语调，可以成 为非主谓句。 • 向左拐！
3.联合短语的语法性质和句法功能
• • • • 名名联合——名词联合短语 动动联合短语——动词联合短语 形形联合短语——形容词联合短语 一般情况下，，联合短语的句法功能，跟联合项的词性一致
• 名词和名名联合短语都可以做宾语，有的名名联合短语可以带 “地”做状语，单独一个名词却不行： •
• 有些形容词和形形联合短语都可以用在谓语部分，但形形联合 短语可以带“地”做状语，单独一个形容词却不行： •

• 句法功能上，定心短语带上特定语气语调，可以成为非主谓句。 • 卑鄙的小人！ • 野兽的嚎叫！ • 在句子中，定心短语的基本功能是充当主语和宾语。以名词为 核心构件的，还可以充当其他成分。 • • • • • 这本书的出版讲求高质量。 高质量是第一位的要求。 这是一批高质量的书。 成果高质量。 一定要高质量地完成任务。
• • • •
不同的联合标志，在结构成分之间所表示的具体关系不完全相同 表示并列：和、及、并、而、而又 表示选择：或、或者 表示递进：且、而且
• 有的联合标志，即使所处语法环境相同，在具体表意上也有差异 • 张三、李四和王五 • 张三李四及王五 • “和”和“及”都可以用在名名之间表示并列关系，但“及”强调 前后联合项有主次之分 • “而又”前后两个联合项是同一个形容词，强调的说法
• 从充当结构成分的语法单位看，定心短语的两个结构成分可以 是词，也可以是短语。
语言学概论_第四章语法

语言学概论_第四章语法

1.语法形式：能够体现一类意义或有共同作用 的形式。
2.语法意义：通过一类共同功能所获得的意义。 语法意义不等于词汇意义。
如：英语中名词加词尾“- s”表示复数， “- s” 就是语法形式，“表示复数”就是语法意义。
3、根据语法形式的共同特点把它们归并为几个基 本类型，这种语法形式的类就叫做“语法手段”。
如：“一张动物园”，看起来是量词误用， 其实是“我要买一张去动物园的票”这句 话的成分省略现象。
初中，某数学老师讲方程式变换，在讲台 上袖子一挽大声喝道：同学们注意！我要 变形了！……
5.语法和逻辑
逻辑是语言表现内容的规律，语法是 语言表达形式的规律，二者的关系非常紧 密。逻辑对语法的影响主要表现为对语言 成分之间搭配关系的制约。从基本要求看， 一般人们说话不但要合语法，也要合逻辑。 个别不合逻辑的，只要大家都这么说，都 懂得是什么意思，就不能完全用逻辑来苛 求了。
“科学”本为名词，后产生出“具有科学属 性的”这一意义，用该词修饰或描写此属
严密的系统性 相对的稳定性
语法的高度抽象性
小明喝牛奶。 妈妈已经吃过饭了。 老师在黑板上写字。
语法规则具有强大的递归性
学生在看书。 隔壁的学生在看他的书。 隔壁在xx小学读书的学生在家里看他的辅
导书。 隔壁在xx小学读书的学生在家里看他昨天
从新华书店买来的他一直想要的辅导书。
语法规则具有严密的系统性
江西人不怕辣 湖南人辣不怕 四川人怕不辣
（4）语调是通过整个句子的音高、重音、停顿等 来表示一定语法意义的形式。语调实际上已经是 表达层面上的一种语法手段了。
如：滚蛋！
6.根据语法手段的不同可把人类语言分为：
语言
综合性语言：主要使用词形变化、 词的轻重音等语法手段的语言。 如俄语、德语
编译原理-第四章语法分析-4.2上下文无关文法

编译原理-第四章语法分析-4.2上下文无关文法

博客园 用户登录 代码改变世界 密码登录 短信登录 忘记登录用户名 忘记密码 记住我 登录 第三方登录/注册 没有账户, 立即注册
编译原理 -第四章语法
1.形式语言 2.例
二、推导
1.定义 2.基本概念 3.例
三、语法分析树
1.定义 推导的图形表示形式，过滤掉了推导过程中对非终结符 应用产生式的顺序，描述如何从文法的开始符号推导出其语言中的一个语句 2.性质 3.例
四、二义性
1.定义 2.原因 在产生句子的过程中某些直接推导有多于一种选择 3.注意 4.例
五、验证文法产生的语言
六、上下文无关文法和正则表达式
1.文法 2.正则表达式 3.正则表达式到上下文无关文法转换 例：
参考——慕课-苏州大学
第四章 语法

第四章 语法


例句分析：
（1）太阳升起在浩荡的平原上。 （2）我们充分利用本地资源制造农业机械化的道路。 （3）在参观期间发生的令人感动的美丽事情层出不穷。 （4）其实对这一点我也以前不十分清楚。 （5）尽管天塌下来，我也能顶得住。 （6）我看书的入神时，不时门开了，好几个同学进来。
二、 语法的组合规则和聚合规则
2. 划分词类应注意的问题 ①在鉴别词类时可以参照词的意义，但不能完全根据意义，而 要有句法功能和形式上的实证。 ②在同一个词类当中，具体的成员有典型与非典型之分。 ③一个词可以兼属两个或两个以上的词类。
3.划分词类对句法描写的意义 划分词类是概括句法格式、发现组合规则的基础。词类 之于句法描写的重要性还表现为，给词分小类可以大大深化 句法描写。
第四章 语法
第一节 语法和语法单位 第二节 组合规则 第三节 聚合规则 第四节 变换 第五节 语言的结构类型和普遍特征
第一节 语法和语法单位
一 语言结构是有规则的
所谓语法，是指用词造句的规则。我们说话写文章都必 须遵守规则，否则的话，就会让对方感到别扭甚至产生误会 。 作为母语的语法规则是潜存于大脑的，通过说话可以表 现出来，但是规则具体是怎样的，一般人却难以说明白。语 法分析的主要任务就是把人们心知其意而难以言状的规则整 理出来，以便人们自觉的运用。语法学家的任务只是归纳、 整理客观存在的规则，选择恰当的方式进行描写，对于语法 规则，语法学家是无权做硬性的规定的。
四、 语法范畴
由词的变化形式所表示的意义方面的聚合，即语法意 义的类就叫做语法范畴。 （一）语法范畴的类： 体词属性范畴和谓词属性范畴 1. 体词属性范畴 就是由名词的词性变化形式表示的意义。印 欧语系的语言中的名词大都有词形变化，主要表示三种范 畴意义：性、数、格。
04 语法分析-自上而下分析

04 语法分析-自上而下分析


待分析的输入串： 待分析的输入串：i+i
只有当a 只有当a是允许出 现在非终结符A 现在非终结符A后 面的终结符时， 面的终结符时， 才可能允许A 才可能允许A自动 匹配。 匹配。
尾随集的定义： VN尾随集的定义：
=*>…Aa Aa…, FOLLOW(A)={a|S =*> Aa , a∈VT}； 特别地，如果S=*> S=*>…A 那么# FOLLOW(A)。 特别地，如果S=*> A，那么# ∈FOLLOW(A)。
例子
文法: S→xAy A→**|* 文法: 输入串：x*y 输入串： S => => => => xAy x**y xAy x*y (S→ xAy) (A→**) 回溯) (回溯) (A→*)
带回溯自上而下分析面临的问题
问题: 问题: 文法的左递归问题 回溯问题 虚假匹配问题 出错位置不确定 低效
实现思想： 实现思想：
分析程序由一组递归过程组成。 分析程序由一组递归过程组成。每一过程 对应于一个非终结符号。 对应于一个非终结符号。 每一个过程的功能是：选择正确的右部。 每一个过程的功能是：选择正确的右部。 在右部中有非终结符号时， 在右部中有非终结符号时，调用该非终结 符号对应的过程。 符号对应的过程。
消除文法的左递归
文法不含回路（形如P=+> P推导 推导） 文法不含回路（形如P=+> P推导） 不含回路 前提： 前提： 不含以ε 也不含以ε 为右部的产生式 结论： 那么可以通过执行消除文法左递 结论： 那么可以通过执行消除文法左递 归的算法消除文法的一切左递归 归的算法消除文法的一切左递归 改写后的文法可能含有以ε （改写后的文法可能含有以ε 为右部的产生式）。 为右部的产生式）。
语法分析

语法分析

23
if(Yi∈VN) { if(i=n or 任一j(i+1≤j≤n)null(Yj)=true) FOLLOW(Yi)=FOLLOW(Yi)∪FOLLOW(A); if(Yi+1∈VT) Yi+1∈FOLLOW(Yi); else for(k=i+1;k<=n;k++) if(k=i+1 or i+1≤j≤k-1)null(Yj)=true ) FOLLOW(Yi)=FOLLOW(Yi)∪FIRST(Yk) }/*end of if*/ }/*end of for*/ } /*end of for*/ while FIRST,FOLLOW,nullable 不再改变
1、思路：对任一输入符号串，通过一切可能的办 法，从树根结点(识别符号)出发，根据文法自 上而下地为输入串建立一棵语法树；或者说， 从识别符号开始，根据文法试图为输入串建立 一个推导序列。 2、特点：是自顶向下分析的一般方法，分析过程 的本质是一种试探过程。
4
例∶假定有文法G[S]:(1)S->cAd (2)A->ab|a 对输入串w=cad。要求自上而下地构造w的语法树。 解决过程： S c a S c A a d A b d －对于输入串w，从文法的开始符号出 发，反复使用不同的产生式谋求匹配 输入串。当用某个非终结符号的候选 式进行匹配失败时，则推翻分析退回 到适当位置再重新试探其它候选式， 直到把所有可能的推导序列都试探完 仍不成功才能确认输入串不是该文法 的句子而报错 。称为带回溯的自顶 向下分析。 －回溯需要推导记住现场，浪费了大量 的时间和空间，必须设法消除。
在推导过程中，可以完全根据向前看符号唯 一决定选择哪个产生式往下推导，因此，分析过 程是完全确定的。这种分析称为确定的自顶向下 分析方法。
第04章-语法分析自上而下分析

第04章-语法分析自上而下分析

否符合语法规则。 ▪ 语法分析器的工作本质：按文法的产生式，识别
输入符号串是否为一个句子。 ▪ 语法分析器在编译器中的地位：
源程序
单词符号
词法分析器
取下一个单 词符号
语法分析器
语法分析树
编译器的 后继部分
2021/4/6
符号表
3
4.1 语法分析器的功能
▪ 语法分析方法
➢ 自上而下分析法
从文法的开始符号出发，反复使用文法的产生式， 寻找与输入符号串匹配的推导。
分析输入串x*y(记为)。
xx**yy
SS
IPIPIP xx A y * **
2021/4/6
7
4.2 自上而下分析面临的问题
▪ 当某个非终结符有多个产生式候选时，可 能带来如下问题：
➢ 1.分析过程中，当一个非终结符用某一个候选 匹配成功时，这种匹配可能是暂时的。这时， 不得不“回溯”。
➢ 2.文法左递归问题。一个文法是含有左递归的 ，如果存在非终结符P
➢ 最后所得的无左递归文法是： S→Qc | c Q→Rb | b R→bcaR | caR |a R R→ bca R |
➢ 不同排序所得的文法的等价性是显然的。
2021/4/6
17
4.3.2 消除回溯、提左因子
▪ 为了消除回溯就必须保证：对文法的任何 非终结符，当要它去匹配输入串时，能够 根据它所面临的输入符号准确地指派它的 一个候选去执行任务，并且此候选的工作 结果应是确信无疑的。
2021/4/6
14
4.3.1 左递归的消除
▪ 例4.3 考虑文法G(S)
S→Qc|c Q→Rb|b R→Sa|a
➢ 令它的非终结符的排序为R、Q、S。 ➢ 对于R，不存在直接左递归。 ➢ 把R代入到Q的有关候选后，把Q的规则变为
第四章 语法分析——自上而下分析

第四章 语法分析——自上而下分析


解二： 规定顺序：S、Q、R
则等价的无左递归的文法： SQc | c QRb| b RbcaR’ | caR’ | aR’ R’bcaR’ |
RSa | a RQca | ca | a
RRbca|bca | ca | a
RbcaR’|caR’ | aR’ R’ bcaR’|
（因为不需要试探某个候选式，而是准确地指派 某个候选式）
17
终结首符集FIRST
令文法G不含左递归，对它的所有非终结符的每 个候选式定义终结首符集 FIRST(): * FIRST()={a | a , a∈VT }
特别地 * 若 ，则规定 ∈ FIRST()
显然， FIRST()是从推导出的所有可能的开头终 结符a或 。
3
§4.2 自上而下分析面临的问题
一、带‚回溯‛的自上而下分析方法：
自上而下分析方法，就是对任何输入串，试 图用一切可能的方法，从文法的开始符号出发， 自上而下地为输入串建立一个语法树（或最左推 导）。 这种分析过程实质上是一种试探过程，即反 复使用不同的产生式以求能匹配输入串。
4
例4.1 设有文法： SxAy
解： S iCtSA | a
A | eS
C b
22
4.3.3 LL（1）分析条件 当一个文法不含左递归，并且满足每个非终结 符的所有候选首符集两两不相交，是不是一定能进 行有效的自上而下的语法分析呢？
若存在 ∈ FIRST() ，则问题较复杂，需要进 一步考虑。 定义：非终结符A的 FOLLOW 集：
* FOLLOW（A）= { a| S …Aa… ，a∈VT } 特别地， * 若S …A，则规定，构造FIRST（X）
a) 若X∈VT，则 FIRST(X)={X}。
my第04章-语法分析：自上而下

my第04章-语法分析：自上而下


自上而下分析法的一般问题
3.
带回溯的自上而下分析法的缺陷 1）如果文法存在左递归，语法分析会无限循环下去。 2）若产生式存在多个候选式，选择哪个进行推导完全 是盲目的。 3）回溯会引起时间和空间的打量消耗 4）如果被识别的语句是错的，算法无法指出错误的确 切位置。
第四章 语法分析--自上而下分析
直接左递归，和非直接左递归的消除方法均在必须掌握之列。这里我们 切不可被形式描述消除左递归的算法吓倒，多做几个例题后再来理解是很 有好处的： [例4.3]： 考虑文法：SQc|c Q Rb|b R Sa|a 消除左递归。 解：将终结符排序为R、Q、S。对于R不存在直接左递归。把R带入到Q 中有关的候选式： Q Sab|ab|b 现在Q同样不含直接左递归，把它带入S的有关候选式： S Sabc|abc|bc|c 经消除S的直接左递归后我们们得到整个文法 S abcS’|bcS’|cS’ S’ abcS’| Q Sab|ab|b R Sa|a 由于关于Q,R的规则式多余的则可化简
本节要 掌握对给定文法构造出每个非终结符的 FIRST和FOLLOW集合。
第四章 语法分析--自上而下分析
掌握LL(1)预测分析表的构造，请参看4。5。1 预测分析程序的 工作过程（P76）和 4。5。2预测分析表的构造（P78）。 现在举一些例子帮助同学们理解： [例4.7 ]对于文法 ETE’ E’ +TE’| T FT’ T’ *FT’| F (E)| i 我们构造每个非终结符的FIRST和FOLLOW集合 解：FIRST(E) = { (, i } FOLLOW(E) ={ ), # } FIRST(E’) = {+, } FOLLOW(E’) = { ), #} FIRST(T) = {(, i } FOLLOW(T) = {+, ), # } FIRST(T’) = {*, } FOLLOW(T’) ={+ , ), # } FIRST(F) = {(, i } FOLLOW(F) ={*, +, ) , # } 在这里我们要注意FOLLOW(F)的求解过程其中： FOLLOW(F)=FIRST(T’)={*}; 因为T’ ,所以将FOLLOE(T)加 到FOLLOW(F)中 （由于TFT’), 则： FOLLOW(F)=FOLLOW(T)=FIRST(E‘)={+}
语言学概论---第四章---语法

语言学概论---第四章---语法

第四章语法一、名词解释1.语法2.客观存在的语法3.主观认识的语法4.历时语法和共时语法5.教学语法和面向信息处理的语法6.普遍语法和个别语法7.词法（形态学）和句法（造句法）8.组合规则和聚合规则9.核心语法（小语法）和外围语法（大语法）10.语法单位：语素、词、词组、句子、句组11.语法形式12.语法意义13.语法手段14．词法手段15．句法手段16．综合性语言17．分析性语言18.虚词、语类选择、语序19.语法范畴20.词法范畴、体词性范畴、谓词性范畴、句法范畴、类别范畴、关系范畴21.附加、屈折、异根、零形式22. 重音、轻读23.词类24.体词性词组、谓词性词组,向心词组、离心词组25.完全主谓句、不完全主谓句、非主谓句。

26.多重复句 27.句组二、简答和论述1.语法规则的性质和特点.2.请结合具体例子谈一谈语法和语音、语法和语汇、语法和修辞、语法和语境、语法和逻辑之间的关系。

3.语言学家研究语法,首先必须限定某个范围,确定自己的研究内容。

研究的内容不同,语法规则就会有所区别,这种区别最重要的有：4.历时语法与共时语法的区别：上面（1）5.教学语法与面向信息处理语法的区别：上面（2）6.普遍语法和个别语法的区别：上面（3）7.语法现象的分类（传统语法学、结构语法学和现代形式语法学分别怎样对语法现象进行划分?）8.词法规则、句法规则的区别：9.组合规则与聚合规则的关系。

10.为什么说每个语言成分都既处在组合关系中又处在聚合关系中？11.为什么说聚合规则是潜在的,组合规则是现实的？12.为什么说聚合规则和组合规则主要是指应用于词和句子的规则？13.现代形式语法学把语法分为核心语法和外围语法，为什么说这种语法分类是一种较新的观点，在理论和方法上都有重要的意义?14.语法单位之间的关系：15．怎样看待语素的语法地位?16.为什么说语法规律只有一种,而语法规则可以多种多样17.为什么说方言语法实际上是共时语法现象反映历时语法现象？18.为什么说形态丰富的语言中词法问题重要,而汉语中句法问题更重要？19．语法手段中的词法手段有哪些?20．语法手段中的句法手段有哪些?21.词的轻重音的作用：22.词的重叠的作用:23.语序的作用：24.语调的作用：25.类别范畴的表现形式：26.关系范畴的表现形式27.词缀和词尾有哪些不同？28.语法形式和语法意义有什么样的对应关系？29.词法范畴中的体词性范畴和谓词性范畴各包括哪些内容?30. 什么是句法范畴?请结合例子论述句法范畴所包括的内容.31.语法手段和语言类型有什么关系？32.不同语言的不同虚词形式：33.不同语言的不同语类选择形式.34.不同语言中相同的语法意义和不同的语法范畴.35.外语中的主句、小句、从句.36.英语的动词谓语句一般可以分为七种主要句型.37.汉语的动词谓语句分类和英语不同38.复杂结构单句、复谓结构单句与复句的区别39.为什么说词和句子是语法结构中最重要的两个单位？40.为什么说句子的意义和词的意义具有突出的地位？41.怎样看待语素的语法地位？42.划分词类可以有哪些不同的标准：43.各种语言词类划分结果的特点？44.为什么不同语言有不同的词类数量和类型?45．如何理解词组作为一种语法单位，它与词这种语法单位实际上是同质不同量的关系?46.词类和词组的聚合类的关系?47.汉语中比较重要的三种特殊词组：48.句子的类型49.什么叫复句，复句的判断标准是什么？50.直接组成成分分析法的定义及其原则:51.多重复句与句组的区别：52.要不要把句组作为一级语法单位?53.句组要不要作为语法单位?(请答出各种不同意见的根据所在)54.句组有哪些语法作用？55.句组的三种意义关系和三类衔接形式：参考答案一、名词解释1.语法：是语言中关于词的构成、变化和词构成词组和句子的规则。

自上而下语法分析

从推导的角度看，从开始符号出发，使用最左 推导，试图推导出与输入符号串相同的句子。
从语法树的角度看，从根节点出发，反复使用 所有可能的产生式，谋求输入串的匹配，试图 向下构造一棵语法树，其末端节点正好与输入 符号串相同。
需要反复试探。
复习
句型的推导
最左（最右）推导：在推导的任何一步α β ， 其中α 、β 是句型，都是对α 中的最左（右）非 终结符进行替换 最右推导被称为规范推导。 由规范推导所得的句型称为规范句型。
例1：判定输入串(i+i)*i是否是下述文法的句子？
G = ({E}, {i, +, *, (, ) } , P , E) P： E E + E E E*E E (E) Ei
解：使用最左推导：
E E*E (E)*E (E + E)*E (i + E)*E
(i + i)*E (i + i)*i
高级语言的语法结构适合用上下文无关文法 来描述，上下文无关文法是语法分析的基础。
语法分析在编译系统中所处的位置
语法分析的接口设计
源程序 词法分析器 token串
语法分析器 语法分析树
编译程序 后续部分
• 语法分析器的输入
– Token序列：词法分析的输出，是各个单词都正 确的源程序的变换形式，是一个有限序列
• 语法分析器的输出
– 分析树：表示方法？ 见教材 P89 – 错误处理信息：定位、继续编译
语法分析器的功能
按照语言的语法构成规则, 识别输入的符号 串能否构成一个句子。这些规则是用文法的 产生式来定义的。
问题
对给定的一个输入串，如何判定它是不是一 个句子？
方法

编译原理第四章语法分析-自上而下分析


• 例 4.4
4.4 递归下降分析程序构造
• 递归下降分析器：
这个分析程序由一组递归过程组成的，每个过程对应 文法的一个非终结符。 E→TE’ E’→+TE’| T→FT’ T’→*FT’| F→(E)|i
PROCEDURE E BEGIN T ; E’ END PROCEDURE E’ IF SYM=‘＋’THEN BEGIN ADVANCE ; T ; E’ END
4.2 自上而下分析面临的问题
• 例4.1 假定有文法
(1) SxAy (2)A**|*
对输入串x*y，构造语法树。 • 构造过程：
(1)把S作为根 (2)用S的产生式构造子树 (3)让输入串指示器IP指向输入串的第一个符号。
S x A y x
S
A y x
S
A y
*
*
*
(4)调整输入串指示器IP与叶结点进行匹配。 (5)如果为非终结符，用A的下一个产生式构建子树。 (6)如果匹配成功则结束；否则，回溯到步骤(4)。
• 一个反例：
– 文法：SQc|c；QRb|b；RSa|a虽然不是直接 左递归，但S、Q、R都是左递归。
• 消除左递归算法：
– 算法的思想是：
• • • • 首先构造直接左递归； 再利用一般转换规则，消除直接左递归 化简文法。 下面算法在不含PP，也不含在右部产生式时可以消除 左递归。
• 消除一个文法的左递归算法：
(1) 把文法 G 的所有非终结符按任一种顺利排列成 P1…Pn；按此顺序执行； (2) FOR i:=1 TO n DO
BEGIN FOR j:=1 TO i-1 DO 把形如Pj+1→Pj 的规则改写成 Pj+11|1|…k| 。其中 Pj1|1|…k 是关于 Pj 的 所有规则； 消除关于Pi规则的直接左递归性。 END 化简由（２）所得的文法。即去除那些从开始符号出发永 远无法到达的非终结符的产生规则。

语法讲义：第四章 句子成分

第四章句子成分一．句子成分的性质(一)配对性句子结构中的直接构成成分，往往是两两相对的，是同现的，相互依存的，这就是句子成分的配对性。

句子成分的配对性通常体现在，具有直接关系的句子成分之间往往是对应关系：句子成分配对性的特点是：具有配对关系的句子成分之间是同现的，相互依存的，离开了一方，另外一方也就无所谓存在了。

这一点，在前边的“语法概说”中，已经有所表述，这里不再讨论。

(二)应对性句子成分的应对性，指的是某些句子成分之间可以互易位置，而句子的意思基本不变。

汉语句子成分应对性通常体现在以下几种情况。

1.主—宾应对：主语、宾语互换位置而句子的意思基本不变。

如：①三个人坐一条凳子。

→一条凳子坐三个人。

②西昌通火车了。

→火车通西昌了。

③自古英雄出少年。

→自古少年出英雄。

2.定—中应对：句子中的定语和中心语互换位置而句子的意思基本不变。

如：①水汪汪的眼睛。

→眼睛水汪汪的。

②朵朵白云，阵阵春风。

→白云朵朵，春风阵阵。

3.状—中应对：句子中状语和中心语互换位置而句子的意思基本不变：①你错写了几个字。

→你写错了几个字。

②四周出奇地肃静。

→四周肃静得出奇。

③车子很慢很慢地开着。

→车子开得很慢很慢。

4.主—谓应对：句子中的主语、谓语互换位置而句子的基本意思不变。

如：①一斤白菜三元钱。

→三元钱一斤白菜。

②一张死契六十块大洋。

→六十块大洋一张死契。

上述各种应对关系的事实都是存在的，语法研究要做的是：进一步找到上述各种易位的条件二．主语、谓语(一)主语的语法构成总体上说，可以充当汉语主语的语言成分很多。

在汉语的词类中，除了副词、叹词和各种虚词之外，其他各类实词和词组都可以充当主语。

就此而言，汉语的“主语”似乎是比较讲究“民主”的——汉语的主语不是“名词性成分”的专利。

从具体情况来看，汉语主语通常由以下各种成分来充当。

1.名词性成分充当主语。

这是汉语最为常见的主语构成形式。

如：①他松了一口气。

②小王走了。

③母亲和宏儿都睡着了。

第章语法分析——自顶


4.2.1 FIRST集合定义及构造方法
对 于 文 法 G 的 任 一 符 号 串 α=X1X2…Xn 可 按 下 列 步 骤 构 造 其 FIRST(α)集合： 1)置FIRST(α)=φ 2)将FIRST(X1)中的一切非ε符号加进FIRST(α)； 3) 若 ε∈FIRST(X1) ， 将 FIRST(X2) 中 的 一 切 非 ε 符 号 加 进 FIRST(α) ； 若 ε∈FIRST(X1) 和 FIRST(X2) ， 将 FIRST(X3) 中 的一切非ε符号加进FIRST(α)；余类推。 4) 若 对 于 一 切 1≤i≤n ， ε∈FIRST(Xi) ， 则 将 ε 符 号 加 进 FIRST(α)。
U
INPUTSYM =‘b’ Y
N 语法错误： 输入串少‘b’
出口
图4.1(a) 非终结符号Z的分析程序
4.3.1 递归下降分析的基本方法
U::=dZ|e
过程U
INPUTSYM =‘d’ N Y
INPUTSYM=下一个符号
Z
INPUTSYM =‘e’ Y
N PUTSYM=下一个符号
={+，)，#} FOLLOW(F)= FIRST(T’) ∪ FOLLOW(T) ∪ FOLLOW(T’)
= {+，*，) ，# } FOLLOW(T’)= FOLLOW(T)= { + ， ) ， # }
4.3 递归下降分析
4.3.1 递归下降分析的基本方法
递归下降分析的概念极为简单，其方法是将文法中的每一个非终结符U的文 法规则看作是识别U的一个过程定义，为每个非终结符号构造一个子程序， 以完成该非终结符号所对应的语法成分的分析和识别任务。如果U的文法规 则的右部只有一个侯选式，则按从左向右的顺序依次构造规则U的识别过程 代码。如果有终结符号，判断能否与输入的符号相等，如果相等，表示识别 成功，读入指针指向下一个输入符号；如果不等，则意味着输入串此时有语 法错误。如果是非终结符号，则简单调用这个非终结符号的子程序，由这个 子程序完成该非终结符号所对应的语法成分的分析和识别任务。当一条规则 右部有多个侯选式时，则根据每个侯选式的第一个符号确定该侯选式分支。 只有被调用的分析和识别某语法成分的子程序匹配输入串成功，且正确返回 时，该语法成分才算真正获得识别。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
编译原理
I3 :
I4:
SR ·
L* · R R · L L · *R L · id Lid ·
I6:
SL= · R R · L L · *R L · id
L*R ·
I7:
I1: I2:
I5:
I8 :
I9:
RL ·
SL=R ·
4
I0
S' S S L=R SR L *R L id RL id R L id
编译原理
23
算法4.38 LR(1)项目集的构造
输入：拓广文法G。 输出： LR(1)项目集规范族，是对G 的一个或多个 可行前缀有效的项目集。 方法：如图4-40所示。
编译原理
24
Fig4.40 Sets of LR(1) items construction for G
function closure(I) begin repeat for each [A B, a] in I each production B of G and each terminal b in FIRST(a) such that [B. , b]is not in I do add [B , b] to I until no more items can be added to I return I end
编译原理 27
例4.39
构造文法 S S SCC CcC|d 的LR(1)和SLR分析表。
计算[S.S,$]的闭包 I0：S.S, $ S.CC, $ C.cC, c/d C.d, c/d c/d FIRST(C$)
编译原理
28
S.S,$ S S.CC,$ C.cC,c/d C.d,c/d I0 C
据假设，存在一个规范推导S *Aw 1B2w 设2w * xw， 则对任何B 有规范推导 S *Aw 1 B 2w 1 Bxw 1 xw 所以 B . 对可行前缀 1 也是有效的。
编译原理 13
一个项目可能对好几个可行前缀都是有效的。 E ·E+T对 和(这两个可行前缀都有效 E E E+T (，1都为空) E E (E) (E+T) ( =“(”，1为空) DFA读入 和(后到达不同的状态，那么项目E ·E+T就出现在不同的项目集中
S BB BaB Bab aBab aaBab aaaBab
rm rm rm
从最右推导S *rm aaBab rm aaaBab看出： [Ba · a]对可行前缀 = aaa是有效的； B, 从最右推导S *rm BaB rm BaaB看出： [Ba · $]对可行前缀 = Baa是有效的。 B,
编译原理
14
一个可行前缀可能有多个有效项目。 可能存在动作冲突 一个可行前缀的有效项目集就是从这个DFA的初态出 发，沿着标记为的路径到达的那个项目集（状态） 。
编译原理
15
例4.35
串E + T *是可行前缀，读完它后，DFA处于状态I7 I7: TT *· F · E ), F · F, ( id
编译原理 22
构造有效的LR(1)项目集
考虑对可行前缀有效的项目[A · , a]，必 B 定存在最右推导S *rm Aax rm Bax，其中 = 。 假设ax能推出by，那么， [B · , b]对有效， b是从 能推出的第一个终结符，或当 可空时， b就是a。bFIRST(a)。
SS.,$ I1 SC.C,$ C.cC,$ C.d,$ I2 c C
SCC.,$ I5 c
C d CcC.,$ I9
Cc.C,$ C.cC,$ C.d,$ I6 Cd.,$ I7
d c c
d
Cc.C, c/d C C.cC, c/d C.d, c/d I3 d Cd.,c/d 编译原理 I4
编译原理
17
图4.36 识别可行前缀的 DFA
I0
E
I1
+
I6
T
I2 I3 (
*
I7
T F ( id F (
I9 to I3 to I4 to I5 I10
*
to I7
F
(
id E T F ) + to I2 to I3
编译原理
to I4 to I5 I11
to I6
I4
I8
id id I5
18
4.7 构造规范的LR分析表
第四章 语法分析(4)
4.7 LR(1)、LALR
1
4.6.4 构造SLR分析表
算法 4.32 构造SLR分析表 输入：一个拓广文法G 输出：G 的SLR分析表的函数action和goto 方法： 1. 构造G 的LR(0)项目集规范族C = {I0, I2, …, In}。 2. 对于状态Ii的分析动作如下： (a) 若A . aB Ii且 goto (Ii ,a)= Ij action[i, a] = “shift j” (b) 若A . Ii, 对于所有a FOLLOW(A) action[i, a] = “reduce A” , A S (c) 若SS. Ii, action[i, $]= “accept” 3. 若goto(Ii, A) = Ij, AVN , 则 goto[i,A] = j 4. 分析表其余位置为error 编译原理
编译原理
6
4.6.5 可行前缀（viable prefix）
对于一个文法G，构造一个LR（0）自动机，它能 识别所有可能出现在分析栈中的文法符号串，栈中 的文法符号串一定是某个右句型的前缀。
S x
rm *
不是右句型的所有前缀都会出现在栈中。
E F * id ( E ) * id
11 S · a 12. S a·
编译原理
10
识别可行前缀的NFA

start
3
S
S
4

S
5
+
6
1
2
7 11

S


8
S
9
*
10
a
12编译原理
11
识别可行前缀的DFA
S SSS . + SSS . * SS. S+ SS. S* S.SS+ S.SS* S.a I3
编译原理
8
识别G的所有可行前缀的NFA
1. 2. NFA的状态是一个LR(0)项目。 从每个形如B · 的状态出发画一条标记为X X 的弧到状态BX · ， 3. 从每个形如B · 的状态出发画一条标记为的 A 弧到所有形如A · 的状态。 这个NFA通过子集构造法得到的DFA和前面构造 的LR(0)自动机是相同的。
2
例4.34 每个SLR(1)文法都不是二义的，但是， 有许多非二义的文法不是SLR(1)。
例如，下面的产生式文法
S L=R SR L *R L id RL
编译原理
3
拓广文法G的LR(0)项目集规范族为：
I0: S' · S S · L=R S · R L · *R L · id R · L S'S · SL · =R RL ·
例 I2有两个项目SL · =R和RL · 当下一个输入为‘=’时用RL · 归约，但是文 法没有以R=…开始的右句型，只有以*R=…开 始的右句型，可见，仅仅知道可行前缀L不应当 进行归约。 扩充项目的定义！
编译原理
19
LR(1)项目
重新定义项目，让它带上搜索符(向前看符号)， 成为如下形式 LR(1)项目: 由LR(0)项目和一个lookahead符号 组成 [ A., a ] 对于项目[ A· a ]，搜索符a表示只有当下一 , 个输入符号是a时，才能进行归约。 这样的a的集合一定是FOLLOW(A)的一个子 集，可能是真子集。
编译原理 5
S
I1
I4 S R
SLR(1)文法的描述能力有限
I0 S' S S L=R SR L *R L id RL
L
S L =R I2 R L
第一个项目使得 action[2, = ] 为shift 第二个项目使得 action[2, = ]为reduce，因 为 = Follow(R)。 S L=R *R=R 但是，不存在以R=…开始 的右句型，只有* R = …开始的右句型。
CcC.,c/d I8
29
算法4.40 规范LR(1)语法分析表的构造
输入：拓广文法G。 输出：文法G的规范LR语法分析表函数action和goto。 方法： 1. 构造G 的LR(1)项目集规范族C={I0, I1, …, In}。 2. 从Ii构造分析器的状态i，状态i的action函数确定如下： 若[A · , b]在Ii中，且goto(Ii, a) = Ij，则置action[i, a a]为“shift j”； 若[A · a]在Ii中，且A S，则置action[i, a]为 , “reduce j”，j是产生式A 的序号； 若[SS·$]在Ii中，则置action[i, $]为“accept”。 ,
I3
R I6 S L= R S L=R RL I9 id L *R L I3 S L =R = L id I2 R L L * * L * R I5 R L L R L I7 L id R id L * R L *R I8 S' S *
编译原理 20
LR(1)项目[A· a]对可行前缀有效，如果 , 存在着推导 S *rm Aw rm w，其中： 1. = ，且 2. a是w的第一个符号，或者w为且a是$。