姓名： 1 of4 麻省理工学院 电气工程与计算机科学 6.035,1999年秋 测试1 9月20日，星期一 1)正规表达式 如果下面的描述定义了一种正规语言，就请写出对应的正规表达式。否则简要说明该语言是 非常规的。注意，只有优雅并且简洁的解决方法才会得到满分3分。 I所有01字符串都表达了权重为2的二进制数。 Ⅱ所有的二-十进制编码数(BCD),BCD数就是十进制数的二进制表达，其中每个十进制 数用4bit编码来表达其二进制值。如2509的BCD编码就为0010010100001001。 Ⅲ在所有的01字符串的每个0处，紧接在0后面的连续1的值大于在这个0之前连续1的 值。 IV没有超过3个连续1的01字符串。 V有一个0偶检验位和1偶校验位的01字符串。 15 10 15 40 2)语法 语言的语法是很简单的，如下所示： ■单个基元是符合Scheme语言的字符串。 ■组合也是字符串。组合意为在一对匹配的圆括号里面的一系列基元或者组 合的合并。 少数合法的iScheme程序示例如下： 82 (+823) (func()(+34)5) 语言的符号有数字、关键字、左括号或“(”和右括号或“)
姓名： 1 of 4 麻省理工学院 电气工程与计算机科学 6.035，1999 年秋 测试 1 9 月 20 日，星期一 1）正规表达式 如果下面的描述定义了一种正规语言，就请写出对应的正规表达式。否则简要说明该语言是 非常规的。注意，只有优雅并且简洁的解决方法才会得到满分 3 分。 Ⅰ所有 0 1 字符串都表达了权重为 2 的二进制数。 Ⅱ所有的二-十进制编码数（BCD），BCD 数就是十进制数的二进制表达，其中每个十进制 数用 4bit 编码来表达其二进制值。如 2509 的 BCD 编码就为 0010010100001001。 Ⅲ在所有的 01 字符串的每个 0 处，紧接在 0 后面的连续 1 的值大于在这个 0 之前连续 1 的 值。 Ⅳ没有超过 3 个连续 1 的 01 字符串。 Ⅴ有一个 0 偶检验位和 1 偶校验位的 01 字符串。 2）语法 语言的语法是很简单的，如下所示： . ■单个基元是符合ìScheme语言的字符串。 . ■组合也是字符串。组合意为在一对匹配的圆括号里面的一系列基元或者组 合的合并。 . 少数合法的ìScheme程序示例如下： . 82 . （＋823） . （func（）（＋34）5） . 语言的符号有数字、关键字、左括号或“（”和右括号或“）
姓名： 2 of4 用iScheme写一段程序。 。 3)语法分析器架构 给定下列语法，中止符（，)和term,非中止符S,E和L。 ES (1) E term (2) E (L) (3) L a (4) L EL (5) I如果中止符tem接受了字符X,写出符合语法的3个字符串。 a) b) c) Ⅱ什么是LR(0)分析法的第三步结果 Ⅱ下面是LR(O)的状态图和以上给定语法的语法分析表。 但是缺失状态7和5的信息。 a)通过添加主题和创造带有卷标的外部边缘来填补状态图。 b)在语法分析表重填入合适的条目
姓名： 2 of 4 . 用ìScheme写一段程序。 . 3）语法分析器架构 . 给定下列语法，中止符（，）和term，非中止符S,E和L。 S E $ (1) E term (2) E ( L ) (3) L å (4) L E L (5) Ⅰ如果中止符term接受了字符X，写出符合语法的3个字符串。 a) b) c) Ⅱ什么是LR（0）分析法的第三步结果 Ⅲ下面是LR(0)的状态图和以上给定语法的语法分析表。 但是缺失状态7和5的信息。 a)通过添加主题和创造带有卷标的外部边缘来填补状态图。 b)在语法分析表重填入合适的条目
姓名： 3 of 4 S1 s2 E S口□ES S口E口s E口口tern E口口(L) term S3 E口term口 S4 term E口口L) EC口term S5 E口（口L) L口口 E L口口EL L S6 E口(L口) s7 S8 L口EL口 ( ) term $ E L 1 s4 出错 s3 出错 转到s2 2 出错 出错 出错 接受 3 降到2 降到2 降到2 降到2 4 S4 降到4 S3 降到4 转到s5 转到s6 降到4 降到4 5 6 出错 出错 出错 7 8 降到5 降到5 降到5 降到5
姓名： 3 of 4 （ ） term $ E L 1 s4 出错 s3 出错 转到s2 2 出错 出错 出错 接受 3 降到2 降到2 降到2 降到2 4 S4 降到4 降到4 S3 降到4 降到4 转到s5 转到s6 5 6 出错 出错 出错 7 8 降到5 降到5 降到5 降到5
姓名： 4 of4
姓名： 4 of 4