《编译技术导论》全套教学课件

编译技术导论第1章绪论第2章高级语言设计基础第3章词法分析第4章自上而下的语法分析第5章自下而上的语法分析第6章语法制导的翻译第7章中间代码生成第8章过程存储分配第9章目标代码生成第10章国产编译器进展第11章词法分析工具Lex第12章语法分析工具yacc全套可编辑PPT课件

第1章绪论content目录01编译器的定义与功能02程序语言的类型03编译过程和编译器的结构04解释程序及软件工具05编译技术的发展历程及典型编译器06本章总结编译器的定义与功能01编译器定义编译器是将高级语言源代码自动转换为机器语言或中间代码的程序，实现从人类可读到机器可执行的翻译。语言桥梁作为高级语言与硬件之间的桥梁，编译器屏蔽底层复杂性，使程序员专注逻辑实现。自动化转换通过词法、语法和语义分析等阶段，编译器精确完成代码解析与目标代码生成。高级语言源代码→编译器→机器语言目标码作为连接人类可读代码与硬件可执行指令的核心工具，编译器不仅进行语言翻译，更承担着错误检查、性能优化等关键任务，是现代软件开发的基石。编译器及其在高级语言与机器语言之间的桥梁作用阐述编译器在软件开发效率与程序可靠性中的关键地位提升开发效率编译器自动转换高级语言为机器代码，大幅减少手工编写低级代码的时间与错误。保障程序可靠性通过语法与语义检查，编译器能在运行前发现错误，提升程序稳定性。支持代码优化编译器在生成目标代码时进行优化，提高程序执行效率与资源利用率。增强可维护性高级语言的抽象特性结合编译技术，使代码更易理解、修改和扩展。解析编译器与解释器的本质区别及其应用场景执行方式差异编译器预先将源代码整体翻译为机器码，生成独立的目标程序；解释器则逐行翻译并立即执行；两者处理时机和方式截然不同。运行效率对比编译型程序执行时无需翻译，效率高、速度快；解释型程序每次运行都要翻译，开销较大；适合对性能要求不同的场景错误检测时机编译器在编译阶段集中报错，便于提前修复；解释器在运行时逐行检测，错误出现在执行时刻；调试时更易定位问题。应用场景区别编译器多用于C、C++等高性能语言；解释器常用于Python、JavaScript等脚本语言；适应开发效率与执行效率的不同需求。开发调试便利性解释器支持即时反馈，便于动态调试；编译器需反复编译链接，调试周期较长；解释型环境更适合快速迭代开发。代码移植性编译后的代码依赖特定平台，移植性差；解释器跨平台运行只需安装对应环境；解释型语言通常具备更好的可移植性。解释执行：逐句翻译的即时运行与编译器不同，解释器边读边执行源代码，无需生成独立的目标文件。这种方式提供了极佳的交互性，但通常执行效率较低。1.读取源程序:逐行读取代码。2.语法/语义分析:对当前语句进行分析和检查。3.执行:将语句转换为内部表示并立即执行。4.结果反馈:立即显示执行结果。BASICLISPSQLPython程序语言的类型02对比机器语言、汇编语言与高级语言的技术特征与演进逻辑01机器语言由二进制代码构成，计算机硬件可直接执行。编写困难，缺乏可读性和移植性。运行效率高，但开发维护成本大。02汇编语言使用助记符表示指令，比机器语言更易理解。需通过汇编器转换为机器码。贴近硬件，常用于底层系统编程。03高级语言语法接近自然语言，可读性强。具备良好可移植性，广泛用于应用开发。通过编译器转化为低级代码执行。04语言层级从低到高分为机器、汇编和高级语言。层级越高越接近人类思维。不同层级对应不同的抽象程度。05翻译机制汇编语言需汇编器转换。高级语言依赖编译器或解释器。机器语言无需翻译，直接执行。06开发效率高级语言显著提升开发效率。低级语言控制精细但编码复杂。语言选择需权衡效率与可维护性。剖析过程式、面向对象与函数式编程语言的设计哲学差异过程式语言以过程和函数为核心，通过指令序列明确控制执行流程，强调程序的线性执行与步骤分解。面向对象语言将数据与操作封装于对象中，通过继承、多态实现模块化设计，提升代码复用性与可维护性。函数式语言以纯函数和不可变性为基础，避免副作用，支持高阶函数，适合并发与逻辑推导场景。探讨声明式、逻辑式与脚本语言在特定领域的应用优势描述目标而非步骤，关注‘做什么’而不是‘如何做’SQL用于数据库查询，提升代码可读性和维护性广泛应用于配置定义和声明式编程场景。基于形式逻辑和规则推理，支持符号计算。Prolog常用于人工智能和专家系统开发。适合解决需要演绎推理和模式匹配的问题。Python和JavaScript语法简洁，支持动态执行广泛用于Web开发、自动化与快速原型构建。显著降低编程门槛，提高开发效率。强调纯函数和不可变数据，避免副作用。支持高阶函数和递归，适合并发编程以对象为核心，封装数据和行为支持继承、多态和模块化设计。按步骤组织代码，强调流程控制和函数调用。C和Pascal为代表，适用于系统级编程编程语言范式声明式语言逻辑式语言脚本语言函数式语言面向对象过程式语言编译过程和编译器的结构03编译器基本结构词法分析器语法分析器语义分析器源程序中间代码生成器代码优化器代码生成器目标程序出错管理器符号表管理器图1.1编译器基本结构词法分析将字符流转化为有意义的词法单元序列输入与输出词法分析器以源代码字符流为输入，输出为词法单元（Token）序列，作为语法分析的基础。词法单元构成每个词法单元包含类型（如关键字、标识符）和属性值（如变量名、常数值），体现语言基本单位。处理机制逐字符扫描源码，跳过空白与注释，依据词法规则识别符号，发现非法字符时报告词法错误。163词法分析将字符流转化为有意义的词法单元序列字符流→Token序列intmain(){return0;}↓关键字int标识符main分隔符(分隔符)分隔符{关键字return…词法分析是编译的第一阶段，其核心任务是读取源代码字符流，并根据词法规则将其分割成有意义的词法单元（Token）。过滤无关内容：跳过注释、空白等不影响程序语义的字符。识别词法单元：利用正则表达式识别关键字、标识符、常数等，并归类。报告词法错误：识别并报告非法符号或不符合规则的字符序列。解析语法分析构建抽象语法树（AST）的文法驱动机制语法分析作用将词法单元序列组织成语法结构正确的抽象语法树，验证代码是否符合语言文法规则。文法驱动解析基于上下文无关文法（CFG）规则，逐级推导出程序的层次化语法结构。AST结构意义以树形结构表示程序语法成分的嵌套关系，为后续语义分析和代码生成提供基础。说明语义分析在类型检查、符号解析与上下文验证中的作用操作数类型匹配，确保表达式中各操作数类型兼容。运行时类型检查，防止非法类型转换和调用。标识符绑定，关联变量声明与引用的位置。作用域验证，确保标识符在正确范围内可见和使用。路径完整性，验证所有分支和循环结构合法。不可达代码检测，标记无法执行到的语句。参数数量匹配，检查实参与形参个数一致。参数类型校验，确保每个实参类型符合形参要求。变量初始化检查，确保使用前已完成赋值。重复声明检测，防止同一作用域内多次定义同一标识符。运算符语义检查，验证操作符适用于操作数类型。副作用分析，识别表达式对程序状态的影响。语义分析类型安全符号表管理控制流检查函数调用上下文验证表达式分析介绍中间代码（IR）的形式化表达及其在跨平台编译中的价值01中间代码定义中间代码（IR）是源语言与目标机器之间的抽象表示，便于进行语言无关的分析与优化。02形式化表达结构IR采用三地址码、静态单赋值等形式，精确描述程序语义，支持控制流与数据流建模。03跨平台价值IR屏蔽源语言和目标架构差异，实现一次编译、多平台生成，提升编译器可移植性。分析静态单赋值（SSA）形式对优化效率的提升机制单赋值特性每个变量仅被赋值一次，简化变量生命周期管理。该特性使数据流关系更加清晰。有助于提升编译器分析精度。显式定义使用明确变量的定义与使用路径。增强依赖关系的可追踪性。利于优化过程中的正确性验证。提升数据流分析减少歧义，加速数据流传播。提高分析算法的效率与准确性。支持更复杂的程序变换。优化依赖追踪精确捕捉变量间的依赖关系。有效支持重排序与并行化优化。降低误判风险。常量传播应用利用SSA形式快速传播常量值。识别更多可优化点。提升执行效率。死代码消除通过未使用定义识别冗余代码。安全移除无影响指令。减小代码体积。GIMPLE表示集成GCC中将代码转换为GIMPLE中间表示。结合SSA提升分析能力。支持多层级优化。循环分析强化在SSA基础上精确分析循环内变量变化。提升循环优化效果。如循环不变量提取。展示循环优化、常量传播与死代码消除等典型优化策略循环优化通过循环展开、不变式外提等手段减少循环开销，提升指令级并行性与执行效率。常量传播将变量的常量值在编译期代入后续计算，消除冗余运算，简化表达式求值过程。死代码消除识别并移除不影响程序输出的无用代码，减小目标代码体积并提高运行性能。优化协同作用多种优化策略联动执行，层层递进，显著提升程序整体执行效率与资源利用率。代码优化：让程序跑得更快更小代码优化是编译器的核心任务之一，它在不改变程序语义的前提下，对中间代码进行等价变换，以提高执行效率、减少资源消耗。局部优化针对程序中的基本块进行优化，如：循环优化、死代码消除。全局优化考虑整个程序的控制流和数据流进行优化，如：公共子表达式消除、常量传播。目标代码生成器将优化后的中间表示映射为机器指令核心功能将优化后的中间代码转换为目标平台的机器指令，实现高级语言到硬件可执行代码的最终映射。指令选择根据目标架构的指令集，为中间表示中的操作选择最合适的机器指令序列。寄存器分配将中间代码中的虚拟寄存器高效映射到CPU的物理寄存器，优化访问速度与资源利用。指令调度重排指令顺序以充分利用流水线，减少CPU停顿，提升程序运行效率。寄存器传输语言（RTL）在指令语义建模中的结构与作用类LISP语法RTL采用类LISP的语法结构，使用嵌套表达式描述指令。这种结构清晰表达操作与操作数的层次关系。形式如(set(reg:SI140)(plus:SI...))。赋值操作语义set操作表示寄存器的赋值动作，定义目标寄存器的内容来源。实现指令级的语义建模。确保操作的精确性。算术操作建模plus等操作符用于描述算术运算，如寄存器间的加法操作。精确表达底层计算逻辑。支持复杂表达式组合。数据类型标识SI等数据模式标识寄存器的数据宽度和类型。确保操作在正确的数据表示下执行。维护语义一致性与类型安全。寄存器引用reg关键字用于引用寄存器，携带编号与类型信息。实现对硬件资源的抽象表示。支持编译器优化与分配。操作数访问机制XEXP宏提供对表达式操作数的访问接口。支持遍历RTL树形结构。便于指令的分析与变换处理。指令形式化表达RTL将指令转化为形式化表达式，精确建模语义动作。有利于编译器进行优化与代码生成。提升处理可靠性。结构化组织通过结构化方式组织指令元素，支持递归遍历与模式匹配。便于实现复杂的编译器变换与验证逻辑。说明链接过程在可执行文件生成中的整合功能链接的必要性单个源文件编译生成的目标文件无法独立运行，需通过链接整合多个目标文件与库函数。符号解析链接器解析各目标文件中的外部符号引用，确保函数与变量的定义和调用正确匹配。地址重定位将各目标文件的相对地址合并为统一的内存布局，完成最终可执行文件的地址分配。静态与动态链接静态链接将库代码嵌入可执行文件，动态链接则在运行时加载共享库以节省空间。解释程序及软件工具04解释程序的功能与实例解释程序是一种高级语言处理程序，它不需要在程序运行前将整个源程序翻译成目标代码，而是逐行读取、分析并执行源程序中的语句，即边解释边执行。这种工作方式使得解释程序特别适合程序员以交互方式工作，因为程序员可以在执行过程中即时看到每个语句的结果，并有机会修改程序。解释程序的工作方式即时反馈：指程序员可以即时看到程序的运行结果，便于调试和修改。交互性强：解释程序适合在交互式环境中使用，如命令行界面或集成开发环境（IDE）。可移植性好：由于解释程序通常不依赖于特定的硬件或操作系统，因此具有较好的可移植性。缺点：主要是执行速度慢以及空间开销大。由于每次执行都需要进行语法和语义分析，因此解释执行的效率通常低于编译执行。解释程序的优缺点编译工具箱：从Lex&Yacc到现代IDE一系列强大的软件工具极大地简化了编译器的开发过程，使开发者能更专注于语言设计和核心算法。词法/语法分析器生成器如Lex/Flex和Yacc/Bison，可根据规则自动生成编译器前端。代码优化与测试工具提供静态分析、动态测试等功能，帮助提升代码质量和性能。集成开发环境(IDE)如Eclipse,VisualStudio，提供编辑、编译、调试等一站式开发体验。模块化与自动化现代工具链将编译过程分解，显著提升了开发效率和可维护性。剖析GCC的多前端架构与GENERIC/GIMPLE中间表示体系GCC编译流程支持C、C++、Fortran等多种语言前端各前端独立解析源码，降低语言耦合性统一输出GENERIC中间表示。语言无关的树形中间表示。为后续降级和优化提供统一基础。将GENERIC降级为三地址码形式。简化控制流，便于进行编译优化。支持静态单赋值（SSA）形式转换。在GIMPLE上执行多轮过程间优化。提升代码性能并减少资源消耗。GIMPLE转换为低层次的RTL表示。接近目标架构的指令风格。RTL进一步处理并生成目标机器码。完成汇编或可重定位目标文件输出。语义分析多前端设计GENERIC结构GIMPLE转换优化处理RTL中间表示代码生成GCC整体结构图CC++JavaGenericASTASTASTmachinecodeRTLSSAGIMPLEoptpass1optpassNUn-SSA前端中端后端...图1.2GCC整体结构图变量的声明示意图图1.3变量a和变量b的声明示意图var_declidentifier_nodestrg:anameinta声明typescpechansizevar_declnametypescpechansizeidentifier_nodestrg:binteger_typenamesizeminmaxidentifier_nodeidentifier_nodestrg:intnametypeintb声明解析LLVM模块化设计与IR在跨语言支持中的优势模块化架构LLVM采用高度模块化设计，各组件可独立扩展，支持多种前端语言与后端目标平台。统一中间表示LLVMIR作为语言无关的中间表示，实现跨语言优化与代码生成，提升复用性与灵活性。多语言支持通过统一IR，LLVM支持C、C++、Swift等语言，广泛应用于iOS开发与跨平台编译。比较GCC与LLVM在优化流程与目标平台适配上的异同GCC多级优化GCC使用GIMPLE和SSA进行多级优化，聚焦过程内优化提升执行效率。该结构强调编译流程的阶段性与深度分析。优化主要在中间表示层完成。RTL后端适配GCC通过RTL后端实现对特定硬件架构的紧密适配，提升代码生成效率。这种设计增强了目标相关优化能力。但降低了后端的可移植性。前端职责明确GCC的语言前端负责将源码转换为统一中间表示。各前端独立实现语法解析与转换逻辑。增强了语言支持的多样性。LLVM模块化IRLLVM采用简洁、通用的中间表示（IR），支持细粒度优化。模块化设计提高了优化passes的可复用性。便于跨语言共享优化流程。跨语言优化LLVM的统一IR支持多种语言前端，实现跨语言优化与链接。提升整体代码质量。有利于构建统一工具链。灵活目标模型LLVM提供分层目标模型，增强对新硬件平台的适应能力。支持JIT和AOT编译模式。整体架构更具扩展性和灵活性。现代编译器架构对比：GCCvs.LLVMGCC前端(C/C++/Java...)↓GENERIC(统一AST)↓GIMPLE(SSA形式)↓RTL(接近汇编)↓后端(机器码)采用多级IR，每层抽象级别不同，优化策略各异。LLVM前端(多种语言)↓LLVMIR↓优化Pass链↓后端(多种目标)采用单一、统一的IR，强调模块化设计和Pass链式优化。编译技术的发展历程及典型编译器05编译技术演进史：从手工规则到智能系统1950s起源首个FORTRAN编译器诞生，标志着高级语言时代的开端。1960-70s理论奠基乔姆斯基文法体系、LR分析算法等为编译器设计奠定理论基础。1970-80s工具成熟Yacc/Lex等自动化工具诞生，编译器构造进入模块化时代。1990s-至今生态繁荣GCC、LLVM等开源项目推动编译技术普惠化，并向AI、异构计算等新领域演进。约翰·巴克斯与FORTRAN在编译器起源中的里程碑意义巴克斯的贡献约翰·巴克斯发明FORTRAN，开创高级语言先河，奠定编译器技术基础。FORTRAN诞生1957年发布，首次实现高级语言到机器代码的自动翻译。编译器起源FORTRAN推动编译器诞生，标志程序自动化翻译时代开启。深远影响极大简化编程，促进后续语言发展，提升软件开发效率。巴克斯-诺尔范式（BNF）对语言语法形式化描述的贡献BNF的起源由约翰·巴克斯提出，后与彼得·诺尔完善，用于精确描述ALGOL60语法，奠定程序语言形式化基础。形式化语法BNF采用规则推导方式定义语言结构，使语法描述清晰、无歧义，成为编译器设计的标准工具。递归定义能力支持递归语法规则表达，能简洁描述嵌套结构，如表达式、语句块等复杂语言构造。深远影响BNF成为后续语法描述基础，衍生出EBNF、ABNF等扩展形式，广泛应用于语言设计与解析器生成。01AI融入编译AI技术集成到编译器中，实现智能代码补全与错误预测。提升开发效率和代码准确性。推动编程自动化发展。01编译技术在AI编程、即时编译与安全验证中的前沿应用02代码自动补全基于AI模型分析上下文，智能推荐代码片段。减少手动输入，提高编码速度。增强开发者体验。0203即时编译优化JIT技术动态优化热点代码执行。平衡启动速度与运行性能。广泛用于主流语言运行时环境。0304静态安全检测结合静态分析与形式化验证。在编译阶段发现内存泄漏等问题。有效提升程序安全性与可靠性。0405漏洞提前识别通过编译时分析识别越界访问等隐患。降低运行时崩溃风险。加强软件质量控制。0506AI模型编译编译技术用于优化AI模型部署。提升推理效率，压缩模型体积。促进边缘端智能化。0608软硬件协同编译器促进算法与硬件深度协同。提升整体系统性能。加速智能化技术落地应用。0807量子编程支持编译技术拓展至量子计算领域。实现高级语言到量子指令的转换。助力前沿计算平台发展。07本章总结06回顾：编译器核心组件速览预处理器↓词法分析器↓语法分析器↓语义分析器↓中间代码生成器↓代码优化器↓目标代码生成器关键概念对比：编译vs.解释编译执行翻译时机:运行前一次性翻译运行速度:快调试体验:较差跨平台:需重新编译空间占用:较小解释执行翻译时机:运行时逐句翻译运行速度:慢调试体验:好(交互式)跨平台:好(需解释器)空间占用:较大现代虚拟机（如JVM）常采用混合模式，即先将代码编译为字节码，再通过解释器或JIT编译器执行。编译原理学习路径与意义掌握编译原理是成为优秀程序员的必修课，它能帮助你深刻理解程序行为、进行性能调优、甚至设计自己的领域特定语言。1.夯实基础深入理解词法、语法、语义分析的核心概念与算法。2.掌握优化学习数据流分析框架和各种经典的机器无关优化技术。3.深入后端了解目标代码生成、指令调度、寄存器分配等后端技术。4.关注前沿跟踪AI编译、异构并行等最新发展趋势，持续进阶。THANKS第2章高级语言设计基础大连理工大学content目录01语言02文法03文法和语言的分类04高级语言设计05语言设计实例06仓颉语言介绍概念图谱短语文法上下文有关文法上下文无关文法正规文法语言文法串字母二义性组合语言01区分自然语言与程序语言的语法与语义特征，理解语言作为符号系统的本质语言二元结构语言由语法和语义构成，语法规定结构形式，语义赋予意义，语法为媒介传递语义。自然vs程序语言自然语言灵活但歧义多，依赖语境；程序语言语法严格、结构清晰，便于机器解析。符号系统本质程序语言是符号串的集合，可视为形式语言，其核心是语法驱动的精确表达系统。自然语言与程序语言2.1.1文法的直观描述针对具体句子的分析【例】设有语句“大熊猫吃小竹子。”<句子>

<主语><谓语><主语>

<形容词><名词><谓语>

<动词><宾语><宾语>

<形容词><名语><形容词>

大|小<名词>

熊猫|竹子<动词>吃图2.1替换过程中的“树”表示2.1.1文法的直观描述针对具体句子的分析【例】设有语句“大熊猫吃小竹子。”<句子>

<主语><谓语><主语>

<形容词><名词><谓语>

<动词><宾语><宾语>

<形容词><名语><形容词>

大|小<名词>

熊猫|竹子<动词>吃图2.2微软办公软件2016版工具集2.1.2符号串的定义【定义】字母表。符号的有限集合是字母表。字母表是有穷非空的符号集合例如：集合{0，1}：

={0，1}。例如：C++语言字母表：

={a~z，A~Z，0~9，+，

，*，/，<，=，>，&，^，\，~，:，‘，;，.，?，(，)，{，}，[，]，空格，!，#，%}。【定义】符号串。字母表

上符号所组成的有穷序列被称为该字母上的符号串。符号串也被称作字符串。空串：不包含任何符号的符号串称为空符号串，记作

。【定义】符号串的长度。符号串的长度是指出现在串中符号的个数，可以写作

。【定义】符号串的连接运算。s

=

s=s

【定义】符号串的串的子序列。2.1.2符号串的定义【定义】符号串的幂。符号串的幂指符号串的指数运算。设s表示一个符号串，把s自身连接n次后，得到符号串为ss…s=sn【定义】符号串的前缀。【定义】符号串的后缀。【定义】符号串的子串。2.1.3语言的形式化定义【定义】语言。语言表示确定的字母表上符号串的任何集合。给定字母表

，一个语言就是

*上任意的可数的串集合。不包含任何元素的集合，称为空集，记作Ø。只包含空符号串的集合记作{

}。C++语言是符合C++语法的程序组成的集合。属于该语言的串称为该语言的句子或者字。构成一个语言的句子集合可以是有穷的，也可以是无穷的。字母组合串语言集合集合字母表图2.3从字母到语言之间的关系图2.1.3语言的形式化定义【定义】语言的连接运算。设L、M是两个语言，则LM表示L与M的连接，定义为：LM={ab|(a

L)and(b

M)}，表示a属于L且b属于M组成的符号串ab组成的集合。【定义】语言的合并运算。语言的并运算就是两个语言对应的符号串集合的并运算，简称并运算。【定义】语言的幂运算。L0={

}L1=L

L2=LLAi+j=AiAj例如，P={ab,x,y}P2=PP={abab,abx,aby,xy,xab,xx,yab,yx,yy}【定义】语言的闭包运算。2.1.3语言的形式化定义【定义】语言的闭包运算。一个语言L的闭包（closure）记作L*，即将L连接0次或多次后得到的串集合。L*=L0∪L1∪…∪Ln∪…L+=L1∪L2∪…∪Ln∪

…L+=LL*【例】设符号串L={A~Z,a~z}，D={0~9}。下面的串分别表示什么样的语言？L∪DLDL5L(L∪D)*D+文法02文法作为生成合法语句的规则集合，在计算机语言中的决定性作用01文法的定义文法是生成语言中所有合法句子的精确规则集合，用数学符号严格描述结构。02形式化作用文法为程序语言提供无歧义的推导框架，确保每个句子结构唯一确定。03决定语法结构编译器依赖文法规则进行词法与语法分析，直接决定前端处理逻辑。04支撑语言设计高级语言的设计基于文法，使其符号串能被系统化生成与准确识别。2.2文法句子构造从‘大熊猫吃小竹子’出发，展示如何依据语法规则逐步构造合法句子。规则应用使用<句子>→<主语><谓语>等产生式规则，逐层替换非终结符。最左推导始终替换最左边的语法成分，确保推导过程具有确定性和可追踪性。结构树形化推导过程可表示为语法树，直观体现句子的层次结构与生成路径。语法规则的推导过程2.2.1文法的形式化定义2.2文法1．文法的定义给定字母表

，一个语言可视为

*中的某个子集。VN为非空有限的非终结符号集，其中的元素称为非终结符或语法变量，代表了一个语法范畴，表示一类具有某种性质的符号。VT为非空有限的终结符号集，其中的元素称为终结符，其代表了组成语言的不可再分的基本符号集。VT即字母表

。设V是文法G的符号集，则V=VN∪VT,VN∩VT=Ø。【定义2.15】产生式。产生式是按一定格式表示的定义语法范畴的文法规则。一条产生式是一个有序对(

,

)，产生式的形式为

（

中至少包含VN中的一个元素，

V*）。其中，

称为产生式的左部，

称为产生式的右部或

的候选式。【定义2.16】文法。一部文法G是一个四元组G=(VN,VT,S,P)。S为文法的开始符号或识别符号，是VN中的一个非终结符，即S

VN。S代表语言最终要得到的语法范畴。P为产生式集合。2.2.1文法的形式化定义注意，有一些通常的约定如下。（1）开始符号S必须至少在文法某个产生式的左部出现一次。（2）第一条产生式的左部是文法的开始符号。（3）字母S通常表示开始符号。（4）一般情况下（默认）使用的字母表示如下。①使用大写字母A、B、C等表示非终结符。②小写斜体符号串，如expr、stmt等用来表示非终结符。③使用小写字母a、b、c、d等表示终结符。④数字0、1、…、9，通常操作符（如+、-）等，标点符号（如逗号、括号等）表示终结符。⑤通常使用希腊字母

、

、

等表示文法符号串（终结符和非终结符组成的符号串）。（5）如果A

1、A

2、…、A

n是所有以A为左部的产生式，则可以写为A

1|

2|…|

n。2.2.1文法的形式化定义【例2.4】给出文法G=(VN,VT,S,P)，其中VN

={A,B}Vr={a,b,c}S=AP={A

AB,A

aAc,B

b}上述文法可以简写为G=({A,B},{a,b,c},A,P)，其中P={A

AB,A

aAc,B

b}。如果产生式的左部相同，则可以写为合并的形式，即A

AB,A

aAc可以写为A

AB|aAc。许多情况下，不需要将文法的四元组显式地写出来，而是只需要将文法的产生式写出来即可。例如，例2.4的文法可以写为G[A]:A

AB|aAc

B

b其中，G[A]中的A表示该文法的开始符号。2.2.1文法的形式化定义2．应用文法推导语言的句子【定义2.17】直接推导

。设有文法G=(VN,VT,S,P)，

、

(VN∪VT)*，若S

，且存在

P，则称

直接推导出

，记作

。【定义2.18】直接推导序列。设有文法G=(VN,VT,S,P)，若存在

=

0

1，

1

2，…，

n-1

n

，或者

0

1

2

…

n-1

n，则

经过n步（n>0）可以推导出

，或者

经过n步（n>0）可以归约到

。当

+

或

=

时，记作

*

。【定义2.19】最左推导。在每一步推导过程中，总是对符号串中最左边的非终结符进行替换，称为最左推导。【定义2.20】最右推导。在每一步推导过程中，总是对符号串中最右边的非终结符进行替换，称为最右推导。最右推导也称为规范推导，最右推导的逆过程称为最在归约（规范归约）。2.2.1文法的形式化定义【例2.5】已知文法G[E]，产生式集合为写出句子id+id*id的最左推导和最右推导。最左推导：

最右推导：E

E+T

E

E+T

T+T

E+T*F

F+T

E+T*id

id+T

E+F*id

id+T*F

E+id*id

id+F*F

T+id*id

id+id*

F+id*idF

id+id*i

id+id*iddE

E+T|TT

T*F|FF

(E)|id2.2.1文法的形式化定义【定义2.21】句型。设有文法G=(VN,VT,S,P)，S

*

（

(VN∪VT)*），则称

为G(S)的句型。由最左（最右）推导产生的句型称为左（右）句型。【定义2.22】句子。设有文法G=(VN,VT,S,P)，S

*

（

VT*），则称

为G(S)的句子。如果一个句型仅由文法的终结符组成，则该句型就是该文法的句子。【定义2.23】语言。设有文法G=(VN,VT,S,P)，其所产生的语言定义为L(G)。 L(G)={

|

VT*∧S

*

，S是文法G的开始符号}2.2.1文法的形式化定义【例2.6】一个文法G=({a,b},{S},S,P)，其中产生式集合P:S

aSb|ab。因为S

aSb

aaSbb

a3Sb3

…

an-1Sbn-1

anbn，其中n>0。所以根据归纳法可知，该文法表示的语言为L(G)={ab,aabb,aaabbb,…}反之，对于任何形式为anbn，n>0的符号串，一定可以用文法G[S]推导出来，即存在推导S

+anbn。因此L(G)={anbn|n>0}。图2.4aaaabbbb推导过程的树表示SS

baSS

babS

S

a

baSS

bbabS

S

a

abaSSS

babSa

2.2.1文法的形式化定义3．文法与语言一个文法能产生一个语言，同一个语言可以由多个不同的文法来生成。【例2.7】一个文法如下：G[A]:A

aR|ab R

Ab其所产生的语言为L(G[A])={anbn|n>0}。给定一个文法G和一个符号串x，要判断x是否是文法G的一个句型，实际上就是从G的开始符号开始推导，看能否通过一系列直接推导得到x。如果能推导出x，那么x就是G的一个句型，否则x就不是G的句型。2.2.1文法的形式化定义对于一个给定的文法，从该文法的开始符号开始，每次使用一个该文法的产生式得到的新的符号串是该文法的一个句型。对于一个符号串推导，可以有多种不同的推导序列，如最左推导序列、最右推导序列等。不同推导序列所产生的句型是不同的，由最右推导序列所得到的句型称为规范句型。需要注意的是，文法和语言的相互关系并非是唯一的，形式语言理论可以证明以下两点。（1）给定一个文法G，能从结构上唯一的确定相应的语言。（2）给定一种语言，能构造其文法，但这种文法不是唯一的，即有L(G1)=L(G2)=…=L(Gn)但G1、G2、…，Gn互不相同。2.2.1文法的形式化定义4．文法的等价当给定一个文法时，可以唯一确定其对应的语言；但是针对一个给定的语言，可以为其构造出若干种不同的文法。为此，下面给出文法等价的概念。【定义2.24】文法等价。若L(G1)=L(G2)，则称文法G1和G2是等价的。文法等价的概念说明，两个文法即使规则不相同，只要所产生的语言集合相同，则认为这两个文法是等价的。同时，等价文法的存在可以使我们在不改变所确定语言的前提下，对文法进行改写，如化简、变换等。2.2.2语法树语法树用于表示经推导而产生的句子结构，这种表示直观形象，有助于理解句子的语法结构层次。一个句子的推导过程即为语法树的生长过程。语法分析树的每个结点都与终结符或非终结符有关。构造一棵语法树的算法如下。设G=(VN,VT,S,P)，上下文无关文法G的一棵语法树应满足如下条件：（1）每个结点有一个标记，是VN∪VT∪{

}中的符号。（2）语法树的根结点是S，表示一切推导都是从开始符号开始的。（3）如果结点是内部结点，则其标记A必在VN中。（4）如果父结点的标记为A，同时n1、n2、…、nk是其子结点从左到右的标识，则P中必定存在产生式A

n1n2…nk。（5）如果结点n有标记

，那么结点n是叶结点，且是它“父亲”唯一的“儿子”，其他叶结点是终结符。2.2.2语法树【例2.8】设有文法G[S]，其中S

aSb

S

c构造句子aacbb的语法树。句子aacbb的推导过程为S

aSbaaSbb

aacbb在例2.8的推导过程中，可以看出推导具备“递归”的特点。语法树是句型推导过程的图形表示，其主要用途如下。（1）表示句子的语法结构。（2）表示句子的分析过程。（3）判断文法的二义性。SbaSc图2.5acb的语法树2.2.3文法二义性1．二义性文法下面介绍文法的二义性，先给出一个例子。【例2.9】文法G的产生式如下：E

E+E|E*E|(E)|id。对句子id*id+id进行最左推导并画出语法树。对于句子id*id+id，有如下两个最左推导：E

E+E

E*E+E

id*E+E

id*id+E

id*id+idE

E*E

id*E

id*E+E

id*id+E

id*id+id根据这两个最左推导得到的语法树的结构也不同，如图2.6所示。2.2.3文法二义性1．二义性文法【例2.9】文法G的产生式如下：E

E+E|E*E|(E)|id。对句子id*id+id进行最左推导并画出语法树。E+EEEEididid*E+EEEEididid*E

E+E

E*E+E

id*E+E

id*id+E

id*id+idE

E*E

id*E

id*E+E

id*id+E

id*id+id图2.6id*id+id的两棵不同的语法树2.2.3文法二义性【定义2.25】二义性文法。对一部文法G，如果至少存在一个句子，对应两棵（或两棵以上）不同的分析树，则称该句子是二义性的。换言之，无二义性的句子只有一棵语法树，即使推导过程不同。包含二义性句子的文法称为二义性文法（或称二义文法）。否则，该文法是无二义性的。定义2.25也可表述为：若文法中存在某个句子，它有两个不同的最左（最右）推导，则这个文法是二义性的。严格说来，文法是对语言的有穷描述，即文法规则是有穷的，而由文法产生的语言一般是无穷的，因此文法的二义性问题是不可判定的。即不存在一个算法能在有限步骤内确切地判定一个文法是否是二义性的。但是，能给出一组充分条件，满足这组充分条件的文法是无二义性的。需要注意的是，文法的二义性与语言的二义性是完全不同的概念，即并非文法有二义性，其描述的语言就有二义性，反之亦然。2.2.3文法二义性【定义2.25】二义性文法。对一部文法G，如果至少存在一个句子，对应两棵（或两棵以上）不同的分析树，则称该句子是二义性的。换言之，无二义性的句子只有一棵语法树，即使推导过程不同。包含二义性句子的文法称为二义性文法（或称二义文法）。否则，该文法是无二义性的。定义2.25也可表述为：若文法中存在某个句子，它有两个不同的最左（最右）推导，则这个文法是二义性的。严格说来，文法是对语言的有穷描述，即文法规则是有穷的，而由文法产生的语言一般是无穷的，因此文法的二义性问题是不可判定的。即不存在一个算法能在有限步骤内确切地判定一个文法是否是二义性的。但是，能给出一组充分条件，满足这组充分条件的文法是无二义性的。需要注意的是，文法的二义性与语言的二义性是完全不同的概念，即并非文法有二义性，其描述的语言就有二义性，反之亦然。2.2.3文法二义性【例2.10】设有文法G[stmt]：stmt

ifexprthen

stmt|ifexprthen

stmt

else

stmt|other显然，这是个二义性的文法，因为对于某些语句，它会有两个语法树，例如针对下面的句型：if

expr

then

if

expr

then

stmt

else

stmt有两种最左推导方法：stmt

if

expr

then

stmt

if

expr

then

if

expr

then

stmt

else

stmtstmt

if

expr

then

stmt

else

stmt

if

expr

then

if

expr

then

stmt

else

stmt

通过改写上述文法，即通过强制匹配matched_stmt和unmatched_stmt，确保else与最近的if绑定，可以消除二义性。改写后的文法如例2.10所示。这里的“other”代表其他语句。2.2.3文法二义性【例2.10】设有文法G[stmt]：stmt

ifexprthen

stmt|ifexprthen

stmt

else

stmt|other改写后的文法如例2.10所示。【例2.11】设有文法G

[stmt]：stmt

matched_stmt|unmatched_stmtmatched_stmt

if

expr

then

matched_stmt

else

matched_stmt

|otherunmatched_stmt

ifexpr

then

stmt

|if

expr

then

matched_stmt

else

unmatched_stmt2.2.3文法二义性2．二义性语言对于程序语言来说，希望生成它的文法是无二义性的，只有这样，对它的每个语句的分析才能是唯一的。【定义2.26】二义性语言。如果一个语言L的任何文法都是二义性文法，则称该语言是二义性语言。目前已经在理论上证明，存在这种二义性语言。这里需要说明，文法的二义性与语言的二义性是两个不同的概念。对于文法G1和G2，假设G1是无二义性的，而G2是有二义性的，但是同时有语言L=L(G1)=L(G2)，即G1和G2所产生的语言是相同的。由于G1是无二义性的，所以语言L是无二义性的。2.2.3文法二义性【例2.12】文法G[E]描述了四则运算构成的算术表达式：E

idE

E+E|E

-

EE

E

E|E

EE

(E)其中，非终结符E表示一类算术表达式，id表示程序语言中的变量。该文法定义了由{id,+,-,

,

,(,)}组成的一类算术表达式的语法结构。变量id定义为一算术表达式，若E1和E2是算术表达式，则E1+E2，E1-E2，E1

E2，E1

E2，(E1)也都是算术表达式。表达式id+id

id是文法G[E]所定义的一个句子，它有两棵不同的语法树，分别如图2.7（a）图2.7和（b）所示。2.2.3文法二义性【例2.12】文法G[E]描述了四则运算构成的算术表达式：E

idE

E+E|E

-

EE

E

E|E

EE

(E)E

EEEEididid+E

EEEEididid+图2.7id+id

id的两棵不同的语法树2.2.3文法二义性【例2.13】G[E′]同样定义了四则运算构成的算术表达式：E′

E′+T|E′-

T|TT

T

F|T

F|FF

(E)|id算术表达式id+id

id同样是文法G[E′]所定义的一个句子，但不是二义性的。E'+

TTF

E'idTFidFid图2.8id+id

id的无二义性的语法树文法和语言的分类032.3文法和语言的分类【定义2.27】乔姆斯基文法。G是一个四元组(VN,VT,S,P)，其中，VN为非空有限的非终结符号集；VT为非空有限的终结符号集；S为文法的开始符号或识别符号，是VN中的一个非终结符，即S

VN，S代表语言最终要得到的语法范畴；P为非空有限的重写规则集合。文法G对应的语言就是从该文法的开始符号S产生的终结符串（句子）的集合。在接下来的讨论中，均有V=VN∪VT，VN∩VT=Ø。2.3.10型文法【定义2.28】0型文法（短语结构文法）。有一文法G=(VN,VT,S,P)，如果对于

P，满足

(VN∪VT)+并且

中至少含有一个非终结符，

(VN∪VT)*，则称G为0型文法，又称短语结构文法或无约束文法。由0型文法所确定的语言为0型语言L0。0型语言可由图灵机来识别。【例2.14】文法G=({S,A,B,C,D,E},{a},S,P)，其中P由以下产生式组成：S

ACaB

Ca

aaC

CB

DBCB

E

aD

Da

AD

ACaE

Ea

AE

G是0型文法，它所产生的语言为L0(G[S])={ai|i是2的正整次方}即L0={aa,aaaa,aaaaaaaa,…}。推导过程如下：SACaBAaaCB

AaaE

AaEa

AeaaaaSACaB

AaaCB

AaaDB

AaDaB

ADaaB

ACaaB

AaaCaB

AaaaaCB

AaaaaE

AaaaEa

AaaEaa

AaEaaa

Aeaaaaaaaa0型语言的特点：不足以描述自然语言，如果使用0型语言描述程序语言，则过于一般化。2.3.2上下文有关文法【定义2.29】上下文有关文法（1型文法）。设文法G=(VN,VT,S,P)，P中每个产生式的形式为

A

其中，A

VN，

,

(VT∪VN)*，

(VT∪VN)+（仅S

除外，但此时S不得出现在任何产生式的右部），则称文法G为上下文有关文法，又称1型文法。【例2.15】文法G=({S,A,B,C,D,E,F},{a,b,c},S,P)，其中P由如下产生式组成：S

ABCS

S

FCA

AC

BA

ABCB

BC CF

Fc

CF

EcBE

Eb BE

DbAD

Da

D

方法G是一个上下文有关文法，它所产生的语言为L1(G[S])={anbncn|n≥1}即L1={abc,aabbcc,aaabbbccc,…}2.3.2上下文有关文法

2.3.2上下文有关文法【定义2.29】上下文有关文法（1型文法）。设文法G=(VN,VT,S,P)，P中每个产生式的形式为

A

其中，A

VN，

,

(VT∪VN)*，

(VT∪VN)+（仅S

除外，但此时S不得出现在任何产生式的右部），则称文法G为上下文有关文法，又称1型文法。【例2.15】文法G=({S,A,B,C,D,E,F},{a,b,c},S,P)，其中P由如下产生式组成：S

ABCS

S

FCA

AC

BA

ABCB

BC CF

Fc

CF

EcBE

Eb BE

DbAD

Da

D

方法G是一个上下文有关文法，它所产生的语言为L1(G[S])={anbncn|n≥1}即L1={abc,aabbcc,aaabbbccc,…}2.3.3上下文无关文法【定义2.30】上下文无关文法（2型文法）。设文法G=(VN,VT,S,P)，P中每个产生式的形式为A

其中，A

VN，

(VT∪VN)*，则称文法G为上下文无关文法。【例2.17】描述程序语言中的上下文无关文法如下。G[S]:S

i=E;

S

if(E)else

S;

S

while(E)S;

S

{S}

S

S;S非终结符E用来表示一类算法表达式，终结符i用来表示程序语言的变量。S

while(E)S;

while(E){S};

while(E){i=E;};注意：如果在一个上下文无关文法G中存在着一个非终结符A，并且有推导A

*

1A

2（其中

1、

2不是空串），则称该上下文无关文法具有自嵌套特性。例如，在上面的例子中，就有推导S

{S}。2.3.3上下文无关文法【例2.18】文法G=({S},{a,b},S,P)，其中产生式P如下：S

aSbS

SSS

ab该文法所对应的实际问题是：实现程序语言的表达式中括号偶对任意地嵌套和并列出现。其中a表示左括号，b表示右括号。该文法可以用来描述括号偶对的对称嵌套结构。【例2.19】文法G=({S,A},{begin,end,[,]},S,P)，其中产生式P如下：S

begin

A

endS

A

[S]由于存在着推导S

begin

A

end

begin[S]end，因此该文法也具有自嵌套特性。任何上下文无关文法如果不包含自嵌套性质，那么它就等价于一个正则文法（RegularGrammar，RG），或者说它只产生正则语言。自嵌套特性区分了上下文无关语言和正则语言。2.3.3上下文无关文法【例2.20】产生相同个数a和b的文法如下。S

aSbSS

bSaSS

这个文法产生的语言是L={x

(a|b)*并且其中x含有相同个数的a和b}。【例2.21】定义偶数非负整数语言的文法如下：even-integer

even-digit|integereven-digitinteger

digit|digitintegerdigit

even-digit|odd-digiteven-digit

0|2|4|6|8odd-digit

1|3|5|7|9使用这个文法，可以很容易生成偶整数，并且画出其对应的语法树，这对语法分析及编译器构造是非常重要的。2.3.4正则文法【定义2.31】正则文法。设文法G=(VN,VT,S,P)，P中每个产生式的形式为A

B或A

或者A

B

或A

其中，A,B

VN，

VT*，则称文法G为正则文法或3型文法线性文法。文法规则为A

B或A

的文法为右正则文法，文法规则为A

B

或A

的文法为左正则文法。2.3.4正则文法例如，用左正则文法和右正则文法定义标识符。假设用I代表标识符，用d表示任意一个数字，l表示任意一个字母，则定义标识符的文法为左正则文法

右正则文法P:I

l|Il|Id

P:I

l|lT

T

l|d|lT|dT再如，无符号整数使用左正则文法和右正则文法来定义，可以写为左正则文法

右正则文法P:N

d|Nd

P:N

d|dN

词法单元是程序语言中基本的文法符号，正则文法是一种描述词法单元的有效工具。【例2.22】描述程序语言中的标识符的正则文法为G[<标识符>]:<标识符>

L|L<字母数字>

<字母数字>

L|D|L<字母数字>|D<字母数字>其中，L表示a～z，A～Z中的任一字母；D表示0～9中任一数字。2.3.5四类文法的比较【例2.23】给定一个语言L1={aibjck|i,j,k≥1}，可以定义如下文法：G2.1({S,A,B},{a,b,c},P1,S)其中，P1为

S

Bc|Sc

B

Ab|Bb

A

Aa|a上述文法G2.1是正则文法，对应的语言L1就是正则语言。【例2.24】给定一个语言L2={aibick|i,k≥1}，可以定义如下文法：G2.2({S,A},{a,b,c},S,P2)其中，P2为

S

Ac|Sc

A

ab|aAb上述文法G2.2是上下文无关文法，对应的语言L2就是上下文无关语言。2.3.5四类文法的比较【例2.25】给定一个语言L3={aibici|i≥1}，可以定义如下文法：G2.3({S,B,C,D},{a,b,c},S,P3)其中，P3为

S

aSBC

S

abC

CB

CD CD

BD BD

BC

bB

bb bC

bc

cC

cc参照定义，上述文法G2.3是上下文有关文法，对应的语言L3就是上下文有关语言。G2.3也是0型文法。但是G2.3是不能用上下文无关文法描述的上下文有关语言。2.3.5四类文法的比较4类文法描述的语言的关系描述功能越来越强0型

1型

2型

3型（L0

L1

L2

L3）产生式限制越来越严格描述功能越来越强0型

1型

2型

3型

产生式限制越来越严格图2.94类文法描述的语言的关系图2.104类文法之间的集合关系高级语言设计042.4高级语言设计设计一门高级语言需要深入考虑以下几方面：数据类型、语句和控制结构等。对于目前使用的程序语言，在编译器中，仍然采用上下文无关文法来描述其语言结构。字符字符串记号词法分析器（正规式）表达式语句程序块程序语法分析器语法分析树（上下文无关文法）2.4.1程序语言的定义（1）语法规则是程序语言的核心，决定了程序如何组织和操作数据。设计语法规则需要确保语言易于学习、使用和阅读，同时要足够灵活，能够表达复杂的程序逻辑。（2）数据类型：数据类型决定了如何表示和处理数据。设计者需要决定语言支持哪些基本数据类型以及如何创建自定义类型。同时还需要考虑类型转换和类型检查的规则。（3）操作符和函数：操作符和函数是程序语言的重要组成部分，决定了程序如何执行操作。设计者需要决定语言支持哪些操作符和函数，以及如何定义和使用自定义操作符和函数。（4）控制结构：控制结构决定了程序如何执行操作。设计者需要决定语言支持哪些控制结构，如条件语句、循环语句、异常处理等。（5）模块化：模块化是程序语言的重要特性，可以简化程序的组织和管理。设计者需要考虑如何定义模块、组织模块，以及模块之间的交互方式。2.4.1程序语言的定义（6）错误处理：错误处理是程序语言的重要特性，可以帮助程序员诊断和修复程序中的错误。设计者需要考虑如何定义错误、报告错误，以及如何处理异常情况。（7）可读性和可维护性：设计一种程序语言需要考虑到可读性和可维护性。这包括使用有意义的变量名、注释代码，以及编写清晰的文档等。（8）性能优化：虽然性能优化通常在编写代码阶段进行，但作为程序语言的设计者，需要考虑如何设计语言，以便更有效地使用计算机资源，同时还需要考虑到程序的性能表现。（9）与其他系统或语言的集成：考虑如何将新语言与现有系统或语言集成，如与其他程序语言交互、调用操作系统API（ApplicationProgramInterface，应用程序接口）等。（10）测试和调试：设计者需要考虑如何测试和调试新语言编写的程序。这包括提供内置的测试框架、调试器和其他工具。2.4.2高级语言的起源冯·诺依曼体系结构在高级语言上的特性主要体现在以下方面。（1）顺序执行。冯·诺依曼体系结构中的指令和数据共享同一存储空间，计算机从存储器中取出指令和数据进行相应的计算，按顺序执行每条指令。（2）存储程序思想。将高级语言程序和数据都以二进制形式存储在存储器中，指令由操作码和地址码组成，且按顺序执行。（3）线性组织和直接寻址。存储单元是定长的线性组织，存储空间的单元是直接寻址的。冯·诺依曼体系结构影响了计算机语言的语义和运行方式，早期的高级语言，如BASIC语言、FORTRAN语言、ALGOL语言、COBOL语言和Pascal语言等，都明显具有语句顺序执行的特征，并且计算机语言程序中的变量代表的是存储空间，而并非数学意义上的变量。这种语言特征也限制了高级语言解决现实问题的能力。随着时间的推移，人们发明了越来越多种类的程序语言，如C、Java、Python等。这些语言都有各自的特点和用途。2.4.3数据类型高级语言的数据类型可以大致分为以下几个层次。（1）基本数据类型：这是最底层的数据类型，包括整型（如int、byte、short、long）、浮点型（如float、double）、字符型（如char）、指针类型和布尔型（Boolean）等。（2）构造数据类型：构造数据类型是由基本数据类型或其他构造类型组合而成的复合数据类型，用于描述复杂数据结构。构造数据类型包括数组（array）、记录（record）、符号串（string）、结构体（struct）、联合体（union）、栈（stack）、队列（queue）、链表（linkedlist）等。构造数据类型的基本表示形式对程序员是可见的，也就是程序员可以对