目录一、前章再叙1. LR2. Bison3. 前后端4. 问题--形式化描述--计算机解决方案设计‘’第二章 文法和语言1. 语言概述语言是由句子组成的集合语法、语义、语用对字符做运算2. 形式语言基础基本概念正则闭包和星闭包联接3. 文法的直观理解定义语言的很好的形式化工具什么是文法推导与产生式从开始符号到句子语法树4. 文法启动文法的定义文法实战无符号整数有符号整数奇数一、前章再叙解释程序不生成目标代码编译程序生成目标代码。对于语法树的推导和规约过程推导属于长(zhang)枝规约属于剪枝。1. LR语法分析中有一种自下而上的方法LR法自下而上意味着它从输入通常是词法分析器产生的记号流的底部开始构建语法树并向上移动直到形成完整的语法树。LR代表从左到右读取输入并按照从右到左的顺序产生派生。它相对于自上而下的方法如LL更为强大因为它可以分析更大的语法子集。2. BisonBison是一个著名的解析器生成器经常被用于生成LR解析器。当给定一个语法规则描述通常为Yacc格式时Bison会生成一个C程序该程序是对应的LR解析器。因此通过Bison开发人员可以方便地为特定的语言定义创建对应的解析器。3. 前后端单趟扫描没有前后端。多趟扫描以中间代码为中心分前端和后端。后端与目标机相关。对于多趟扫描我们通常将编译器的任务划分为两个主要部分前端前端主要与编程语言有关它负责解析源代码进行语法和语义分析并生成中间代码。后端后端则是与目标平台如特定的处理器架构相关的部分。它取得前端生成的中间代码进行进一步的优化并生成最终的机器码。通过这种方式例如一个编译器的前端可以为多个不同的目标平台共用而针对每个目标平台都有一个专门的后端来处理中间代码并生成相应的机器码。这为编译器的设计和维护提供了便利因为当添加对新语言特性的支持时只需修改前端而要为新的目标平台生成代码时只需添加或修改后端。4. 问题--形式化描述--计算机解决方案设计‘’这是解决计算问题的三个步骤。首先我们有一个实际的问题。然后我们需要将这个问题形式化即用数学或逻辑等形式语言来描述它。最后我们设计一个计算机解决方案来解决这个形式化的问题。自编译编译的编译任何一种语言都提供了一个特别的思考角度第二章 文法和语言语言的不同的定义语言与源程序有关是源程序的集合。但有无限多个我们借助具体的表达Grammer文法。课前思考计算机高级程序语言有哪些一般性特性1. 语言概述语言是由句子组成的集合当我们谈论“语言”我们通常指的是一组按照某种规则组织的句子或表达式。例如英语、中文、Python、Java 都是语言。不论是自然语言还是编程语言它们都是由一系列句子或表达式组成的。语法、语义、语用这三个概念用于描述和定义任何语言的重要特性。语法 (Syntax): 定义了句子或表达式的结构或形式。它是一组规则定义了什么样的字符组合是有效的什么样的组合是无效的。例如在英语中“我是大学生”是一个语法正确的句子而“我大学生是”可能就不是。语义 (Semantics): 是关于句子或表达式的意义的。当我们说一个句子是“有意义的”我们是指它在语义上是有意义的。例如“太阳是冷的”在语法上是正确的但在语义上是错误的至少在我们的现实世界中。语用 (Pragmatics): 关心的是句子或表达式在实际上下文中的使用。它涉及到语境、说话者的意图等。例如“你能把窗户关上吗”在语用上可能是一个请求尽管字面上它是一个问题。语言的实例若在语法上是正确的其相关联的意义可从两个观点来看其一是该句子的创立者所想要表示的意义另一是接收者所检验到的意义。这两个意义并非总是一样的前者称为语言的语义后者是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。对字符做运算在编程语境中我们经常对字符或字符串进行运算。这可能包括连接、裁剪、搜索、替换等。例如在许多编程语言中我们可以使用运算符来连接两个字符串。2. 形式语言基础基本概念一、字母表和符号串字母表符号的非空有限集合例å{abc}符号字母表中的元素 例abc符号串符号的有穷序列例a, aa, ac,abc..特别地,空符号串无任何符号的符号串(ε)符号串集合由符号串构成的集合。符号串相等若x、y是集合上的两个符号串则xyiff当且仅当组成x的每一个符号和组成y的每一个符号依次相等。空串和空集是两个概念符号串的联接保持联接的有序性不同序列不一样。空串和字符的联接结果是字符本身空串与空集空串在形式语言中空串通常表示为ε或λ它是一个长度为0的字符串。换句话说它没有任何字符但仍然被认为是一个有效的字符串。空集在数学中空集表示为∅它是一个没有元素的集合。所以说空串与空集是两个不同的概念。空串是一个没有字符的字符串而空集是一个没有元素的集合。符号串的联接联接是指将两个或多个字符串或符号串按照顺序连接在一起。例如考虑两个字符串Ahello和Bworld那么A和B的联接就是helloworldhelloworld。请注意联接是有顺序的即helloworld与worldhello是两个不同的结果。空串与字符的联接当你将空串与任何其他字符串或字符联接时结果仍然是原始的字符串或字符。这是因为空串本身没有内容。例如考虑一个字符Ca和一个空串ε那么C和ε的联接就是aεa。此处的结果仍然是原始的字符a。正则闭包和星闭包正则闭包所有元素能够组成的所有符号串。星闭包所有元素能够组成的所有符号串空串。二者都是在集合的基础上提出的首先我们来理解闭包这个概念。在数学和计算机科学中闭包经常指一个操作对于一个集合内的所有元素都是有效的并且结果也在这个集合内。对于正则表达式而言闭包有两种常见的形式正则闭包和星闭包。正则闭包: 当我们说一个集合的“正则闭包”我们指的是由这个集合的元素可以组合成的所有可能的字符串。例如如果我们有一个集合 {a, b}其正则闭包包括如下字符串a, b, aa, ab, ba, bb, aaa, aab, aba, abb, ...可以无限组合下去。星闭包: 星闭包与正则闭包非常相似但它还包括一个额外的元素空字符串通常表示为ε或λ。使用上面的集合 {a, b} 为例其星闭包为ε, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, ...。两者的区别是星闭包包括了空字符串而正则闭包不包括。这两种闭包在正则表达式和自动机理论中是非常基础的概念。例如在正则表达式中使用星号*表示一个模式出现的次数为0次或多次这其实就是星闭包的应用。联接联接在形式语言和自动机理论中通常是指字符串或序列的串联。在集合的上下文中这意味着将一个元素与另一个元素串在一起以形成一个新的组合。这与数学上常用的集合操作不同因为我们现在是在元素级别而不是集合级别进行操作。字符串联接同样注意顺序A^3在字母表A上的所有长度等于3的字符串的集合A*在字母表A上所有字符串的集合在集合和字符串的上下文中可以认为闭包是一种自联接的结果。这种“自联接”意味着集合中的元素不断与其自身组合生成新的元素直到满足某些条件例如在正则闭包中直到生成所有可能的字符串。这种概念是类似的但请注意它们仍然是在不同的上下文中应用的。3. 文法的直观理解定义语言的很好的形式化工具什么是文法在编译器理论中文法是一种形式化的方法用于描述程序设计语言的语法。它是一组产生式规则每个规则描述了如何从一个符号或称为非终结符推导出一个符号串。符号串可以是非终结符、终结符或二者的组合。所谓文法是在形式上对句子结构的定义与描述而未涉及语义问题。举个例子就明白辣谓语等称为“非终结符”我称为终结符。推导与产生式在文法中使用产生式规则进行推导是基本操作。例如有这样一个产生式规则句子 - 主题 谓语这意味着在推导过程中我们可以将句子替换为主题 谓语。这样的替换就是一次“推导”。从句子多步推导成具体的句子就是我们的目标。从开始符号到句子通常文法有一个特定的非终结符作为其开始符号。推导的目的是从开始符号开始逐步使用产生式规则最终得到一个只含有终结符的符号串。推导成功表示这个符号串就是这个文法中的句子。例如考虑以下简单文法句子 - 名词 动词 名词 - 猫 | 狗 动词 - 跑 | 跳从句子开始我们可以推导出如下句子“猫跑”、“猫跳”、“狗跑”、“狗跳”。语法树语法树是句子的图形表示展示了如何使用产生式规则从开始符号推导出该句子。它是一种树形结构其中每个内部节点代表一个非终结符每个叶节点代表一个终结符。对于句子“猫跑”其对应的语法树为句子 / \ 名词 动词 | | 猫 跑这棵树清晰地展示了从句子开始如何使用产生式规则得到句子“猫跑”。文法和推导是编译器前端的基石特别是在语法分析阶段。它们提供了一种方法来正式描述和理解程序设计语言的结构和语法。而语法树为编译器提供了一种内部数据结构用于表示源代码的结构为后续的语义分析、优化和代码生成阶段提供基础。4. 文法启动文法的定义首先我们从文法的定义开始。文法G(V_N,V_T,P,Z)通常由四个组成部分定义在产生式中终结符只出现在右边或者说在产生的结果中。非终结符必须至少出现在产生式的左边可以出现在右边。通过产生式非终结符可以被展开成其它的非终结符或终结符从而描述了某种语法结构或模式。一个非终结符如果没有在任何产生式的左边出现那么它在该文法中是没有意义的因为我们无法知道它如何被展开或解释。所以为了文法有意义每一个非终结符都必须至少在一个产生式的左边出现。文法实战无符号整数文法定义S - SD | D D - 0 | 1 | 2 | ... | 9D代表单个数字。这是基本的构建块表示一个整数可以是任意的单个数字。S可以被看作是数字序列。考虑这样的问题“一个数字序列是什么”答案是它可以是一个单独的数字或者是一个数字紧跟着一个数字序列。这正是产生式S - SD所代表的。这也允许我们生成任意长度的数字序列。这个文法描述了一个无符号整数。以18为例进行推导S SD S8 D8 18然后作者发现推导的时候需要先转到相同符号数量的形式。以18为例先转到SD与18都是两位。再逐个转换到最终值转化D这个最好转化的再变化高位基本上就是从易到难。有符号整数然后如果要定义有符号整数的话只需在无符号整数的基础上增加一个符号部分。这可以通过增加以下产生式来完成S - S | S | -S现在S不仅可以是一个数字或数字序列还可以是一个正数或负数。例如要推导出“-18”我们首先从S开始然后使用产生式S - -S得到-S然后再按照无符号整数的推导规则得到“-18”。有符号先推出符号奇数对于奇数的定义作者在课堂后与老师探讨确定了最终的答案。首先定义最高位O不能是0O - 1 | 2 | ... | 9再定义S这个S和上面无符号整数的S定义相同作为中间数S - SD | D D - 0 | 1 | 2 | ... | 9然后定义M这个M只能是奇数即M - 1 | 3 | 5 | 7 | 9将这些组合在一起为奇数定义一个入口点。假设N为入口点则N - OSM | OM | M这里的N表示一个奇数。我们可以看到一个奇数可能只有一个数字只有M、可能有两个数字O和M如19或可能有多个数字如135这是通过OSM表示的。