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

第四章 语法分析(2)

  • 格式：ppt
  • 大小：441.00 KB
  • 文档页数：34

下载文档原格式

  / 34

合集下载

第四章语法分析

第四章语法分析



最右推导
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推出

叶蜚声 语言学概论 第四章 语法(2)

叶蜚声 语言学概论 第四章 语法(2)
32
一、语言的语法结构类型
（二）屈折语 代表：英语、俄语、法语、德语 特点： （1）有丰富的词形变化，其中有内部屈折，语序 不像孤立语那么重要。 （2）一个词尾可以同时表示几种语法意义。 （3）词尾和词根结合紧密，脱离词尾，句中词根 works 第三人称、普通体、现在时 不能独立存在。
33
一、语言的语法结构类型
3
二、形 态
形态——词在组合时为了表明不同的语法意义而词 形发生相应的变化，这些变化形成的聚合就叫“形态”。 形态主要有四种： 附加词尾 异根 内部曲折 零形式
4
二、形 态
（一）附加词尾 英语：two pens
worked being
俄语：
three glasses working been
5
二、形 态
下面两个句子句法结构相同吗？
通知的同志还没有来。 采购的东西还没有来。
28
三、变换和句法多义
①通知的同志还没有来。 →他通知的同志还没有来。 √
→通知他的同志还没有来。
②采购的东西还没有来。
√
→他采购的东西还没有来。 √
→采购他的东西还没有来。 × 第二句为什么不能继续变换？
29
语言学
第五节 语言的结构类型和普遍特征
形态、语法范畴、孤立语、黏着语、屈折语 复综语
37
26
三、变换和句法多义
句法多义——同一句型可表示不同的结构意义。 一个多义句型，可以变成几个单义句型。 ①鸡不吃了。→鸡不吃食了。
“鸡”是施事
→我们不吃鸡了。 “鸡”是受事 ②他在甲板上写字。 →他蹲在甲板上写字。 →他把字写在甲板上。
27
三、变换和句法多义
变换的目的：
1. 把句法多义句变成不同的单义句，消除歧义。 2. 辨析句法结构的细微差别。

编译原理 语法分析(2)_ LL(1)分析法1

编译原理 语法分析(2)_ LL(1)分析法1

自底向上分析法
LR分析法的概念 LR分析法的概念 LR(0)项目族的构造 LR(0)项目族的构造 SLR分析法 SLR分析法 LALR分析法 LALR分析法
概述
功能：根据文法规则 文法规则， 源程序单词符号串 单词符号串中 功能：根据文法规则，从源程序单词符号串中
识别出语法成分，并进行语法检查。 识别出语法成分，并进行语法检查。
9
【例】文法G[E] 文法G[E] E→ E +T | T 消除左递归 T→ T * F | F F→(E)|i 请用自顶向下的方法分析是否字 分析表 符串i+i*i∈L(G[E])。 符串i+i*i∈L(G[E])。
E→TE’ E’→+TE’|ε T →FT’ T’→*FT’|ε F→(E)|i
编译程序组织结构
表 处 理
前
端 中
源 程 序
词 法 分 析
语 法 分 析
语 义 分 析
间 代 码 生 成
中 后 目 端 间 标 代 代 码 码 优 生 化 成
目 标 程 序
错 误 处 理
第4章 语法分析
自顶向下分析法
递归子程序法（递归下降分析法） 递归子程序法（递归下降分析法） LL(1)分析法 LL(1)分析法
通常把按LL(1)方法完成语法分析任务的程序叫LL(1)分析程序或者LL(1)分析器。 通常把按LL(1)方法完成语法分析任务的程序叫LL(1)分析程序或者LL(1)分析器。 LL(1)方法完成语法分析任务的程序叫LL(1)分析程序或者LL(1)分析器
输入串
一、分析过程
#
此过程有三部分组成: 此过程有三部分组成: 分析表 总控程序） 执行程序 (总控程序） 分析栈） 符号栈 （分析栈）

第四章 语法

第四章 语法

例句分析：
（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推导） 不含回路 前提： 前提： 不含以ε 也不含以ε 为右部的产生式 结论： 那么可以通过执行消除文法左递 结论： 那么可以通过执行消除文法左递 归的算法消除文法的一切左递归 归的算法消除文法的一切左递归 改写后的文法可能含有以ε （改写后的文法可能含有以ε 为右部的产生式）。 为右部的产生式）。

叶蜚声 语言学概论 第四章 语法(2)

叶蜚声 语言学概论 第四章 语法(2)

26
三、变换和句法多义
句法多义——同一句型可表示不同的结构意义。 一个多义句型，可以变成几个单义句型。 ①鸡不吃了。→鸡不吃食了。
“鸡”是施事
→我们不吃鸡了。 “鸡”是受事 ②他在甲板上写字。 →他蹲在甲板上写字。 换和句法多义
变换的目的：
1. 把句法多义句变成不同的单义句，消除歧义。 2. 辨析句法结构的细微差别。
下面两个句子句法结构相同吗？
通知的同志还没有来。 采购的东西还没有来。
28
三、变换和句法多义
①通知的同志还没有来。 →他通知的同志还没有来。 √
→通知他的同志还没有来。
②采购的东西还没有来。
√
→他采购的东西还没有来。 √
→采购他的东西还没有来。 × 第二句为什么不能继续变换？
29
语言学
第五节 语言的结构类型和普遍特征
（二）异根 换用不同的词根表示不同的语法意义。 英语：I (主) 、my (属)、 me (宾)
be： am、are、is
was、were
（人称、现在式） （过去式）
good（原）、better（比较）、best（最高）
俄语：
6
二、形 态
（三）内部屈折 改变词语内部的读音，以表示不同的语法意义。 英语：goose（单）、 geese （复）
（三）黏着语 代表：日语、维吾尔语、土耳其语、朝鲜语 特点： （1）有丰富的词形变化，但无内部屈折。 （2）一个变词语素只表示一种语法意义。
（3）词尾和词根结合不紧密，需要时黏附上去。 土耳其语： sev-miš-dir-ler 爱（他们以前爱过） 新しい （基本形） 爱 过去式 ない （否定式） 新しく 三人称 复数
writing （××正在写信。主动态 ）

第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的规则变为

语法知识八年级第四章教学解析

语法知识八年级第四章教学解析第四章：语法知识教学解析在八年级学习语法知识的第四章中，我们将深入探讨一些重要的语法概念和规则。

本文将对该章节的教学内容进行解析和讲解。

一、句子成分分析句子是语言表达的基本单位，了解句子成分的构成对于理解句子结构和语法规则非常重要。

1. 主语：句子的主要发出者或动作的执行者。

2. 谓语：主语所表达的动作或状态。

3. 宾语：谓语动作的对象或接受者。

4. 定语：修饰名词或代词的成分。

5. 状语：修饰动词、形容词、副词或整个句子的成分。

6. 补语：用来说明或补充主谓之间的关系。

二、常见从句类型从句是句子中的一个独立成分，它可以在句中充当名词、形容词或副词的作用。

1. 名词性从句：在句子中充当名词的从句，可以作主语、宾语、表语或同位语。

2. 定语从句：修饰名词或代词的从句，用来对其进行进一步的说明或限定。

3. 状语从句：在句子中充当状语的从句，用来表达时间、原因、目的、条件、方式等。

三、时态和语态1. 时态：表示动作发生的时间，包括一般现在时、一般过去时、一般将来时等。

2. 语态：表示句子的主语与动作之间的关系，包括主动语态和被动语态。

四、虚拟语气1. 虚拟条件句：表示与事实相反的假设情况，包括与现在事实相反的虚拟条件句和与过去事实相反的虚拟条件句。

2. 虚拟语气用法：包括虚拟语气的动词形式、从句引导词和主句中的语气标志词。

五、直接引语和间接引语1. 直接引语：直接引用他人的原话，要用引号将其括起来。

2. 间接引语：将别人的话转述成自己的话，不使用引号。

六、倒装句倒装句是指将谓语动词的全部或部分提前到主语之前的语序结构。

1. 完全倒装：将谓语动词全部提前到主语之前。

2. 部分倒装：将谓语动词的助动词、情态动词或系动词提前到主语之前。

七、固定短语和习惯用语固定短语和习惯用语是汉语中经常使用的一些搭配词组，掌握这些短语和用法可以丰富语言表达能力。

八、语病和修辞1. 语病：语法上或用词上的错误。

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


• 例 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 化简由（２）所得的文法。即去除那些从开始符号出发永 远无法到达的非终结符的产生规则。

《语法分析》PPT课件


➢ 最后,我们将消除回溯的条件归纳为,对G中每个AVT,A-产生式中任何两 个候选式i,j,均满足:
(1)FIRST(i) FIRST(j)=
(ij 1i,jm)
(2) i,j中,至多有一个能推导出;
(3)若j*,则FIRST(i)FOLLOW(A)= (i=1,2,…,m ij)
➢ 注: 条件(2)可省略. 即(1) (2)
2
自顶向下分析方法的特点
1.若G有左递归,则分析不能正常进行.因此, 分析必须 先消除文法的左递归;
2.分析过程是反复进行试探的过程,因此,难免会出现大量
的回溯.特别是当wL(G)时,只有在穷举完所有的试
探后才能拒绝w.
由于回溯,就需将从出错点到迄今为止已做过的大量 工作废弃,显然会大大降低分析的效率.特别是在语法 分析阶段还往往要进行同步的语义分析和处理,这些 工作也就白做了.因此,消除回溯是分析的另一目标.
➢ 若这两种选择都可行,则回溯不可避免. 因此,就必须要求 当i *时,跟在A后的符号串不能推导出其它j 所能推 导出的首终结符符号串.为此,我们定义可紧跟在A后的所 有终结符之集
FOLLOW(A)={a | S#*Aa, aVT{#}, ,V*}
其中,当A为一句型的尾符号时,#FOLLOW(A).
*
S w1A AVNV* (4.17 )
j* ai
且 w1a1a2 ai1,1in
而其它的k(kj), k 都推导不出以 ai打头的符号串,则选定产生式Aj
注意,i=1时,w1=,A=S
就是唯一可行的推导,即
由假设可知,到目前为止,w的前
wL(G)选Aj正确;
缀w1已匹配,现在需对A进行推
wL(G)选任何产生式均不能匹 配
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

LR分析综述 分析综述
计算机理论研究已证明了如下结论: LR(k)文法是无二义性 无二义性文法; 无二义性 LR(k)文法与LR(1)文法等价 等价. 等价 由于常见的程序设计语言均能由LR(1)文法产生,因此我们只讨 论k=0,1两种情况; 本节中,我们将先介绍LR分析器的逻辑结构及工作原理,再分别 介绍几种LR分析器(即LR(0),SLR(1))的构造; LR(0)简单,能力低; SLR(1)能力强于LR(0);
文法符号:X1X2…Xm是 目前已移进并归约出的句 型部分.
状态栈:(S0,#)为预先 放到栈中的初始状态 和符号.
一个 分析器由 个部分组成: 一个LR分析器由 个部分组成: 一个 分析器由3个部分组成 LR分析程序,又称总控程序.所有的LR分析器都是相同的. 分析程序, 分析器都是相同的. 分析程序 总控程序.所有的 分析器都是相同的 分析表 分析函数 ,不同的文法分析表不同,同一个文法采用的 分析表(分析函数 不同的文法分析表不同,同一个文法采用的LR 分析表 分析函数), 分析器不同时,分析表也不同,分析表又可分为动作表 动作表(ACTION)和 分析器不同时,分析表也不同,分析表又可分为动作表 和 状态转换(GOTO)表两个部分,它们都可用二维数组表示. 状态转换 表两个部分,它们都可用二维数组表示. 分析栈,包括文法符号栈和相应的状态栈,它们均是先进后出栈. 分析栈,包括文法符号栈和相应的状态栈,它们均是先进后出栈. 分析栈
4.2.4
LR分析法 LR分析法
迄今为止我们所学的分析方法对文法都有一定的要求,即有局限 性; 1965年D.Knuth提出了分析效率极高的LR(k)分析技术; LR分析 自左至右扫描的自底向上的分析; LR分析 分析: 在分析的每一步,只须根据分析栈中的已移进的和已归约出的符 号,并至多向前扫描k个字符就能确定应采取什么分析动作(移进, 移进, 移进 归约,接受,报错); 归约,接受,报错 LR分析对文法要求很少,效率极高,且能及时发现错误,是目前最 广泛使用的方法;一般用CFG描述的语言均可用LR分析法 分析法
LR分析法 分析法
自底向上分析方法是一种移进-归约过程,当分析的栈 顶符号串形成句柄时就采取归约动作,因而自底向上 分析法的关键问题是在分析过程中如何确定句柄.LR 分析法正是给出一种能根据当前分析栈中的符号串(通 常以状态表示)和向右顺序查看输入串的K个(K≥0)符号 就可唯一地确定分析器的动作是移进还是归约和用哪 个产生式归约,因而也就能唯一地确定句柄.LR分析 法的归约过程是规范推导的逆过程,所以LR分析过程 是一种规范归约过程. 向前查看0个符号,就是LR(0)分析方法,向前查看1个 符号,就是LR(1)方法.
2. 分析表的组成: 分析表维数组 分析动作表 是一个
符号 状态 S0 S1 … Sn a1 a2 … … … … … at action[S0 , at] action[S1 , at] … action[Sn , at]
action[S0 , a1] action[S0 , a2] action[S1 , a1] action[S1 , a2] … …
自底向上分析法的关键问题是如何确定句柄.LR分 析法与算符优先方法一样,LR方法也是通过求句柄 逐步归约来进行语法分析. 在算符优先分析中,通过算符的优先关系得到句柄, LR方法中句柄是通过求活前缀而求得.
1,LR分析方法的逻辑结构 , 分析方法的逻辑结构
LR分析方法的基本思想 基本思想是:在规范归约过程中, 基本思想 一方面记住已移进和归约出的整个符号串(历史), 另一方面又根据所用产生式推测未来可能碰到的 输入符号(对未来的展望). 当某一符号串类似于句柄出现在栈顶时,需要根 据已记载的"历史","展望"和"现实"的输 入符号三方面的内容来决定栈顶的符号串是否构 成了真正的句柄,是否需要归约. 一个LR分析器的组成见下图.
符号 状态
x1
x2
…
… … … …
xt
goto[S0 , xt] goto[S1 , xt] … goto[Sn , xt]
S0 S1 … Sn
goto[S0 , x1] goto[S0 , x2] goto[S1 ,x1] goto[S1 , x2] … …
goto[Sn , x1] goto[Sn , x2]
移进: 移进:当前输入符号ai进符号栈,下一输入符号变成当前输入 符号,将action表中指出的状态S进状态栈.三元式变为:
(S0S1…SmS, # X1X2…Xmai, ai+1…an#)
归约: 归约:按某个产生式A→β进行归约,若产生式的右端长度为 r,则两个栈顶的r个元素同时出栈.将归约后的符号A进符号 栈; 根据新栈顶状态Sm-r和归约符号A查GOTO表, S=goto[Sm-r, A]进状态栈.三元式变为:
分析器实际上是一个带有先进后出栈的确定的 分析器 有穷自动机.将"历史"和"展望"综合成 状态",分析栈用来存放状态,状态概括了 "状态 状态 从分析开始直到某一归约阶段的全部历史和展 望资料,不必象算符优先分析法中要翻阅栈中 的内容才能决定是否要进行归约.只需根据栈 根据栈 顶状态和输入符号就可以唯一决定下一个动作. 顶状态和输入符号就可以唯一决定下一个动作
3 3
10
为了介绍LR分析过 为了介绍 分析过 程,直接给出该文法 的分析表, 的分析表,以后再介 绍如何生成 产生式
8 9 10 i
的序号
r 表示按第i个产 r3 r3 生式进行归约 11
r3 空白表示分
析动作出错 r5
根据上述分析表, 的分析过程如下: 根据上述分析表,对输入串 i * i + i 的分析过程如下: 序号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 状态栈 0 05 03 02 027 0275 02710 02 01 016 0165 0163 0169 01 符号栈 # #i #F #T #T* #T*i #T*F #T #E #E+ #E+i #E+F #E+T #E F→i → T→F → E →E+T F→i → T→T*F → E→T → F→i → T→F → 产生式 输入串 i*i+i# 0和#进栈 和 进栈 *i+i# i和S5进栈 和 进栈 *i+i# i和S5退栈 F和S3进栈 和 退栈 和 进栈 退栈, *i+i# F和S3退栈 T和S2进栈 和 退栈 和 进栈 退栈, i+i# *和S7进栈 和 进栈 +i# i和S5进栈 和 进栈 +i# i和S5退栈 F和S10进栈 和 退栈 和 退栈, 进栈 +i# F*T和S10,7,2退栈 T和S2进栈 退栈, 和 退栈 和 进栈 +i# T和S2退栈 E和S1进栈 和 退栈 和 进栈 退栈, i# +和S6进栈 和 进栈 # i和S5进栈 和 进栈 # i和S5退栈 F和S3进栈 和 退栈, 和 进栈 退栈 # F和S3退栈 T和S9进栈 和 退栈 和 进栈 退栈, # T+E和S9,6,1退栈 E和S1进栈 和 退栈, 退栈 和 进栈 说明
状 态
0 1
ACTION i表示转第i个状 i S5 + S6 r2 r4 S5 r6 S5 S5 S6 r1 r5 S7 r5 r6 S4 S4 S1 r1 r3 r5 r1
GoTo F 3
2 3 4 5 6 7
*态,即第i个状 E T ( ) # 态进状态栈. 1 2 S4 ac c Si表示把当前输入 S7 r2 r2 符号移进栈,第i个 r4状态进状态栈. r4 r4 S4 r6 r6 r1 9 8 2
(S0S1 … Sm-r S, # X1X2…Xm-rA, aiai+1…an #)
接受: 接受:分析成功,终止分析.三元式不再变化. 出错: 出错:报告出错信息.三元式的变化过程终止.
举例说明LR具体 举例说明 具体 分析过程: 分析过程:
设文法为G[L]: : 设文法为 (1) (2) (3) (4) (5) (6) E →E+T E →T T →T*F T →F F →(E) F →i
表中goto[Si,xj]指出栈顶状态为Si,碰到文法符号为Xj时应转 到的下一状态.
显然: 显然:分析表定义了一个以文法非终结符为字母表的 DFA
LR分析过程: 分析过程: 分析过程
用三元式: 用三元式
(状态栈,符号栈,输入符号 状态栈,符号栈,输入符号)
表示分析过程中状态栈,符号栈,输入符号的变化. 表示分析过程中状态栈,符号栈,输入符号的变化. 将初始状态 0和#进分析栈.三元式为: 将初始状态S 进分析栈. 进分析栈 三元式为:
LR分析表的优缺点
优点:
比其他"移进-归约"分析法,如算符优先分 析法使用更加广泛,识别效率高 能用LL(1)分析法分析的所有文法都能使用LR 方法来进行分析. LR分析法在自左至右扫描输入串的过程中就 LR 能发现其中的任何错误,并能准确地指出出错 位置.
缺点:
手工构造分析表工作量太大.必须使用自动生 成器.
总控程序根据分析表的内容来决定其下一步的处理 动作, 动作,分析表是根据具体的文法按某种规则构造出 来的. 来的.
LR方法:根据具体文法的分析表对输入串进行分析处 方法: 方法
理.
LR分析过程:在总控程序的控制下,从左到右扫描输 分析过程:在总控程序的控制下, 分析过程
入符号串,根据分析栈中的状态和当前输入符号, 入符号串,根据分析栈中的状态和当前输入符号, 按分析表中的内容完成相应的分析工作. 按分析表中的内容完成相应的分析工作.
LR(0)项目:在文法G中每个产生式的右部 项目: 右部适当位置 项目 右部 添加一个圆点构成项目. 例如:产生式 S→XYZ 对应有4个项目. → [0] S→●XYZ [1] S→X●YZ → → [2] S→XY●Z [3] S→XYZ● → → 产生式A 只对应一个项目: 产生式 →ε只对应一个项目: A →● 项目 项目指明了在分析过程的某时刻,已看到的产生式 部分 项目集: 项目集:若干个项目组成的集合称为项目集. 例如: 对于上述产生式的4个项目即构成一个项目集. 后继符号 : 在项目中紧跟在符号" ● "后面的符号 后继符号: 称为该项目的后继符号. 后继符号表示下一时刻读 到的符号.