编译原理 第三章上下文无关文法及分析.ppt

1、第三章理解上下文相关语法和分析，学习目标：理解上下文相关语法，柔道，回文，分析树，理解抽象语法树，理解：语法的结构，异议语法，分析学习的主要内容语法结构的说明：上下文无关语法语法语法语法分析方法(代码实现语法规则分析)自上而下语法分析自下而上语法分析，结果的数据结构3.1分析过程3.2上下文无关语法3.3分析树和抽象语法树3.4异义性、3.1分析过程、分析操作构成分析树或语法树，其中程序的语法结构隐含或明确地表示扫描仪生成的令牌中的结构。如果分析的介面输入：分析进程需要以下令牌，分析器将调用扫描机进程从输入获取输出：配置的隐式或显式语法树。语法树中的每个节点都包含编译后续进程所需的特性。分析的

2、错误处理在错误修复中报告有意义的错误消息，并继续分析以找到尽可能多的错误。错误修正从提交的错误版本推断可能的正确代码版本(通常只在简单的情况下发生)，3.2上下文无关语法。与角色上下文无关的语法说明编程语言的语法结构与使用正则表达式说明词汇结构非常相似，不同之处在于与上下文无关的语法包括递归规则。例如，整数算术表达式的上下文无关语法为：exp-exp op exp |(exp)| number op-|-| * number的正则表达式number=digitdigit * digit=0 | 1 |VNVT=P是结果集或语法规则(a)。其中A VN是起始符号，(VNVT) * S是起始符号，

3、-，*，/，(，)VN=exp，op Exp生成起始符号：exp-exp opexp exp-(exp箭头的右侧定义了结构的布局。生成式格式(a)称为Backus-Naur范式(或BNF)，根据符号，只能写一种语法。通常，第一个生成表达式的左侧是开始符号，使用小写字母表示终止符。大写或包围的表达非终止符a-1，a-我们可以写成A- 1 | 2 | | n。例如，简单算术表达式的语法是： E-E O E | (E) | num O-|-| * |/，语法的Chomsky分类包括4茄子语法3360无限语法(0英寸)上下文相关语法(1英寸)上下文相关语法(2 常规语法s0a | 1b | 0a0a

4、| 1b | 0sb1b | 1 |派生和摘要中的角色上下文无关语法规则，根据规则定义的结构中的符号确定与语法匹配的字符串集。 例如，相应的语法EXP-EXP OP EXP |(EXP)| Number OP-|-| *(34-3)* 42是有效的字符串(34)，42不是有效的字符串语法规则。通过导出或汇总符号符号的正则集直接推导and，A-是语法G的生成表达式。如果V和W符合：v=A，w=，(VNVT) *直接引导V到W，或者直接引导W到V。V=w直接推导是将生成表达式的左侧(不是终止符)替换为生成表达式的右侧部分的过程，是将生成表达式的右侧部分替换为生成表达式的左侧非终止符的过程(例如，语

5、法G: S0S1)。S01直接提取：0s 100S 11(s0s 1)00s 11000S 111(s0s 1)000S 111 0000111(s01)s0s 1(s0s 1)，提取和减少=的闭合，=其中例如，exp-exp op exp |(exp)| num op-| | *(34-3)* 42的导出为3360 (1) exp=exp op exp (exp-) 如果(VNVT) *，语法G的文章G的文章w是G的文章模式，w只包含终结符，则w是G的文章(例如G 3360 s0s 1)。0s 1，000 s11，000 s111都是G的文章0000111是G的句子，语法G定义的语言是L 语

6、法G和l (g)的关系取决于语法，通过派生与以下语法对应的语言：G:ee t | tttf | ff(e)| a ee t t f t a t a t a t a ff a ff a af a a a a a l(G)，(字符串中的0和1个数相同，语法如下：a0b | 1cb1 | 1a | 0bbc 0 | 0a | 1cc，3.3分析树和抽象语法树，3.3.1分析树分析树中的角色分析树是表示令牌字符串结构的非常有用的表示。解析树视觉化表现法导出，例如： ee T | tttf | f f f f(E)| I I ii 的导出和解析树，e=e t，e=E=E T，E=E T，=e t，=衍生

7、表示不能唯一表示字符串的结构，分析树可以。分析树的定义语法g的分析树之一是标记的树：树的根节点。用起始符号标记的树s每个叶节点都标记为终结器，或每个非叶节点都标记为非终结器。如果节点A VN有n个孩子，则每个x1、x2、xn(可以是终结器或非终结器)A-X1X2Xn P。最左侧和最右侧的派生最左侧的派生意味着，在每个派生的步骤中，用分析树中的旧序列号替换最左侧的非终结器。例如，exp-exp op exp |(exp)| num op-| | *“num num”的最左侧派生为exp=exp op exp=num op exp=num exp=这是分析分析树和派生关系每个派生生成一个分析树。多

8、个导出可以产生同一分析树的最左侧和最右侧导出。分析树唯一表示的语法结构，不一定需要其他派生。3.3.2抽象语法树抽象语法树中的必需分析树包含与编译器生成可执行代码无关的信息。表达式(34-3)*42的分析树和抽象语法树如下所示：抽象语法树的定义抽象语法树是实际令牌字符串的抽象表示，它包含转换所需的所有信息(准确显示字符串的含义内容)。比分析树更有效的表示分析器通过分析树表示的所有步骤。仅配置一个抽象语法树。例如，语法说明-| other-if ()-else |-0 | 1字符串“if (0) other else other”的分析树和抽象语法树具有：3.4二重性，通常为E=可能有多个分析树

9、(或最左边/最右边的派生)，如整数算术表达式语法3360ee | ee。两个最左边的派生：1:e e e e e e e ie ii e ii e ii ii 2:e e e ie ii e ii e ii 2，双性语法中的一个字符串与两个不同的语法树(或两个不同的最左边) ，如何解决对偶问题解决两个茄子对偶问题的基本方法：设置规则，指示在每个对偶情况下哪些语法树是正确的。消除异义性规则：乘法的优先级高于加法和加法。整数算术表达式语法：ee | ee | (e) | I字符串“I I I I I I”有两个不同的语法树3360牙齿。根据两个茄子语义消除规则，第一个是正确的。将语法变更为强制正确分析树结构的格式，可以解决双重性。例如，E-E E | EE | (E) |添加I优先级将具有相同优先级的运算符汇总到组中，并针对每