第三章 词法分析及词法分析程序 课后答案【khdaw_lxywyl】.pdf

课后答案网 用心为你服务 大学答案 中学答案 考研答案 考试答案 最全最多的课后习题参考答案 尽在课后答案网 Khdaw团队一直秉承用心为大家服务的宗旨 以关注学生的学习生活为出发点 旨在为广大学生朋友的自主学习提供一个分享和交流的平台 爱校园 课后答案网 淘答案 第三章 词法分析及词法分析程序 1 试用某种高级语言编写一个 FORTRAN 源程序的预处理子程序 其功能是 每调用它一次 即把源程序中的一个完整语句送入扫描缓冲区 要求删去语句中的注释行 删去续行标记字 符 把语句中的各行连接起来 并在语句的末端加上语句结束符 此外 还要求此程序具有 组织源程序列表输出的功能 2 画出用来识别如下三个关键字的状态转移图 STEP STRING SWITCH 3 假定有一个猎人带着一只狼 一头山羊和一棵白菜来到一条河的左岸 拟摆渡过河 而岸 边只有一条小船 其 大小仅能装载人和其余三件东西中的一件 也就是说 每一次猎人只 能将随行者中的一件带到彼岸 若猎人将狼和山羊留在同一岸上而无人照管 那么 狼就会 将羊吃掉 如果猎人把山羊和白菜留在同一岸 山羊也会把白菜吃掉 现在 请你用状态转 换图作为工具 描述猎人可能采取的种种摆渡方案 并从中找出可将上述三件东西安全地带 到右岸的方案来 4 设已给文法 G VN VT P S 其中 P 仅含形如 A BA V T B VN 的产生式 试证明 由此种文法所产生的语言是一正规语言 5 试证明 任何有限个符号串所组成的集合 L x1 x3 xn xi 都是 3 型语言 6 试构造一右线性文法 使得它与如下的文法等价 S ABA UTU a aU T b bTB c cB 并根据所得的右线性文法 构造出相应的状态转换图 7 对于如题图 37 所示的状态转换图 1 写出相应的右线性文法 2 指出它接受的最短输入串 3 任意列出它接受的另外四个输入串 4 任意列出它拒绝接受的四个输入串 8 对于有限自动机 M K f S0 Z 其中 K S0 S1 S2 S3 S4 S5 a b Z S1 S4 S5 f 由如下的状态转移矩阵给出 a bS0 S2 S1S1 S3 S1S2 S0 S4S3 S0 S0S4 S5 S4S5 S4 S0 试找出一个长度最小的输入串 使得 1 在识别此输入串的过程中 每一状态至少经历一次 2 每一状态转换至少经历一次 9 对于下列的状态转换矩阵 a bS A SA A BB B B i 初态 S 终态 B a bS A BA B AB B B ii 初态 S 终态 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 型文法 3 用自然语言分别描述它们所识别的输入串的特征 10 对于下面所给的文法 G1 S A B C D a b c d P1 S P1 由如下产生式组成 S aAS BA abS 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 A BbB BbB a w w w k h d a w c o m 课后答案网 C DC BabD d 1 试分别对 G1 和 G2 构造相应的状态转换图 提示 对于右线性文法 可将形如 C D 的 产生式视为 C D 而对左线性文法 则可将它视为 C D 2 对于 G1 构造一等价的左线性文法 G1 对于 G2 构造一等价的右线性文法 G2 3 对于 G1 和 G1 分别给出如下符号串的推导序列 abbaababbbcdcbb 对于 G2 和 G2 分别给出如下符号串的推导序列 aabaaabcadca 4 试给出若干个不能由 G1 或 G2 产生的符号串 并验证它们同样不能用 G1 和 G2 产生 11 分别构造将左线性文法转换为右线性文法以及将右线性文法转换为左线性文法的算法 12 将如题图 312 所示的 NFA 确定化和最小化 13 将如题图 313 所示的具有 动作的 NFA 确定化 14 将如题图 314 所示的有限自动机最小化 15 试用一种高级语言分别写出将 NFA 确定化以及将 DFA 最小化的算法 16 构造一产生 FORTRAN 语言 COMMON 语句的 3 型文法 假定分别用 和 代表标识符和整常 数 它们都是终结符号 且假定数组的维数不加限定 构造相应的 DFA 并写出描述 COMMON 语句的正规式 17 设 r s 等为任意的正规式 试证明下列的关系式成立 1 r r rr r 2 rs r r sr 3 r s r s r s 18 对于解习题 36 所得的文法 试用正规式描述它所产生的语言 a bS0 S1 S5S1 S2 S7S2 S3 S5S3 S5 S7S4 S5 S5S5 S3 S1S6 S3 S0S7 S0 S1S8 S3 S8 1 初态 S0 终态 S1 S2 S6 S7 a bS0 S5 S2S1 S6 S2S2 S0 S4S3 S3 S5S4 S6 S2S5 S3 S0S6 S3 S1 2 初态 S0 终态 S4 S5 S6 题图 314 19 对于习题 310 所给的文法 G1 和 G2 试分别用正规式描述它们所产生的语言 20 设有如下的文法 G 标号说明 标号说明 LABEL 标号表 标号表 d 标号段 标号段 d 标号段 标号 标号 d 标号段 其中 LABEL d 等为终结符号 1 试求出描述此文法所产生语言的正规式 2 构造识别此语言的具有最少状态的 DFA 21 求出描述习题 37 所给有限自动机所识别语言的正规式 22 分别构造识别如下正规语言的 DFA 1 0 1 1 0 2 b a aa b b 3 a abab a bab a b 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 w w w k h d a w c o m 课后答案网 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 试回答如下问题 1 由 Dn 所表述的正规集是什么 2 如果将 Dn 中所出现的 Dn 1 用前面已定义的辅助定义式反复进行替换 则可最终将 Dn 化为 a b 上的正规式 此正规式有多长 3 用来识别 Dn 的 DFA 至多需要几个状态 25 试将 LEX 中的 动作子程序 Ai 的功能加以扩充 使之可用来生成文本编辑程序 26 指出下列 LEX 正规式所匹配的字符串 1 2 a z A Z 0 9 3 0 9 r n 4 n 5 n n 27 写出一个 LEX 正规式 它能匹配 C 语言的所有无符号整数 例如 OX89ab 0123 45 Z t xab 012 等等 28 写出一个 LEX 正规式 它能匹配 C 语言的标识符 29 编写一个 LEX 源程序 它将一个正文文件中的全部小写字母均换为大写字母 并将其中 的制表字符 空白字符序列均用单个空格字符进行替换 提示 在语义动作中使用全程变 量 yytext 30 编写一个 LEX 源程序 它能统计一个 PASCAL 程序中所含用户定义之标识符个数 并能找 出最长标识符中的字符个数 提示 使用全程变量 yytext 及 yyleng 上 机 实 习 题 对于如下文法所定义的 PASCAL 语言子集 试编写并上机调试一个词法分析程序 程序 变量说明 BEGIN 语句表 END 变量说明 VAR 变量表 类型 空 变量表 变量表 变量 变量 类型 INTEGER 语句表 语句表 语句 语句 语句 赋值语句 条件语句 WHILE 语句 复合语句 过程定义 赋值语句 变量 算术表达式 条件语句 IF 关系表达式 THEN 语句 ELSE 语句 WHILE 语句 WHILE 关系表达式 DO 语句 复合语句 BEGIN 语句表 END 过程定义 PROCEDURE 标识符 参数表 BEGIN 语句表 END w w w k h d a w c o m 课后答案网 参数表 标识符表 空 标识符表 标识符表 标识符 标识符 算术表达式 算术表达式 项 项 项 项 初等量 初等量 初等量 算术表达式 变量 无符号数 关系表达式 算术表达式 关系符 算术表达式 变量 标识符 标识符 标识符 字母 标识符 数学 字母 无符号数 无符号数 数字 数字 关系符 字母 A B C X Y Z 数字 0 1 2 8 9 空 要求和提示 1 单词的分类 可将所有标识符归为一类 将常数归为另一类 保留字和分隔符则可采取一词一类 2 符号表的建立 可事先建立一保留字表 以备在识别保留字时进行查询 变量名表及常数表则在词法分析过 程中建立 3 单词串的输出形式 所输出的每一单词 均按形如 CLASS VALUE 的二元式编码 对于变量标识符和常数 CLASS 字段为相应的类别码 VALUE 字段则是该标 识符 常数在其符号表中登记项的序号 要求在变量名表登记项中存放该标识符的字符串 其最大长度为四个字符 常数表登记项中则存放该整数的二进制形式 对于保留字和分隔 号 由于采用一词一类的编码方式 所以仅需在二元式的 CLASS 字段上放置相应的单词的类 别码 VALUE 字段则为 空 不过 为便于查看由词法分析程序所输出的单词串 也可以 在 CLASS 字段上直接放置单词符号串本身 4 可以仿照程序 34 的结构来编写上述词法分析程序 但其中的若干语义过程有待于具体 编写 5 写出它的 LEX 源程序 并上机进行处理 第三章 习题解答 1 从略 2 w w w k h d a w c o m 课后答案网 3 假设 W 表示载狐狸过河 G 表示载山羊过河 C 表示载白菜过河 用到的状态 1 狐狸和山羊在左岸 2 狐狸和白菜载左岸 3 羊和白菜在左岸 4 狐狸和山羊 在右岸 5 狐狸和白菜在右岸 6 山羊和白菜在右岸 F 全在右岸 4 证明 只须证明文法 G A B 或 A A B VN VT 等价于 G1 A aB 或 A a a VT G1 的产生式中 A aB 则 B 也有 B bC C cD 所以有 A abc B a b c VT B VN 所以与 G 等价 2 G 的产生式 A B VT 因为 是字符串 所以肯定存在着一个终结符 a 使 A aB 可见两者等价 所以由此文法产生的语言是正规语言 5 6 根据文法知其产生的语言是 L ambnci m n i 1 可以构造如下的文法 VN S A B C VT a b c P S aA A aA A bB B bB B cC C cC C c 其状态转换图如下 7 1 其对应的右线性文法是 A 0D B 0A B 1C C 1 1F C 1 0A F 0 0E 1A D 0B 1C E 1C 0B 2 最短输入串 011 3 任意接受的四个串 011 0110 0011 000011 4 任意以 1 打头的串 8 从略 9 w w w k h d a w c o m 课后答案网 2 相应的 3 型文法 w w w k h d a w c o m 课后答案网 i S aAS bS A aA A bB B a aB B b bB ii S aA a S bB B aB bB A aB A b bA iii S aA S bB A bA A aC B aB B bC C a aC C b bC iv S bS S aA A aC A bB B aB B bC C a aC C b bC 3 用自然语言描述输入串的特征 i 以任意个 包括 0 b 开头 中间有任意个 大于 1 a 跟一个 b 还可以有一个由 a b 组成的任意字符串 ii 以 a 打头 后跟任意个 包括 0 b iii 以 a 打头 中间有任意个 包括 0 b 再跟 a 最后由一个 a b 所组成的任意串结尾或 者 以 b 打头 中间有任意个 包括 0 a 再跟 b 最后由一个 a b 所组成的任意串结尾 iv 以任意个 包括 0 b 开头 中间跟 aa 最后由一个 a b 所组成的任意串结尾或者 以任意个 包括 0 b 开头 中间跟 ab 后再接任意 包括 0 a 再接 b 最后由一个 a b 所 组成的任意串结尾 10 1 G1 的状态转换图 G2 的状态转换图 2 G1 等价的左线性文法 S Bb S Dd D C B Db C Bc B Ab B A a G2 等价的右线性文法 S dD S aB D C B abC B bB B bA B C cA A a 3 对 G1 文法 abb 的推导序列是 w w w k h d a w c o m 课后答案网 S aA abB abb 对 G1 文法 abb 的推导序列是 S Bb Abb abb 对 G2 文法 aabca 的推导序列是 S Aa Cca Babca aabca 对 G2 文法 aabca 的推导序列是 S aB aabC aabcA aabca 4 对串 acbd 来说 G1 G1 文法都不能产生 11 将右线性文法化为左线性文法的算法 o 1 对于 G 中每一个形如 A aB 的产生式且 A 是开始符 将其变为 B a 否则若 A 不是开始符 B Aa o 2 对于 G 中每一个形如 A a 的产生式 将其变为 S Aa 12 1 状态矩阵是 记 S q0 B q1 A B q2 S A q3 最小化和确定化后如图 2 记 S q0 A q1 B S q2 最小化和确定化后的状态转换图如下 13 1 将具有 动作的 NFA 确定化后 其状态转换图如图 记 S0 S1 S3 q0 S1 q1 S2 S3 q2 S3 q3 w w w k h d a w c o m 课后答案网 2 记 S q0 Z q1 U R q2 S X q3 Y U R q4 X S U q5 Y U R Z q6 Z S q7 14 1 从略 2 化简后 S0 和 S1 作为一个状态 S5 和 S6 作为一个状态 状态转换图如图 15 从略 16 从略 1 r 表示的正规式集是 r rr rrr w w w k h d a w c o m 课后答案网 r 表示的正规式集是 r rr rrr r rr rrr rr 表示的正规式集是 r rr rrr r r r rr rrr 所以四者是等价的 2 rs r 表示的正规式集是 rs rsrs rsrsrs r r rsr rsrsr rsrsrsr r sr 表示的正规式集是 r sr srsr srsrsr r rsr rsrsr rsrsrsr 所以两者等价 18 写成方程组 S aT aS 1 B cB c 2 T bT bB 3 所以 B c cT b bc c S a ab bc c G1 S aA B 1 B cC b 2 A abS bB 3 C D 4 D bB d 5 把 4 5 代入 2 得 B c bB d b cbB cd b 得 B cb cd b 代入 3 得 A abS b cb cd b 把它打入 1 得 S a abS b cb cd b cb cd b aabS ab cb cd b cb cd b aab ab cb cd b cb cd b G2 S Aa B 1 A Cc Bb 2 B Bb a 3 C D Bab 4 D d 5 可得 D dB ab C ab ab bA ab ab b c ab b S ab ab b ca ab ba ab ab ab b ca ab ba ab 20 识别此语言的正规式是 S LABEL d d d 从略 21 从略 22 构造 NFA w w w k h d a w c o m 课后答案网 其余从略 23 下面举一个能够识别 1 2 3 10 20 100 的例子 读者可以推而广之 include include include define ON1 define TW 2 define THRE 3 define TE 10 define TWENT 20 define HUNDRE 100 define WHITE9999 upper A Z ONEreturn ON TWOreturn TW THREEreturn THRE TENreturn TE TWENTYreturn TWENT HUNDREDreturn HUNDRE treturn WHITE nreturn0 main int argc char argv int c i 0 char tmp 30 if argc 2 if yyin fopen argv 1 r NULL printf can t open s n argv 1 exit 0 w w w k h d a w c o m 课后答案网 while c yylex 0 switch c case ON c yylex if c 0 goto i 1 label c yylex if c HUNDRE i 100 else i 1 break case TW c yylex c yylex if c HUNDRE i 200 e