发布时间 : 星期二 文章哈工大编译原理习题及答案更新完毕开始阅读68851b05bed5b9f3f90f1ca1
[]a[]bS0[]S2[]S1S1[]S3[]S1S2[]S0[]S4S3[]S0[]S0S4[]S5[]S4S5[]S4[]S0 试找出一个长度最小的输入串，使得：
(1) 在识别此输入串的过程中，每一状态至少经历一次； (2) 每一状态转换至少经历一次。 3.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) 用自然语言分别描述它们所识别的输入串的特征。 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 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′产生。
3.11分别构造将左线性文法转换为右线性文法以及将右线性文法转换为左线性文法的算法。
3.12将如题图312所示的NFA确定化和最小化。 题图312
3.13将如题图313所示的具有ε动作的NFA确定化。 题图313
3.14将如题图314所示的有限自动机最小化。
3.15试用一种高级语言分别写出将NFA确定化以及将DFA最小化的算法。 3.16构造一产生FORTRAN语言COMMON语句的3型文法 (假定分别用λ和μ代表标识符和整常数，它们都是终结符号，且假定数组的维数不加限定)，构造相应的DFA，并写出描述COMMON语句的正规式。
3.17设r,s等为任意的正规式，试证明下列的关系式成立： (1) r*=(ε|r)*=ε|rr*=(r*)* (2) (rs)*r=r(sr)*
(3) (r|s)*=(r*s*)*=(r*|s*)*
3.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
3.19对于习题310所给的文法G1和G2，试分别用正规式描述它们所产生的语言。 3.20设有如下的文法G［〈标号说明〉］： 〈标号说明〉→′LABEL′〈标号表〉 〈标号表〉→d〈标号段〉
〈标号段〉→d〈标号段〉|,〈标号〉|； 〈标号〉→d〈标号段〉
其中′LABEL′,′d′,′,′,′;′等为终结符号。 (1) 试求出描述此文法所产生语言的正规式； (2) 构造识别此语言的具有最少状态的DFA。
3.21求出描述习题37所给有限自动机所识别语言的正规式。 3.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)*
3.23试设计一个识别器，它识别由下列英语单词： ONE, TWO, THREE, ?， NINE， TEN，
ELEVEN， TWELVE， THIRTEEN， ?， NINETEEN， TWENTY， THIRTY， FORTY， ?， NINETY， HUNDRED
所表示的从1到999间的任何整数 (各单词间用空格分隔，如THREE HUNDRED FIFTY SIX)，并将它们翻译为相应的阿拉伯数字 (如356)作为输出。 3.24设有辅助定义式 D0=a|b D1=D0D0 D2=D1D1 ?
Dn=Dn-1Dn-1 试回答如下问题：
(1) 由Dn所表述的正规集是什么?
(2) 如果将Dn中所出现的Dn-1用前面已定义的辅助定义式反复进行替换，则可最终将Dn化为Σ={a,b}上的正规式，此正规式有多长? (3) 用来识别Dn的DFA至多需要几个状态?
3.25试将LEX中的“动作子程序”Ai的功能加以扩充，使之可用来生成文本编辑程序。
3.26指出下列LEX正规式所匹配的字符串： (1) \［^{］*\
(2) ^［^a-z］［A-Z］［0-9］$ (3) ［^0-9］|［＼r＼n］
(4) ＼′(［^′＼n］|＼′＼′)+＼′ (5) ＼\［^\＼n］|＼＼［\＼n］)*＼\
3.27写出一个LEX正规式，它能匹配C语言的所有无符号整数 (例如：OX89ab，0123，45，′Z′,′＼t′,′＼xab′,′＼012′,等等)。 3.28写出一个LEX正规式，它能匹配C语言的标识符。
3.29编写一个LEX源程序，它将一个正文文件中的全部小写字母均换为大写字母，并将其中的制表字符、空白字符序列均用单个空格字符进行替换 (提示： 在语义动作中使用全程变量yytext)。
3.30编写一个LEX源程序，它能统计一个PASCAL程序中所含用户定义之标识符个数，并能找出最长标识符中的字符个数 (提示： 使用全程变量yytext及yyleng)。 上 机 实 习 题
对于如下文法所定义的PASCAL语言子集，试编写并上机调试一个词法分析程序： 〈程序〉→〈变量说明〉BEGIN〈语句表〉END.
〈变量说明〉→VAR〈变量表〉：〈类型〉；|〈空〉 〈变量表〉→〈变量表〉，〈变量〉|〈变量〉 〈类型〉→INTEGER
〈语句表〉→〈语句表〉；〈语句〉|〈语句〉
〈语句〉→〈赋值语句〉|〈条件语句〉|〈WHILE语句〉|〈复合语句〉|〈过程定义〉 〈赋值语句〉→〈变量〉∶=〈算术表达式〉
〈条件语句〉→IF〈关系表达式〉THEN〈语句〉ELSE〈语句〉 〈WHILE语句〉→WHILE〈关系表达式〉DO〈语句〉 〈复合语句〉→BEGIN〈语句表〉END
〈过程定义〉→PROCEDURE〈标识符〉〈参数表〉； BEGIN〈语句表〉END
〈参数表〉→(〈标识符表〉)|〈空〉
〈标识符表〉→〈标识符表〉，〈标识符〉|〈标识符〉 〈算术表达式〉→〈算术表达式〉+〈项〉|〈项〉 〈项〉→〈项〉*〈初等量〉|〈初等量〉
〈初等量〉→(〈算术表达式〉)|〈变量〉|〈无符号数〉 〈关系表达式〉→〈算术表达式〉〈关系符〉〈算术表达式〉 〈变量〉→〈标识符〉
〈标识符〉→〈标识符〉〈字母〉|〈标识符〉〈数学〉|〈字母〉 〈无符号数〉→〈无符号数〉〈数字〉|〈数字〉 〈关系符〉→=|＜|＜=|＞|＞=|＜＞ 〈字母〉→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源程序，并上机进行处理。