编译原理-语法分析

《编译原理-语法分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、往其前端的中心部件就是语法分析器。语法分析器在编译器中的位置和作用：23.1.1语法分析器的作用（续）根据词法分析器提供的记号流，为语法正确的输入构造分析树（或语法树），这是本章的重点，在以后各节中详细讨论；检查输入中的语法（可能包括词法）错误，并调用出错处理器进行适当处理，下边简单介绍语法错误处理的基本原则，而在以后的讨论中忽略此问题。语法分析器的两个重要作用：33.1.2语法错误的处理原则词法错误如非法字符或拼写错关键字、标识符等@intege20times语法错误是指语法结构出错，如少分号、begin/end不配对等beginx:=a

3、+by:=x;静态语义错误：如类型不一致、参数不匹配等a,b:integer;x:array[1..10]ofinteger;x:=a+b;动态语义错误(逻辑错误)：如死循环、变量为零时作除数等while(t){...};a:=a/b;<1>源程序中可能出现的错误两类：语法（包括词法）错误和语义错误43.1.2语法错误的处理原则（续1）大多数错误的诊断和恢复集中在语法分析阶段。一个原因是大多数错误是语法错误，另一个原因是语法分析方法的准确性，它们能以非常有效的方法诊断语法错误。编译时想要准确诊断语义或逻辑错误有时是很困难的。对语法错误的处理

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

5、.2语法错误的处理原则（续3）紧急方式：x:=a+b+d;--丢弃b后若干记号，直到遇到+短语级恢复：x:=a+b;--加入分号，使之成为一个赋值句y:=c+d;例3.1下述两条是有语法错误的语句，其中第一条赋值句结束时忘记加分号，采用紧急恢复方式和短语级恢复方式的可能结果分别如下所示。x:=a+by:=c+d;73.2上下文无关文法(ContextFreeGrammar,CFG)3.2.1CFG的定义与表示定义3.1CFG是一个四元组G=（N，T，P，S），其中（1）N是非终结符（Nonterminals）的有限集合；（2）T是终结符（T

6、erminals）的有限集合，且N∩T=Φ；（3）P是产生式（Productions）的有限集合，A→α，其中A∈N（左部），α∈(N∪T)*（右部），若α=ε，则称A→ε为空产生式（也可以记为A→）；（4）S是非终结符，称为文法的开始符号（Startsymbol）。■83.2.1CFG的定义与表示（续1）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）例3.2简单算术表达式的上下文无关文法可表示如下：<1>产生式的一般读法可以将产生式中的记号→读作

7、“定义为”或者“可导出”。更一般的，“E→E+E”可用自然语言表述为“算术表达式定义为两个算术表达式相加”。或者“一个算术表达式加上另一个算术表达式，仍然是一个算术表达式”。93.2.1CFG的定义与表示（续2）前提：若文法正确，第一个产生式的左部是文法开始符号S则：N是可以出现在产生式左边符号的集合，T是绝不出现在产生式左边符号的集合（记号）P:E→E+E（1）E→E*E（2）E→（E）（3）E→-E（4）E→id（5）S=EN={E}T={+，*，(，)，-，id}<2>由产生式集表示CFG103.2.1CFG的定义与表示（续3）(a)

8、用大小写区分：E→id(b)用""区分：E→"id"E→E"+"E(c)用<>区分：→+约定：大写英文字母A、B、C表示非终结符；小写英文字母a、b、c表示终结