编译原理课程项目

编译原理课程项?

计算机学院陈寅

2015-03-09

1简介

本课程为编译原理课程的后序课程。这是?门必修课。2012级的1?5班共214?选修了这门课程。课程项?可以选择完成以下两个题?中的?个。课程项?可以独?完成，也可以?由组合为不超过3个?的?组。如果?组由3?组成，则必须完成可选内容。课程的成绩根据提交的?档和代码评定。2一阶谓词公式的实例化

我们考虑?个包含?较运算符但是不包含函数符号的?阶语?。谓词??写字母所组成的字符串表?，例如p,q,edge等。变量??写字母开始的字符串表?，例如X,Y,X1,Next等。常量?正整数或者字符串表?，例如1,123,35,”a”,”red”等。常量之间可以?较??。逻辑运算符包括¬,∧,∨,→,?,?,?等。?较运算符包括=,<,>,≤,≥,=。?阶逻辑逻辑的公式，?由变元，闭公式，公式的可满?性等概念可参看离散数学的教材。

2.1例子

给定?个?阶公式和它的论域，这个公式的可满?性可以等价为?个对应的命题公式的可满?性。下?是?个例?。

设公式集Γ包含如下公式：

?X?Y(p(X)∨¬q(Y)∨r(Y))

?X(p(X)→?Y(q(Y)∧X=Y))

r(1)∧¬r(2)(1)(2)(3)

其中p,q,r是谓词，X,Y是变量，1和2是常量。如果?Γ中出现的所有常量的集合D={1,2}做为论域，则Γ可实例化为如下的命题公式集ΓD：

p(1)∨q(1)∨r(1)

p(2)∨q(1)∨r(1)

p(1)∨q(2)∨r(2)

p(2)∨q(2)∨r(2)

p(1)→((q(1)∧1=1)∨(q(2)∧1=2))

p(2)→((q(1)∧2=1)∨(q(2)∧2=2))

r(1)∧¬r(2)

1(4)(5)(6)(7)(8)(9)

其中(1)通过消去量词后变为(4-7)，(2)通过消去量词后变为(8,9)。ΓD可以进?步的化简为如下的公式集Γ′D

p(1)∨q(2)

p(2)∨q(2)

p(1)→q(2)

p(2)→q(1)

r(1)∧¬r(2)

因为：

(S1)根据(3)，r(1)为真，因此(4)和(5)是永真式，可以删除；

(S2)根据(3)，r(2)为假，因此(6)和(7)可化简为(10)和(11)；

(S3)根据常量之间?较运算的真假，可以将(8)和(9)可化简为(12)和(13)(10)(11)(12)(13)

2.2问题的描述

实例化：输??个?阶闭公式集，以这个公式集中出现的常量的集合为论域，将这个?阶公式集转化为和它等价的命题公式集。

(A1)输?的公式集??本?件保存。设计?个语?可以表?上述的?阶公式集，

给出这个语?的词法和语法；

(A2)对输?的?件进?语法分析，定义相应的数据结构保存这个公式集和其中

出现的常量。定义相应的语法树，并且可以输出语法分析的结果。当出现可能的输?错误时，可以指出出错的位置和可能的错误原因；

(A3)将这个公式集实例化并化简（?(S1-S3)的?式），将结果以?本的形式输

出。

(A4)（选做）判断输出的命题逻辑公式集是否是可满?的，如果是则给出?个模

型。利?这个系统解决?些实际的问题。

3进一步的讨论

?阶公式的实例化有着?泛的应?前景，同时也存在很多值得研究的问题。如何?效的实现?阶公式的实例化，?直都有很多的研究1。

对于选做的(A4)，标准的做法是将实例化后的命题公式保存为CNF格式2，然后?已有的SAT求解器加以求解即可3。

例如GroundingwithBoundsJohanWittocx,MaartenMariën,MarcDenecker,AAAI,20082http://logic.pdmi.ras.ru/~basolver/dimacs.html

3可参看：http://wendang.chazidian.com/essays/minisat-user-guide.html1

2

4

4.1比特大战游戏简介

这个游戏来源于《?私的基因》4。?个N回合的?特?战由A和B两?进?，每个回合A和B可以选择0（背叛）或1（合作），共进?N个回合。如果第n(1≤n≤N)个回合A和B的选择分别为An和Bn，则他们在这个回合的得分SA(n)和SB(n)由下表决定：nABABnABABnnA和B的总分为N个回合各?得分的和。

4.2游戏的策略

对于N个回合的?特?战，每回合的得分可能是0,1,5，因此总分总是在0和5?N之间。双?不同的策略可能导致不同的得分。以下是?些可能的策略：(T1)永远合作，每次都选择1；

(T2)随机，每次以某个概率随机选择1，否则选择0；

(T3)针锋相对，第?次选择1，以后每次都选择对?的上?次选择；

(T4)老实人探测器，基本上和“针锋相对”?样，只是会随机的选择?次0；(T5)永不原谅，?直选择1，?旦对?选择0，则?直选择0

这些策略可以?如下的算法描述：

T1永远合作

StategyT1://T1表?策略的名字

return1;

T2随机

StategyT2://以0.75的概率返回1

i=RANDOM(3);//随机函数，RANDOM(k)以等概率返回0到k之间的?个整数if(i==3)

return0;

else

return1;

T3针锋相对

4道?斯（英）著，卢允中等译，中信出版社

3

StategyT3:

//CUR表?当前的回合数

//A[1..N]和B[1..N]是两个预定义的数组分别保存??和对?的每次选择//在第CUR个回合，可以访问数组中的前CUR-1个元素

if(CUR==1)

return1;

else

returnB[CUR-1]；

T4老实人探测器

StategyT4:

if(CUR==1)

return1;

else{

i=RANDOM(9);

if(i==9)

return0

else

returnB[CUR-1]；

}

T5永不原谅

StategyT5:

i=1；

k=1;

while((k<CUR)&&(i==1)){

if(B[k]==0)

i=0;

k=k+1;

}

returni;

4.3问题的描述

(B1)设计?种程序设计语?可以?来描述?特?战的策略。这个语?应该?少

可以描述上述T1-T5的策略；

(B2)实现对这个语?的语法分析。定义相应的语法树，并且可以输出语法分析

的结果。当出现可能的输?错误时，可以指出出错的位置和可能的错误原因；

(B3)实现?个程序：?户可以输?若?的策略，每个策略保存为?个?本?件，

模拟这些策略两两之间的N回合（例如，n=200）的?特?战，并以所有对战得分的总和为这些策略排序；

(B4)（选做）实现?个?上的?特?战对战平台。

4

4.4进一步的讨论

有关?特?战的更多有趣内容可以参看《?私的基因》的第12章。以此为基础可以进?步的发现更多的游戏?式。同时?次为平台，通过计算机模拟也可以产?很多有关博弈论的深?的课题。

5

5.1相关事项邮箱和QQ群

?QQ群：101303485“编译原理课程项?”，请在加?群之后将名字改为“学号后4位+姓名”；

?邮箱地址：csscnu@http://wendang.chazidian.com，请把课程有关的?档和代码都发送到这个邮箱。请使?普通附件发送，不要使?超?附件发送。

5.2课程的安排02

03

06

1403/1503/2204/12（1-3班）06/07（4,5班）课程项?介绍各班学委提交分组名单项?计划：1分组及分?

2计划使?的开发平台和?具

3词法和语法设计

4系统设计概要

说明?前的进度

1?组成员?作量的百分?

2系统设计?档

3简要的?户使?说明

4系统的源代码

5编译后的可执??件242708/16（4,5班）09/06（4,5班）

5