吉林大学：《编译原理》课程教学资源（PPT课件讲稿）第四章 文法与语法分析

第四章文法与语法分析 主要内容: 语法分析概述 文法 进行语法分析的几种方法 语法错误处理

第四章文法与语法分析 主要内容： ⚫ 语法分析概述 ⚫ 文法 ⚫ 进行语法分析的几种方法 ⚫ 语法错误处理

语法分析概述 口语法分析器和识别器 语法分析的功能 口语法错误类别 口语法错误的处理

语法分析概述 ❑ 语法分析器和识别器 ❑ 语法分析的功能 ❑ 语法错误类别 ❑ 语法错误的处理

语法分析器和识别器 语法分析器的功能: Token/Token list arser 语法树/语法错误信息 语法错误类别 程序的开始符,语句(表达式)的开始符 (后继符)错 标识符(常量)错:该出现时未出现 括号类错误:不匹配 分隔符错: ass i gnment;

⚫ 语法分析器和识别器 ⚫ 语法分析器的功能： ⚫ 语法错误类别 程序的开始符，语句（表达式）的开始符 （后继符）错 标识符（常量）错：该出现时未出现 括号类错误：不匹配 分隔符错：assignment; Token/TokenList Parser 语法树/语法错误信息

●语法错误处理 要求:报告错误出现的位置 修复错误并继续检查后续部分 执行开销不应太大 修改策略 插入/删除/修改 应急方式恢复: 一定义同步符号集合(分隔符,end,某些 语句头符,else等) 发现错误时,跳过一些 Token,直到找 到某个同步符号,再继续进行分析。 同步符号保证接下来的分析是从正确的 头位置开始

⚫ 语法错误处理 要求：报告错误出现的位置 修复错误并继续检查后续部分 执行开销不应太大 修改策略： 插入/删除/修改 应急方式恢复: 定义同步符号集合(分隔符，end,某些 语句头符， else等) 发现错误时，跳过一些Token，直到找 到某个同步符号，再继续进行分析。 同步符号保证接下来的分析是从正确的 头位置开始

文法 ●文法能清晰地描述程序设计语言的语法构成 易于理解 ●文法能自动地构造有效的语法分析器,检 查源程序是否符合语言规定的语法形式。 ●文法定义可以了解程序设计语言的结构,有 利于将源程序转化为目标代码,以及检查出 语法错误。 ●基于文法实现的语言易于扩展

文法 ⚫ 文法能清晰地描述程序设计语言的语法构成 易于理解。 ⚫ 文法能自动地构造有效的语法分析器，检 查源程序是否符合语言规定的语法形式。 ⚫ 文法定义可以了解程序设计语言的结构，有 利于将源程序转化为目标代码，以及检查出 语法错误。 ⚫ 基于文法实现的语言易于扩展

小语言 Micro的定义 P>begin VDL, SL end VDL >VDVD; VDL ●VD→ var id:T SL→S|s;SL s>id: = E write(E) read(id) o T>integer real E → id num E+ E E米E (∈E)

小语言Micro的定义 ⚫ P → begin VDL;SL end. ⚫ VDL → VD | VD ; VDL ⚫ VD → var id : T ⚫ SL → S | S ; SL ⚫ S → id:= E | write(E) | read(id) ⚫ T → integer | real ⚫ E → id | num | E + E | E * E |(E)

文法的定义 ●文法G定义为四元组r,V,S,P) V是有限的终极符集合 V是有限的非终极符集合 S是开始符,S∈V P是产生式的集合,且具有下面的形式 α→>β,其中α,β∈VN)*

文法的定义 ⚫文法G定义为四元组(VT,VN,S,P) ▪ VT是有限的终极符集合 ▪ VN是有限的非终极符集合 ▪ S是开始符，S VN ▪ P是产生式的集合，且具有下面的形式：  →，其中，(VTVN )*

文法的分类 0型文法:也称为短语文法,其产生式具有形式 a→β,其中α,β∈(∪V)*,并且a至少含一个非 终极符。 1型文法:也称为上下文有关文法。它是0型文法 的特例,要求a≤|β|(S→λ例外,但S不得出 现于产生式右部)。 2型文法:也称为上下文无关文法。它是1型文法 的特例,即要求产生式左部是一个非终极符: A→β。 ●3型文法:也称为正则文法。它是2型文法的特例 即产生式的右部至多有两个符号,而且具有下面 形式之 A→a,A→aB 其中A,B∈V,a∈Ⅵ

文法的分类 ⚫ O型文法: 也称为短语文法，其产生式具有形式: →，其中,(VTVN )*，并且至少含一个非 终极符 。 ⚫ 1型文法: 也称为上下文有关文法。它是0型文法 的特例，要求||  || (S→例外，但S不得出 现于产生式右部)。 ⚫ 2型文法: 也称为上下文无关文法。它是1型文法 的特例，即要求产生式左部是一个非终极符: A→ 。 ⚫ 3型文法: 也称为正则文法。它是2型文法的特例， 即产生式的右部至多有两个符号，而且具有下面 形式之一: A →a ，A →a B 其中A,BVN ，aVT

上下文无关文法(CFG) 定义为四元组W,V,s,P) V是有限的终极符集合 V是有限的非终极符集合 S是开始符,S∈V P是产生式的集合,且具有下面的形式: A→12… 其中A∈V,X∈(r),右部可空

上下文无关文法（CFG） ⚫定义为四元组(VT,VN,S,P) ▪ VT是有限的终极符集合 ▪ VN是有限的非终极符集合 ▪ S是开始符，S VN ▪ P是产生式的集合，且具有下面的形式： A→X1X2…Xn 其中AVN，Xi (VTVN ) ，右部可空

●推导:如果A→>B是一个产生式,则有 aAy→>0βy,其中→表示一步推导(用A→β)。 这时称aBy是由aA直接推导的。→的含义是 使用一条规则,代替→左边的某个符号,产 生→右端的符号串 ●a→+β:表示α通过一步或多步可推导出β ●→*β:表示a通过0步或多步可推导出β

⚫ 推导：如果A→是一个产生式，则有 A ,其中表示一步推导(用A →)。 这时称是由A直接推导的。 的含义是， 使用一条规则，代替左边的某个符号，产 生右端的符号串 ⚫  + : 表示通过一步或多步可推导出 ⚫  *  : 表示通过0步或多步可推导出