语法分析在编译程序中的逻辑位置 语 法 分 析 表 处 理 源 程 序 词 法 分 析 语 义 分 析 中 间 代 码 生 成 中 间 代 优 化 目 标 代 码 生 成 目 标 程 序 错 误 处 理

第三章 语法分析(Parsing / Syntax Analysis) —自顶向下分析方法 语法分析程序的功能简介 语法分析的理论根据—文法 语法分析方法的分类： 自顶向下语法分析方法 (Top-Down) 自底向上语法分析方法 (Bottom-Up) 两种自顶向下语法分析方法： 递归下降子程序方法 LL（1）方法 2

第三章 语法分析 第一部分 形式语言基础(1) 语言与文法 文法的定义 文法的分类 文法的相关概念 3

1 语法分析程序的功能 语法树 / 语法分析器 语法错误信息 Token List 语法分析的任务是： 把词法分析的输出作为输入，按照一定的语法规则，从源程序符号串中识别出各类语法成分，同时进行语法检查，为语义分析和代码生成做准备; 语法分析器 语法树 / 语法错误信息 Token List

2 语言与文法 自然语言：是人类在社会生活中发展起来的，用于日常相互交流的符号系统。 2018/11/22 2 语言与文法 自然语言：是人类在社会生活中发展起来的，用于日常相互交流的符号系统。 形式语言：是为了特定应用而设计的人工语言，是用精确的数学或机器可处理的公式定义的语言，公式由人们公认的数学和逻辑符号组成。 程序设计语言：是专门设计用来表达计算过程的形式语言，具有语法严格、结构正规及便于计算机处理等特点。 符号串

语法与语义 一个程序设计语言是一个记号系统，它的完整定义包括语法和语义两个方面。 语法（Grammar）是一组规则，用它可以产生一个符合其规则规定的合法程序,语法是语言的形式。 语义(Semantic )是语言的内容，以语法为媒介来说明语义是语言的实质。 2.1

文 法 文法是描述语言的语法结构的形式规则 int max(int x, int y); void printStar( ); 3. <类型>  <简单类型> | <指针类型> | <自定义类型> 4. <简单类型>  int | char | double | float | long | short | void 5. <指针类型>  <简单类型> * | <自定义类型>* 6. <自定义类型>  enum id | struct id | union id | id

2.1 文法的定义 一个文法G是一个四元组: G = ( VN, VT, S, P ) 其中： VT：有限的终极符集合 S：开始符，SVN P：产生式（规则）的集合

文法G四元组: G = ( VN, VT, S, P ) VT 终极符，是一个语言不可再分的基本符号，一般用字母表里排在前面的小写字母表示，如a、b、 c。 VN 非终极符或中间符，一般用< >括起来或大写字母表示，它不出现在句子中。 注： 设V是文法G的符号集，则有: V = VN ∪ VT , VN ∩VT =  一般用、、γ 表示文法V中符号串

P 产生式:表示文法的规则。其形式为：    或  ::=  其中: ① ：称为产生式的左部(头）， ∈V+ (≠ε)，并且至少含有一个非终极符； ② ：称为产生式的右部（体），∈V* ； ③ “”或“:: = ” ：读作“定义为”或“由…组成”； ④ 开始符号S必须至少在某个产生式的左部出现一次。 ⑤为了书写方便，若干个左部相同的产生式，如 ： P  1 P  2 …… P  n 可合并为一个，缩写为: P  1 | 2 | … | n 其中，每个i 称为 P 的一个候选式，符号“|”读作“或” 。

例1 G =（VN,VT, S, P） 其中：VN={ S , A} VT={ a, b, c } P={S  aA, S  b, A  Ac , A  c } G： S  aA | b A  Ac | c G[S]： S aA S b A  Ac A  c G[S]： S  aA | b A  Ac | c

例2:定义简单的加减运算表达式的文法表示如下： G =（VN,VT, S, P） 其中：VN={ E, D } VT={ id, num } P={ E  E+D, E  E-D, E  D, D  id, num } G[E]： E  E+D | E-D | D D  id, num

SaPd PbPc | bc abcd S => aPd => abPcd => abbPccd abbccd …… 例3：文法G[S]: SaPd PbPc | bc abcd S => aPd => abPcd => abbPccd …… => abb…bPcc…cd => abb…bbccc…cd abbccd abbbcccd …… 文法G表示的语言为：L(G) = {abncnd | n≥1}

例4： 文法G[S]: S  aSd | P P  bPc | bc S => aSd => aaSdd => aaaSddd …… => a…aSd…d => a…aPd…d => a…abPcd…d => a…ab…bPc…cd…d L(G)={anbmcmdn | m ≥1,n≥0}

例5:字母表∑ ={a}上的符串集： S={a2n | n>=1} 其文法表示如下： G[S]： S  aa | Saa

例6：给出下面语言的上下文无关文法描述 (1) L1 = {abna | n≥0} S  aBa B bB |  (2) L2 = {anbn | n≥1} S aSb | ab (3) L3 = {anbnci | n≥1, i≥0} S  Sc | B B aBb | ab (3) L4 = {aibj | j≥ i≥1} S  aSb | Sb | ab

(5) L5 = {a2nb3n | n≥0} S  aaSbbb |  (6)L6 = {anbnambm | n，m≥0} S  AA A aAb |  (7) L7 = {1n0m1m0n | n, m≥0} S  1S0 | B B 0B1 |  (8) L8= {ar |  属于{0，a}*，r表示的逆序 ，如=00aa0,则r =0aa00} S  0S0 | aSa | a

2018/11/22 3 文法的分类 O型文法：也称为短语文法，其产生式具有形式: →，其中 (VTVN)+, 并且至少含一个非终极符 ， (VTVN)* 。 1型文法：也称为上下文相关文法。它是0型文法的特例，要求A  , A∈VN ，，∈(VT∪VN)*， ∈(VT∪VN)*。 2型文法：也称为上下文无关文法。它是1型文法的特例，即要求产生式左部是一个非终极符: AX1X2…Xn。 3型文法：也称为正则文法。它是2型文法的特例，即产生式具有下面形式之一: A →a ，A →a B, 其中A,BVN ，aVT 。 也称为右线性文法。 2型文法中A->x1x2x3，A只能有这一种定义方式；而1型文法可以在不同的上下文中有不同的解释，cAb->cx1x2x3b, dAB->dy1y2y3B, 在cb环境下可以解释为x1x2x3，在dB环境下可以解释为y1y2y3。1型的表示能力增强，但要考查上下文也增大识别的难度；在0型就更为灵活了。 3型文法中一个状态A接收一个输入改就到另一个状态，表现出状态的线性变化，但无法实现自循环特性，无法表示2型中的A->xAy形成的xnyn。

四类文法之间的关系 2型文法 1型文法 0型文法 3型文法 0型文法 1型文法 2型文法 3型文法 产生式限制越来越严 描述功能越来越强

定理：给定一个正则文法G(VN, VT, P, S) 构造一个等价的有限自动机 M(S,,f,s0,Z)，使得L(G)=L(M)。 正则文法与有限自动机FA的相互转换 定理：给定一个正则文法G(VN, VT, P, S) 构造一个等价的有限自动机 M(S,,f,s0,Z)，使得L(G)=L(M)。 构造方法： 令 M:S=VN∪{Z0}； =VT ； s0=S; Z={Z0}; 转换函数f: 如果有XaY 如果有Xa 如果有X X Y a X Z0 a X

DMA： a W X a Y b Z c 等价正则文法： W aX X bY Y c X aX 等价正则表达式： aa*bc 21

例:将 下列正则文法转换为相应的DMA。 Y aY | bZ Z bZ |  X aY 等价DMA： 等价正则表达式： aa*bb* 2018/11/22 例:将 下列正则文法转换为相应的DMA。 X aY Y aY | bZ Z bZ |  等价DMA： a b X Y a Z b 等价正则表达式： aa*bb* 22

自嵌入特性是区分真正2型上下文无关文法与3型正则文法的判定标准。 2018/11/22 自嵌入特性是区分真正2型上下文无关文法与3型正则文法的判定标准。 自嵌入特性 A* A ，且 和不能为空串 例： S * uAy， A* vAx ， A* w 则： L(G) = {uviwxiy | i≥0} 这种周期形式是正规文法所不具备的。

其中AVN，Xi(VTVN) ，右部可空。 在编译技术中通常用3型正则文法来描述高级程序设计语言的词法部分，2型文法或上下文无关文法描述程序设计语言的语法结构，比如描述算术表达式，描述各种语句等等。 对“文法”一词如无特殊说明则均指上下文无关文法。其文法产生式的集合具有下面的形式： AX1X2…Xn 其中AVN，Xi(VTVN) ，右部可空。

1.推导（直接推导）：如果A是一个产生式，则有A ,其中表示一步推导。这时称是由A直接推导的。 4 文法相关概念--推导和归约 1.推导（直接推导）：如果A是一个产生式，则有A ,其中表示一步推导。这时称是由A直接推导的。 的含义是，使用一条规则，代替左边的某个符号，产生右端的符号串。  + :表示通过一步或多步可推导出  * :表示通过零步或多步可推导出 推导的逆过程称为归约。

例：对于表达式文法G: E→E+E （1） | E*E （2） | (E) （3） | i （4） 符号串 i + i*i　的直接推导序列是： （1） 即：E =>+ i+i*i E => E+E => i+E => i+E*E => i+i*E => i+i*i （4） （2）

在推导过程中，总是对当前符号串中最右边的非终极符进行替换，称为最右推导，又称之为规范推导, 并用符号 rm 表示。 2.最右推导 在推导过程中，总是对当前符号串中最右边的非终极符进行替换，称为最右推导，又称之为规范推导, 并用符号 rm 表示。 规范推导的逆过程最左规约称为规范归约。 例：上述符号串 i+ i*i　的最右推导过程是： E => E+E => E+E*E => E+E*i => E+i*i => i+i*i 最右非终极符 最右非终极符 最右非终极符 最右非终极符 最右非终极符 即：E =>r m i+i*i +

在推导过程中，总是对当前符号串中最左边的非终极符进行替换，称为最左推导，并用符号 lm 表示。 3.最左推导 在推导过程中，总是对当前符号串中最左边的非终极符进行替换，称为最左推导，并用符号 lm 表示。 例：对于表达式文法G: E→E+E | E*E | (E) | i 符号串 i+ i*i　的最左推导过程是： E => E+E i+E => i+E*E => i+i*E => i+i*i 即：E =>l m i+i*i +

4.句型: 设有文法G ，S是文法G的开始符号，如果有: S *  , ∈(VT∪VN)* , 则称为G的句型。 最右推导得到的句型称为最右句型或规范句型 最左推导得到的句型称为最左句型。 5. 句子：设为文法G的一个句型，且只包含终极符，则称为G的句子。

6.语言： 所有句子的集合称为文法的语言。记作: L(G) = {α| S * , ∈VT* } 每一种高级程序设计语言都有自己的语法 符合高级语言文法的程序就是该语法的句子 所有程序组成的集合就构成了语言。 对于定义完的这些东西和程序设计语言的关系，以及他们如何用到程序设计语言中来，每一种高级程序设计语言都有自己的一套语法，看书上的时候，有的程序设计书后面的附录就带有语言的文法。所谓的句子就是用户写的程序，也就是每个人写的程序，如果符合文法的话都应该是文法的一个句子。所谓语言是什么呢？ 就是所有句子的集合，相当于语言中所有程序的集合。C语言有个文法，C语言是什么呢？就是C语言所有的程序组成的集合。徐家福老先生来吉大，问了好多人 什么是语言 很多人都没答上，实际上就是符合语言文法句子的集合，老先生说所谓语言是符合某些规则的符号串，这个跟我们的定义是一样的。所以对应到程序设计语言上，就是这么一种情形。真正的情形应该是什么样呢？

7. 短语：设S是文法的开始符，是句型(即有 S . ），如果满足条件： S 7.短语：设S是文法的开始符，是句型(即有 S *），如果满足条件： S* A A+  则称是句型相对于非终极符A的一个短语。 8.直接短语（简单短语）：如果满足条件： S* A A  则称是句型相对于非终极符A的一个简单短语。 9.句柄：一个句型可能有多个简单短语，其中最左的简单短语称之为句柄。

例1：设有文法 G[S]: S  AB A  Aa | bB B  a | Sb 问句型baSb的短语、直接短语和句柄。 S => AB => bBB =>baB => baSb B => Sb，所以Sb是句型baSb相对于B的短语且为直接短语 B => a，所以a是句型baSb相对于B的直接短语，还是句型的句柄 A + ba，所以ba是句型baSb相对于A的短语，但不是直接短语 S + baSb ，所以baSb是句型baSb相对于S的短语

例： C语言简单文法 <函数定义>  <类型>id(<参数表>){<函数体>} <函数体>  <声明语句><函数块> <声明语句>  <类型> id; <声明语句> |  <函数块>  <赋值语句><函数块>|<for语句><函数块>|<条件语句><函数块>|<调用语句><函数块>|<函数返回><函数块>| <赋值语句>  id=<表达式>; <for语句>  for(<赋值语句><逻辑表达式>;<后缀表达式>）{<函数体>} <条件语句>  if(<逻辑表达式>){<函数体>}<否则语句> <否则语句>  else{<函数体>}|  <调用语句>  id((<参数列表>) <函数返回>  return(<表达式>); <形参表>  <形参表> , <形参表> | <类型> id |  <类型>  <简单类型> | <指针类型> | <自定义类型> <简单类型>  int | char | double | float | long | short | void 随便写几句。C语言的文法比较乱，所以给一个pascal语言的文法定义，看一下意思： 程序 (开始符)首部 声明部分 体部分（VN） 首部程序头（program）（运行环境）; program是一个保留字 虽然有很多符号，但是他是一个终极符 接下来就一层层的往下定义 声明部分标号声明 常量声明 类型声明 变量声明 函数过程声明 然后每一个又可以继续定义 标号声明xxx 体部分条件 循环 赋值 输入输出 过程调用。。。 一直定义到终极符那个级别

例： PASCAL 语言简单文法 <程序>  <首部><声明部分><程序体> <首部>  program id; <声明部分>  var <标号声明><常量声明><类型声明><过程声明><函数声明> <程序体>  begin<条件语句><循环语句><赋值语句><输入输出语句><过程调用语句>...end. 随便写几句。C语言的文法比较乱，所以给一个pascal语言的文法定义，看一下意思： 程序 (开始符)首部 声明部分 体部分（VN） 首部程序头（program）（运行环境）; program是一个保留字 虽然有很多符号，但是他是一个终极符 接下来就一层层的往下定义 声明部分标号声明 常量声明 类型声明 变量声明 函数过程声明 然后每一个又可以继续定义 标号声明xxx 体部分条件 循环 赋值 输入输出 过程调用。。。 一直定义到终极符那个级别

课堂练习： 试构造产生下列语言的上下文无关文法 2018/11/22 课堂练习： 试构造产生下列语言的上下文无关文法 1. L(G)= {aibj | j≥ i≥1} S  aSb | Sb | ab 2. L(G)= {xnyxn | n≥1} S  xSx | xyx 3. L(G)={anb2n+1 | n>=1} S  aSbb | abbb 4. L(G)={a2m-1bm | m>0} S  aaSb | ab 5. L(G)={anbmck|m=n+k,n≥1,m>1,k≥1} S  AB A  aAb | ab B  bBc | bc 1. S  aSb | Sb | ab 2. SxSx| xyx 3. SaSbb|abbb 4.SaaSb|ab 5.SAB AaAb|ab BbBc|bc