编译原理课程项目.pdfVIP

编译原理课程项⽬ 计算机学院 陈寅 2015-03-09 1 简介 本课程为编译原理课程的后序课程。这是⼀门必修课。2012 级的 1 ⾄5 班共 214 ⼈选修了这门课程。课程项⽬可以选择完成以下两个题⽬中的⼀个。课程项 ⽬可以独⽴完成，也可以⾃由组合为不超过3 个⼈的⼩组。如果⼩组由 3 ⼈组 成，则必须完成可选内容。课程的成绩根据提交的⽂档和代码评定。 2 一阶谓词公式的实例化 我们考虑⼀个包含⽐较运算符但是不包含函数符号的⼀阶语⾔。谓词⽤ ⼩写字母所组成的字符串表⽰，例如 等。变量⽤⼤写字母开始的 字符串表⽰，例如 等。常量⽤正整数或者字符串表⽰，例如 ”” ”” 等。常量之间可以⽐较⼤⼩。逻辑运算符包括 , 等。⽐较运算符包括 ̸ 。⼀阶逻辑逻辑的公式，⾃由变元，闭 公式，公式的可满⾜性等概念可参看离散数学的教材。 2.1 例子 给定⼀个⼀阶公式和它的论域，这个公式的可满⾜性可以等价为⼀个对应的 命题公式的可满⾜性。下⾯是⼀个例⼦。 设公式集 包含如下公式： (1) ̸ (2) (3) 其中 是谓词， 是变量， 和 是常量。如果⽤ 中出现的所有常量 的集合 做为论域，则 可实例化为如下的命题公式集 ： (4) (5) (6) (7) ̸ ̸ (8) ̸ ̸ (9) 1 其中 (1) 通过消去量词后变为 (4-7)，(2) 通过消去量词后变为 (8,9)。 可以进 ⼀步的化简为如下的公式集′ (10) (11) (12) (13) 因为： (S1) 根据 (3)， 为真，因此 (4) 和 (5)