课 后 答 案 网
第三章 词法分析及词法分析程序 1 试用某种高级语言编写一个 FORTRAN 源程序的预处理子程序，其功能是： 每调用它一次， 即把源程序中的一个完整语句送入扫描缓冲区。要求删去语句中的注释行；删去续行标记字 符，把语句中的各行连接起来，并在语句的末端加上语句结束符。此外，还要求此程序具有 组织源程序列表输出的功能。 2 画出用来识别如下三个关键字的状态转移图。 STEP STRING SWITCH 3 假定有一个猎人带着一只狼、一头山羊和一棵白菜来到一条河的左岸，拟摆渡过河，而岸 边只有一条小船，其 大小仅能装载人和其余三件东西中的一件，也就是说，每一次猎人只 能将随行者中的一件带到彼岸。若猎人将狼和山羊留在同一岸上而无人照管，那么，狼就会 将羊吃掉；如果猎人把山羊和白菜留在同一岸，山羊也会把白菜吃掉。现在，请你用状态转
试找出一个长度最小的输入串，使得：
h (1) 在识别此输入串的过程中，每一状态至少经历一次；
(2) 每一状态转换至少经历一次。 9 对于下列的状态转换矩阵：[]a[]bS[]A[]SA[]A[]BB[]B[]B(i) 初态：S
k 终态：B[][][]a[]bS[]A[]BA[]B[]AB[]B[]B(ii) 初态：S
26 指出下列 LEX 正规式所匹配的字符串：
. (1) "{" ［^{］*"}"
(2) ^［^a-z］［A-Z］［0-9］$ (3) ［^0-9］|［＼r＼n］
w (4) ＼′(［^′＼n］|＼′＼′)+＼′
(5) ＼"(［^"＼n］|＼＼［"＼n］)*＼"
a 27 写出一个 LEX 正规式，它能匹配 C 语言的所有无符号整数 (例如：OX89ab，0123，45，
A→BbB→BbB→a
课 后 答 案 网
C→DC→BabD→d (1) 试分别对 G1 和 G2 构造相应的状态转换图 (提示：对于右线性文法，可将形如 C→D 的 产生式视为 C→εD；而对左线性文法，则可将它视为 C→Dε)。 (2) 对于 G1，构造一等价的左线性文法 G1′；对于 G2 构造一等价的右线性文法 G2′。 (3) 对于 G1 和 G1′，分别给出如下符号串的推导序列： abbaababbbcdcbb
〈WHILE 语句〉→WHILE〈关系表达式〉DO〈语句〉 〈复合语句〉→BEGIN〈语句表〉END 〈过程定义〉→PROCEDURE〈标识符〉〈参数表〉； BEGIN〈语句表〉END
课 后 答 案 网
〈参数表〉→(〈标识符表〉)|〈空〉 〈标识符表〉→〈标识符表〉，〈标识符〉|〈标识符〉 〈算术表达式〉→〈算术表达式〉+〈项〉|〈项〉 〈项〉→〈项〉*〈初等量〉|〈初等量〉 〈初等量〉→(〈算术表达式〉)|〈变量〉|〈无符号数〉 〈关系表达式〉→〈算术表达式〉〈关系符〉〈算术表达式〉 〈变量〉→〈标识符〉 〈标识符〉→〈标识符〉〈字母〉|〈标识符〉〈数学〉|〈字母〉 〈无符号数〉→〈无符号数〉〈数字〉|〈数字〉 〈关系符〉→=|＜|＜=|＞|＞=|＜＞
课后答案网，用心为你服务！
大学答案 --- 中学答案 --- 考研答案 --- 考试答案 最全最多的课后习题参考答案，尽在课后答案网（）！ Khdaw团队一直秉承用心为大家服务的宗旨，以关注学生的学习生活为出发点，
旨在为广大学生朋友的自主学习提供一个分享和交流的平台。 爱校园（） 课后答案网（） 淘答案（）
终态：A[]a[]bS[]A[]BA[]C[]AB[]B[]CC[]C[]C(iii) 初态：S
. 终态：A,C[][][]a[]bS[]A[]SA[]C[]BB[]B[]CC[]C[]C(iv) 初态：S
终态：C (1) 分别画出相应的状态转换图； (2) 写出相应的 3 型文法；
w(3) 用自然语言分别描述它们所识别的输入串的特征。
m 14 将如题图 314 所示的有限自动机最小化。
15 试用一种高级语言分别写出将 NFA 确定化以及将 DFA 最小化的算法。
o 16 构造一产生 FORTRAN 语言 COMMON 语句的 3 型文法 (假定分别用λ和μ代表标识符和整常
数，它们都是终结符号，且假定数组的维数不加限定)，构造相应的 DFA，并写出描述 COMMON 语句的正规式。
a 8 对于有限自动机 M=(K,Σ,f,S0,Z)
其中，K={S0,S1,S2,S3,S4,S5},Σ={a,b},Z={S1,S4,S5}。 f 由如下的状态转移矩阵给出：
d []a[]bS0[]S2[]S1S1[]S3[]S1S2[]S0[]S4S3[]S0[]S0S4[]S5[]S4S5[]S4[]S0
′Z′,′＼t′,′＼xab′,′＼012′,等等)。 28 写出一个 LEX 正规式，它能匹配 C 语言的标识符。
d 29 编写一个 LEX 源程序，它将一个正文文件中的全部小写字母均换为大写字母，并将其中
的制表字符、空白字符序列均用单个空格字符进行替换 (提示： 在语义动作中使用全程变
h 量 yytext)。
程中建立。 (3) 单词串的输出形式。
w 所输出的每一单词，均按形如
(CLASS，VALUE)
a 的二元式编码。对于变量标识符和常数，CLASS 字段为相应的类别码，VALUE 字段则是该标
识符、常数在其符号表中登记项的序号 (要求在变量名表登记项中存放该标识符的字符串， 其最大长度为四个字符；常数表登记项中则存放该整数的二进制形式)。对于保留字和分隔
c 17 设 r,s 等为任意的正规式，试证明下列的关系式成立：
(1) r*=(ε|r)*=ε|rr*=(r*)*
. (2) (rs)*r=r(sr)*
(3) (r|s)*=(r*s*)*=(r*|s*)* 18 对于解习题 36 所得的文法，试用正规式描述它所产生的语言。
w []a[]bS0[]S1[]S5S1[]S2[]S7S2[]S3[]S5S3[]S5[]S7S4[]S5[]S5S5[]S3[]S1S6[]S3[]S0S7[]
m 换图作为工具，描述猎人可能采取的种种摆渡方案，并从中找出可将上述三件东西安全地带
到右岸的方案来。
o 4 设已给文法 G=(VN,VT,P,S)，其中，P 仅含形如
A→αBA→αα∈V*T，B∈VN 的产生式，试证明： 由此种文法所产生的语言是一正规语言。 5 试证明： 任何有限个符号串所组成的集合 L={x1,x3,…,xn}xi∈Σ+ 都是 3 型语言。
〈变量说明〉→VAR〈变量表〉：〈类型〉；|〈空〉 〈变量表〉→〈变量表〉，〈变量〉|〈变量〉
w〈类型〉→INTEGER
〈语句表〉→〈语句表〉；〈语句〉|〈语句〉 〈语句〉→〈赋值语句〉|〈条件语句〉|〈WHILE 语句〉|〈复合语句〉|〈过程定义〉
w〈赋值语句〉→〈变量〉∶〈语句〉ELSE〈语句〉
10 对于下面所给的文法： G1=({S,A,B,C,D}, {a,b,c,d},P1,S)
wP1 由如下产生式组成： S→aAS→BA→abS w A→bBB→bB→cC
C→DD→dD→bB 以及 G2=({S,A,B,C,D},{a,b,c,d},P2,S) P2 由如下产生式组成： S→AaS→BA→Cc
30 编写一个 LEX 源程序，它能统计一个 PASCAL 程序中所含用户定义之标识符个数，并能找 出最长标识符中的字符个数 (提示： 使用全程变量 yytext 及 yyleng)。
k 上 机 实 习 题
对于如下文法所定义的 PASCAL 语言子集，试编写并上机调试一个词法分析程序：
. 〈程序〉→〈变量说明〉BEGIN〈语句表〉END.
19 对于习题 310 所给的文法 G1 和 G2，试分别用正规式描述它们所产生的语言。
h 20 设有如下的文法 G［〈标号说明〉］：
〈标号说明〉→′LABEL′〈标号表〉 〈标号表〉→d〈标号段〉
k 〈标号段〉→d〈标号段〉|,〈标号〉|；
〈标号〉→d〈标号段〉
. 其中′LABEL′,′d′,′,′,′;′等为终结符号。
m 〈字母〉→A|B|C|…|X|Y|Z
〈数字〉→0|1|2|…|8|9
o 〈空〉→
要求和提示： (1) 单词的分类。
c 可将所有标识符归为一类；将常数归为另一类；保留字和分隔符则可采取一词一类。
(2) 符号表的建立。
. 可事先建立一保留字表，以备在识别保留字时进行查询。变量名表及常数表则在词法分析过
(4) (b|aa|ac|aaa|aac)* (5) a(a|b)*b(a|b)*a(a|b)*b(a|b)* 23 试设计一个识别器，它识别由下列英语单词： ONE, TWO, THREE, …， NINE， TEN，
课 后 答 案 网
ELEVEN， TWELVE， THIRTEEN， …， NINETEEN， TWENTY， THIRTY， FORTY， …， NINETY， HUNDRED 所表示的从 1 到 999 间的任何整数 (各单词间用空格分隔，如 THREE HUNDRED FIFTY SIX)， 并将它们翻译为相应的阿拉伯数字 (如 356)作为输出。 24 设有辅助定义式 D0=a|b D1=D0D0 D2=D1D1 … Dn=Dn-1Dn-1
k (5) 写出它的 LEX 源程序，并上机进行处理。 第三章 习题解答
. 1．从略 www2．
课 后 答 案 网
3 假设 W:表示载狐狸过河，G:表示载山羊过河，C:表示载白菜过河 用到的状态 1：狐狸和山羊在左岸 2：狐狸和白菜载左岸 3:羊和白菜在左岸 4:狐狸和山羊 在右岸 5:狐狸和白菜在右岸 6:山羊和白菜在右岸 F:全在右岸
c 6 试构造一右线性文法，使得它与如下的文法等价
S→ABA→UTU→a|aU
. T→b|bTB→c|cB