同济大学编译原理第二章高级语言及其语法描述剖析.ppt

例 非CFL的文法 L={anbncn|n0}的文法 S?aBC|aSBC CB?BC aB?ab bB?bb bC?bc 可以证明不存在CFG G ,使L(G)=L 非CFL结构 在我们使用的程序语言中,有些语言结构并不是总能用上下文无关文法描述的。 例1 L1={wcw|w∈{a,b}+}。aabcaab就是L1的一个句子。这个语言是检查程序中标识符的声明应先于引用的抽象。 ?例2 L2={anbmcndm|n,m≥0}，它是检查过程声明的形参个数和过程引用的参数个数是否一致问题的抽象。 * * * 语境：指理解和实现程序设计语言的环境，包括编译环境和运行环境 * 赋值语句语法的非形式化描述为：赋值语句由一个变量，后随一个符号“=”，再在后面跟一个表达式所构成。 赋值语句的语义为：先对该语句的右部表达式求值，然后把所得结果与语句左部的变量相结合，并取代该变量原有的值。 赋值语句的语用为：赋值语句可用来计算和保存表达式的值。 * 注意这里提到三个概念：a.一个程序只是用一个有限字符集作为字母表；b.词法规则是指单词符号的形成规则。单词符号一般包括：各类型的常数、标识符、基本字、算符和界符等。C.语言的语法规则规定了如何从单词符号形成更大的结构（即语法单位），换言之，语法规则是语法单位的形成规则。一般程序语言的语法单位有：表达式、语句、分程序、函数、过程和程序等。 * 软件发展的三个里程碑：子程序、高级语言、结构化程序设计 自上而下看上述层次结构：顶端是程序本身，他是一个完整的执行单位。一个程序通常是由若干个子程序或分程序组成的，他们常常含有自己的数据（局部名）。子程序或分程序是由于语句组成的。而组成语句的成分是个种类型的表达式。表达式是描述数据运算的基本结构，它通常含有数据引用、算符和函数调用。 自下而上看上述层次结构：我们希望通过对下层成分的了解掌握上层成分，从而掌握整个程序。 在学习编译原理的过程中特别注意：程序语言的每个组成成分都有（抽象的）逻辑和计算机实现两方面的意义。当从数学上考虑每一个组成成分时，我们注重它的逻辑意义，当从计算机这个角度来看时，我们注重他在机内的表示和实现的可能性与效率。 * * 强制式：命令驱动，面向语句 * 辅助程序段可以是子程序、函数段或数据。每程序段由一系列说明语句和执行语句组成。各程序段可以独立编辑。这对模块设计甚为方便。 一个FORTRAN 程序个程序段所定义的各种名字通常是彼此独立的。同一个标识符在不同的程序段中一般都可以代表不同的名字，即代表不同的存储单元，个程序段对它们的引用或赋值是彼此无关的。但是，不同程序段里的同名公用块（Common Block)却代表同一个存储区域。因此，出现在COMMON语句中的名字所代表的单元在其他程序块中也可以引用。所以说，公用区具有全局性。不出现在COMMON中的名字所代表的单元具有局部性。 * Pascal这种嵌套结构中允许同一标识符在不同的子程序段中表示不同的名字。关于名字的作用域的规定是： a.一个在子程序B1中说明的名字X只在B1中有效（局部于B1）。 b.如果B2是B1的一个内层子程序，且B2中对标识符X没有新的说明，则原来的名字X在B2中仍然有效。如果B2对X重新作了说明，那么，B2中对X的任何引用都是指重新说明过的这个X。 * * * * 在多数语言中算术算符和逻辑算符的优先顺序一般规定如下： 乘幂 （ ** 或 ↑ ） 一元负 （ - ） 乘、除 （ * ， /， ÷ ） 加、减 （ + ， - ） 关系符 （ , = , , =, , = ) 非 （ ﹁， not, 或 .NOT. ) 与 （∧， , and 或 .AND. ) 或 （ ∨，∣， or 或 .OR . ) 隐含 （ ? 或 imp ) 等值 （ ≡, ～ 或 equi ) 算符的代数性质（交换率、结合率和分配率）常常可用来优化目标程序的质量。但是必须注意两点： （1） 代数性质引用到什么程度视具体语言的不同而不同。如在ALGOL中把 A*B+C*D 处理成C*D+A*B, 则至少是对ALGOL不够忠实。 （2）数学上成立的代数性质在计算机上未必完全成立。如：(A+B)+C=A+(B+C)在计算机上并不普遍成立。 * 我们知道，每个名字有两方面的特征：一方面它代表一定的存储单元，另一方面它又以该单元的内容作为值。 * * 开始符号:文法产生式中有一个符号S称为开始符 号，它至少要在一条产生式中作为左部出现。例：G(S)={S→Ab,A→a} 终结