程序语言.ppt

《程序语言.ppt》由会员分享，可在线阅读，更多相关《程序语言.ppt（70页珍藏版）》请在三一办公上搜索。

1、第三章 语言翻译,程序结构,语法 程序是什么样的BNF(上下文无关文法)一种非常有用的描述语法的表示法。语义 执行行为静态语义 语义在编译时确定：var A:integer;A 的类型和存储int B10;数组 B 的类型和存储float MyProcC(float x;float y).;函数属性动态语义 语义在执行时确定：X=ABC SNOBOL4语言的例子:X 是一个字符串X=1+2;X 是一个整数:(X)X 是一个地址；转移到标号为 X 的地方,主要内容,程序语言的语法语法的一般准则、次要（或二级）准则语法的基本元素程序-程序的组织结构程序的翻译源程序分析：词法分析（扫描）、语法分析、

2、语义分析目标程序的综合翻译模型BNF、正则文法（有限状态自动机）、下推自动机PERL概述,3.1 语言的语法,语法：单词的组织方式，用来展示单词之间的关系单词作为语句中的元素语法描述了构成有效程序的符号序列。如C中，x=y+z是有效的符号序列，而xy+则不是。语法提供了理解程序的含义所需的信息，也提供了大量的从源程序到目标程序翻译所需的信息。,语言的语法（2）,单靠语法并不足以无二义地刻划语句的结构。如：x=2.45+3.67，语法并不能告诉我们x是否被声明过或是否声明为实数。x=5,6或6.12均是可能的。因此，对语言的完整描述单靠语法结构是不够的，还需涉及语义。如：声明的使用、操作、顺序控

3、制和引用环境等影响变量性质的一些属性，并不总是由语法决定。,语言的语法（3）,虽然如此，语法仍是语言描述中的重要属性。现在，语法描述已是一个解决了的问题，源程序的语法理解阶段是相当机械的，YACC等工具可自动生成给定程序的语法描述。,返回,语法的一般准则,语法的主要目的是为程序员和语言处理器间通讯提供一套注记方法。而选择特殊的语法结构主要是为了传递特殊的信息项。例如：某特定变量有类型实数，可以用多种方式表达。可以是显式声明或隐含的命名约定，等。语法细节的选择大部分是基于第二准则，如可读性，它和通讯的主要目标无关。有很多二级准则，通常可按其目标分类，分为：易读、易写、易翻译、无二义等目标。这些目

4、标间有时会有冲突。,易读性（Readabitity）,程序是易读的：如果程序表示的算法和数据的结构可以很容易从程序文本中了解到。一个易读的程序，通常称为自成文档的（不需其他用于理解的辅助文档）。增加易读性的方式：自然的语句格式、结构化语句、关键字和噪音字的自由使用、嵌入式注释机制、不限长标识符、助记符、自由域格式、完全的数据声明等。不同的语法应反映不同语义，做相似事的程序结构是相似的。做不同事的程序其结构需有明显不同。语言如只提供了少数不同语法结构，通常导致程序易读性差。如APL，SNOBOL4等，只提供一种语句格式，赋值、子程序调用、简单GOTO、子程序返回，多路条件分支、及其它常见程序结构

5、的差异只能通过个别操作算子的不同来反映。,易读性（Readabitity）,易读性并不能由语言设计保证，最好的设计也可能由于糟糕的编程而破坏。当然，语法设计也可能使好程序员写出难理解的程序，如APL。COBOL强调易读，但其代价是牺牲了易写和易翻译。,易写性,易写性（使用简明的、规则的语法结构）通常和易读性（冗余结构是有帮助的）相冲突。隐含的语法约定允许声明和操作不需预先刻划，从而使程序更短、更易写，但不易读。有些语法冗余性有用的，因它允许程序易读，并允许翻译时错误检测。缺点是不易写。语法称为冗余的，如果以多种方式传达同样的信息。大多数缺省规则（针对语言结构含义）试图减少冗余，而删去了某些显式

6、的含义陈述，因为这些含义可从语境中导出。例，Fortran中约定，I-N打头的变量为整型，其他为实数，这样不需声明，但缺点是有副作用，如：拼写错误不能被编译器检测到，例如：INDEX被写成INDX则变成新变量。,易写性,对两个目标均有增强的一些特征：如结构化语句、简单自然语句格式、助记符、未限制标记符等通常使程序易写通过允许在程序中直接表示问题的算法和数据的自然结构。,易验证性,和易读、易写相关的概念是程序正确性或程序验证。多年经验表明，理解每条程序语言语句是容易的，创建正确程序的整个过程却是困难的。因此，需有技术，使得能数学地证明程序是正确的。,易翻译性,即易于翻译成可执行形式。易读性和易写

7、性是面向程序员的需要。易翻译性（关键是结构的正则性）是面向翻译器（处理被写成的程序）的需要。如LISP程序，不易读、也不易写、但易于翻译，主要由于其语法简单且正则。当特殊语法结构增加，将导致翻译困难，如COBOL，它允许大量的语句和声明形式。,无歧义性,含混性是语言设计中的一个中心问题。一个语言定义应尽可能地为每个语法结构提供唯一的意义。而含混性结构允许两个或多个不同解释。通常不是由个体程序元素的结构产生，而是由于不同结构的交迭。例如：if Boolean exp then statement1 else statement2.If Boolean exp then statement1当两种

8、形式组合时，有可能出现二义情况。Fortran中，A（I，J）可能是数组元素，也可能是函数调用。事实上，上面提到的含混在语言中均有解决方案。,条件语句的两种不同解释,歧义性的解决方法,例：因组合而形成的悬空else：If Boolean exp1 then if Boolean exp2 then stat1 else stat2Algol解决方案：改变语法，引入分界符beginend。Ada解决方案：每个if语句必须以end if分界符结尾。C和Pascal解决方案：从二义结构中任选一种解释。对本例而言，最后的else总是和最近的then配对。FORTRAN中函数调用和数组引用的二义性由规则

9、解决：A(I,J)被视为函数调用，如果没有数组A的声明。但这个假定只能在程序装载、链接时被检查。Pascal中区分二者的方法是使用不同的括号，如：用于界定数组参数，()用于界定函数调用的参数。,返回,语言的语法元素（1/7）,语言的语法风格由各种基本语法元素的选取所决定。字符集字符集的选择是语言设计的第一件事。已有一些标准字符集，如：ASCII码。通常是选择一个标准的字符集。但也有不标准的，如APL。字符集的选择对确定可被用于语言实现的I/O设备的类型是非常重要的。如：C的字符集可用于大多数I/O设备。而APL的字符集则不能直接用于大多数I/O设备。通常用8位来表示字符（60年代早期用6位），

10、这似乎是足够的。但是，随着计算机产业的国际化进程，可能16位表示是必需的（可有65536个字符）。,语言的语法元素（2/7）,标识符字和数字串，以字母开头常用的选择。也可能使用特殊字符，如用.或-来改善易读性和长度限制。操作符符号+，-，*，/表示基本算法操作。通常简单操作可完全使用特殊符号。当然，也可以使用标识符来表示简单操作，如LISP中的PLUS、TIMES。大多数语言采用二者的组合。,语言的语法元素（3/7）,关键字和保留字关键字用于语句语法中固定部分的标识符。保留字不能被程序员使用的关键字。大多数语言使用保留字以改善翻译器的错误检测能力，使语法分析更为容易。噪声字可选的字，被插入语句

11、中以改善易读性。如：COBOL中Go语句可写为GO TO,语言的语法元素（4/7）,注释是文档中的重要部分，几种注释方式：1、分开的注释行，Fortran2、特殊标志界定，/*/，界定字符丢失可能导致大面积出错。3、在行中任意地方开始，但在行末结束，如C+的/空白（空格）语言中常使用空白规则，通常都是作为分隔符。也有的语言中空格有其他用途。,语言的语法元素（5/7）,界定符（分界符）和括号用于标记语法单位的开始和结束，如 括号是一对分界符。自由和固定域格式自由域语句可写在任何地方固定域在输入行中通过位置来传递信息。Fortran是典型例子。当前固定域越来越少。,语言的语法元素（6/7）,表达式

12、访问程序中数据对象并反回值，是基本的语法建筑块。在命令型语言中，表达式形成基本操作，状态被语句所改变。在作用型语言中，表达式形成了驱动程序执行的基本顺序控制。,语言的语法元素（7/7）,语句是命令型语言中最主要的语法部件。语句的语法对语言整体的正则性、易读性和易写性有着关键影响。有的语言采用单一语句格式，强调正则性；而其它语言对不同语句类型使用不同语法，着重于易读性。语句结构中的一个更重要的差异是：结构性（或嵌套）语句和简单语句。,返回,程序结构,分开的子程序定义Fortran中，每个子程序定义被处理为分开的语法单元，每个子程序被分别编译，被编译程序在装载时链接。这种组织方式主要是针对这样一种

13、情况：每个子程序均需含所有数据元素的完整数据声明，即使是对那些在COMMON块中的或与其它子程序共享的数据。需要这些声明主要是由于分开编译的需要。基本的子程序单元用于表示某种能提供相关功能的结构。分开的数据定义把所有操作于给定数据对象之上的操作组合在一起，如C+中类。主要是基于数据抽象的原则。,嵌套的子程序定义,如PASCAL，子程序定义在主程序中作为声明出现，子程序本身又可含有其他子程序定义。其目标是强调结构化的语句，但事实上产生了不同用途。结构化语句的引入主要是为算法结构的常见的层次划分提供一种自然的注记方式，但嵌套子程序定义为编译时定义的子程序提供了非局部的作用环境。从而允许静态类型检查

14、，和有效的可执行代码的生成。嵌套的另一好处是作用域管理。允许子程序名具有较少的作用域。,分开的接口定义,FORTRAN的结构使得编译分开子程序变得非常容易，但缺点是不同子程序共享的数据可能有不同的定义，而这种不同是编译器在编译时无法检测到的。PASCAL允许编译器访问所有这样的定义以帮助发现错误，缺点是全部程序，即使其有上千条语句，必须在每次修改后重新编译。结合上面的技术可以改善编译行为。程序实现由几个相互交互的子程序构成，这些部件称为模块，将被连接在一起以创建可执行程序，但每次只有修改的模块被重编译。而在一个部件中的过程间传送的数据必须具有公共声明，从而允许编译器的高效检查。为了在分开的编译

15、模块间传递数据，引入了规约部件，如C中.h文件。Ada中的Package（接口定义规约+实现体）。,数据描述和可执行语句分离,COBOL包含了早期的部件结构形式。在COBOL中，所有子程序的数据声明和可执行语句被分入不同的程序中，即数据段和过程段，而用环境段包含关于外部操作环境的声明。一个程序的过程段被组织为子单元，以对应子程序体，但所有数据对所有子程序均是全局的，没有东西对应于通常子程序中的局部数据。中心化数据段的优点是：强迫形成数据格式和过程段中算法的逻辑独立性，数据结构的细小修改可只修改数据段而不需修改过程段。同时将数据描述搜集到一个地方，而不是散布在子程序中也是方便的方式。这适合于大量

16、数据的处理。在某种意义是，数据库应用是这种形式的扩展。,未分离的子程序定义,不分开主程序和子程序语句，如SNOBOL4中，程序是一个语句表。子程序间没有语法分隔，函数调用开始新的子程序执行，返回语句结束该子程序。程序的行为是动态的。事实上，任意语句可以同时是主程序的一部分，也可以是子程序的一部分。这体现在该语句可在主程序的执行中某点被执行，而后又在某子程序的执行中某点被执行。这种混沌结构仅仅对允许运行时翻译和相对简单的新语句和子程序执行机制具有价值。,返回,3.2 翻译的阶段,逻辑上，翻译可分为两个主要部分（输入源程序的分析，可执行目标程序的综合），两个阶段又可细分。大多数翻译器的中这些逻辑阶

17、段不是可以明确划分开的，而是混合在一起使得分析和综合交替进行（通常逐条语句进行）。,翻译的阶段,编译器通常对源程序扫描两遍第一遍将程序分解为部件并从程序中导出信息。第二遍根据这些收集的信息生成目标程序。如果编译速度是重要的考虑（如教学用编译器），一遍扫描是常用方式，在程序被分析时，立即被翻译为目标代码。如果执行速度是重要考虑，三遍甚至更多遍扫描也是可能的。第一遍分析源程序。第二遍使用各种定义好的优化算法将源程序重写为更多效的形式。第三遍生成目标代码。,返回,翻译的阶段,源程序的分析（1/3）,词法分析将源程序字符流分隔、分组，成为一些基本的构成成分，如：标识符、分界符、操作符、数、关键字、噪音

18、字、空白、注释等。这些称为词法项，Token（语言符号）。,源程序的分析（2/3）,语法分析（parsing）标识大的程序结构（语句，声明、表达式等）（基于前面得到的语言符号）。通常语法分析和语义分析交替进行（使用栈作为通讯工具）。语法分析器向栈中输入各种语法单元元素，语义分析器检索并处理。需要高效的语法分析技术，主要基于形式化文法的应用。,源程序的分析（3/3）,语义分析翻译的中心阶段处理语法分析器识别的语法结构，并开始形成可执行目标码的结构，语义分析是分析和综合间的桥梁。这阶段的工作包括一些重要工作，如符号表维护、大多数错误检测，宏扩展以及编译时语句的执行。在简单情况下，语义分析器直接生成

19、可执行代码，但大多数情况下，是产生最终可执行程序的某种内部格式，然后被优化处理。语义分析器可分为一些小的语义分析器，各自处理一特殊类型的程序结构。它们之间通过存放在各种数据结构、特别是中心符号表中的信息而进行交互。,常见的语义分析功能（1/4）,1、符号表维护符号表（最早由词法分析形成）含有对程序中不同标识符的表项（不仅含标识符，还包含涉及标识符属性的附加数据，如：标识符类型，值类型，引用环境等。）语义分析器在处理声明、子程序头、语句等时，填入相关信息。编译型语言的符号表在翻译结构后通常丢弃。但有的语言在执行时仍保留，如：允许运行时创建新标识符的语言（ML、LISP等，符号表是运行时的中心数据

20、结构），以及辅助调试（dbx使用运行时符号表来调试C程序）。,常见的语义分析功能（2/4）,2、隐含信息的插入在源程序中，有的信息经常是隐含的，必须在低级目标程序中显式化。这类隐含信息包括：一些缺省约定信息，类型推导信息等。,常见的语义分析功能（3/4）,3、错误检测语法和语义分析器必须能够处理不正确的和正确的程序。语法分析器可能会接收到和当时语境不相容的词法项，如：表达式中出现分界符，语句序列中出现声明等。更微妙的错误有：实数变量出现在需要整数的地方，对声明只有二维的数组出现三维下标引用等。属语义错。语义分析器不仅需要能够识别这样的错误并产生适当的出错消息，还必须能够在大多数情况下，确定合适

21、的方式以继续剩余程序的语法分析工作。,常见的语义分析功能（4/4）,4、宏处理和编译时操作并非所有语言具有宏特征和编译时操作。但如果具备，通常在语义分析中处理。语义分析器必须识别宏调用并处理宏替换。通常，该任务需要中断词法和语法处理，而让它们去处理宏体中的字符流。另一个方法是宏体可能已预先被部分翻译，语义分析器可以直接处理，在继续源程序分析前插入适当的目标码并建立合适的表项。用于控制翻译。编译时操作是在翻译中完成的操作，用于控制源程序的翻译。C中提供了大量这样的操作。如：#define允许常量或表达式在程序被编译前计值。#ifdef允许不同的代码序列被编译，根据某些变量的存在与否。这些设施允许

22、程序员修改被编译的语句序列。,返回,目标程序的综合,翻译的最后阶段是根据语义分析的结果，构造可执行程序。优化语义分析器通常以某种中间形式来产生可执行程序，中间形式可以是操作符和操作数的串，也可以是操作符和操作数序列的表。在代码生成前，对中间形式进行优化处理是必要的。代码生成在中间形式被优化后，必须产生最后的输出结果：可执行程序。它可能是汇编语言语句、机器代码序列或其它目标形式。它可能能够直接执行，也可能需要链接装载后才可执行。连接和装载形成最终可运行程序。,返回,3.3 形式化翻译模型,编译器理论的语法识别部分是相当标准的，通常基于上下文无关理论。语言语法的形式定义通常称为文法（grammar

23、）一个文法由一个规则集合组成，规则被称为产生式，刻划了形成允许程序的字符序列。一个形式文法是用严格定义的记号体系刻划的文法。编译技术中常用两类文法。BNF文法（上下无关文法）正则文法,BNF文法,Backus-Naur Form。John Backus开发，用于Algol语言的语法定义。Peter Naur是开发Algol委员会的主席。几乎同时，语言学家Noam Chomsky设计了上下文无关文法来定义自然语言的语法。在能力上，二者是等价的，差异只是符号体系不同。BNF文法的语法表示BNF文法规定的语言、以及语句的理解和结构化表示 语法分析树BNF文法的二义性,BNF文法 语法,BNF文法包含

24、一个BNF文法规则的有限集合，它定义了一个语言。语法仅仅涉及形式而不涉及含义，一个语言从语法上考虑，由一个语法正确的程序集合构成，每个程序只简单地是一个字符序列。语法正确的程序不一定有语义，即可能不一定计算出什么结果，甚至没有结果。不考虑语义，语言是任意有限字符串的集合，这些字符选自某固定符号集。,BNF文法 语法,下面均为语言1、所有C中赋值语句的集合2、所有C程序的集合3、所有LISP原子的集合4、a、b.构成的序列的集合，所有a在所有b之前。语言可包含有限的串集合，也可能包含无限的串集合。考虑上面例子，可发现用自然语言描述语言带来了一些问题，如：4例中，b是否是语言的成员？是否串上必须有

25、a？因此，描述并不完整。解决这个问题的方法：给出形式的数学规则集合，准确地确定语言中的串是什么。,BNF文法 语法,非终结符:符号的有限集:终结符:符号的有限集:the,boy,girl,ran,ate,cake开始符:一种非终结符:规则(产生式):替换规则的有限集：:=:=:=:=ran|ate:=the:=boy|girl|cake替换操作:用任一规则右边的值替换任意非终结符(写作),BNF文法 语法,最简单的文法规则是列出有限语言的所有元素，如：:=0|1|2|38|9这里表示一个非终结符或语法范畴，09为终结符。一旦定义了基本的语法非终结符集合，可以构造更复杂的串，如：:=if the

26、n else|if then 规则定义的非终结符可本身被用在规则中，从而形成递归规则。:=|,返回,语法分析树（parse tree）,给定文法，可使用替换规则生成语言的串。如：下面文法生成平衡的括号序列：SSS|（S）|（）一个推导过程：S（S）（SS）（）S）（）（）推导中的每个项称为句型。语言是句型的集合，其中的巨型只含有终结符(即句子)，并可从文法的初始符号推导出来。语言即句子的集合。为了确定一个字符串是否是由文法所定义的语言所规定的语法上合格的程序，我们必须使用文法规则去构造该字符串的语法分析树，如分析成功，则是该语言的程序。,语法分析树,BNF文法将一个结构赋给语言中的每个串。被赋

27、的结构实质上是一棵树，这是由于BNF文法的限制。树的叶节点是单个字符或词法项，中间的分叉点是一个语法范畴，由非终结符标记，根节点是表示整个语言的非终结符。分析树为程序提供了大部分的直觉的语义结构。,语法分析树,赋值语句W=Y*(U+V)的语法分析树：,语法分析树,不能用BNF文法定义的语法是那些涉及上下文依赖的语法，如：如下限制不能用BNF刻划。同样的标识符不能在相同块中声明两次。每个标识符必须声明在包括其使用点的块中。一个用二维声明的数组不能用三个下标引用。此类限制必须用对显式化BNF的补遗来定义。,返回,文法的二义性,一种文法是有歧义的，如果某个句子有两种不同的分析树。歧义性通常是文法中的

28、问题，而不一定是语言的问题。如：G1：SSS|0|1 具有二义性。,如果对给定语言的每个文法均是含混的，则称语言是固有含混的。然而上面G1文法描述的语言不是含混的，因为可以为它写出不含混的文法。G2：T0T|1T|0|1,返回,有限状态自动机,语言由语言符号（Token）构成。语言符号具有简单的结构，有限状态自动机或状态机是一种有效的识别语言符号的工具。,有限状态自动机,例如：识别奇数个1构成的串的FSA。,输入100101的机器操作如下处理：输入 当前状态 接受串否？NullAno1Byes10Byes100Byes1001Ano10010Ano100101Byes,有限状态自动机,通常，F

29、SA有一个开始状态，一个或多个终态，以及一组从状态到状态的变迁。任何串，只要能使机器从初态变迁到终态（通过一系列变迁），则该串为机器所接受。例如：识别带符号整数。,非确定型有限自动机,确定型FSA对其每个状态，每个输入符号，有唯一的变迁到相同或不同状态。非确定型FSA具有：1、一个状态集合2、一个初始状态3、一个终止态集合4、一个输入符号集合5、一个从状态到状态的变迁集合，每个变迁接受来自输入符号集的一个元素。非确定性是指：从一个状态有多个具有相同标记的弧线连出，从而必须作出选择。一个串称为可接受的，如果存在从初始结点到终止结点之一的路径，即使其他路径可能不能到达某终态。,FSA 和 NDFS

30、A 的等价性,将NDFSA的状态的子集作为DFSA的状态。记住所有能迁移进入的子集的踪迹。任意从 A 到 D 或 CD 的字符串都表示原NDFSA中一条从 A 到 D 的路径。,正则文法,正则文法是BNF文法的特例，等价于FSA，形式为：:=|例：A0A|1A|0 产生以0为结尾的01串。,正则表达式,正则表达式是语言定义的另一种形式，等价于FSA和正则文法。操作：串联(连接)或(|，有时也写成)Kleene 闭包(*-0或多个实例)定义：1、单个终结符是正则表达式2、如a、b是正则表达式，则ab,ab,(a),a*也是正则表达式。3、除1、2外，没有其他是正则表达式。,正则表达式,可以用正则

31、表达式来表示任何用正则文法或FSA定义的语言，虽然将任意FSA转换为正则表达式并不总是明显的。下面两图为到FSA的转换：,返回,下推自动机 Pushdown Automata,PDA是类似于FSA的抽象模型机，等价于BNF文法，它具有有限个状态，有一个下压栈，其移动规划如下：1、读输入符号，并读栈项符号2、基于两个输入，机器进入一个新状态，并写0个或多个符号在栈顶。3、如果栈空，则串被接受（或PDA处于终态）易于看出PDA比FSA具有更强大的能力。如：anbn不能被FSA识别，但可以被PDA识别。PDA接受的语言等价于上下文无关语言。,下推自动机,考虑产生串的最左推导的过程，在这种情形，句型存

32、放在栈中，PDA的操作如下：1、如栈顶是终结符，将其和下一输入比较，如相同，则弹出栈。如不相匹配，则出错。2、如栈顶是非终结符X，用串替代X，是产生式X的右端。这样PDA模拟了上下文无关文法的最左推导，这种构造实际上形成了一个非确定型PDA，等价于对应的BNF文法。在第二步中，可能有多个X样式的规则，规则的选用需人来选择。,确定型PDA和非确定型PDA,确定型PDA和非确定型PDA是不一样的。例如：考查下面的回文文法S 0S0|1S1|2我们可以用一个确定型PDA来识别该语言中的字符串：1.当读到0和1时，都压入栈中；2.当读到2时，进入一个新的状态；3.此后，总是比较栈顶和新输入的字符，并弹

33、出栈顶元素。但是，如果回文文法如下：S 0S0|1S1|0|1则不可能知道到底哪儿是回文字符串的中间。要识别这类回文，自动机只能猜测回文的中间在哪儿(这样就出现了所谓的非确定性)。,PDA的例子,给定回文 011010110，PDA必须猜测回文的中间在哪儿：堆栈:猜测的中间:等待匹配的字符串:0 110101100 1 101011001 1 010110011 0 101100110 1 011001101 0 110011010 1 100110101 1 001101011 0 只有第五种猜测才能使得字符串被正确地识别。如果某种猜测能导致输入串被完整地分析出来，则说该字符串是符合文法的。

34、,常用语法分析算法,文法描述语言是自顶向下，而语法分析则是自底向上，从个体字符开始。一般的分析策略：每种类型的形式文法总是和某类型的自动机紧密相关。自动机是一种抽象机，读一个输入带，产生一个输出带。然而，BNF文法可能是含混的，因此，自动机必须是非确定的。通过使用猜测策略，非确定型下推自动机能识别任何上下文无关文法。对语言翻译而言，不需猜测的确定型自动机是需要的。对正则文法，总有对应的确定型自动机。对BNF文法则没有，除非文法无二义并满足某些其他限制。,文法和机器的等价性,已经证实：正则文法=FSA=NDFSA上下文无关文法=NDPDA但 NDPDA 并不等价于 DPDA上下文有关文法=非确定

35、型 LBA（线性受限自动机）无限制文法=TM（图灵机）=NDTM但现在还不知道NDLBA=DLBA？,文法与机器的等价性,常用语法分析算法,对无二义BNF文法，已找到直接的语法分析技术。最早的技术是递归下降法。主要的进展是Knuth的LR文法（left to right parsing algorithms），可描述所有可用确定型下推自动机识别的BNF文法。确定型PDA等价于LR（K）文法（从左向右分析、向前看K个符号）该 PDA 可以确定是将下一个符号压栈，还是根据后面的K个符号，将栈顶符号弹出。LR（1）为了确定分析决策，只需向前看一个符号。SLRsimple LR，LR的子类LALRlo

36、okahead LRLL自顶向下技术，是递归下降的推广,Perl 概述,Perl(实用抽取和报告语言，Practical Extraction and Report Language)是一种解释型语言，用于高效的文本处理应用。由 Larry Wall 在 1986 年开发。一开始叫 PEARL，但因为和一种图形语言相冲突，所以缩写成现在的名字。该语言包括模式匹配、文件处理、以及标量数据。它的语法跟C语言的语法很相似，但它实质上是一种外壳脚本语言。其突出的特点就是它把程序和文件都看能使数据。它是一种能有效地与Web页面进行交互的编程语言。,Perl 的结构,变量要么是整型的，要么是字符串的，变量

37、都以符号$开头。一个简单的 Perl 程序由一组打印语句构成。它也具有那些通常的顺序控制结构，如：for,while,和 until 循环、以及 if 条件语句。Perl 也可以像其他处理语言那样处理正则表达式。例子：$ENVUSER=mvz 如果登陆用户名为 mvz，则表达式为真。这表明 Perl 可以和系统环境进行交互。,Perl 程序实例,1#!/usr/bin/perl 2 inputdata=split(/,);3$count=0;4 foreach$nextone(inputdata)5 print$nextone;6$count=$count+$nextone;7 print S

38、um=;8 print$countn;,Perl 的正则表达式,Perl 可以直接翻译正则表达式。例如，正则表达式 a+b+可以用 Perl 语言脚本实现如下：#!/usr/bin/perl#This is a Perl script$_=;#Read in input to argument$_if(/a+b+$/)then print“yesn”;else print“non”;#Match$_ with a+b+模式/X/由字符串参数来匹配。如果输入行从开始字符到结尾字符构成的字符串正好是正则表达式 a+b+，则模式匹配成功。如果只想知道某个字符串是否包含了 a+b+，只要用模式/a+b+/即可。,