当前位置：文档之家 › 编译原理,陈意云 ,课后解答3

编译原理,陈意云 ,课后解答3

  • 格式：ppt
  • 大小：110.00 KB
  • 文档页数：12

下载文档原格式

  / 12

合集下载

编译原理陈意云课后答案.ppt

编译原理陈意云课后答案.ppt

5
3.2
• 考虑文法 S -> aSbS|bSaS|ε (a) 为句子abab构造两个不同的最左推导， 以说明此文法二义 (b) 为abab构造对应的最右推导 (c) 为abab构造对应的分析树 (d) 这个文法产生的语言是什么
2019/3/22
luanj@
6
3.2 (续)
luanj@ 9
2019/3/22
3.4 (续)
• 该文法没有体现运算符 |、*、() 、并置的优 先级，因而是二义的。
R=>R|R=> a|R =>a|R*=>a|b* R=>R*=>R|R*=>a|R*=>a|b*
• E -> E’|’T | T T -> TF | F F -> F* | (E) | a | b
• (1) S=>aSbS=>abS=>abaSbS=>ababS=>abab (2) S=>aSbS=>abSaSbS=>abaSbS=>ababS=>abab • S=>aSbS=>aSb=>abSaSb=> abSab =>abab (2)
S a S ε b a S ε (1) 描述的语言是a,b数目相等的串 S b S ε S
S
( L S a L , ( L S a
2019/3/22 luanj@ 3
) S L , ) S a
3.1 (续) - (a,((a,a),(a,a)))
S =>(L) =>(L,S) =>(S,S) =>(a,S) =>(a,(L)) =>(a,(L,S)) =>(a,(S,S)) =>(a,((L),S)) =>(a,((L,S),S)) =>(a,((S,S),S)) =>(a,((a,S),S)) =>(a,((a,a),S)) =>(a,((a,a),(L))) =>(a,((a,a),(L,S))) =>(a,((a,a),(S,S))) =>(a,((a,a),(a,S))) =>(a,((a,a),(a,a))) S =>(L) =>(L,S) =>(L,(L)) =>(L,(L,S)) =>(L,(L,(L))) =>(L,(L,(L,S))) =>(L,(L,(L,a))) =>(L,(L,(S,a))) =>(L,(L,(a,a))) =>(L,(S,(a,a))) =>(L,((L),(a,a))) =>(L,((L,S),(a,a))) =>(L,((L,a),(a,a))) =>(L,((S,a),(a,a))) =>(L,((a,a),(a,a))) =>(S,((a,a),(a,a))) =>(a,((a,a),(a,a)))

《编译原理》课后习题答案第三章第3章文法和语言第1

《编译原理》课后习题答案第三章第3章文法和语言第1

《编译原理》课后习题答案第三章第3 章文法和语言第1 题文法G＝({A,B,S},{a,b,c},P,S)其中P 为：S→Ac|aBA→abB→bc写出L(G[S])的全部元素。

答案：L(G[S])={abc}第2 题文法G[N]为：N→D|NDD→0|1|2|3|4|5|6|7|8|9G[N]的语言是什么？答案:G[N]的语言是V+。

V={0,1,2,3,4,5,6,7,8,9}N=>ND=>NDD.... =>NDDDD...D=>D......D或者：允许0 开头的非负整数？第３题为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。

答案：G[S]:S->S+D|S-D|DD->0|1|2|3|4|5|6|7|8|9第4 题已知文法G[Z]：Z→aZb|ab写出L(G[Z])的全部元素。

盛威网（）专业的计算机学习网站 1《编译原理》课后习题答案第三章答案：Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbbL(G[Z])={anbn|n>=1}第5 题写一文法，使其语言是偶正整数的集合。

要求：(1) 允许0 打头；(2)不允许0 打头。

答案：(1)允许0 开头的偶正整数集合的文法E→NT|DT→NT|DN→D|1|3|5|7|9D→0|2|4|6|8(2)不允许0 开头的偶正整数集合的文法E→NT|DT→FT|GN→D|1|3|5|7|9D→2|4|6|8F→N|0G→D|0第6 题已知文法G：<表达式>::=<项>｜<表达式>＋<项><项>::=<因子>｜<项>*<因子><因子>::=（<表达式>）｜i试给出下述表达式的推导及语法树。

（５）i+(i+i)（６）i+i*i盛威网（）专业的计算机学习网站 2 《编译原理》课后习题答案第三章答案：<表达式><表达式> + <项><因子><表达式><表达式> + <项><因子>i<项><因子>i<项><因子>i（ )(5) <表达式>=><表达式>＋<项>=><表达式>＋<因子>=><表达式>＋（<表达式>）=><表达式>＋（<表达式>＋<项>）=><表达式>＋（<表达式>＋<因子>）=><表达式>＋（<表达式>＋i）=><表达式>＋（<项>＋i）=><表达式>＋（<因子>＋i）=><表达式>＋（i＋i）=><项>＋（i＋i）=><因子>＋（i＋i）=>i＋（i＋i）<表达式><表达式> + <项><项> * <因子><因子> i<项><因子>ii(6) <表达式>=><表达式>＋<项>=><表达式>＋<项>*<因子>=><表达式>＋<项>*i=><表达式>＋<因子>*i=><表达式>＋i*i=><项>＋i*i=><因子>＋i*i=>i＋i*i盛威网（）专业的计算机学习网站 3《编译原理》课后习题答案第三章第7 题证明下述文法G[〈表达式〉]是二义的。

编译原理教程-课后习题答案第三章语法分析

编译原理教程-课后习题答案第三章语法分析

由 A′→ABl 得 FIRST(′l′) FOLLOW(B) ， 即 FOLLOW(B)={l}；
由 A→aA′ 得 FOLLOW(A) FOLLOW(A′) ， 即 FOLLOW(A′)={#,d}；
第三章 语法分析
由 B→dB′ 得 FOLLOW(B) FOLLOW(B′) ， 即 FOLLOW(B′)={l}。
第三章 语法分析
求得：
FIRST(A)={a}
FIRST(A′)={a, ε }
FIRST(B)={d}
FIRST(B′)={b, ε }
对文法开始符号A，有FOLLOW(A)={#}。
由 A′→ABl 得 FIRST(B)\{ ε }FOLLOW(A) ， 即 FOLLOW(A)={#,d}；
第三章 语法分析
3.9 考虑文法G[S]: S→(T) | a+S | a T→T,S | S
消除文法的左递归及提取公共左因子，然后对每 个非终结符写出不带回溯的递归子程序。
【解答】 消除文法G[S]的左递归： S→(T) | a+S | a T→ST′ T′→,ST′| ε
第三章 语法分析 提取公共左因子：
短语和最左素短语。 【解答】 (1) 句型(S, (a))的语法树如图3-5所示。
第三章 语法分析
S (L ) L ,S S (L )
S a
图3-5 句型(S,(a))的语法树
第三章 语法分析
(2) 由图3-5可知： 短语：S、a、(a)、S,(a)、(S,(a))； 直接短语：a、S； 句柄：S； 素短语：素短语可由图3-5中相邻终结符之间的优 先关系求得，即：
由图3-3可直接得到正规文法G[S]如下： G[S]：S→aA|bB A→aS|bC|b B→bS|aC|a C→bA|aB|ε

编译原理陈意云_课后答案2.

编译原理陈意云_课后答案2.

2021/4/13
luanj@
22
3.15
• (a) 用3.1的文法构造(a,(a,a))的最右推导， 说出每个右句型的句柄
• (b) 给出对应(a)的最右推导的移进-归约分 析器的步骤
• (c) 对照(b)的移进-归约，给出自下而上构 造分析树的步骤。
2021/4/13
➢ 期望的是： if expr then if expr then matched_stmt else if expr then matched_stmt else stmt
2021/4/13
luanj@
13
3.5 (续)
• 一种推导，和期望的不一样
➢ stmt
=> matched_stmt => if expr then matched_stmt else stmt => if expr then if expr then matched_stmt else stmt else stmt => if expr then if expr then matched_stmt else if expr then stmt else stmt => if expr then if expr then matched_stmt else if expr then matched_stmt else stmt
2021/4/13
luanj@
S
( L) L,S
S ( L)
aL
,
S
S
( L)
( L) L , S
L , SS
a
S
aa
4
a
3.1 (续)
• 描述的语言： 括号匹配的串，串中的各项由”,”隔开，

编译原理部分课后答案,仅供参考

编译原理部分课后答案,仅供参考

第一章编译程序概述1.1什么是编译程序编译程序是现代计算机系统的基本组成部分之一，而且多 数计算机系统都含有不止一个高级语言的编译程序。

对有些高 级语言甚至配置了几个不同性能的编译程序。

1.2编译过程概述和编译程序的结构编译程序完成从源程序到目标程序的翻译工作，是一个复 杂的整体的过程。

从概念上来讲，一个编译程序的整个工作过 程是划分成阶段进行的，每个阶段将源程序的一种表示形式转 换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连 接在一起的。

一般一个编译过程划分成词法分析、语法分析、 语义分析、中间代码生成，代码优化和目标代码生成六个阶段,这是一种典型的划分方法。

事实上，某些阶段可能组合在一起， 这些阶段间的源程序的中间表示形式就没必要构造岀来了。

我 们将分别介绍各阶段的任务。

另外两个重要的工作：表格管理 和岀错处理与上述六个阶段都有联系。

编译过程中源程序的各 种信息被保留在种种不同的表格里，编译各阶段的工作都涉及 到构造、查找或更新有关的表格，因此需要有表格管理的工作； 如果编译过程中发现源程序有错误，编译程序应报告错误的性 质和错误发生的地点，并且将错误所造成的影响限制在尽可能 小的范围内，使得源程序的其余部分能继续被编译下去，有些 编译程序还能自动校正错误， 这些工作称之为岀错处理。

图1.3表示了编译的各个阶段。

图1.3编译的各个阶段它不生成目标代码，它每遇到一个语句，就要对这个语句进行 分析以决定语句的含义，执行相应的动作。

右面的图示意了它 的工作机理第二章：PL/O 编译程序问答第1题 PL/0语言允许过程嵌套定义和递归调用，试问 它的编译程序如何解决运行时的存储管理。

答：PL/0语言允许过程嵌套定义和递归调用，它的编译程序在运行时采用了栈式动态存储管理。

(数组CODE 存放的只读目 标程序，它在运行时不改变。

)运行时的数据区S 是由解释程序 定义的一维整型数组，解释执行时对数据空间S 的管理遵循后进先岀规则，当每个过程(包括主程序)被调用时，才分配数据 空间，退出过程时，则所分配的数据空间被释放。

编译原理 第3章习题解答

编译原理 第3章习题解答

第三章习题参考解答3.1 构造自动机A，使得①②③当从左至右读入二进制数时，它能识别出读入的奇数；④它识别字母表{a, b}上的符号串，但符号串不能含两个相邻的a，也不含两个相邻的b；⑤它能接受字母表{0, 1}上的符号串，这些符号串由任意的1、0和随后的任意的11、00对组成。

⑥它能识别形式如±dd*⋅ d*E ±dd的实数，其中，d∈{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}。

3.2 构造下列正规表达式的DFSA：① xy*∣yx*y∣xyx；② 00∣(01)*∣11；③ 01((10∣01)*(11∣00))*01；④ a(ab*∣ba*)*b。

3.3 消除图3.24所示自动机的空移。

图3.24 含空移的自动机3.4 将图3.25所示NDFSA确定化和最小化。

图3.25 待确定化的NDFSA3.5 设e、e1、e2是字母表∑上的正规表达式，试证明① e∣e=e；② {{e}}={e}；③ {e}=ε∣e{e}；④ {e1 e2} e1= e1{e2 e1};⑤ {e1∣e2}={{e1}{e2}}={{e1}∣{e2}}。

3.6 构造下面文法G[Z]的自动机，指明该自动机是不是确定的，并写出它相应的语言： G[Z]:Z→A0A→A0∣Z1∣03.7 设NDFSA M=({x, y},{a, b},f, x, {y}), 其中，f(x, a)={x, y}, f(x, b)={y}, f(y, a)=∅, f(y, b)={x, y}。

试对此NDFSA 确定化。

3.8 设文法G[〈单词〉]：〈单词〉→〈标识符〉∣〈无符号整数〉 〈标识符〉→〈字母〉∣〈标识符〉〈字母〉∣〈标识符〉〈数字〉 〈无符号整数〉→〈数字〉∣〈无符号整数〉〈数字〉 〈字母〉→a ∣b 〈数字〉→1∣2试写出相应的有限自动机和状态图。

3.9 图3.29所示的是一个NDFSA A ，试构造一个正规文法G ，使得L(G)= L(A)。

编译原理陈意云课后答案


22.07.2020
luanj@
9
3.16 (续)
• Goto(I4, )) =
I6 S -> (L ) ∙
• Goto(I4, ,)=
I7 L -> L , ∙ S S -> ∙(L) S -> ∙a22.07.20来自0luanj@23
谢谢！！
22.07.2020
luanj@
19
3.26 (续)
I0 L’ -> ∙L, $ L -> ∙MLb, $ L -> ∙a, $ M -> ∙ , a
L I1 L’ -> L ∙, $
I2
M
L -> M ∙Lb, $ L -> ∙MLb, b
L -> ∙a, b
M -> ∙, a
• 只有直接左递归 S -> (L)|a L -> SL’ L’-> ,SL’|ε
22.07.2020
luanj@
3
3.8(b) (续)
• S -> (L)|a L -> SL’ L’-> ,SL’|ε
• FIRST(S) = {(, a} FIRST(L) = FIRST(S) = {(, a} FIRST(L’) = {,, ε}
➢S->aAc A->bAb|b
22.07.2020
luanj@
22
3.30 (续)
• 第二个不是LR(1)文法 第二个文法在句子的正中心按A->b规约， 而只向后看一位是无法判断是否到达句子 的中心位置的
• 存在冲突的项目集：
S -> a∙Ac, $ A -> ∙bAb, c A -> ∙b, c

编译原理第3章 习题解答

第3章习题解答1.构造正规式1(0|1)*101相应的DFA.[答案]先构造NFA确定化0 1X AA A ABAB AC ABAC A ABYABY AC AB重新命名，令AB为B、AC为C、ABY为D0 1X AA A BB C BC A DD C B转化成DFA：============================================================== 2.将下图确定化：[答案]0 1S VQ QUVQ VZ QUQU V QUZVZ Z ZV ZQUZ VZ QUZZ Z Z重新命名，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。

0 1S A BA C BB D EC F FD FE C EF F F转化为DFA：================================================================ 3.把下图最小化：[答案]（1）初始分划得Π0：终态组{0}，非终态组{1,2,3,4,5}对非终态组进行审查：{1,2,3,4,5}a {0,1,3,5}而{0,1,3,5}既不属于{0}，也不属于{1,2,3,4,5} ∵{4} a {0}，所以得新分划 （2）Π1：{0}，{4}，{1,2,3,5} 对{1,2,3,5}进行审查： ∵{1,5} b {4}{2,3} b {1,2,3,5}，故得新分划 （3）Π2：{0}，{4}，{1, 5}，{2,3} {1, 5} a {1, 5}{2,3} a {1,3}，故状态2和状态3不等价，得新分划 （3）Π3：{0}，{2}，{3}，{4}，{1, 5} 这是最后分划了 （4）最小DFA ：======================================= 4.构造一个DFA ，它接收Σ={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。

编译原理课后习题答案

第一章1．典型的编译程序在逻辑功能上由哪几部分组成？答：编译程序主要由以下几个部分组成：词法分析、语法分析、语义分析、中间代码生成、中间代码优化、目标代码生成、错误处理、表格管理。

2. 实现编译程序的主要方法有哪些？答：主要有：转换法、移植法、自展法、自动生成法。

3. 将用户使用高级语言编写的程序翻译为可直接执行的机器语言程序有哪几种主要的方式？答：编译法、解释法。

4. 编译方式和解释方式的根本区别是什么？答：编译方式：是将源程序经编译得到可执行文件后，就可脱离源程序和编译程序单独执行，所以编译方式的效率高，执行速度快；解释方式：在执行时，必须源程序和解释程序同时参与才能运行，其不产生可执行程序文件，效率低，执行速度慢。

第二章1.乔姆斯基文法体系中将文法分为哪几类？文法的分类同程序设计语言的设计与实现关系如何？答：1）0型文法、1型文法、2型文法、3型文法。

2）2. 写一个文法，使其语言是偶整数的集合，每个偶整数不以0为前导。

答：Z→SME | BS→1|2|3|4|5|6|7|8|9M→ε | D | MDD→0|SB→2|4|6|8E→0|B3. 设文法G为：N→ D|NDD→ 0|1|2|3|4|5|6|7|8|9请给出句子123、301和75431的最右推导和最左推导。

答：N⇒ND⇒N3⇒ND3⇒N23⇒D23⇒123N⇒ND⇒NDD⇒DDD⇒1DD⇒12D⇒123N⇒ND⇒N1⇒ND1⇒N01⇒D01⇒301N⇒ND⇒NDD⇒DDD⇒3DD⇒30D⇒301N⇒ND⇒N1⇒ND1⇒N31⇒ND31⇒N431⇒ND431⇒N5431⇒D5431⇒75431N⇒ND⇒NDD⇒NDDD⇒NDDDD⇒DDDDD⇒7DDDD⇒75DDD⇒754DD⇒7543D⇒75431 4. 证明文法S→iSeS|iS| i是二义性文法。

答：对于句型iiSeS存在两个不同的最左推导：S⇒iSeS⇒iiSesS⇒iS⇒iiSeS所以该文法是二义性文法。

编译原理部分课后答案,仅供参考

第一章编译程序概述1.1什么是编译程序编译程序是现代计算机系统的基本组成部分之一，而且多 数计算机系统都含有不止一个高级语言的编译程序。

对有些高 级语言甚至配置了几个不同性能的编译程序。

1.2编译过程概述和编译程序的结构编译程序完成从源程序到目标程序的翻译工作，是一个复 杂的整体的过程。

从概念上来讲，一个编译程序的整个工作过 程是划分成阶段进行的，每个阶段将源程序的一种表示形式转 换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连 接在一起的。

一般一个编译过程划分成词法分析、语法分析、 语义分析、中间代码生成，代码优化和目标代码生成六个阶段,这是一种典型的划分方法。

事实上，某些阶段可能组合在一起， 这些阶段间的源程序的中间表示形式就没必要构造岀来了。

我 们将分别介绍各阶段的任务。

另外两个重要的工作：表格管理 和岀错处理与上述六个阶段都有联系。

编译过程中源程序的各 种信息被保留在种种不同的表格里，编译各阶段的工作都涉及 到构造、查找或更新有关的表格，因此需要有表格管理的工作； 如果编译过程中发现源程序有错误，编译程序应报告错误的性 质和错误发生的地点，并且将错误所造成的影响限制在尽可能 小的范围内，使得源程序的其余部分能继续被编译下去，有些 编译程序还能自动校正错误， 这些工作称之为岀错处理。

图1.3表示了编译的各个阶段。

图1.3编译的各个阶段它不生成目标代码，它每遇到一个语句，就要对这个语句进行 分析以决定语句的含义，执行相应的动作。

右面的图示意了它 的工作机理第二章：PL/O 编译程序问答第1题 PL/0语言允许过程嵌套定义和递归调用，试问 它的编译程序如何解决运行时的存储管理。

答：PL/0语言允许过程嵌套定义和递归调用，它的编译程序在运行时采用了栈式动态存储管理。

(数组CODE 存放的只读目 标程序，它在运行时不改变。

)运行时的数据区S 是由解释程序 定义的一维整型数组，解释执行时对数据空间S 的管理遵循后进先岀规则，当每个过程(包括主程序)被调用时，才分配数据 空间，退出过程时，则所分配的数据空间被释放。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

3.30
• 下面哪个不是LR(1)文法？对非LR(1)文法 给出所有冲突的LR(1)项目集
➢S->aAc A->Abb|b
➢S->aAc A->bAb|b
3.30 (续)
• 第二个不是LR(1)文法 第二个文法在句子的正中心按A->b规约， 而只向后看一位是无法判断是否到达句子 的中心位置的
• 存在冲突的项目集：
3.26 (续)
I0 L’ -> ∙L, $ L -> ∙MLb, $ L -> ∙a, $ M -> ∙ , a
ቤተ መጻሕፍቲ ባይዱ
L I1 L’ -> L ∙, $
I2
M
L -> M ∙Lb, $ L -> ∙MLb, b
L -> ∙a, b
M -> ∙, a
a I3 L -> a ∙, $
L I4
b I7
L -> M L ∙ b, $
I1 S’ -> S ∙
• Goto(I0, () =
I2 S -> (∙ L) L -> ∙ L , S L -> ∙ S S -> ∙(L) S -> ∙a
• Goto(I0, a) =
I3 S -> a∙
3.16 (续)
• Goto(I2, L) =
I4 S -> (L ∙ ) L -> L ∙ , S
3.26
• 一个非LR(1)的文法如下： L -> MLb | a M -> ε
给出所有有移进-规约冲突的规范LR(1)项目 集
3.26 (续)
• 拓广文法： L’ -> L L -> MLb | a M -> ε
• I0
I0 L’ -> ∙L, $ L -> ∙MLb, $ L -> ∙a, $ M -> ∙ , $/a
L -> M L b ∙, $
I5 M L -> M ∙ Lb, b
L -> ∙MLb, b
L -> ∙a, b
M -> ∙, a
a
a
I6 L -> a ∙, b
L I8 L -> ML ∙ b, b
b M
I9 L -> ML b ∙, b
3.26 (续)
• I0,I2,I5面临a时存在移进-规约冲突
3.23
• 证明下面文法不是SLR(1)文法 S -> X X -> Ma | bMc | dc | bda M -> d
3.23 (续)
• S -> X X -> Ma | bMc | dc | bda M -> d
• 存在移进-规约冲突 如句子dc，当d进栈后，面临c，此时项目 [X -> d ∙ c]要求移进，而c在FOLLOW(M)中， 因此项目[M -> d ∙]要求规约
编译原理习题课(3)
10.08.2020
3.8(a)
• (a) 消除3.1的左递归 (b) 在（a）的基础上构造LL(1)分析表
3.8(a) (续)
• S -> (L)|a L -> L,S|S
• 只有直接左递归 S -> (L)|a L -> SL’ L’-> ,SL’|ε
3.8(b) (续)
• Goto(I2, S)=
I5 L -> S ∙
• Goto(I2, ()=I2 • Goto(I2, a)=I3
3.16 (续)
• Goto(I4, )) =
I6 S -> (L ) ∙
• Goto(I4, ,)=
I7 L -> L , ∙ S S -> ∙(L) S -> ∙a
3.16 (续)
L -> ∙ S
S -> ∙(L)
S -> ∙a
(
I6 S -> (L ) ∙
(
I4 S -> (L ∙ ) L -> L ∙ , S
,
a
( I7
a
I3 S -> a∙
a
L -> L , ∙ S S S -> ∙(L) S -> ∙a
I8 L -> L , S ∙
3.16 (续)
• SLR(1)分析表构造
1) 若A∙a∈I，且goto(I,a)=J，则 action[I,a]=sJ 2)若A∙ ∈ I，则action[I,b] = r A,b∈Follow(A) 3)若S‘S∙ ∈ I，则action[I,$] = acc
4)若goto(I,B)=K，则GOTO[I,B]=K
5)其它为空白/error
• Goto(I6, S) =
I8 L -> L , S ∙
• Goto(I6, () =I2 • Goto(I6, a) =I3
3.16 (续)
I0 S’ -> ∙S
S -> ∙(L)
S -> ∙a
S
I1 S’ -> S ∙
I5 L -> S ∙
S
( I2 S -> (∙ L)
L -> ∙ L , S L
• S -> (L)|a L -> SL’ L’-> ,SL’|ε
• FIRST(S) = {(, a} FIRST(L) = FIRST(S) = {(, a} FIRST(L’) = {,, ε}
• FOLLOW(S) = (FIRST(L’)-{ε}) + FOLLOW(L) + FOLLOW(L’) + {$} = {,, ), $} FOLLOW(L) = {)} FOLLOW(L’) = FOLLOW(L) = {),$}
3.16 (续)
• 拓展文法： (1) S‘ -> S (2) S -> ( L ) (3) S -> a (4) L -> L , S (5) L -> S
• 初态：I0 = closure{S’ -> ∙S} =
I0 S’ -> ∙S S -> ∙(L) S -> ∙a
3.16 (续)
• Goto(I0, S) =
S -> a∙Ac, $ A -> ∙bAb, c
3.16 (续)
状
action
态( ) a , $
0 s2
s3
1 s2
s3
acc
2
3
r3
r3 r3
4 s5
s6
5
r5
r5
6
r2
r2 r2
7 s2
s3
8
r4
r4
goto SL 1 14
7
3.16 (续)
• S -> ( L ) | a L -> L , S | S
• FOLLOW(S) = {$} + FOLLOW(L) = {$, ), ,} FOLLOW(L) = {), ,}
3.8(b) (续)
(
)
,
a
$
S S -> (L)
S -> a
L L -> SL’
L -> SL’
L’
L’ -> ε L’-> ,SL’
L’ -> ε
3.16
• 给出接收文法 S -> ( L ) | a L -> L , S | S
的LR(0)活前缀的DFA；并且在此基础上构 造SLR(1)分析表.