编译原理第二章高级语言及其语法描述

《编译原理第二章高级语言及其语法描述》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章高级语言及其语法描述2.1程序语言的定义(描述)2.2高级语言的一般特性2.3程序语言的语法描述2.1程序语言的定义语法：语言的语法是指这样的一组规则，用它可以产生和形成一个合式的程序。例如：变量的标示符要以非数字开头…语法分为词法规则和语法规则。词法规则：指单词符号的形成规则，单词符号包括：各种类型常数、标示符、算符和界符等。词法分析工具：正规式和有限自动机理论。语法规则：是语法单位的形成规则。语法单位包括：表达式、语句、子程序、函数等。语法规则描述工具：上、下文无关文法。语义：是指这样的规则，使用它可以定义一个程序的意义

2、。语义描述的方法：属性文法的语法制导翻译方法。该方法接近形式化方法。相同语句不同含义的例子：Z=X+Y可以表示整数相加和实数相加等不同的语义。编译程序就是要从基本的单词符号和语法单位分析程序的语义。2.2高级语言的一般特性高级语言分类：过程式语言-命令驱动、面向语句，如C语言等。函数式语言-从功能出发构造函数，如LISP等。基于规则的语言-检查一定的条件，当他满足，则执行适当的动作，如Prolog语言。面向对象的语言-支持封装、继承和多态性等。2.3程序语言的语法描述基本概念：Σ：是一个有穷字母表，它的每个元素称为一个符号。Σ上的

3、字（符号串）：是指由Σ中的符号所构成的一个有穷序列。ε：不包含任何符号的序列称为空字。Σ＊：表示Σ上所有字的集合，其中包括空字ε。φ:不包含任何元素的集合φ={}集合运算：集合的积运算：UV={αβ

4、α∈U&β∈V}Vn=VV…V：其中V0={ε}集合的或运算：U∪V={α

5、α∈UORα∈V}集合的闭包运算：V＊=V0∪V1∪V2∪V3∪…集合的正规闭包：V+=VV＊2.3.1上下文无关文法文法：描述语言的语法结构的形式规则。特点：这些规则必须是准确的，易于理解的，而且，应当有相当强的描述能力，足以描述各种不同的结构。例如：<句子

6、>-><主语><谓语><间接宾语><直接宾语>上、下文无关文法：它所定义的语法范畴是完全独立于这种范畴可能出现的环境的。一个上、下文无关文法G包括四个组成部分：一组终结符号一组非终结符号一个开始符号一组产生式终结符号：是组成语言的基本符号，在程序语言中就是以前屡次提到的单词符号，如基本字、标识符、常数、算符和界符等。非终结符号：用来代表语法范畴。如：语句A、表达式B等。开始符号：是一个特殊的非终结符号，它代表所定义的语言中我们最终感兴趣的语法范畴，这个语法范畴通常称为“句子”或是“程序”。产生式：是定义语法范畴的一种书写规则。一个

7、产生式的形式是A→α或A::=αA：是非终结符号α：是由终结符号或与非终结符号组成的一个符号串。例如：一个简单的算术表达式文法：E→iE→E+EE→E*E(2-1)E→(E)终结符号：i非终结符号：E开始符号：算术表达式产生式：(2-1)形式化定义：一个上下文无关文法是一个四元式（VT,VN,S,Γ）VT是一个非空有限集，它的每个元素称为终结符号；VN是一个非空有限集，它的每个元素称为非终结符号，VT∩VN=ф；S是一个非终结符号，称为开始符号；S∈VN。Γ是一个产生式集合（有限），每个产生式的形式是P→а。其中，P∈VN，а∈（

8、VT∪VN）＊。开始符号S至少必须在某个产生式的左部出现一次。P→а1

9、а2

10、…

11、аn。其中，аi称为是P的一个候选式。→读作定义，直竖读为“或”,它是元语言符号。上、下文无关文法语言：从文法的开始符号出发，反复使用产生式，对非终结符施行替换和展开。例子：求解文法2-1的语言？E(E)(E+E)(i+E)(i+i)推导：称A直接推出，即：A，仅当A→是产生式，且、(VTVN)*如果α1α1…αn，则称序列是一个推导；称α1可推出αn；表示经一步或若干步可推出表示经0步或若干步推出假定G是

12、一个文法，S是它的开始符号。如果有:则称α是一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为L(G)。L(G)={α

13、S*α&α∈VT*}最左推导：任何一步α=>β都是对α中的最左非终结符进行替换的。最右推导：任何一步α=>β都是对α中的最右非终结符进行替换的。例2.1、例2.2、例2.32.3.2语法分析树与二义性语法树定义：句型推导的树形表示称为语法树。EEE(根)()i*+EEEii文法二义性：文法存在某个句子对应两颗不同的语法树，则称这个文法是二义性文法。例如：EEE(根)()i*+E

14、EEiiEEE(根)()i+*EEEii二义性文法特点：文法的二义性和语言的二义性不同，不同的文法可以有相同的语言，即L(G)=L(G*)，其中G是二义性文法。文法的二义性证明是NP-Hard问题。上、下文无关文法的限制：文法中不含任何下面形式的产