西安电子科技大学《编译原理》

《西安电子科技大学《编译原理》》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章语法分析词法分析：元素是字母表，组成字符串，线性结构，单词的集合语法分析：元素是终结符，组成句子，树结构，句子的集合语法的双重含意：①语法规则：上下文无关文法（子集－LL文法或LR文法）②语法分析：下推自动机（LL或LR分析器），自上而下和自下而上分析本章主要内容：<1>与语法分析有关的基本概念和相关问题<2>上下文无关文法<3>自上而下分析<4>自下而上分析<5>上机作业－第二部分：函数绘图语言的语法分析器13.1语法分析的若干问题3.1.1语法分析器的作用语法分析器是编译器前端的重要组成部分，许多编译器，特别是由自动生

2、成工具构造的编译器，往往其前端的中心部件就是语法分析器。语法分析器在编译器中的位置和作用下：它的主要作用有两点：<1>根据词法分析器提供的记号流，为语法正确的输入构造分析树（或语法树），这是本章的重点，在以后各节中详细讨论；<2>检查输入中的语法（可能包括词法）错误，并调用出错处理器进行适当处理，下边简单介绍语法错误处理的基本原则，而在以后的讨论中忽略此问题。23.1.2语法错误的处理原则<1>源程序中可能出现的错误两类：语法错误和语义错误。①词法错误如非法字符或拼写错关键字、标识符等；@intege20times②语法错误是指

3、语法结构出错，如少分号、begin/end不配对等。beginx:=a+by:=x;③静态语义错误：如类型不一致、参数不匹配等；a,b:integer;x:array[1..10]ofinteger;x:=a+b;④动态语义错误（逻辑错误）：如无穷递归、变量为零时作除数等。while(t){...};a:=a/b;大多数错误的诊断和恢复集中在语法分析阶段。一个原因是大多数错误是语法错误，另一个原因是语法分析方法的准确性，它们能以非常有效的方法诊断语法错误。在编译的时侯，想要准确诊断语义或逻辑错误有时是很困难的。33.1.2语法错

4、误的处理原则（续1）<2>语法错误处理的目标对语法错误的处理，一般希望达到以下基本目标：清楚而准确地报告错误的出现，地点正确、不漏报、不错报也不多报；迅速地从每个错误中恢复过来（以便分析继续进行）；不应使对语法正确源程序的分析速度降低太多。43.1.2语法错误的处理原则（续2）<3>语法错误的基本恢复策略紧急方式恢复：抛弃若干输入，直到遇到同步记号。短语级恢复：采用串替换的方式对剩余输入进行局部纠正（抛弃＋插入）。出错产生式：用出错产生式捕捉错误（预测错误）。预置型的短语级恢复方式。全局纠正：对错误输入序列x，找相近序列y，使得

5、x变换成y所需的修改、插入、删除次数最少。例3.1下述两条是有语法错误的语句，其中第一条赋值句结束时忘记加分号，采用紧急恢复方式和短语级恢复方式的可能结果分别如下所示。x:=a+by:=c+d;紧急方式：x:=a+b+d;--丢弃b之后的若干记号，直到遇到同步记号+为止。短语级恢复：x:=a+b;--加入分号，使之成为一个赋值句y:=c+d;53.2上下文无关文法(ContextFreeGrammar,CFG)3.2.1CFG的定义与表示定义3.1CFG是一个四元组G=（N，T，P，S），其中（1）N是非终结符（Nontermi

6、nals）的有限集合；（2）T是终结符（Terminals）的有限集合，且N∩T=Φ；（3）P是产生式（Productions）的有限集合，A→α，其中A∈N（左部），α∈(N∪T)*（右部），若α=ε，则称A→ε为空产生式（也可以记为A→）；（4）S是非终结符，称为文法的开始符号（Startsymbol）。■例3.2简单算术表达式的上下文无关文法可表示如下：N={E}T={+，*，(，)，-，id}S=EP:E→E+E（1）E→E*E（2）E→（E）（3）(G3.1)E→-E（4）E→id（5）6<1>由产生式集表示CFG3.

7、2.1CFG的定义与表示（续1）前提：若文法正确，第一个产生式的左部是文法开始符号S则：N是仅出现在产生式左边符号的集合，T是所有不出现在产生式左边符号的集合（记号）P:E→E+E（1）E→E*E（2）E→（E）（3）E→-E（4）E→id（5）<2>产生式的一般读法可以将产生式中的记号→读作“定义为”或者“可导出”。更一般的，“E→E+E”可用自然语言表述为“算术表达式定义为两个算术表达式相加”，或者“一个算术表达式加上另一个算术表达式，仍然是一个算术表达式”。<3>终结符与非终结符书写上的区分(a)用大小写区分：E→id(b

8、)用“”区分：E→"id"E→E"+"E(c)用<>区分：→+约定：大写英文字母A、B、C表示非终结符；小写英文字母a、b、c表示终结符；小写希腊字母α、β、δ表示任意文法符号序列。S=EN={E}T={+，*，(，)，-，id}7<4>产生式