编译原理中的文法及二义性研究.docx

堡里鱼堕尘信息技术编译原理中文法是个非常重要的概念。没有文法形式语言和自动机理论就无法实现描述。而文法的二义性是一种常见的现象有些文法甚至是先天二义性的本文从文法的定义及语法树、文法的二义性、如何消除文法的二义性等个方面进行了分析。一、文法的定义及语法树文法是描述语言的语法结构的形式规则即语法规则。一个上下文无关文法包括四个组成部分一组终结符号一组非终结符一个开始符号以及一组产生式。在程序语言中我们最终感兴趣的是“程序”这个语法范畴而其他的语法范畴都只不过是构造“程序”的一块块砖石。产生式也称为产生规则或简称规则是定义语法范畴的一种书写规则。一个产生式的形式是其中箭头左边的是一个终结符称为产生式的左部符号箭头右边的是终结符号或与非终结符号组成的一符号串称为产生式的右部。形式上定义一个上下文无关文法是一个四元式。其中是一个非空有限集它的每一个元素称为终结符号是一个非空有限集它的每一个元素称为非终结符号。是一个非终结符号称为开始符号是一个产生式有限集合每个产生式形式是咆其中开始符号至少必须在某一产生式的左部出现一次。假定是一个文法是它的开始符号。如果事表示从发经步或若干步可推出则称【是一个句型。仅含终结符号的句型是一个句子。文法所产生的句子的全体是一个语言将它记为。例如终结符号串是文法。的一个句子。是因为有等从开始符号至的一个推导。而、等是文法的句型。潲撇稳固昌器镫四窝团第七一三研究所张志红朱晨光二、文法的二义性如果对于某文法的同一个句子存在两棵不同的语法树则该句子是二义性的。而该文法是二义性文法。这里的二义性是指语法结构上的。如果一个句子具有二义性。那么对这个句子的结构可能有多种“正确”的解释。通常情况下句子的语义要通过其语法结构来定义所以二义性一般是有害的。一般来讲二义性是针对文法而言的。说语言二义性是无意义的。例如考虑表达式下面的文法其产生式如下对于句子存在如下两个最左推导争争木争木木水争宰99争木木由于句型有不同的两棵分析树因此该文法具有二义性。再来分析以下例子在语言中将语句定义为其中代表布尔表达式代表语句。显然。符号串应是述语言中的一个合法语句。但是上述句子却存在两种不同的理解即存在两种不同的最右推导或对应于这两种理解将存在两棵不同的语法树。因此此文法是二义性的。语言中的语句亦有类似的情况。由此可见二义性是一种常见的现象。显然对于编译程序而言我们自然要求它们所处理的语言是用无二义性的文法来定义的。三、如何消除文法的二义性一个文法兼有左递归和右递归是导致其二义性的最常见原因之一。由于同一个语言可能由若干个等价的文法来定义。因此若一个语言由某一文法定万方数据国信息技术郑州大学信息程学院舒畅赵东明东华大学信息科学与技术学院沈今括目前有许多网站的浏览服务器的安全性都不是很高而且一些安全设施也不是很完善尤其在一些个人网站、学校及政府机关的网站中因为在这些部门中往往服务器的软硬件设施都比较陈旧但同时这些部门的网络信息又都相当重要如遇黑客攻击破坏后果将非常严重因此对一些重要数据文件采取更进一步的监控保护措施就显得尤为重要了。传统的安全模式趋向于加强保护资源的保护层采用严格的访问控制、访问审计、数据加密等手段进行保护。但在目前的网络环境下强有力的安全保护层必然会削弱提供用户访问网络服务的能力和灵活性而且在不可避免的网络威胁面前对数据和网络的完整性保护就成为目前解决传统模式缺陷的必然选择。因此对于一个安全的计算机系统来说保证其文件和进程的安伞是保护系统安全的一个重点对文件进行监控是我们保护系统安伞乃至灾情评估的基础所以需要对文件的实时监控技术进行分析和研究也就是通过文件监控来保证数据的完整性。而月前大部分文件监控类的软件都存在着一些大的缺陷例如部分小犁监控软件使用普通应用程序自身的安全性和稳定性都无法得到很好的保证许多监控软件实时性很差算法消耗大苗的机器时日和操作复杂等等因此开发一种安全、方便且高效的文件监控软件平台就显得尤为重要了。一、设计思想首先我们需要分析在现有的软件、硬件条件下特别是当前网络的运营条件下一个人侵者或是入侵程序通常需要调用那些系统调用也就是说至少需要做什么义而是一个二义性文法则往往可对进行改写以期求得另一文法使而是无二义性的。例如把下面文法改写为无二义性现在构造句子有如下两个不同的最左推导一一一一一一一一所以该文法是二义的原因是该文法没有规定结合的顺序现规定左结合的顺序可以改造文法如下聿不过并非所有的二义文法都能通过等价改造来消除其二义性。换言之也就是存在这样的前后文无关语言用来定义该语言的一切文法都是二义性的。通常我们把这样的语言称为先天或同有二义性的语言。任何二义文法都不是一个文法因此也不是或文法。但是某些二义文法是非常重要的。例如文法是一个二义文法。但只要对算符、赋予优先级和结合关系就可以用于描述算术表达式。与文法斗幸卜一相比也有明显的好处。经过分析我们可以看出二义性文法的优缺点优点如需要改变算符的优先级或结合关系无需去改变文法自身。文法的无单一产生式按分析法构造的分析表体积小。缺点二义性文法决不是。文法所以构造的项目集规范族一定会出现动作冲突。这种冲