第一章词法分析课堂练习题含答案VIP免费

第一章词法分析本章主要掌握下面一些内容。1．词法分析器的作用和接口，用高级语言编写词法分析器等内容，它们与词法分析器的实现有关。（我们没有安排这方面的习题，因为大部分教材上都有这方面的例子）。2．掌握下面涉及的一些概念，它们之间转换的技巧、方法或算法。非形式描述的语言正规式（表示两个方向的转换都要掌握）正规式NFA（非确定的有限自动机）非形式描述的语言NFANFADFA（确定的有限自动机）DFA最简DFA非形式描述的语言DFA（或最简DFA）1.1．叙述正规式(00|11)((01|10)(00|11)(01|10)(00|11))描述的语言。答案该正规式所描述的语言是，所有由偶数个0和偶数个1构成的串。另外，和该正规式等价的正规式有(00|11|((01|10)(00|11)(01|10)))。分析叙述正规式描述的语言并没有一种统一的办法，只能是通过对正规式的具体分析去总结。该正规式的一个重要特点是，它是两个字符一组来考虑的。正规式(00|11)表示的串的长度是偶数，每两个字符一组的话，不是00就是11。再看正规式(01|10)(00|11)(01|10)，它表示的串由01或10开始，中间有若干组00或11，最后出现01或10。这样的串仍然由偶数个0和偶数个1构成，只不过第一组是01或10的话，那么一定还要有一组01或10才能保证它们的偶数性。显然，正规式(01|10)(00|11)(01|10)(00|11)表示的串也仍然是由偶数个0和偶数个1构成。这样，可以判断题目所给的正规式表示的语言的每个句子都是由偶数个0和偶数个1构成。反过来还需要考虑，任何由偶数个0和偶数个1构成的串是否都在这个语言中。这实际上是问，每个这样的串，其结构是否都符合正规式(00|11)((01|10)(00|11)(01|10)(00|11))所做的刻划。我们可以这样叙述由偶数个0和偶数个1构成的串，从左向右，每两个字符一组地考察，它1，由若干个（强调一下，可以是零个）00或11开始（这由正规式(00|11)描述）；2．一旦出现一个01或10，那么经过若干个00或11后，一定会出现一个01或10。这第二个01或10的后面可能还有若干个00或11，一直到串的结束，或者到再次出现01或10为止。如果串没有结束的话，就是重复出现这里所描述的结构（所以这由((01|10)(00|11)(01|10)(00|11))描述）。因此正规式(00|11)((01|10)(00|11)(01|10)(00|11))描述的是偶数个0和偶数个1构成的串。可能会提出一个问题，这样的串是否能用更简单的观点来看待，也就是该语言是否能用更简洁的正规式描述。这是可能的。我们写出这样的正规式，(00|11|((01|10)(00|11)(01|10)))它是基于这样的考虑，满足要求的最简单的串有三种形式（空串除外）：1．002．113．(01|10)(00|11)(01|10)它们任意多次的重复构成的串仍然满足要求。1.2．写出语言“由偶数个0和奇数个1构成的所有0和1的串”的正规定义。答案even_0_even_1(00|11)((01|10)(00|11)(01|10)(00|11))even_0_odd_11even_0_even_1|0(00|11)(01|10)even_0_even_1分析有了上一题的结果，这个问题应该容易解决。首先给上一题的正规式起个名字：even_0_even_1(00|11)((01|10)(00|11)(01|10)(00|11))对于偶数个0和奇数个1构成的串，其第一个字符可能是0或1。1．如果是1，那么剩下的部分一定是偶数个0和偶数个1。2．如果是0，那么经过若干个00或11，一定会出现一个01或10，才能保证0的个数是偶数，1的个数是奇数。若串还没有结束，剩余部分一定是偶数个0和偶数个1。这样，正确的正规定义是：even_0_odd_11even_0_even_1|0(00|11)(01|10)even_0_even_11.3．写出语言“所有相邻数字都不相同的非空数字串”的正规定义。答案no_0-89no_0-7(8|no_0-88)(no_0-88)(no_0-8|)|no_0-8no_0-6(7|no_0-77)(no_0-77)(no_0-7|)|no_0-7no_0-5(6|no_0-66)(no_0-66)(no_0-6|)|no_0-6no_0-4(5|no_0-55)(no_0-55)(no_0-5|)|no_0-5no_0-3(4|no_0-44)(no_0-44)(no_0-4|)|no_0-4no_0-2(3|no_0-33)(no_0-33)(no_0-3|)|no_0-3no_0-1(2|no_0-22)(no_0-22)(no_0-2|)|no_0-2no_0(1|no_0-11)(no_0-11)(no_0-1|)|no_0-1answer(0|no_00)(no_00)(no_0|...