1、中华人民共和国国家标准程序设计语言发布实施中华人民共和国电子工业部发布中华人民共和国国家标准程序设计语言中华人民共和国电子工业部批准实施本标准等同采用国际标准程序设计语言范围和概貌范围本标准定义计算机程序设计语言它将作为具有权威性的参考文件而不是简单的入门介绍定义通过规定一个翻译和解释程序的概念机器来完成条简要介绍了语言中所包含的语句和数据类型本标准的结构与使用方法以及定义语言的方法条描述本标准中的概念机器与实际实现之间的关系条给出了所用到的表示法的详细说明从条开始包括第章至第章是定义的主体定义的非形式化指南提要一个程序由一组书写成一系列语句的过程组成在程序翻译过程中可以使用构件并入其他来源的
2、正文的所有语句类型分组综述如下分组的原则是便于了解整个语言的概貌并与本标准的组织有关结构类过程语句入口语句开始语句执行语句结束语句申述类申述语句默契语句格式语句流程控制类调用语句返回语句如果语句转向语句空语句停止语句异常处理语句变状态语句置状态语句中断处理存储类分配语句释放语句赋值语句输入输出类打开语句关闭语句取语句送语句流式输入输出读语句写语句定位语句重写语句删除语句记录型输入输出下列类型的数据可用名字来申述数据可以是单值的也可以是数组或结构形式的聚集算术型字符型或形象二进位型区域型入口型文卷型格式型标号型位移型指针型值可通过使用一组专门的运算符和内部函数及用户定义的过程书写的表达式来计算大
3、部分内部函数既适用于单值又适用于聚集值用户定义的过程也可运算和返回聚集值或单值数据本定义的形式概念机器是一个处理器它具有一组施加于存放在其存储器内信息的操作以算法形式规定的这些操作可以看作是一单个算法即实现整个翻译和解释处理的定义程序算法的组成部分存储器内的信息均以树结构的形式存放定义算法操作如下表示外部过程即不被任何其他过程所包含的过程的符号序列先由一个翻译器处理处理过程包括系统地分析变换和证实每一个外部过程分析首先使用称为具体语法的文法来产生以树结构表示的外部过程的具体形式具体形式又被变换为抽象形式抽象形式是一棵满足抽象语法的树抽象语法设计得更便于解释然后对抽象形式作进一步的证实接着由解释
4、器进行程序在应用于给定初始数据集时的语义处理数据集是机器存储器的一部分是满足机器状态语法的树正是数据集的改变序列构成了所定义的语义除翻译和解释所有按定义有效的程序外机器还检测有无对于与翻译和解释过程中所执行的算法中的词汇必须或必须不不得有关条文的违反将这种违反称为非标准标准与某个具体实现之间的关系在条中描述定义方法的轮廓如下把抽象机看成下列形式也是有帮助的翻译器和解释器均可在该抽象机上运行从机外来的输入出现在翻译器和解释器的初始化阶段在解释过程中数据集可以改变然而抽象机未定义任何输出因为按照本定义的意图数据集被作为机器存储器的一部分即在需要时是联机的章条结构一览表第章所叙述的操作用于驱动翻译器
5、和解释器翻译器的全部操作包含在第章中使用第章和第章所述的语法解释器的操作由第章至第章中的全部操作组成在第章所述的初始化后有关的操作将根据须解释的语句类型分别在第章中叙述所有上述章节在需要时均将使用第章所述的操作每章的条款按逻辑组织可参考目录以了解章节结构的概貌推荐读者先完整地阅读并仔细理解第章随后可以系统地阅读整个标准也可以利用对整体结构的了解和合理地使用索引在本标准中查找针对某一专门问题的答案在此对每一章都举一个本标准可解答的样本问题为例子以解释后一种用法第章包含具体语法的定义具体语法由以具体树形式描述构件有效形式的规则组成它允许某些构件在语法上认为正确但无实际意义从这个意义上说具体语法是容
6、错的问题语句是否正确答案首先应检查语句有无语法错误查取语句的索引项可知它属于中级语法研究规则和揭示格式逗号分隔的输入目标表执行规格需外加一对括号以避免本例中固有的二义性取决于要把最后一个输入值赋于或正确的格式应为或第章包含抽象语法的定义抽象语法描述的许多部分与具体语法中的对应部分类似抽象语法中的名字选择也与具体语法中的相应名字相似以尽可能使两个语法之间的关系更为明显问题读语句的键去向选择是否可以指定以某变量的子串为键答案关于键去向选择的具体语法只规定必须指定引用然而抽象语法说明了在翻译器处理完全部申述后的程序形式并可将每个引用与适当的申述结合使差别更为细微有关键去向选择的规则中包含目标引用标量
7、与字符规则说明这允许一个伪变量引用例如子串伪变量加括号的限制标量与字符表示它必须是一个字符值的单个目标不得为数组或结构使用索引检索翻译器和解释器未发现进一步的限制因而答案是可以但该子串必须是字符型的标量第章定义了翻译器翻译器将每一个独立的程序部分外部过程从所提交的字符串形式翻译为树形式并添加到程序树中这个处理过程包括对每一外部过程使用具体语法进行分析获得一棵具体树插入遗漏的任选项以将该具体树的属性集补完整然后将该具体树转换为抽象树最后证实整个程序一旦构造完成抽象树不再修改问题语句中隐含哪一个文卷答案初看起来这似乎是有关送语句的一个语义问题然而抽象语法表明在送文卷中必须出现一个文卷选择这意味着若
8、在具体形式中缺省了该文卷选择则只要语句是有效的翻译器将补上一个文卷选择事实上在对输入进行语法分析后翻译器立即以各种方式将具体过程补完整其中方式之一就是在送语句中插入的等价物补全任选项操作中的步骤见第条必须由翻译器早期进行处理的原因是若本例中的语句不在一个已有的对的申述的作用域内它将导致一个对名字的按上下文的申述为了正确解决引用问题必须在执行前将所有申述补完整第章包含机器状态语法的定义机器状态树的初始化和解释处理的开始问题程序中执行的第一个过程是否可以带有从外界传递来的变元答案关于执行的初始化参考第和第条在解释阶段操作步骤条中从定义外获取一个入口值它指示程序中将被激活的第一个过程条文中的限制词不
9、得说明本标准对一个其入口点是由含参数名表的入口值所指示的程序并未规定任何意义见条中对必须的定义另外在解释操作的步骤条中用于激活第一个过程的是仅含一个入口值而不是一个已建立的变元表的求值后的入口引用见第条的产生式规则因此对第一个过程传递变元将是超出本标准所定义的语言范围的一种扩展第章描述了影响程序中分程序由引导的语句组和语句控制流程的解释操作正常的控制流由执行分程序中一系列可执行的程序段构成第六章也定义了调用参数和变元的匹配结果的返回和由中断引起的异常控制流程问题是否允许改变未执行过异常处理语句的条件答案这是一个有关中断处理的语义问题条的执行变状态语句操作在当前已建立的异常处理程序单位表中有合适
10、的成员时删除该成员否则按正常顺序将控制传递给下一语句由于执行异常处理语句仅在这类表中添加已建立的异常处理程序单位显然执行变状态语句与是否执行过添加动作无关答案是允许且对中断处理机制无影响第章定义了存储区的使用包括存储区的分配释放和初始化变量与命名常量的引用还定义了赋值语句聚集赋值和伪变量问题语句是否能在分配时使的五个元素均置为零答案存储区的分配与初始化在第章处理条的初始化数组操作在当时重复迭代步骤由于本例中等于见步骤的初值是且在步骤中增故只进行一次迭代因此上述语句只将第一个元素初始化为零第章处理外部媒体与内部存储区间的数据传输包括文卷的打开和关闭流式和记录型传输以及可应用于输入输出操作的中断问
11、题语句序列是否有效答案尽管大部分申述结构在抽象语法中是明显的且由翻译器检验但文卷属性例外有可能直到执行打开文卷操作时文卷属性仍不完整因此在执行阶段也还需要检查文卷属性组合的有效性条的打开操作表明打印在步骤中隐含流式且同时为流式与记录型会导致打开文卷操作失败因此若执行打开语句打开文卷时会导致标志文卷未定义状态见条中执行单项打开要求操作的步骤第章描述表达式求值表达式求值过程中可能出现的数据类型转换和的内部函数问题能否将结构与数组相加答案第章的表达式求值从考虑聚集型操作数的一般处理开始条的相容性定义引导我们查阅情况得到答案数组的一个元素必须与给定结构相容再次应用相容性检验得出结论如数组的一个元素是标
12、量情况或相容的结构情况和进一步递归则可以相加元语言导论在进入条更严格的定义之前先非形式化地讨论一下元语言的主要特色树的概念定义涉及三类不同的树具体语法分析树抽象正文树和机器状态树而使用了统一的树概念本标准中的树是每一结点均加标号例如过程的有向图任一结点的子树均是有序的尽管次序在许多情况下并无意义但有些场合需要例如在具体语法分析和表中都用到次序在设计时经权衡认为采用简单的统一形式比将有次序与无次序的情况明显地加以区别更具优点而且每一结点均隐含地有一个唯一的名字需要时可用它来表记该结点树的副本具有与正本相同的有序结构和标号但使用新的唯一名指示其结点两棵树除结点的唯一名外均相同则称为等价唯一名也相同
13、的等价树称为同一结点的显式标号可以是语法上的分类名也可以是某种其他类型的值例如整数或指示符即与某个结点隐式相关的唯一名的副本因此一个单值可作为仅有一个以该值为标号的根结点的退化树处理元语言中引用的数据对象均统一地作为树处理关于树的有关术语的定义从由一个结点称为根结点和一个有可能是空的该结点所直接所含的树的有序集合所组成的树着手若树直接包含在树中或直接包含在由所包含的某棵树中则称包含在中或为所包含当且仅当包含在中且不为所包含的根结点等于或的根结点的任何树所包含时称简单包含在中或简单包含例如若称一个表达式简单包含在表示程序中某个语句的树中指的是完全的表达式树而不是在以表达式为根的树中某个低层次的也
14、以表达式为根的子表达式由于简单包含是常用的概念使用任何形式的不含动词包含或名词成分的所有格短语时均隐含简单包含例如若具有含一个表达式意为根结点标号为表达式的树的表达式或它的表达式等上述术语使得对树可执行三类基本操作即检测树是否存在或其子树的类型选择其中的子树以及构造或修改树然而若用下列文字叙述构造根结点有两棵直接子树其中第一棵子树是它有直接子树和第二棵子树是这里是某棵树的名字意味着在构造新树时要复制的一个副本是相当费事的因此可以缩写为缩排有助于阅读大型树结构但不是必要的所构造的树的结尾部分的分号可用圆点代替语法从考虑特定的树开始到各类树我们将遇到由以稍加扩展的巴科斯诺尔范式表示的产生式规则所构
15、成的文法对这些规则的解释是它们描述了由文法所描述的各类树的结构仅当按传统的语法使用这些规则时树的终极结点的序列才获得特别的重要意义即终极结点的序列是代表了该语言中表达方式的字符序列我们以构造符合下列形式规则的树为例来作说明表元语言中的语法规则十分类似于用它所定义的语言中的语句即元语言规则本身也有语法结构必须得到证实和正确的解释在此先不给出元语言的形式文法仅如实描述规则是如何解释的以避免循环或回归定义上述规则指定任何标号为的结点必须具有如规则右边所描述形式的子树共有三类元语言运算符连接在规则中以并列表示置换和选择连接的优先级最高选择的优先级最低带括号的表达式作为单操作数处理按规则构造树的第一阶段
16、是将语法表达式划分为由最低优先级的号分隔的子表达式并选择这些子表达式中的一个假设不管只有的子表达式第二步按运算符划分另一个子表达式并使用置换使这些划分的顺序逆转得到表方括号表示其中的内容可以省略在此我们采取省略其内容的做法花括号内的语法表达式必须按刚才所描述的方法解释选择其中的表则可得到下述树表用黑体字表示它总是标识所讨论的文法中的终极结点即它不出现在任何产生式的左边按照习惯表表示它包含一个或多个类型为的直接子树接着我们可对每一子树分别应用的规则当树的每一终极结点都是终极符类型或产生空子树集的类型时树的构造工作完成算法概念抽象机的操作由算法定义可类比为支持计算机操作码的逻辑或微码这些操作检测或
17、改变机器状态即抽象机的内存机器状态中包含直接或间接影响语义的全部信息包括某种形式的程序本身元括号和用在机器状态结点的定义中属于抽象程序文法的结点除外后者用和标识便于读者区别一个机器操作由一系列步骤或编号从至的一组互斥情况定义步骤或情况内还可包含编号为至的步骤或情况以此类推每一步骤或情况都使用元语言中的各种非形式化的语句类型规定所要执行的动作每一种情况都以应用该情况时所必须满足的谓词引导例是程序起始操作的定义在此作为一个实例例中第一段给读者一些指导真正的定义部分从操作开始程序起始本操作在每一个分程序被激活时执行以建立局部于该分程序的自动类和已定义类变量若申述中指定了初始化则初始化自动类变量在程序
18、起始阶段求值的任何表达式例如范围表达式或初值说明中的表达式均不允许引用该分程序中其他局部自动类或已定义类变量寻找目录项操作在发现一个在具有起始旗标的分程序中申述的引用时将施加限制仅当程序起始操作处于活动状态时才出现起始旗标操作程序起始步骤在当前连接部分附加起始旗标步骤对当前分程序中包含自动类或已定义类的每一个申述执行步骤步骤令表示直接包含在中的标识符令表示直接包含在的变量中的数据描述执行求值数据描述以便分配以获得一个求值后的数据描述情况包含自动类步骤执行分配操作得到一个世代步骤在当前自动类目录项表中添加一个自动类目录项步骤若包含初值说明则执行初始化世代操作情况包含已定义类在当前已定义类目录项表
19、中添加一个已定义类目录项步骤删除当前连接部分的起始旗标步骤用语句控制操作表推进执行的操作替换当前的语句控制例程序起始操作步骤是一个附加动作其含义是将一棵树作为子树复制到另一棵树中按照后者类型的语法规则前者可合法出现的位置修饰词当前的已用定义所用的特殊机器状态作了精确的定义所谓光前连接部分是指直接包含在对应于当前所要执行的分程序的分程序状态中的连接部分步骤使用词对每一个指明要迭代适用于第一种形式的执行动作即执行同一操作一次或多次逗号后引入的名字例如是一个局部于该操作的变量其值假定是是紧先于的树的一个指示符以后用到时除非已用类似于初始定义的方法重新定义了例如在本例中对每一个的下一次迭代时即出现重新
20、定义的情况或用词令重新定义了均对作逆引用即它表示由指示的树令语句是这类局部变量定义的一种更明显的语法步骤中包含了一个实例若包含自动类情况中的谓词得到满足将依次执行步骤至第二种形式的执行动作用于调用例如为子程序或函数的另一个操作出现在步骤中在本例中是一个函数引用该函数获得一个结果值然后对该值赋予一个名字作为参数传递给该操作其定义将命名一个对应的参数参数传递是传地址即将参数的指示符作参数值传递以后用到时对该值作逆引用其行为类似于局部变量步骤中的添加动作在表的末尾添加一棵树步骤举例说明了含有子程序调用的如果语句步骤和包含其他两类要用到的树操作删除和替换当用一棵树替换另一棵树时原有的树被删除用于替换的
21、树的一个副本的根置于原先树的根位置副本的根结点与被删树的根具有相同的隐含名在置动作的语法形式中允许将一个值赋予一个变量例如置为真但这仅是使用常用的变量名隐式逆引用来进行替换的一种替代形式其含义是用真替换由指示符值所指示的树在此未作解释的其他语句类型有转向不要滥用未到最后一步完成就终止一个操作以及从函数返回一个值也终止操作值的返回也是传地址因而若结果是在函数中构造的树则必须复制给调用者调用者获得该副本的指示符局部于某个操作的值在操作终止时删除通过上述介绍我们已有了对元语言可进行机器处理的直觉下面将进一步说明可将元语言机器化的理由步骤提供了线索步骤中构造了一棵树置于机器状态中在机器状态的操作表中只
22、有一个称为活动的且附有一个可执行操作的概念处理器特别是机器具有一个当前分程序状态该状态有一个语句控制在语句控制中可将解释当前分程序中的语句的元语言动作机器化可将操作表设想为一个下推堆栈每一个操作都将有一棵子树对该子树尚未作形式定义但子树中包含下列信息操作名含有肖前值的参数表和局部变量表在执行该操作时所构造或从所调用的子程序中复制回的全部树在那一个步骤或那一种情况下执行其算法的指示在对每一迭代中已进行的迭代次数等等当一次执行调用另一个操作时该操作被压入堆栈并成为活动操作当一个操作终止时其整棵树包括局部值都被删除该操作弹出堆栈栈顶的操作成为活动的并从被挂起的位置恢复其算法的执行回到本条开始时的类比
23、元语言处理就象一个抽象处理机该机每一机器周期执行一批微码操作每次都使用操作被调用时的局部存储器并具有先进的堆栈能力本标准与实现间的关系概念机的输入是表示外部过程的一个或多个符号表一个入口值和一个数据集表它们的组合称为一次程序运行对某个特定的实现的标准定义还需不一定使用本标准的风格定义在条中所列出的由实现所定义的设施以及在实现的操作环境中程序运行的元素符号表入口值和数据集表的表示法才完整有了这些信息概念机才能对程序运行给出一个或多个解释本标准的主要目的是定义解释有效程序运行的语义这些语义完全由机器状态的数据集的变化序列组成一种实现可自由地选择任何方法获得这些变化序列操作和机器状态中的其他部分是本
24、标准定义语义所用的机制不一定要在实现中直接反映当且仅当某个实现符合下列概念解释之一才称该实现符合本标准若概念解释拒绝一个程序运行在必须测试中失败或永不终止翻译阶段则实现无论作任何解释都符合标准特别地某一个实现拒绝程序运行的地点可与本标准不同甚至根本不拒绝程序运行否则若实现的解释跟概念解释获得同样的数据集变化序列则符合标准若实现的解释仅在条中所指定的解释的灵活性所允许的部分与和规定的不同则也符合标准注意的规定隐含了实现可提供超出本标准所定义的语言的扩展但扩展后的实现对不用这些扩展的程序的解释仍须符合标准解释的灵活性术语任选地的以任意次序的使用使概念机的操作定义具有为高效实现所需的大部分灵活性然而
25、有些规则若用元语言形式化地描述则将需要相当复杂的构造以致会严重妨碍理解因此在本条中用非形式化的语言描述这些规则并直接引用实现所可能采取的动作程序的拒绝若对程序的某一部分的解释会导致拒绝程序则即使概念解释不会到达该部分实现也可拒绝程序定量限制实现可作未包含在标准中的定量限制例如可用下列文字作出限制当语法允许任意次的迭代或递归构件时只要不删除上述构件实现可限制这些构件的规模特别是一个标准实现可限制标识符的最大长度但不得少于个字符对翻译或解释过程中的信息量可加限制对解释程序运行所需的时间可以限制操作环境实现可对与环境的接口例如外部标识符或标题的组成等作出限制为执行符合本标准的程序实现可要求适当的语言
26、外信息表达式求值操作对表达式求值对变量引用求值和对目标引用求值定义了一个或多个严格的求值顺序实现可在下列方面与严格顺序不同实现不一定须激发严格求值所激发的全部中断实现激发中断的顺序可与严格求值激发中断的顺序不同实现对表达式值引用变量引用或目标引用的求值可通过以任意次序对它们所包含的表达式值引用和变量引用求值来完成注意这并不意味着允许改变运算符或其操作数的优先顺序因为翻译器已在表达式的树结构中固定了优先顺序若实现可不经实际求值就确定表达式变量引用或目标引用的结果则实现不必执行求值操作然而若结果取决于某个所包含的过程函数引用的返回值则对该过程函数引用必须求值在决定是否需要执行求值时实现可不考虑该求
27、值操作激发中断的可能性中断和赋值执行赋值语句操作决定了求值的严格顺序如条的所述实现可在激发中断的数量和顺序方面与严格顺序有所区别当某个实现超出了一个或多个由实现所定义的限制时可标志下列异常状态上溢下溢定点溢出零除尺寸串长度串范围下范围存储区域和差错输入输出环境说明属性和选择用于说明与操纵文卷值和数据集有关的由实现所定义的信息若出现环境说明则可能会影响本标准中所描述的算法执行必要的表达式求值操作或者影响打开的文卷值和数据集的对应关系若不出现环境说明则按给定的算法执行出现在环境说明中的表达式在由实现所定义的地点求值若在打开语句中有多个单项打开要求实现可在执行由单项打开操作所执行的标志输入输出状态文
28、卷未定义操作方面与严格顺序不同特别是实现可推迟标志输入输出状态操作的执行直至语句中的其他操作均已执行完毕但标志异常状态的顺序必须与严格顺序相同若在取语句中有复写选择实现可在执行输出串项操作上与严格顺序有区别特别是实现可交替地执行输出串项操作与取语句中输出串项操作之后的任何操作若存在多个输出串操作则它们之间的相对执行顺序必须与严格顺序所规定的相同而与相对于取语句中其他操作的顺序无关在任何包含文卷选择或复写选择的输入输出语句的执行过程中实现可标志传输异常状态取决于由输入输出语句所传输的数据的用法和有效性在标志传输异常状态后程序的继续执行可能成为未定义的传输异常状态由执行标志输入输出状态传输异常文卷
29、值键操作所设置其中文卷值和键取决于该输入输出语句如在程序结尾过程中关闭文卷时所执行的输出操作出现须标志传输异常状态的情况时实现可执行任何由实现所定义的动作取串不得直接包含其中简单包含一个变量引用的表达式该变量引用标识一个由执行对取串的输入规格说明求值所引用的分配单元送串不得直接包含一个目标引用该目标引用标识一个由执行对送串的输出规格说明求值所引用的分配单元异常处理程序单位为避免异常处理程序单位的某些副作用和避免对进入异常处理程序单位时的机器状态作多重定义一个程序必须满足下列机所未显式说明的限制除非经执行转向语句终止该异常处理程序单位否则由于下溢转换或串长度异常而进入的异常处理程序单位及其任何动
30、态后代都不得分配释放或赋值给被中断的分程序中所用的任何分配单位元令表示激发中断时的当前分程序状态即被中断的分程序当为当前分程序状态时机的任何操作所引用的分配单元称为分程序所用的分配单元令表示一个分程序状态令表示当为当前分程序状态时所执行的一个可执行的程序单位在的执行过程中将调用对目标引用求值操作返回多个世代令表示由这些世代所指示的分配单元集合即给定语句执行的目标在的执行过程中任何时刻请求中断操作时的任何成员所包含的基本值均被置为未定义的若控制到达该中断操作的步骤则恢复原始的基本值除非包含它们的分配单元已被异常处理程序单位或其动态后代赋予一个或多个基本值在进行过上述赋值的情况下将该分配单元的基本
31、值置为未定义的由实现所定义的设施下面所列的语言设施称为由实现所定义的它们的规格说明用于完善特定实现的语言定义在此只给出了每一设施的简单描述并在括号中列出详细说明所在的条目标志传输异常状态的场合条在程结尾过程中执行关闭文卷的输出操作时代替标志记录异常键异常或传输异常状态所执行的动作以及其他不标志上述三种异常状态的场合条条和条传递给解释操作的数据集如何决定条传递给解释操作的入口值如何决定条环境说明属性和选择的语法条和语义第章任选项属性和选择的语法条和语义数据字符集中的语言外字符和条并入构件中正文名的组成条实现的字符集中的字符内序硬件表示图形表示和符号名和条算术型数据的默契精度条区域的默契尺寸条外部
32、申述中环境说明和任选项属性的一致性要求条和入口引用中任选项属性的一致性要求条作为虚元传递的区域值尺寸条异常处理语句中指定了时所输出的信息条内部函数取代码异常值所返回的值条出现存储区异常状态时标准的系统动作条出现差错异常状态时标准的系统动作条作为标准系统动作输出的注释形式条须标志差错异常状态的场所须标志存储异常状态的场所条区域尺寸规格说明的使用条对伪变量机内表示形式的解释条数据集的具体表示条记录的大小条键的长度条流式数据集控制项的表示条文卷打开时的数据集如何决定条流式输出文卷的默契行长度条打印文卷的默契页长度条打印文卷默契的制表位置条文卷标题的长度条须标志键异常状态的场合条条条和条当标志记录异常
33、状态且正常返回时写出或不写出记录的情况以及那些记录的值条条和条写语句和定位语句对记录异常状态的标志条在索引顺序文卷中的记录位置条数据型送语句输出的项目条按定点格式编辑时用的最大数字位数条每一种基数和数制组合中的最大数字位数条条条和其他条文整型数的精度条表达式和内部函数的浮点结果如何决定条变元为浮点数的舍入内部函数的结果条内部函数时间返回的串长度条内部函数取机内表示的结果条数值转换的结果条条和条浮点数阶码部分的位数条币符数字和数符的表示条元语言在条的入门介绍后本条给出更精确更仔细的元语言定义本标准的定义部分由一组产生式规则一组操作限制属性定义和变元名表格术语定义以及描述实现与本机器化定义之间关系
34、的条文组成表达定义的元语言中有三种主要的记法将在本条中给出它们是元语言中基本的数据类型树的记法定义树种类的产生式的记法对树进行操纵的操作的记法其他定义部分的材料由限制属性或变元为前导表格用实线框标识在首次定义一个术语非语法分类时将该术语用黑体字表示以后用到该术语时不再用黑体字示例用虚线框标识示例不属于定义部分语法和操作的导论段落也不起定义的约束作用树树是由本标准所定义的处理动作操纵的唯一数据类型该处理过程的所有内部操作仅使用树该处理过程从环境取得的输入均是适当地构造了的树由该过程所定义的语义解释必须用其所执行的树操作来说明为了一致起见即使是单值例如数字或字符也作为单结点的树处理从本标准所定义的
35、处理的严格机器化角度出发事实上只能有一棵树存放整个处理状态在此讨论的其他树均是这一棵树的子树然而由于本标准在树的定义中遗留了一些非形式化的空隙因此也可将处理过程看作对一组独立的树进行操作其中一棵树对应于状态其他的树更局部于特殊的定义阶段条中定义了本标准所用的树的一般抽象形式及讨论树所用的技术术语条中讨论用于构造树结点的对象的基本性质使这些树更专门化在和条中讨论用于书写每个结点的记法和整棵树的记法条的讨论树的副本在有关树和树记法的一般性描述条文之后条讨论产生式规则产生式规则规定了本标准中所用的特殊类别的树树的定义结点是对象的有序对这些对象称为结点的类型和唯一名树是结点及结点间结构关系的有限集合这
36、些关系是树中有一个规定的结点称为根结点除根结点以外的其余结点称为树的子结点可划分为零个或多个不相交的集合每一个集合又构成一棵树这些树称为所定义树的直接子树在这些直接子树间有规定的线性顺序若树是树的一棵直接子树或树的某棵直接子树的一棵子树则称树是树的子树若不存在一棵树使得是树的子树树是的子树并且的根结点与的根结点或的根结点类型相同则称是的简单子树对基于词包含的术语的使用是一致的称子结点和子树是包含在给定的树中直接子树和简单子树分别称为直接包含在和简单包含在给定的树中类似地对基于词成分的术语的使用也是一致的即称子结点和子树是给定树的成分直接子树和简单子树分别称为给定树的直接成分和简单成分直接子树和
37、简单子树的根结点分别称为直接子结点和简单子结点由术语简单包含所表示的概念在后面使用得十分频繁以致通常都将其省略这隐含了在具有包含或所有关系的两个结点间的关系语句中若不明确使用任何中有形式的词包含或成分则解释为隐含简单包含关系例如简单包含可表达为带有的中的甚至简化为在单个句子中这些缩写还可以复合若两棵树中结点数量相同并且两者各包含类型相同的一个单结点或两者均包含多个结点根结点类型相同直接子树的数量也相同且每一对直接子树都相等时称这两棵树相等若树和均是某树的直接子树且在的子树线性顺序中之后的下一个是则称紧后于若树紧后于树则称紧先于若满足下列条件之一则称树后于树紧接存在一棵树使得后于且后于存在一棵树
38、使得包含且后于存在一棵树使得包含且后于若树后于树则称先于注意上述定义并未定义树中所有子结点的线性顺序仅定义了一个偏序特别是包含某一棵树的树既不先于也不后于它所包含的树应用于任何各别树集合的术语第一棵和最后一棵具有习惯的含义即无先于它的和无后于它的对某些树集合用这些定义并不能给定唯一的第一棵和最后一棵树但在本标准中仅对存在唯一结果的树集合使用这两个词类似地给定树的下一棵树也按习惯上的含义定义意为之后的第一棵也用在有唯一结果的场合当包含在树中的结点和包含在树中的结点在的根结点的直接子树的有序集合中或在和对应结点的直接子树的有序集合中所占位置次序相同时称对应于第章条中包含在某些特定上下文中有用的有关
39、对应的进一步定义结点对象条中给出的结点定义中并未定义用作结点类型和结点唯一名的对象的本质这些对象的可选集合是有限制的见条和条唯一名可用作结点唯一名的对象集合有两个作用所有结点唯一名均从该集合中选出另外某些结点类型也可在该集合中选择任何与用作结点类型的其他对象有区别的可能的对象的无限集合均可作唯一名称结点的唯一名成分有两条理由其一任何时候两个各别的结点均不得有相等的唯一名成分其二在创建新结点时不能使用与任何已创建的结点唯一名重复的名字某结点的唯一名在该结点的整个生存期内保持不变因此可用来标识或指示该结点见条类型可用作结点类型的对象集合是下列不相交集合的并分类名集合它是产生式所用的对象的有限集合此
40、集合可进一步划分为几个逻辑上相关的子集每一个子集有固定的记法习惯实数集合也可能是某个与实现有关的包含整数的实数子集整数用作索引或序号实数可包括整数用作算术型变量的值如条所定义的唯一名集合该集合中用作结点类型的一个成员称为指示符指示符用于显式地唯一选取或指示树的结点一个指示符或只包含单个指示符的树指示以同一对象作唯一名的结点注意这种构造法加上条中的唯一性规则意味着可以对指示符进行检验并在构造过程中判别所要指示的结点事实上是否已被删除一般规则是在结点的整个生存期中结点的类型保持不变当移去旧结点和构造新类型和新唯一名的结点时则修改了树唯一的例外是替换指令见条结点的记法在元语言中结点的唯一名只起隐含保
41、证唯一指示和正确区分子树的作用基本上是不可见的元语言中讨论结点时总是使用结点类型从不直接引用唯一名集合中的特定对象因此对唯一名不须规定记法实数的记法是普通的十进制记法在后面的条文中上下文可保证区别用作结点类型的数和用于其他目的的数根据使用特定分类名的逻辑性质不同分类名的记法也不同分类名的各种记法和含义如下命名分类由小写字母连词符数字形为和和或和的括号组成的名字用于指示某些分类名对这些名字括号部分除外可任选地用黑体字表示一般选用中文助记词或缩写表示分类名的作用另外三类括号分别表示分类名是在具体语法分析阶段抽象语法分析阶段还是在解释阶段起作用如果是黑体字表示该分类名仅作为不含成分的结点类型出现字符
42、语言字符集中的个字符用作分类名时有两种记法可用在大多数不会出现混淆的情况下直接使用各别字符的记法字母用大写空白用符号在有可能混淆时在直接记法基础上加上具体括号如关键字某些分类名代表关键字即所选的字母或数字顺序在中有特殊意义对关键字也有两种记法在大多数不出现混淆的情况下将构成关键字的各个字母或数字直接连接中间不留间隔例如加引号的符合和在有可能混淆时在直接记法基础上加上具体括号类或类类型的结点称为有具体表示的它是由个语言字符中的任何字符组成的非树字符串对这类结点其具体表示仅是结点类型的简单指示其中用空白代替分类语言外字符的任何可能的子结点都假设为有具体表示且不同于任何字符的具体表示满足所有不含成分
43、的结点类型均有具体表示这一限制的树也可称为有具体表示该树的具体表示是将树中各结点的具体表示按先后顺序连接构成的字符串树的记法枚举树一棵特定的树可用从根结点开始描述其每一个结点的直接成分直至终极结点为止的方法完全指定这也可用枚举树更精确地表达所谓枚举树是一种记法其格式是根结点的类型任选地跟一个速号和指示根结点的名字见条任选地跟有一个冒号和根结点直接成分直接成分本身也可以是枚举树或指示所要复制的其他树的名字直接成分可括在方括号和内表示当且仅当其值为缺席时该成分可省略和一个分号例如由一个数据类型该数据类型直接包含一个非计算类型该非计算类型又紧接包含格式和局部的所构成的树可写成数据类型非计算类型格式局
44、部的常用缩排使记法更为直观例如数据类型非计算类型格式局部的枚举树末尾紧接于圆点之前的分号可以省略在元语言中枚举树的使用表示局部树的创建见条该局部树具有所指定的结构和结点类型并插入了某些树的副本见上述而且设置了对应于如上述中任选地使用的名字的指示符指示所创建的结点对某类特定的枚举树常用的缩写方法是将可能的具体表示用双引号括起来这是对以符号表为根以引号内的字符串为具体表示的树的缩写形式元语言中对要在树中搜索的模式可使用与枚举树相同的记法但不能包含所要复制的树的名字元语言中这种记法的使用总是冠以词形式使用这种记法表示要搜索该模式或检测该模式的一致性产生真或假值且当且仅当搜索或检测返回真值时设置对应于
45、如条中所用的名字的指示符以指示对应于它们的结点在形式中使用方括号表示括号内的内容可出现也可缺席树的副本一棵给定树的副本构造如下构造一棵与给定树相等的树对给定树中每一个同时也指示给定树中结点的指示符结点改变所构造的对应于的结点使它指示所构造的对应于的结点产生式规则本标准中所用到的树是按条的定义可构成的所有可能的树的一个有限子集产生式规则用作元语言的申述部分并通过对本标准定义过程所用的树的型式规定限制来申述产生式规则和语法产生式规则的书写格式是一个分类名符号后接一个语法表达式见条或在某几种情况下后接一条短语所组成并可有一个任选的由大写字母和数字组成的标号这样的产生式规则称为对写在之前的分类名的定义
46、产生式规则在本标准中任一分类名最多只能有一条定义产生式规则产生式规则的基本作用是对类型为所定义的分类名的结点的直接子结点的数量类型和次序定义一个可能性集合这通过按条给出的算法解释产生式中的语法表达式来实现指定直接子结点时可用一种习惯记法来说明创建重复的直接子结点表这样扩展了产生式规则该惯用记法适用于加括号的内容以表或逗号分隔的表结尾的分类名使用这习惯记法后对这类分类名不需出现显式的定义产生式规则即本标准中对这类分类名未写出定义产生式规则语法是任何产生式规则的集合例如本标准中所有产生式规则的集合是一个语法本标准中五个不相交的产生式规则子集具有足够的逻辑相关性所以已对它们命名即高级具体语法中级具体
47、语法低级具体语法抽象语法和机器状态语法为了区别这些语法对构成这些语法的产生式规则分别冠以以符号和引导的数字标号无标号的产生式规则不属于这些语法中的任何一个若语法中出现某分类名的定义产生式规则则称该分类名是语法中的非终极符在语法中产生式规则的语法表达式中出现的任何分类名若在语法中无对应的定义产生式规则且如果它的记法中除去括号后以表逗号分隔的表或指示符结尾则称为语法中的非终极符否则称为语法中的终极符属于由本标准中所有产生式规则所构成的语法中的非终极符简称非终极符类似地属于由本标准中所有产生式规则所构成的语法中的终极符简称终极符抽象语法中还允许对某些分类名规定限制这种限制写在有关分类名后的括号内由翻
48、译器或在解释阶段应用但对由语法规定的树的构造并无影响完全树和部分树给定一个语法对该语法而言的完全树是经下列步骤所获得的树从一给定类型的结点开始向按条的算法构造的树的结点上重复地附加子结点直至对该树的每一结点都有一个解释对本标准中所有的产生式规则构成的语法而言的完全树可简称为完全树从完全树中删去某些结点后所获得的非完全树称部分树本标准的定义过程只使用完全树或部分树而不用任何其他可能形式的树而且通常都是用完全树至少在各种定义操作的界面是使用完全树的部分树一般仅在建立完全树过程中的非常局部的上下文中出现但有几处例外元语言中的一些指令见条的设计实际上就是为了对建立完全树的过程有所帮助产生式上下界说明下
49、界上界星号定义了两种可能可写作或如下上下界说明上下界说明下界或星号上界类型为标识符表的结点可有任何非零个类型为标识符的直接子结点即标识符表或标识符表或标识符表标识符标识符标识符标识符标识符标识符等等类型为逗号分隔的参数表的结点可有任何非零个参数直接子结点但相邻的参数子结点间插入类型为字符的结点即逗号分隔的参数表或逗号分隔的参数表或逗号分隔的参数表参数参数参数参数参数参数等等产生式重复选择表达式标量说明只有产生标量值即非聚集值的表达式才是重复选择的合法直接子结点例语法语法表达式和语法单位给定一个语法单个语法单位或每两个相邻的语法单位间用或符号分隔的一系列语法单位称为语法表达式引号中的两上符号分别称为或符号和置换符号给定一个语法语法单位定义为下列之一单个分类名括在方括号和内的语法表达式或括在花括号和内的语法表达式产生式规则的应用给定一个语法和一个分类名使用下文所列算法可获得一个分类名的有序集合可能是空集称为按给定的语法对给定分类名的解释在构造按给定语法的完全树时任何这种有序集合可被用作连接到类型为给定分类名的任何结点上的直接子结点有序集合的对应的类型对分类名的解释定义如下情况在给定分类名的记法中去掉
