编译原理（全套课件660p）（可编辑）

编译原理（全套课件660P）编译原理课时授课课时48实验课时8课程性质必修/考试考试方式闭卷考试主讲敬茂华JING_JMHTOM先修课程离散数学、组成原理、汇编语言、数据结构、C或其他程序设计语言第0章预备知识本门课程的目的和意义程序设计语言与程序的翻译程序设计语言的语法描述为什么要学习编译原理例INTFACTSTATICINTI5IFI0RETURNIELSEII1RETURNIABS1FACT/第9行,函数ABS求绝对值/MAINPRINTF“FACTOROF5D/N”,FACT上程序的运行结果是120。但是，如果把第9行的ABS1改成1的话，该程序结果是1。分析I是静态变量，所有地方对I的操作都是对同一地址空间的操作，所以每次递归进入FACT函数后，上一层对I的赋值仍然有效。由于C语言的编译机制，每次调用时，IABS1FACT中IABS1的值都先于FACT算出。所以，第1次递归时，所求值为5FACT，第2次递归时，所求值为4FACT，第3次递归时，所求值为3FACT，第4次递归时，所求值为2FACT，第5次递归时，所求值为1FACT，而此时FACT为1。这样，程序相当于是求一个阶乘函数54321，所以，结果为120。程序改动后结果变化，主要是和编译时代码生成策略有关。对于表达式IABS1FACT，因两个子表达式都有函数调用，因此，编译器先产生左子表达式代码，后产生右子表达式代码。当ABS1改为1后，左子表达式就没有函数调用了，于是，编译器会先产生右子表达式代码，这样一来，每次递归调用时，I1FACT中I1的值后于FACT算出。第1次递归时，所求值为I1FACT，第2次递归时，所求值为I1FACT，第5次递归时，所求值为I1FACT，而此时FACT为1，I为0，即实际上每次递归调用所求的实际都是1FACT，最后结果还是1。编译原理课程关注的内容面向机器的语言计算机的硬件只能识别由0、1字符串组成的机器指令序列，即机器指令程序。特点不易理解，编写程序既困难又容易出错。用容易记忆的符号来代替0、字符串。用符号表示的指令被称为汇编指令，汇编指令的集合被称为汇编语言，由汇编语言编写的指令序列被称为汇编语言程序。面向人类的语言通用程序设计语言，如，JAVA，C；数据查询语言，如；形式化描述语言，如EBNF、。其他面向特定应用领域的语言面向互联网应用的6HTML、XML；面向计算机辅助设计的MATLAB；面向集成电路设计的VHDL、VERILOG；面向虚拟现实的VRML；语言之间的翻译高级语言之间的翻译，一般被称为转换，如FORTRAN到ADA的转换等，或者被称为预处理，如SQL到C/C的预处理。高级语言可以直接翻译成机器语言，也可以翻译成汇编语言，这两个翻译过程是将高级语言的源程序翻译成低级语言的目标程序，这种翻译被称为编译。将一个汇编语言汇编为可在另一平台上运行的机器指令，则称为交叉汇编，而建立在交叉汇编基础之上的编译模式称为交叉编译。把机器语言翻译成汇编语言，或者把汇编语言翻译成高级语言，分别称它们为反汇编和反编译。上述语言之间的翻译虽然各不相同，但基本方法，特别是对源语言的分析方法是相同的。编译原理与编译技术编译原理与编译技术是两类不同的过程。编译原理研究的就是语言翻译方法中所用到的基本原理，关注的是产生编译器的理论和原理。一般并不深入讨论某一具体的编译器的实现和工作机制。编译技术更关注编写（实现）编译器过程中所用到的技术。编译原理是学习编译技术以及深入掌握利用高级语言进行编程的基础。通用程序设计语言的主要成份通用程序设计语言的典型特征之一是抽象，其抽象程度是以程序设计语言所支持的基本结构为特征的。可以大致划分为三种形式过程、模块（抽象数据类型，ADT）和类。以过程为基本结构的程序设计语言的典型代表有C、PASCAL等；以ADT为基本结构的程序设计语言的典型代表是ADA83；而以类为基本结构的程序设计语言包括当前流行的C、JAVA和ADA95等。这三种形式经过了一个演变过程，每一次演变都使得程序设计语言的抽象程度得到一次提高，同时也为这些程序设计语言的编译器提出了新的要求。类概念的引入，为利用程序设计语言构造类型提供了真正的支持，也是面向对象程序设计（OOP）语言的重要特征之一。程序设计语言提供的机制与程序设计的风格有着密切关系，以过程为基本抽象的程序设计语言支持的是过程式的程序设计范型（PARADIGM），以类为基本抽象的程序设计语言支持的是面向对象的程序设计范型，以ADT为基本抽象的程序设计语言介于二者之间，一般被认为是面向过程的语言，但也被认为是基于对象的语言。有些面向对象的程序设计语言是由过程式的语言发展而来的，如C、ADA95等，它们实质上是支持多范型的程序设计语言。本课程以PL/0（面向过程的语言）编译器为例，讨论把高级语言中应用最广的通用程序设计语言翻译成汇编语言程序所涉及的基本原理、技术和方法。这些原理、技术和方法也同样适用于其他各类翻译器的构造，同时有些技术和方法也可以被用于其他软件设计。内容上以最简单的、以过程为基本结构的程序设计语言为背景进行讨论。因为无论何种形式的程序设计语言，均是由声明和操作这样两个基本元素构成的，所不同的是声明和操作的范围和复杂程度不同。以过程为基本结构的程序设计语言的特征是把整个程序作为一个过程。过程的定义由两类语句组成声明性语句和操作性语句。一般来讲，声明性语句提供所操作对象的性质，如数据类型、值、作用域等。而操作性语句确定操作的计算次序，完成实际操作。本门课程的目的和意义计算机问题求解的基本途径对问题进行抽象和形式化表示，然后进行处理。掌握形式语言与自动机理论。掌握编译原理及方法。了解编译程序的实现原理和技术。培养形式化描述和抽象思维能力。利用从本课程学到的知识，增强编写和调试程序的能力。编译原理及技术在其他方面的应用正文查找正文处理指令识别等程序设计语言与程序的翻译一般的程序设计语言的定义都涉及语法、语义和语用三个方面。由符号（单词）构成语法成分的规则称为一般语法规则。由基本符号构成的符号（单词）书写规则特称为词法规则。程序设计语言的语法描述语法图BNF范式；语法成分的定义；|表示“或者”扩充的BNF范式增加了三个符号X表示X可以出现0到多次。X表示X可能出现，也可能不出现。（X|Y）表示X和Y二者取一。文法口语第一章概述11什么是编译程序12编译的基本过程13编译程序的逻辑结构14决定编译阶段组合的因素15与编译器相关的程序16编译器的翻译步骤17编译器中的主要数据结构18编译器结构的其他观点直观印象两数之和的程序8086/8088机器语言的程序10100000000000010000000010001010001001100000001000000000000000001110000010100010000000110000000011110100IBMPC汇编语言的程序STARTMOVAX,DSEGMOVDS,AXMOVAL,DATA1MOVAH,DATA2ADDAL,AHMOVRLT,ALHLT11什么是编译程序COMPILER编译程序是现代计算机系统的基本组成部分。从功能上看，一个编译程序就是一个语言翻译程序,它把一种语言称作源语言书写的程序翻译成另一种语言称作目标语言的等价的程序。什么是编译程序语言转变）换系统111编译程序的功能112翻译程序的种类汇编程序用于特定计算机上的汇编语言的翻译程序。编译程序将高级语言翻译成低级语言的翻译程序解释程序将会话式语言翻译成目标指令的翻译程序编译程序与解释程序的根本区别113编译程序生成的目标程序的形式可立即执行的机器语言代码汇编语言程序待装配的机器语言代码模块114什么叫机器语言计算机提供的基本操作称为指令。指令的全体称为指令系统。指令系统也称为机器语言。指令的基本形式115什么是编译系统116编译理论和编译器的发展史12编译的基本过程词法分析从左至右读字符流的源程序、识别拼单词例POSITIONINITIALRATE60词法分析POSITIONINITIALRATE60单词类型单词值标识符1ID1POSITION算符赋值标识符2ID2INITIAL算符加标识符3ID3RATE算符乘整数60分号；语法分析功能层次分析。依据源程序的语法规则把源程序的单词序列组成语法短语表示成语法树。POSITIONINITIALRATE60规则“”“”“”“”“”ID1ID2ID3N语义分析语义审查静态语义上下文相关性类型匹配类型转换语义分析中间代码生成源程序的内部中间表示三元式、四元式、PCODE、CCODE、UCODE、BYTECODEID3T1T2T2ID3T1T2ID3T1中间代码生成代码优化代码优化T1BCT1BCT2T10T2T1T1T3BCAT2T4T2T3AT4目标代码生成符号表管理记录源程序中使用的名字收集每个名字的各种属性信息类型、作用域、分配存储信息出错处理检查错误、报告出错信息、排错、恢复编译工作13编译程序的逻辑结构COMPONENTS词法分析程序语法分析程序语义分析程序中间代码生成程序代码优化程序目标代码生成程序符号表管理程序出错处理程序14决定编译阶段组合的因素分析，综合SYNTHESIS源程序的分析线性分析层次分析语义分析目标程序的综合编译的前端（FRONTEND）编译的后端（BACKEND）遍（趟）从头到尾扫描源程序（各种形式）一遍PASS。15与编译器相关的程序翻译程序编译程序（COMPLIER）解释程序（INTERPRETOR）汇编程序（ASSEMBLER）连接程序（LINKER）装入程序（LOADER）预处理程序（PREPROCESSOR）编辑器（EDITOR）调试程序（DEBUGGER）描述器（PROFILER）项目管理程序（PROJECTMANAGER）16编译器的翻译步骤例AINDEX42一、扫描程序（SCANNER）8个记号（或单词）（TOKEN）A标识符左括号INDEX标识符右括号4数字加号2数字二、语法分析程序（PARSER）三、语义分析程序（SEMANTICANALYZER）四、源代码优化程序（SOURCECODEOPTIMIZER）五、代码生成器（CODEGENERATOR）17编译器中的主要数据结构记号（TOKEN）（也叫单词）语法树（SYNTAXTREE）符号表（SYMBOLTABLE）常数表（LITERALTABLE）中间代码（INTERMEDIATECODE）临时文件（TEMPORARYFILE）补充知识高级语言解释系统INTERPRETER功能让计算机执行高级语言（BASIC,LISP,PROLOG与编译程序的不同1）不生成目标代码2）能支持交互环境（同增量式编译系统）源程序初始数据解释系统直接对源程序中的语句进行分析，执行其隐含的操作。如B2AB2编译程序WRITEA解释程序直接将4的值输出（显示）编译阶段和运行阶段存储结构编译时运行时解释系统存储结构13编译技术的发展和应用功能程序集成环境实现方式手工机器语言汇编系统程序设计语言自动构造工具LEXYACCGCC编译程序的发展编译程序的发展语言范型PARADIGMS命令式IMPERATIVELANGUAGE应用式APPLICATIVE基于规则的（RULEBASED）面向对象的（OBJECTORIENTED）编译程序执行环境批处理交互环境嵌入系统环境语言范型（支持的计算模式）命令式程序特点语言执行的解释编译技术发展快语句1；改变机器状态系统语言语句2；内存自动化生成技术语句3；各种寄存器的内容外存与冯诺伊曼机的体系结构一般应用式（函数式）程序特点FUNCTIONNFUNETION2FUNETION1DATA程序执行执行一个个函数施用在数据上的变换最终得到的结果编译语法分析容易；语义处理复杂；基于规则的语言（PROLOG,YACC程序特点使能条件1动作1使能条件2动作2使能条件3动作3面向对象语言抽象数据类型，继承机制编译动态绑定；执行环境批处理环境将源程序作为整体处理排除程序错误不能依靠用户的外部帮助交互环境解释增量式编译嵌入式系统环境交叉编译分布并行环境并行编译程序创建和测试环境独立编译编译和调试同时设计考虑编译技术的发展和应用结构化编译器程序分析工具静态分析动态分析度量工具结构度量模块接口复杂度C分析工具SOURCEINSIGHT广泛的语言领域数据库系统查询脚本语言置标语言SGMLHTMLXML研究领域并行编译技术交叉编译技术硬件描述语言及其编译技术并行化编译技术目的提高并行计算机体系结构的性能。超大规模计算的日益增长的需求高性能计算机并行软件并行体系结构编译技术支持串行程序并行化编译技术支持并行程序设计语言编译依赖于目标机的优化（低层）并行算法复杂，难掌握，难编程开发并行软件的困难并行程序的不确定行为，难调试，验证设计新的并行算法修改已有串行程序尽量（直接用并行程序并行化（研究算法和设计语言和并行程应用的人同时工作）序库实现。HPFOCCOMPVM嵌入式硬件描述语言及其编译技术电路设计依据验证结果如VHDL第一章小结内容1什么是编译程序2编译过程和编译程序的结构3为什么要学习编译程序本章没有难以理解的内容,重点对编译程序的功能和结构做一综述,要说难点的话可能是了解编译程序各个成分在编译阶段的逻辑关系以及他们怎样作为一个整体完成编译任务的。参考书TOMASPITTMN,THEARTOFCOMPILERDESIGNTHEORYANDPRACTICE,PRENTICEHALL1992ALFREDVAHO,RAVISETHI,JEFFREYDULLMAN,COMPILERSPRINCIPLES,TECHNIQUESANDTOOLSADDISSONWESLEY1986陈火旺刘春林等程序设计语言编译原理国防工业出版社2000DAVIDAWATT（常量说明部分）VARB,C（变量说明部分）PROCEDUREP（过程说明部分）VARDPROCEDUREQVARXBEGINREADXDXWHILEX0DOCALLPENDBEGINWRITEDCALLQENDBEGINCALLPENDPL/0语言文法的EBNF表示EBNF引入的符号元符号用左右尖括号括起来的语法成分为非终结符定义为的左部由右部定义|或表示花括号内的语法成分可重复任意次或限定次数表示方括号内的语法成分为任选项表示圆括号内的成分优先例用EBNF描述的定义|0|1|2|3|4|5|6|7|8|9或更好的写法|01|2|3|4|5|6|7|8|90|PL/0语言是PASCAL语言的子集同PASCAL作用域规则（内层可引用包围它的外层定义的标识符），上下文约束，过程可嵌套定义，可递归调用子集数据类型,只有整型数据结构,只有简变和常数数字最多为14位标识符的有效长度是10语句种类过程最多可嵌套三层目标代码类PCODE目标代码类PCODE是一种假想栈式计算机的汇编语言。指令格式CONSTA10VARB,CPROCEDUREPBEGINCBAENDBEGINREADBWHILEB0DOBEGINCALLPWRITE2CREADBENDEND0JMP08转向主程序入口1JMP02转向过程P入口2INT03过程P入口,为过程P开辟空间3LOD13取变量B的值到栈顶4LIT010取常数10到栈顶5OPR02次栈顶与栈顶相加6STO14栈顶值送变量C中7OPR00退栈并返回调用点168INT05主程序入口开辟5个栈空间9OPR016从命令行读入值置于栈顶10STO03将栈顶值存入变量B中11LOD03将变量B的值取至栈顶12LIT00将常数值0进栈13OPR09次栈顶与栈顶是否不等14JPC024等时转24（条件不满足转）15CAL02调用过程P16LIT02常数值2进栈17LOD04将变量C的值取至栈顶18OPR04次栈顶与栈顶相乘2C19OPR014栈顶值输出至屏幕20OPR015换行21OPR016从命令行读取值到栈顶22STO03栈顶值送变量B中23JMP011无条件转到循环入口1124OPR00结束退栈PL/0编译程序的结构PL/0编译程序的总体设计其编译过程采用一趟扫描方式以语法、语义分析程序为核心词法分析程序和代码生成程序都作为一个过程，当语法分析需要读单词时就调用词法分析程序，而当语法、语义分析正确，需要生成相应的目标代码时，则调用代码生成程序。表格管理程序实现变量，常量和过程标识符的信息的登录与查找。出错处理程序，对词法和语法、语义分析遇到的错误给出在源程序中出错的位置和与错误性质有关的编号，并进行错误恢复。PL/0编译程序词法分析的设计与实现识别的单词保留字或关键字如BEGIN、END、IF、THEN等运算符如、/、等标识符用户定义的变量名、常数名、过程名常数如10、25、100等整数界符如,、等词法分析过程GETSYM所要完成的任务读源程序（GETCH滤空格识别保留字识别标识符拼数识别单字符单词拼双字符单词词法分析过程GETSYM框图（见教材图25）程序（PROCEDUREGETSYM）当识别到标识符时先查保留字表保留字表（BEGINMAIN）WORD1BEGIN；WORD2CALL；WORD13WRITE；查到时找到相应的内部表示WSYM1BEGINSYMWSYM2CALLSYM；WSYM13WRITESYM；字符对应的单词表SSYMPLUSSSYMMINUSSSYMSEMICOLON词法分析如何把单词传递给语法分析TYPESYMBOLNUL,IDENT,NUMBER,PLUS,VARSYM,PROCSYM；3个全程量SYMSYMBOLIDALFANUMINTEGER通过三个全程量SYM、ID和NUM将识别出的单词信息传递给语法分析程序。SYM存放单词的类别如有程序段落为BEGININITIAL60；END对应单词翻译后变为BEGINBEGINSYM,INITIALIDENT,BECOMES,60NUMBER,；SEMICOLON，ENDENDSYM。ID存放用户所定义的标识符的值如INITIAL（在SYM中放IDENT，在ID中放INITIAL）NUM存放用户定义的数如60（在SYM中放在NUMBER在NUM中放60）使用状态转换图实现词法分析程序的设计方法词法分析程序的设计使用状态转换图实现PL/0编译程序语法语义分析PL/0编译程序语法分析的设计与实现自顶向下的语法分析递归子程序法自顶向下的语法分析VARABEGINREADAENDVAR；ABEGINENDREAD（）A递归子程序法递归子程序法对应每个非终结符语法单元，编一个独立的处理过程（或子程序）。语法分析从读入第一个单词开始，由非终结符（即开始符）出发，沿语法描述图箭头所指出的方向进行分析。当遇到非终结符时，则调用相应的处理过程，从语法描述图看，也就进入了一个语法单元，再沿当前所进入的语法单元所指箭头方向继续进行分析。当遇到描述图中是终结符时，则判断当前读入的单词是否与图中的终结符相匹配，若匹配，再读取下一个单词继续分析。遇到分支点时，将当前的单词与分支点上多个终结符逐个相比较，若都不匹配时可能是进入下一个非终结符语法单位或是出错。编译程序总体流程图PL/0编译程序语义分析的设计与实现PL/0编译程序语法、语义分析的的核心程序是BLOCK过程，说明部分的分析与处理表格管理过程体语句）的分析与处理说明部分的分析与处理对每个过程（含主程序）说明的对象（变量，常量和过程）造符号表登录标识符的属性。标识符的属性种类，所在层次,值和分配的相对位置。登录信息由ENTER过程完成。符号表TXTABLE表的下标指针,是以值参数形式使用的。DX计算每个变量在运行栈中相对本过程基地址的偏移量，放在TABLE表中的ADR域，生成目标代码时再放在CODE中的A域过程体的处理对语句进行语法分析语义分析当遇到标识符的引用时就调用POSITION函数查TABLE表，看是否有过正确定义，若已有，则从表中取相应的有关信息，供代码的生成使用。若无定义则错。当语法语义正确时，就生成相应语句功能的目标代码代码生成代码生成是由过程GEN完成。GEN有3个参数，分别代表目标代码的功能码，层差和位移量。例如GENOPR,0,16GENSTO,LEVLEVEL,ADRLEV当前处理的过程层次LEVEL被引用变量或过程所在层次CX为目标代码CODE数组的下标指针PL/0编译程序错误处理的实现对语法错误的两种处理方法1对于易于校正的错误，如丢了逗号，分号等，指出出错位置，加以校正，继续进行分析。2对于难于校正的错误，给出错误的位置与性质，跳过后面的一些单词，直到下一个可以进行正常语法分析的语法单位。在进入某个语法单位时，调用TEST,检查当前符号是否属于该语法单位的开始符号集合。若不属于，则滤去开始符号和后继符号集合外的所有符号。在语法单位分析结束时，调用TEST,检查当前符号是否属于调用该语法单位时应有的后继符号集合。若不属于，则滤去后继符号和开始符号集合外的所有符号。类PCODE代码解释器的实现类PCODE解释器的结构目标代码解释执行时数据栈的布局（运行栈的存储分配）类PCODE解释器的结构目标代码存放在数组CODE中。解释程序定义一个一维整型数组S作为运行栈栈顶寄存器（指针）T，基址寄存器（指针）B，程序地址寄存器P，指令寄存器I目标代码解释执行时数据栈的布局（运行栈的存储分配）在每个过程调用时在栈顶分配3个联系单元SL静态链，指向定义该过程的直接外过程（或主程序）运行时最新数据段的基地址。DL动态链，指向调用该过程前正在运行过程的数据段基地址。RA返回地址，记录调用该过程时目标程序的断点，即调用过程指令的下一条指令的地址。目标代码的解释执行运行栈SM调用过程Q目标代码的解释执行几条特殊指令在CODE中的位置和功能INT0A在过程目标程序的入口处，开辟A个单元的数据段。A为局部变量的个数3。OPR00在过程目标程序的出口处，释放数据段（退栈），恢复调用该过程前正在运行的过程的数据段基址寄存器B和栈顶寄存器T的值，并将返回地址送到指令地址寄存器P中，以使调用前的程序从断点开始继续执行。目标代码的解释执行几条特殊指令在CODE中的位置和功能CALLA调用过程，还完成填写静态链、动态链、返回地址，给出被调用过程的基地址值，送入基址寄存器B中，目标程序的入口地址A的值送指令地址寄存器P中，使指令从A开始执行。附运行时数据栈S的变化状态教材25页第三章文法和语言本章目的为语言的语法描述寻求工具工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读）形式工具形式语言抽象地定义为一个数学系统。“形式”是指这样的事实语言的所有规则只以什麽符号串能出现的方式来陈述本章知识点内容引言和预备知识文法和语言的形式定义文法的类型上下文无关文法及其语法树上下文无关文法的句型分析有关文法实用中的一些说明31文法的直观概念和语言概述当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题给出一些规则，用这些规则来说明或者定义句子的组成结构。“我是大学生”。是汉语的一个句子句子主语谓语主语代词名词代词我你他名词王明大学生工人英语谓语动词直接宾语动词是学习直接宾语代词名词有了一组规则以后，按照如下方式用它们导出句子开始去找左端的带有句子的规则并把它由右端的符号串代替，这个动作表示成句子主语谓语，然后在得到的串主语谓语中，选取主语或谓语，再用相应规则的右端代替之。比如，选取了主语，并采用规则主语代词，那么得到主语谓语代词谓语，重复做下去，句子“我是大学生”的全部动作过程是句子主语谓语代词谓语我谓语我动词直接宾语我是直接宾语我是名词我是大学生“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。注用于产生其他语言的语言称为元语言。32编译原理所涉及到的一些数学概念和运算集合笛卡儿乘积关系符号串321集合概念表示法（1）枚举法1,2,3（2）谓词法X|X32特性（1）唯一性（2）确定性集合间的关系相等、不相等、子集集合的运算并集、交集、差集、幂集322笛卡儿乘积序偶由两个按一定次序排列的客体组成的序列，记为（X，Y）N重序组由N个按一定次序排列的客体组成的序列，记为（X1，X2，XN）笛卡儿乘积A、B为任意两个集合，若序偶的第一个成员是集合A的一个元素，第二个成员是集合B的一个元素，则所有这样的序偶组成的集合称为集合A和B的笛卡儿乘积。323关系定义关系矩阵和关系图关系的基本性质1、自反2、非自反3、对称4、非对称5、传递关系的乘积关系的传递闭包自反传递闭包33有关定义和记号符号可以相互区别的记号（元素）。字母表符号（元素）的非空有穷集合。符号串由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。1空符号串没有符号的符号串是上的符号串2若X是上的符号串,A是的元素,则XA是上的符号串3Y是上的符号串,当且仅当它可以由1和2导出。例如A,B,A,B,AA,AB,AABBA都是上的符号串介绍有关符号串的一些运算符号串的头,尾，固有头和固有尾如果ZXY是一符号串，那么X是Z的头，Y是Z的尾，如果X是非空的，那么Y是固有尾；同样如果Y非空，那么X是固有头。举个例子设ZABC,那么Z的头是,A,AB,ABC,除ABC外，其它都是固有头；Z的尾是,C,BC,ABC,Z的固有尾是,C,BC。当对符号串ZXY的头感兴趣而对其余部分不感兴趣时，采用省略写法ZX；如果只是为了强调X在符号串Z中的某处出现，则可表示为ZX；符号T是符号串Z的第一个符号，则表示为ZT。符号串的连接设X和Y是符号串，它们的连接XY是把Y的符号写在X的符号之后得到的符号串由于的含义，显然有XXX。例如XST，YABU，则它们的连接XYSTABU，看出X2，Y3，XY5符号串的方幂符号串自身连接N次得到的符号串AN定义为AAAAN个AA1A,A2AA且A0例；若XAB则X0X1ABX2ABABX3ABABABXNXXN1XN1XN0符号串集合若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。两个符号串集合A和B的乘积定义为ABXY|XA且YB若集合AAB,CDEB0,1则ABAB1,AB0,CDE0,CDE1使用表示上的一切符号串（包括）组成的集合。称为的闭包。上的除外的所有符号串组成的集合记为。称为的正闭包。例A,B,A,B,AA,AB,BA,BB,AAA,AAB,A,B,AA,AB,BA,BB,AAA,AAB,有关定义和记号语言是由句子组成的集合，是由一组符号所构成的集合。换言之,字母表上的一个语言是上的一些符号串的集合字母表上的每个语言是的一个子集。例如字母表A,B,A,B,AA,AB,BA,BB,AAA,AAB,集合AB,AABB,AAABBB,ANBN,或表示为W|W且WANBN,N1为字母表上的一个语言。集合A,AA,AAA,或表示为W|W且WAN,N1为字母表上的一个语言。是一个语言。即是一个语言。34文法和语言的形式定义语言是由句子组成的集合，是由一组符号所构成的集合。汉语所有符合汉语语法的句子的全体英语所有符合英语语法的句子的全体程序设计语言所有该语言的程序的全体每个句子构成的规律研究语言每个句子的含义每个句子和使用者的关系程序设计语言的概念和描述方法程序设计语言是形式语言，其定义和描述包括语法、语义和语用三个方面。程序设计语言的语法实际上是一组规则。程序设计语言的语句可分为两大类1、非执行语句2、可执行语句描述程序程序设计语言的语法规则的有效工具是文法中的上下文无关文法。语言研究的三个方面语法SYNTAX语义SEMANTICS语用PRAGMATICS语法表示构成语言句子的各个记号之间的组合规律，即句子的组成结构。语义表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）语用表示在各个记号所出现的行为中，它们的来源、使用和影响。每种语言具有两个可识别的特性，即语言的形式和该形式相关联的意义。语言的实例若在语法上是正确的，其相关联的意义可以从两个观点来看，其一是该句子的创立者所想要表示的意义，另一是接收者所检验到的意义。这两个意义并非总是一样的，前者称为语言的语义，后者是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式”是指这样的事实语言的所有规则只以什麽符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。文法和语言的形式定义如何来描述一种语言如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经生成方式（文法）语言中的每个句子可以用严格定义的规则来构造。识别方式（自动机）用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要麽能停止并回答“不是”，（要麽永远继续下去。）文法即是生成方式描述语言的语言中的每个句子可以用严格定义的规则来构造下面给出文法的定义进而在文法的定义的基础上，给出推导的概念，句型、句子和语言的定义。定义文法G定义为四元组VN，VT，P，S其中VN为非终结符号或语法实体，或变量集；VT为终结符号集；P为产生式也称规则的集合；VN，VT和P是非空有穷集。S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。VN和VT不含公共的元素，即VNVT用V表示VNVT，称为文法G的字母表或字汇表规则，也称重写规则、产生式或生成式，是形如或的，有序对，其中是字母表V的正闭包V中的一个符号，是V中的一个符号。称为规则的左部，称作规则的右部。文法的定义例文法G（VN，VT，P，S）VNS,VT0,1PS0S1,S01S为开始符号例文法G（VN，VT，P，S）VN标识符，字母，数字VTA,B,C,X,Y,Z,0,1,9PA,Z0,9S文法的写法1GSAABAABAAABA2GSAABAAABASASB3GSAAB|AAB|SASB元符号|习惯表示大写字母终结符小写字母非终结符SABAAX|YBZ推导的定义直接推导“”是文法G的产生式，若有V,W满足V,W,其中V,V则称V直接推导到W,记作VW也称W直接归约到V例GS0S1，S010S100S1100S11000S111000S11100001111S0S1VARBEGINREADENDVARABEGINREADEND推导的定义若存在VW0W1WNW,N0则记为VW，V推导出W，或W归约到V若有VW，或VW，则记为VW例GS0S1，S010S100S1100S11000S111000S11100001111S0S100S11000S11100001111S00001111SS00S1100S11句型、句子的定义句型有文法G，若SX，则称X是文法G的句型。句子有文法G，若SX，且XVT，则称X是文法G的句子。例GS0S1，S01S0S100S11000S11100001111G的句型S,0S1,00S11,000S111,00001111G的句子00001111,01例GEEET|TTTF|FFE|AEETTTFTATATFAFFAAFAAA句子用符号A，和构成的算术表达式文法，语言的定义由文法G生成的语言记为LG,它是文法G的一切句子的集合LGX|SX，其中S为文法的开始符号，且XVT例GS0S1，S01LG0N1N|N1例文法GS（1）SASBE（2）SABE（3）EBBE（4）ABAB（5）BBBB（6）BEBE（7）EEEEL（G）ANBNEN|N1SASBESASBEAABEBESABEAABEBEABABAABBEEEBBEAABBEE（BBBBAABBEE（BEBEAABBEE（EEEEG生成的每个串都在LG中LG中的每个串确实能被G生成使用产生式1N1次，得到推导序列SAN1SBEN1，然后使用产生式2一次，得到SAN1SBEN1ANBEN。然后从ANBEN继续推导，总是对EB使用产生式3的右部进行替换，而最终在得到的串中，所有的B都先于所有的E。例如，若N3,AAABEBEBEAAABBEEBEAAABBEBEEAAABBBEEE。即有SANBNEN接着，使用产生式4一次，得到SANBBN1EN，然后使用产生式5N1次得到SANBNEN，最后使用产生式6一次，使用产生式7N1次，得到SANBNEN也能证明，对于N1，串ANBNEN是唯一形式的终结符号串文法的等价若L（G1）L（G2），则称文法G1和G2是等价的。如文法G1AA0R与G2SS0S1等价A01S01RA1文法的类型通过对产生式施加不同的限制，CHOMSKY将文法分为四种类型0型文法对任一产生式，都有VNVT，VNVT1型文法对任一产生式，都有|，仅仅S除外2型文法对任一产生式，都有VN，VNVT3型文法任一产生式的形式都为AAB或AA，其中AVN，BVN，AVT文法的类型例1型（上下文有关）文法文法GSSCDABBACACABAABCBCBBBBBADADCBDBDDAABD文法的类型例2型（上下文无关）文法文法GSSABABS|0BSA|13型文法GSS0A|1B|0A0A|1B|0SB1B|1|0GIILTILTLTTDTTLTD文法的类型四种文法之间的逐级“包含”关系文法和语言0型文法产生的语言称为0型语言1型文法或上下文有关文法（CSG）产生的语言称为1型语言或上下文有关语言（CSL）2型文法或上下文无关文法（CFG）产生的语言称为2型语言或上下文无关语言（CFL）3型文法或正则（正规）文法（RG）产生的语言称为3型语言正则（正规）语言（RL）根据形式语言理论,文法和识别系统间有这样的关系0型文法（短语结构文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何0型语言都是递归可枚举的1型文法（上下文有关文法）产生式的形式为1A212，即只有A出现在1和2的上下文中时，才允许取代A。其识别系统是线性界限自动机。2型文法（上下文无关文法CFG）产生式的形式为A，取代A时与A的上下文无关。其识别系统是不确定的下推自动机。3型文法（正规文法RG）产生的语言是有穷自动机（FA）所接受的集合上下文无关文法及其语法树上下文无关文法有足够的能力描述程序设计语言的语法结构语法树句型推导的直观表示例文法GE,I,P,E其中P为EI,EEE,EEE,EEE表示算术表达式,I表示程序的“变量”，该文法定义了由变量，,和组成的算术表达式的语法结构，即变量是算术表达式；若E1和E2是算术表达式，则E1E2，E1E2和E1也是算术表达式描述一种简单赋值语句的产生式赋值语句IE描述条件语句的产生式条件语句IF条件THEN语句IF条件THEN语句ELSE语句句型、推导GEEET|TTTF|FFE|AEETTTFTATATFAFFAAFAAAEETETFETAEFAEAATAAFAAAAAEETTTTTFFTFFFFAFFAFAAAA规范推导规范句型最左（最右）推导在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换最右推导被称为规范推导。由规范推导所得的句型称为规范句型语法树设GVN,VT,P,S为一上下文无关文法，若一棵树满足下列4个条