编译原理-语法分析
42页1、1,第三章 语法分析,词法分析:字母是元素,组成字符串,记号的集合,线性结构 语法分析:记号是元素,组成句子, 句子的集合,树结构 语法的双重含意: 语法规则:上下文无关文法(子集LL文法或LR文法) 语法分析:下推自动机(LL或LR分析器),自上而下和自下而上分析,本章主要内容: 与语法分析有关的基本概念和相关问题 上下文无关文法 自上而下分析 自下而上分析 上机作业第二部分:函数绘图语言的语法分析器,结束(2010年3月25日),2,3.1 语法分析的若干问题 3.1.1 语法分析器的作用,语法分析器是编译器前端的重要组成部分,许多编译器,特别是由自动生成工具构造的编译器,往往其前端的中心部件就是语法分析器。语法分析器在编译器中的位置和作用:,3,3.1.1 语法分析器的作用(续),根据词法分析器提供的记号流,为语法正确的输入构造分析树(或语法树),这是本章的重点,在以后各节中详细讨论; 检查输入中的语法(可能包括词法)错误,并调用出错处理器进行适当处理,下边简单介绍语法错误处理的基本原则,而在以后的讨论中忽略此问题。,语法分析器的两个重要作用:,4,3.1.2 语法错误的处理原则
2、,词法错误如非法字符或拼写错关键字、标识符等 intege 20times 语法错误是指语法结构出错,如少分号、begin/end不配对等begin x:=a+b y:=x; 静态语义错误:如类型不一致、参数不匹配等a,b:integer; x:array110 of integer;x:=a+b; 动态语义错误(逻辑错误):如死循环、变量为零时作除数等while (t) .; a:=a/b;, 源程序中可能出现的错误 两类:语法(包括词法)错误和语义错误,5,3.1.2 语法错误的处理原则(续1),大多数错误的诊断和恢复集中在语法分析阶段。一个原因是大多数错误是语法错误,另一个原因是语法分析方法的准确性,它们能以非常有效的方法诊断语法错误。编译时想要准确诊断语义或逻辑错误有时是很困难的。,对语法错误的处理,一般希望达到以下基本目标: 清楚而准确地报告错误的出现,地点正确、不漏报、不错报也不多报; 迅速从每个错误中恢复过来(以便分析继续进行); 不应使对语法正确源程序的分析速度降低太多。, 语法错误处理的目标,6,3.1.2 语法错误的处理原则(续2),紧急方式恢复:抛弃若干输入,直到
3、遇到同步记号。 短语级恢复:采用串替换的方式对剩余输入进行局部纠正(抛弃插入)。 出错产生式:用出错产生式捕捉错误(预测错误)。预置型的短语级恢复方式。 全局纠正:对错误输入序列x,找相近序列y,使得x变换成y所需的修改、插入、删除次数最少。, 语法错误的基本恢复策略,7,3.1.2 语法错误的处理原则(续3),紧急方式: x := a + b + d; - 丢弃b后若干记号,直到遇到+ 短语级恢复:x := a + b; - 加入分号,使之成为一个赋值句y := c + d;,例3.1 下述两条是有语法错误的语句,其中第一条赋值句结束时忘记加分号,采用紧急恢复方式和短语级恢复方式的可能结果分别如下所示。,x := a + b y := c + d;,8,3.2 上下文无关文法(Context Free Grammar,CFG) 3.2.1 CFG的定义与表示,定义3.1 CFG是一个四元组G =(N,T,P,S),其中 (1) N是非终结符(Nonterminals)的有限集合; (2) T是终结符(Terminals)的有限集合,且NT=; (3) P是产生式(Production
4、s)的有限集合,A,其中AN(左部),(NT)*(右部),若=,则称A为空产生式(也可以记为A ); (4) S是非终结符,称为文法的开始符号(Start symbol)。,9,3.2.1 CFG的定义与表示(续1),N = E T = +,*,(,),-,id S = E P: E E + E (1)E E * E (2)E (E) (3) (G3.1)E -E (4)E id (5),例3.2 简单算术表达式的上下文无关文法可表示如下:, 产生式的一般读法可以将产生式中的记号读作“定义为”或者“可导出”。更一般的,“E E + E”可用自然语言表述为“算术表达式定义为两个算术表达式相加”。或者“一个算术表达式加上另一个算术表达式,仍然是一个算术表达式”。,10,3.2.1 CFG的定义与表示(续2),前提:若文法正确,第一个产生式的左部是文法开始符号S 则: N是可以出现在产生式左边符号的集合,T是绝不出现在产生式左边符号的集合(记号),P: E E + E (1)E E * E (2)E (E) (3)E -E (4)E id (5),S=E N=E T=+,*,(,),-,id
《编译原理-语法分析》由会员xzh****18分享,可在线阅读,更多相关《编译原理-语法分析》请在金锄头文库上搜索。
爱心树活动教案
世界文化之旅0
七年级学年知识归纳
七年级历史下册第二单元第12课《蒙古的兴起和元朝的建立》课件人教新课标版
一片美丽的叶子
非谓语动词 (6)
[中学联盟]江苏省太仓市第二中学七年级英语上册教学课件:Unit3READING1 (2)
“数与代数”教材修订说明
2014年7月师院培训
字理教学快捷入门之一20140521s
议论文写作指导之新材料作文审题立意 (2)
压缩语段 (2)
琵琶行课件 (2)
2014年各年级的教学计划和建议
(苏教版)五年级数学下册找规律第二课时
秋姑娘的信 (5)
苏教版数学五年级上册《复式条形统计图》课件 (2)
【名校课时通】2014届九年级化学全册第二单元探秘水世界第三节原子的构成名师教学课件鲁教版
《逻辑与语文》课件2
《检阅》[1]
2022-05-20 22页
2022-05-20 29页
2022-04-21 115页
2022-04-21 68页
2022-04-17 34页
2022-04-17 38页
2022-04-15 89页
2022-04-15 181页
2022-04-15 148页
2022-04-15 81页