当前位置：文档之家 › 编译原理作业集-第五章-修订

编译原理作业集-第五章-修订

  • 格式：doc
  • 大小：534.00 KB
  • 文档页数：22

下载文档原格式

  / 22

合集下载

编译原理chapter5

编译原理chapter5
D)对任何X，若文法开始符号S+ X…，则#<•X，
若S+ …X，则X•>#。
第五章 优先分析法
第二节 简单优先分析方法
三、简单优先分析的基本思想
根据优先关系的定义，将简单优先文法中各 文法符号之间的这种关系用一个矩阵表示，称 作简单优先矩阵。PDA读入一个单词后，比较 栈顶符号和该单词的优先级，若栈顶符号优先 级低于该单词，继续读入；若栈顶符号优先级 高于或等于读入符号，则找句柄进行归约，找 不到句柄就继续读入。直到最后栈内只剩下开 始符号，输入串读到“＃”为止。此时识别正 确。
1、自下而上归约
2、规定算符(更一般地说，指终结符)的优先级 及结合规则，以使得分析过程唯一
3、比较相邻两个算符而决定动作
注：1)这里的关键是对所有算符定义某种优先 关系
2)算符优先分析法是仿效四则运算的计算过 程而构造的一种语法分析方法
第五章 优先分析法 第三节 算符优先分析方法 一、基本思想
4、实例 表达式文法：
第五章 优先分析法 第二节 简单优先分析方法
四、简单优先矩阵
用于表示文法符号之间的简单优先关系的矩阵。
注：简单优先矩阵的构造可通过Warshall算法实 现。
第五章 优先分析法 第二节 简单优先分析方法
五、简单优先分析法的优缺点
优点：技术简单 缺点：适用范围小，分析表尺寸太大。
第五章 优先分析法 第三节 算符优先分析方法 一、基本思想
设A1A2…Ai-1AiAi+1…An是文法G的一个句型， 1)、若AiVN，则Ai-1、Ai+1 VT，即不许出现相继两个
非终结符；
第五章 优先分析法
第三节 算符优先分析方法 四、算符优先文法及优先表的构造 3、算符文法和算符优先文法定义的意义

编译原理作业集

编译原理作业集

编译原理作业集1 第二章词法分析1. C或Java语言的标示符是字母和数字组成的序列，第一个字符必须是字母，下划线视为字母，且大小写字母不同。

请写出匹配C或Java语言标示符的正规表达式。

2.为下边所描述的串写正规式，字母表是 {0, 1}. a) 以11 结尾的所有串 b) 只包含一个1的所有串2 第三章上下文无关文法1. ________是描述程序设计语言语法结构的形式工具。

2. 设G=(VN，VT，P，S)是一文法，且V= VN∪VT，若S =>*α，α∈V，则称α为文法G的，若S=>*α，α∈VT，则称α为文法G的。

3. 给出语言L={ab|j>i>=1}的上下文无关文法。

4. 文法G[S]的产生式如下：S?SaS | SbS | cS | Sd | t 对于输入串 tbctat: (1) 给出一个推导；(2) 画出(1)中推导对应的分析树；ij**(3) 文法G是否是二义性的，请证明你的结论。

3 第四章语法分析1. 考虑文法G[S]:S-> A��B A->a|b B->(C) C->CS|S 1) 消除上述文法的左递归，重写该文法。

2) 求消除左递归后的文法的非终结符构造First集合和Follow集合。

3) 为消除左递归后的文法构造LL(1)分析表。

4) 并写出对句子 (ab) 的LL(1)分析过程。

2. 给定文法G[S]: S->SaSb��c给出句子 cacbacb 的规范推导，画出该句子的语法推导树，指出该句子的句柄。

3. 给定文法G[S]:S->S b A��A A->a 1) 造文法G[S]的LR(1)项目的DFA。

2) 上述文法构造LR(1)分析表。

3) 写出句子 ababa的分析过程。

4 第五章语义分析1.通过下面文法给出的十进制数的浮点数值，写出一个属性文法(提示：使用一个属性count计算小数点右面数字的个数)。

编译原理_第1-5章习题课答案

编译原理_第1-5章习题课答案

（1）以01结尾的二进制数串。 (0 | 1)*01
（2）能被5整除的十进制数。
0|5
| (1|2|3|4|5|6|7|8|9)
（3）包含奇數個1或奇數個0的二進制串
0*1(0|10*1)*|1*0(0|10*1)*
（4）英文字母组成的所有符号串，要求符号串中的 字母按字典序排列。
(A | a)* (B | b)* (C | c)*… (Z | z)*
I00
0 ΦC
0
B {c,d} 1 0
E
1
{c,d} D
{c,d,f}
1
1
{c,d}
{c,d,f}
chapter1~5习题
I1 {b,c,d} 1 {c,dF,e}
{c,d,e} 0 {c,d,e} {c,d,e,g}
{c,d,e}
S
0
A(始态)
Φ
B
C
C
C
D
E
E
C
F(终态)
E
1 B D D D F(终态) D
1(0|1)*101 1(0|1)*101
chapter1~5习题
g
1
a
(0|1)* b
101
d
g
1 a
0
ε
ε
b
c
1
1
0
1
d
e
f
g
编译原理
②.状态转换矩阵
1 a
0
ε
ε
b
c
1
chapter1~5习题
1
0
1
d
e
f
g
I {a} {b,c,d} {c,d} {c,d,e} {c,d,f} {c,d,e,g}

5编译原理,陈意云 ,课后答案5

5编译原理,陈意云 ,课后答案5

10
7.5 (续) (续
• (a) *a-+bc • (c) 表达式翻成前缀形式的语法制导定义
E -> E+T | T T -> T*F | F F -> -F | (E) | id L -> En { printf(E.string); } E -> E1 + T { E.string = “+” + E1.string + T.string; } E -> T { E.string = T.string; } T -> T1*F { T.string = “*” + T1.string + F.string; } T -> F { T.string = F.string; } F -> -F1 { F.string = “-” + F1.string; } F -> (E) { F.string = E.string; } F -> id { F.string = id.value; }
2011-3-28
luanj@
8
7.4 (续) (续
• D -> ID_LIST:T ID_LIST -> ID_LIST,ID_LIST|id • D -> { Init(idtable) } ID_LIST:T { for each name in idtable do enter(name, T.type, offset); offset := offset + T.width; end; } ID_LIST -> { Init(idtable1); Init(idtable2) } ID_LIST1,ID_LIST2 { merge(idtable1, idtable2, idtable) } ID_LIST -> id { add(idtable, ); }

编译原理第五章语法制导翻译

编译原理第五章语法制导翻译

状态 0 1 2 3 4 5 6 7 8
+
s5 r4 r3 r1 r2
LR(0)分析表 action o n b # S4 S3 acc s7 r4 r4 r4 r4 r3 r3 r3 r3 s4 s3 r1 r1 r1 r1 s4 s3 r2 r2 r2 r2
GOTO E T 1 2
6 8
LR分析器的栈加入语义值。
的前缀表示法相比较，其共同的特点是： 1. 运算符的个数不变 2. 运算量的次序和个数不变 同时, 逆波兰表示法还具有两个明显的优点： 1. 无括号，形式简洁清楚 2. 运算符的顺序与运算的次序完全相同
（4）相关名字检查。有时，同一名字必须出现两 次或多次。例如，Ada 语言程序中，循环或程 序块可以有一个名字，出现在这些结构的开头 和结尾，编译程序必须检查这两个地方用的名 字是相同的。 (5)名字的作用域分析

如果语义正确，则进行中间代码的翻译。
中间代码
何谓中间代码 . Intermediate code Intermediate representation Intermediate language
第五章 语法制导翻译和 中间代码的生成
本章的主要内容
语法制导翻译的基本思想；
典型的中间代码表示法；
产生中间代码的语义子程序设计；
各种基本语言成分的自下而上分析的制导
翻译； 类型检查的基本原理。

语义分析是干什么的？
其任务是对语法分析所识别出的各类语法范畴， 分析其含义，并进行初步翻译。 包括两个方面的工作。 首先是对各种语法范畴进行静态语义检查，例 如，变量是否定义、类型是否正确等等。 如果语义正确，则进行中间代码的翻译。

软件工程 编译原理 第五章 自顶向下的语法分析方法

软件工程 编译原理 第五章 自顶向下的语法分析方法
PROCEDURE T； BEGIN F；T END PROCEDURE T； IF SYM=‘*’ THEN BEGIN ADVANCE； F；T END；
例:文法G(E):
E→TE E→+TE | T→FT PROCEDURE F； T→*FT | IF SYM=‘i’ THEN ADVANCE F→(E) | i ELSE 对应的递归下降子程序为: IF SYM=‘(’ THEN
其中不以P开头。
可以把P的规则等价地改写为如下的非直接左递归 形式： 左递归变 P→P 右递归 P→P|
一般而言，假定P关于的全部产生式是 P→P1 | P2 | … | Pm | 1 | 2|…|n 其中，每个都不等于，每个都不以P开头 那么，消除P的直接左递归性就是把这些规则改写 成：
第5章 自顶向下的语法分析方法
语法分析的作用是识别由词法分析给出 的单词符号序列是否是给定文法的正确句 子(程序)。 目前语法分析常用的方法有: 1、自顶向下（自上而下）分析 2、自底向上（自下而上）分析
5.3非LL(1)文法到LL(1)文法的等价转换
确定的自顶向下分析要求给定语言的文法必
须是 LL(1)形式。然而，不一定每个语言都是 LL(1)文法，对一个语言的非LL(1)文法是否能变
换为等价的LL(1)形式以及如何变换是我们讨论
的主要问题。由LL(1)文法的定义可知若文法中 含有左递归或含有左公共因子，则该文法肯定不 是LL(1)文法，因而，我们设法消除文法中的左 递归，提取左公共因子对文法进行等价变换。
1、提取公共左因子
若文法中含有形如：A→αβ|αγ的产生式，这导 致了对相同左部的产生式其右部的FIRST集相交， 也就是 SELECT(A→αβ)∩SELECT(A→αγ) ≠ φ ，不满足 LL(1)文法的充分必要条件。

编译原理第五章 (2)


可归前缀集：
开始符产生式的右部
｛aAc｝ ｛aAc，aAbb ｝ ｛aAc，aAbb，ab ｝
13
A → Abb[2] A → b[3]
LR(0)分析法基本概念

LR(0)项目： S 若A→是产生式，则称A→为LR(0)项目(简称项目）。 a A A c c
例： S → aAc 对应四个LR(0)项目： c 1. S → aAc 符号栈中不包含句柄的任何部分 2. S → aAc 符号栈中包含句柄中的a 3. S → aAc 符号栈中包含句柄中的aA 4. S → aAc 符号栈中包含完整句柄aAc
G[S]的LRSM
B e [4]

例3：构造LR(0)状态机 SE$ EE+T ET T id T ( E )
25
SE$ EE+T ET T id T ( E )
0
T
9
T
6
S→ E $ E→ E+T E→ T T→ id T→ ( E )
(
id +
E→T
活前缀的描述性定义 形成可归前缀之前，包括可 归前缀在内所有规范句型的前缀都称为活前缀。 LR类语法分析的思想。 LR(0)分析法关键技术是计算文法的所有规范活

前缀及所有归约规范活前缀。
9
派生定理
开始符产生式的右部是归约活前缀。 如果A是归约活前缀，且A→是产生式，则也 是归约活前缀。 分析： A A、 A
20

例1：计算下列文法的LR(0)状态机。 G[S]: S → aAc[1] A → dbb[2] A → b[3]
21
0
S → aAc[1]
εNO a
G[S]: S → aAc[1] A → dbb[2] A → b[3]

编译原理 龙书 第二版 第5、6章

elseE.type=float
2)E->T
E.type=T.type
3)T->num
T.type=integer
4)T->num.num
T.type=float
(2)
产生式
语义规则
1)E->E1+T
If E1.type ==T.type then E.type=E1.type
Else begin
E.type=float
105: goto–
6)按照产生式B->B1 || M B2进行归约
7)按照产生式B->（B1）进行归约
8)按照产生式B->B1 && M B2进行归约
9)各子表达式的truelist和falselist在上图中已标出
3）三元式序列
4）间接三元式序列
答：(1)抽象语法树
(2) 四元式序列
t1=b+c
t2=minus t1
t3=a+t2
op
Arg1

result
0
+
b
c
T1
1
minus
T1
T2
2
+
a
T2
T3
(3)三元式序列
op
Arg1
Arg2
0
+
b
c
1
minus
(0)
2
+
a
(1)
(4)间接三元式序列
10
(0)
E.type=T.type; E.val=T.val
3)T->num
T.type=integer; T.val=num

编译原理-第5章


规则(2)的语义动作为: E的语义值为0～9之间任一个数.
这样，按照它们的语义动作，我们在分析每个句子的同时一步一步 地算出每个句子的值 。
2019/1/14 8
§5.1 语法制导翻译概述
二、语法制导翻译原理
例如，假定有输入串1+2+3，我们通过语法树的分析来看如何进行 语法制导翻译，来求出该句子最后值。 输入串1+2+3的语法树如下图所示：
（4）把5推进栈。
（5）将栈顶两个元素4和5相乘，使它们退出栈，然后将结果20存入栈。 （6）结束时栈顶的值(这里是20)是整个表达式值。
2019/1/14 21
§5.2 中间语言
二、逆波兰表示
2、逆波兰表示的扩充
只要遵守在运算对象后直接紧跟运算符这条规则，我们就可以 简单地把这种后缀式扩充到比通常表达式更大范围，即扩充到程序 语言的其它语法成分。 以赋值语句为例—— 〈左部〉:=〈表达式〉 把赋值号“:=”看成是一个赋值运算符，它的后缀式为 〈左部〉〈表达式的后缀式〉：= 例如：x:=5 x5:=
结点表示运算符，如表达式 a+b, a-b, -a 的树表示分别定义为： －
b
+ a b a
－
a
2019/1/14
27
§5.2 中间语言
四、树形表示
1、表示方法
双目运算对应二叉树，多目运算对应多叉树，单目运算对应单叉 树。如表达式a*b-(c+d)/(e-f) 的二叉树如下图：
－
*
后序遍历上述二叉树便
式序列（或三元式表）中某一个三元式位置的指示器（对于运算对象
是中间结果的情况）。 如：A+B*C对应的三元式表示为：

《编译原理》习题参考答案(六)

《编译原理》习题参考答案（六）第五章5.4 为下列类型写类型表达式：(a) 指向实数的指针数组，数组的下标从1到100。

(b) 两位数组（即数组的数组），他的行下标从1到10，列下标从1到20。

(c) 函数，他的定义域是从整数到整数的指针的函数，它的值域是从一个整数和一个字符组成的纪录。

Solution:(a) array ( 1 . . 100 , pointer ( real ) )(b) array ( 1 . . 10 , array ( 1 . . 20 , type ) )(c) ( integer →pointer(integer) )→record((i : integer) * ( c : char )) 假定作为值域的记录类型的两个域分别叫i和c。

5.6 下列文法定以字面常量表的表。

符号的解释和图5.2文法的那些相同，增加了类型list，它表示类型T的元素表。

→ D ; EP→ D ; D | id : TD→ list of T | char | integerTE→ ( L ) | literal | num | id→ E , L | EL写一个类似5.3节中的翻译方案，以确定表达式( E )和表( L )的类型。

P→ D ; ED→ D ; DD→ id : T { addtype ( id.entry , T.type ) }T→ char { T.type := char }T→ integer { T.type := integer }T→ list of T1 { T.type := list ( T1.type ) }E→ literal { E.type := char }E→ num { E.type := integer }E→ id { E.type := lookup ( id.entry ) }E→ ( L ) { E.type := list ( L.type ) }L→E{L.type:=E.type}L→ E , L1 { L.type := if L1.type = E.type then E.typeelse type_error }5.16 对下面的每对表达式，找出最一般的合一代换：(a) α1 → ( α2 →α1 )(b) array ( β1 ) → ( pointer( β1 ) →β2 )(c) γ1 →γ2(d) δ1 →(δ1 →δ2 )Solution:S(α1) = array ( β1 ) S(α2) = pointer ( β1 ) S(β2) = array ( β1 ) (a)(c):S(γ1) = α1 S(γ2) = α2 → α1 (a)(d):S(α1) = S(α2) = S(δ1) = S(δ2) = α (b)(c):S(γ1) = array ( β1 ) S(γ2) = pointer ( β1 ) → β2 (b)(d): 无 (c)(d):S(γ1) = δ1 S(γ2) = δ1 → δ25.17 仿效例5.5，推到下面map 的多态类型: map: ∀ α . ∀ β . ( ( α → β ) * list ( α ) ) → list ( β ) map 的ML 定义是 fun map ( f , l ) = if null ( l ) then nilelse cons ( f ( hd ( l ) ) , map ( f , tl ( l ) ) );在这个函数体中，内部定义的标识符的类型是： null : ∀α . list (α ) → boolean ; nil : ∀α . list (α ) ;cons : ∀α . ( α * list (α ) ) → list (α ) ;hd:∀α . list (α ) →α;∀α . list (α ) → list (α ) ;tl:Solution:行定型断言代换规则(1) f : α( Exp Id )(2) l : β( Exp Id )(3) map : γ( Exp Id )(4) map ( f , l ) : δγ = ( α * β ) →δ(Exp Funcall)(5) null : list (α0) → boolean ( Exp Id ) 和( Type Fresh )(6) null ( l ) : boolean β = list (α0) (Exp Funcall)(7) nil : list (α1) ( Exp Id ) 和( Type Fresh )(8) l : list (α0) 由（2）可得(9) hd : list (α2) →α2( Exp Id ) 和( Type Fresh )(10) hd ( l ) : α0α2 = α0(Exp Funcall)(11) f ( hd ( l ) ) : α3α = α0→α3( Exp Id )(12) f : α0→α3由（1）可得(13) tl : list (α4)→ list (α4) ( Exp Id ) 和( Type Fresh )(14) tl ( l ) : list (α0) α4 = α0(Exp Funcall)(15) map : ((α0→α3)*list(α0))→δ由（3）可得(16) map ( f , tl ( l ) ) : δ(Exp Funcall)(17) cons : α5 * list(α5) → list(α5) ( Exp Id ) 和( Type Fresh ) (18) cons (…) : list (α3) α5 = α3 , δ=list(α3) (Exp Funcall)(19) if : boolean *α6 * α6→α6( Exp Id ) 和( Type Fresh )(20) if (…) : list (α1) α6 = α1 , α3 = α1(Exp Funcall)(21) match : α7 *α7 →α7( Exp Id ) 和( Type Fresh ) (22) match (…) : list (α1) α7 = list (α1) (Exp Funcall)至此有map : ( (α0→α1)*list(α0) )→list(α1)所以map : ∀α . ∀β . ( ( α→β ) * list ( α ) ) → list ( β )5.18 假定类型名link和cell如5.5节那样定义，下面的表达式中，那些结构等价？那些名字等价？(a) link(b) pointer ( cell )(c) pointer ( link )(d) pointer ( record ( ( info : integer ) * ( next : pointer ( cell ) ) ) ) Solution:(a)、(b)、(d)结构等价，无名字等价。

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

编译原理作业集 第五章 自下而上语法分析 西安理工大学计算机科学与工程学院 张发存编写 4/27/2022 7:31:03 AM - 1 - 第五章 语法分析—自下而上分析

本章要点 1. 自下而上语法分析法的基本概念： 2. 算符优先分析法； 3. LR分析法分析过程； 4. 语法分析器自动产生工具YACC； 5. LR分析过程中的出错处理。

本章目标 掌握和理解自下而上分析的基本问题、算符优先分析、LR分析法及语法分析器的自动产生工具YACC等内容。

本章重点 1．自下而上语法分析的基本概念：归约、句柄、最左素短语； 2．算符优先分析方法：FirstVT, LastVT集的计算，算符优先表的构造，工作原理； 3．LR分析器： （1）LR(0)项目集族，LR(1)项目集簇； （2）LR(0)、SLR、LR(1)和LALR(1)分析表的构造； （3）LR分析的基本原理，分析过程； 4．LR方法如何用于二义文法；

本章难点 1. 句柄的概念； 2. 算符优先分析法； 3. LR分析器基本；

作业题

一、单项选择题： 1. LR语法分析栈中存放的状态是识别________的DFA状态。 a. 前缀；b. 可归前缀；c. 项目；d. 句柄； 2. 算符优先分析法每次都是对________进行归约： (a)句柄 （b）最左素短语 (c)素短语 (d)简单短语 编译原理作业集 第五章 自下而上语法分析 西安理工大学计算机科学与工程学院 张发存编写 4/27/2022 7:31:03 AM - 2 - 3. 有文法G＝（｛S｝，｛a｝，｛S→SaS，S→ε｝，S），该文法是________。 a. LL(1)文法；b.二义性文法；c.算符优先文法；d.SLR(1)文法； 4. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类， 和LL(1)分析法属于自顶向下分析； a. 深度分析法 b. 宽度优先分析法 c. 算符优先分析法 d. 递归下降子程序分析法 5. 自底向上语法分析采用 分析法，常用的是自底向上语法分析有算符优先分析法和LR分析法。 a. 递归 b. 回溯 c. 枚举 d. 移进－归约 6. 一个LR(k)文法，无论k取多大， 。 a. 都是无二义性的；b. 都是二义性的；c. 一部分是二义性的；d. 无法判定二义性； 7. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类， 和LR分析法属于自底向上分析。 a. 深度分析法 b. 宽度优先分析法 c. 算符优先分析法 d. 递归下降子程序分析法 8. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，自顶向下分析试图为输入符号串构造一个 ； a. 语法树 b. 有向无环图 c. 最左推导 d. 最右推导 9. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，自底向上分析试图为输入符号串构造一个 。 a. 语法树 b. 有向无环图 c. 最左推导 d. 最右推导 10. 采用自顶向下分析方法时，要求文法中不含有 。 a. 右递归 b. 左递归 c. 直接右递归 d. 直接左递归 11. LR分析是寻找右句型的 ；而算符优先分析是寻找右句型的 。 a. 短语； b. 素短语； c. 最左素短语； d. 句柄 12. LR分析法中分析能力最强的是 ；分析能力最弱的是 。 a. SLR(1)； b. LR(0)； c. LR(1)； d. LALR(1) 13. 设有文法G： T->T*F | F F->FP | P P->(T) | a 该文法句型T*P(T*F)的最左直接短语是下列符号串________。 a. (T*F)， b. T*F， c. P， d. P(T*F) 14. 在通常的语法分析方法中，（ ）特别适用于表达式的分析。 a．算符优先分析法 b．LR分析法 c．递归下降分析法 d．LL(1)分析法 15. .运算符的优先数之间有几种关系 。 a.3种 b. 2种 c. 4种 d. 1种 16. 算符优先法属于（ ） a.自上而下分析法 b.LR分析法 c.ＳLR分析法 d.自下而上分析法 17. 在LR分析法中，分析栈中存放的状态是识别规范句型 的DFA状态。 a.句柄 b. 前缀 c. 活前缀 d. LR(0)项目

一．答案： 1. b；2. b；3. b；4. d；5. d；6. a；7. c；8. c；9. d；10. b；11. d，c；12. c，b；13. a；14. a 15. a；16. d；17. c； 编译原理作业集 第五章 自下而上语法分析 西安理工大学计算机科学与工程学院 张发存编写 4/27/2022 7:31:03 AM - 3 - 二、填空题： 1. 规范归约的关键问题是________ 。 2. LR(k)分析法中，L的含义是____________________，R的含义是_______________________，k的含义是 。 3. 移进一归约分析对符号串的使用有四类操作：移进、__________、_________和出错处理。 4. 设文法G（E为其开始符号）产生式如下： E→E+T|T T→T*F|F F→（E）|i 则句型E+T*F+i的句柄是_________________。 5. 自下而上分析方法的基本思想是：从输入符号串开始，利用文法规则逐步进行归约，直至归约到文法的 。 6. 在算符优先分析中，用 来刻画“可归约串”；在规范归约分析中，用 来刻画“可归约串”。 7. 在LR(0)分析中，相容的项目集，必须满足的条件是_______，_______。 8. LR语法分析栈中存放的状态是识别_______的DFA状态。 9. 在LR分析过程中的任何时候，栈里的文法符号从下往上应该构成 ，把输入串的剩余部分配上之后应成为 。 10. 对于LR(0)分析法来说，项目A→12对活前缀1是有效的，其条件是存在规范推导 。 11. 形式上我们说一个LR(1)项目[A→，a]对于活前缀是有效的，如果存在规范推导 。 12. LR(k)分析方法中项目类型可分为四类 、 、 和 。 13. 所谓算符优先分析法就是仿照算术四则运算的运算过程设计的一种语法分析方法。它首先要规定 ，然后利用这种关系确定 ，并进行 。 14. 如图所示的语法树中，a，b不在同一句柄中， 先归约，所以 的优先级高于 。

P

b R …… a … Q

15. 对于句型η的语法树，若它的一棵子树的根标记为A，且将此子树的末端结点标记从左至右排列起来所形成的符号串为β，则β是 ；此时文法中必有推导 。 16. LR(0)每个项目中圆点的左部表示在分析过程中，要用该产生式归约时， ，右部表示 。 17. 根据项目的定义，可给出文法中所有产生式的项目，而每个项目都为识别 的NFA的一个状态。 编译原理作业集 第五章 自下而上语法分析 西安理工大学计算机科学与工程学院 张发存编写 4/27/2022 7:31:03 AM - 4 - 二．答案： 1. 寻找或确定一个句型的句柄；2. 从左到右扫描输入串，构造一个最右推导的逆过程；3. 归约，接受；4. T*F；5. 开始符号；6. 最左素短语，句柄；7. 移进项目和归约项目并存，多个归约项目并存；8. 文法活前缀和可归前缀；9. 活前缀，规范句型；10.

21

*'RRAS；11. RRAS*'，其中=，a是的第一个符号，或者a

是#而为。12. 归约项目，接受项目，移进项目，待约项目；13. 运算符之间的优先关系；句型的“句柄”， 归约；14. a，a，b；15. 句型η相对于A的一个短语；A==>+ β；16. 句柄已识别的部分(进入符号栈)，等待识别的部分；17. 活前缀

三、判断题 1. 一个二义性文法可以是SLR文法或LALR文法。（ ） 2. LL(1)文法不能用LR（1）分析器来分析。（ ） 3. LR分析器在自左至右扫描输入串时就能发现其中的任何错误，并能准确地指出出错地点。( ） 4. 在归约过程的任一时刻，一个上下文无关文法的任何句型的直接短语一般都不是唯一的。( ) 5. 算符优先分析法不是一种规范规约法。 ( ) 6. 存在有左递归规则的文法是LL(1)的。 ( ) 7. 任何算符优先文法的句型中不会有两个相邻的非终结符号。 ( ) 8. 算符优先文法中任何两个相邻的终结符号之间至少满足三种关系(＜·，·＞，＝·)之一。 ( ) 9. 任何LL(1)文法都是无二义性的。 ( ) 10. 每一个SLR(1)文法也都是LR(1)文法。 ( ) 11. 存在一种算法，能判定任何上下文无关文法是否是LL(1)的。 ( ) 12. 任何一个LL(1)文法都是一个LR(1)文法，反之亦然。 ( ) 13. LR(1)分析中括号中的1是指，在选用产生式A→α进行分析，看当前读入符号是否在FIRST(α)中。 ( ) 14. 若某一个句型中出现了某一产生式的右部，则此右部不一定是该句型的句柄。（ ） 15. 算符优先关系表不一定存在对应的优先函数。 （ ） 16. 简单优先文法允许任意两个产生式具有相同右部。 （ ） 17. 一个句型的句柄一定是文法某产生式的右部。 （ ） 18. 若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。 （ ） 19. 根据项目的定义，可给出文法中所有产生式的项目，而每个项目都为识别活前缀的DFA的一个状态。 （ ） 四．答案：1. ×；2. ×；3. ；4. ；5. ；6. ×；7. ；8. ×；9. ；10. ；11. ；12. ×；13. ；14. ×；15. √；16. ×；17. √；⒙ ×；19. ×；