编译原理-语法分析.ppt

《编译原理-语法分析.ppt》由会员分享，可在线阅读，更多相关《编译原理-语法分析.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章 语法分析 词法分析：字母是元素，组成字符串，记号的集合，线性结构语法分析：记号是元素，组成句子，句子的集合，树结构语法的双重含意：1.语法规则：上下文无关文法（子集LL文法或LR文法）2.语法分析：下推自动机（LL或LR分析器），自上而下和自下而上分析 本章主要内容：1.与语法分析有关的基本概念和相关问题2.上下文无关文法3.自上而下分析4.自下而上分析5.上机作业第二部分：函数绘图语言的语法分析器结束（2010年3月25日）13.1 语法分析的若干问题 语法分析器的作用 语法分析器是编译器前端的重要组成部分，许多编译器，特别是由自动生成工具构造的编译器，往往其前端的中心部件就是语法分

2、析器。语法分析器在编译器中的位置和作用：2 语法分析器的作用（续）1.根据词法分析器提供的记号流，为语法正确的输入构造分析树（或语法树），这是本章的重点，在以后各节中详细讨论；2.检查输入中的语法（可能包括词法）错误，并调用出错处理器进行适当处理，下边简单介绍语法错误处理的基本原则，而在以后的讨论中忽略此问题。语法分析器的两个重要作用：3 语法错误的处理原则 1.词法错误如非法字符或拼写错关键字、标识符等 intege 20times2.语法错误是指语法结构出错，如少分号、begin/end不配对等begin x:=a+b y:=x;3.静态语义错误：如类型不一致、参数不匹配等a,b:inte

3、ger;x:array1.10 of integer;x:=a+b;4.动态语义错误(逻辑错误)：如死循环、变量为零时作除数等while(t).;a:=a/b;源程序中可能出现的错误 两类：语法（包括词法）错误和语义错误4 语法错误的处理原则（续1）大多数错误的诊断和恢复集中在语法分析阶段。一个原因是大多数错误是语法错误，另一个原因是语法分析方法的准确性，它们能以非常有效的方法诊断语法错误。编译时想要准确诊断语义或逻辑错误有时是很困难的。对语法错误的处理，一般希望达到以下基本目标：1.清楚而准确地报告错误的出现，地点正确、不漏报、不错报也不多报；2.迅速从每个错误中恢复过来（以便分析继续进行）

4、；3.不应使对语法正确源程序的分析速度降低太多。语法错误处理的目标5 语法错误的处理原则（续2）1.紧急方式恢复：抛弃若干输入，直到遇到同步记号。2.短语级恢复：采用串替换的方式对剩余输入进行局部纠正（抛弃插入）。3.出错产生式：用出错产生式捕捉错误（预测错误）。预置型的短语级恢复方式。4.全局纠正：对错误输入序列x，找相近序列y，使得x变换成y所需的修改、插入、删除次数最少。语法错误的基本恢复策略 6 语法错误的处理原则（续3）1.紧急方式：x:=a+b+d;-丢弃b后若干记号，直到遇到+2.短语级恢复：x:=a+b;-加入分号，使之成为一个赋值句 y:=c+d;例3.1 下述两条是有语法错

5、误的语句，其中第一条赋值句结束时忘记加分号，采用紧急恢复方式和短语级恢复方式的可能结果分别如下所示。x:=a+by:=c+d;73.2 上下文无关文法(Context Free Grammar,CFG)CFG的定义与表示 定义3.1 CFG是一个四元组G=（N，T，P，S），其中（1）N是非终结符（Nonterminals）的有限集合；（2）T是终结符（Terminals）的有限集合，且NT=；（3）P是产生式（Productions）的有限集合，A，其中AN（左部），(NT)*（右部），若=，则称A为空产生式（也可以记为A）；（4）S是非终结符，称为文法的开始符号（Start symbol）。8