[toc]

2文法和语言的形式定义

1 文法及其分类

• 文法是产生式的又穷非空的集合

• 文法$G$是一个四元组，$G[S]=(V_N,V_T,P,S)$

  • $V_N:$非终结符号集
  • $V_T:$终结符号集
  • $P:$表示产生式的有穷非空集合
  • $S:$开始符号（识别符号），至少在一条产生式中作为左部

• 文法分类：

  • 乔姆斯基(Chomsky)把文法分成四种类型：0型、1型、2型和3型
  • 0型文法 短语结构文法 Phrase Structure Gramma
  • 1型文法 上下文有关文法 Context-Sensitive Gramma
  • 2型文法 上下文无关文法 Context Free Gram
  • 3型文法 正规(正则)文法 Regular Gramma
    

2 语言的形式定义

3词法分析

1 DFA

• 确定的有穷自动机的形式定义$DFA， DFA=(Q,\sum,t,q_0,F)$

  • $Q:$有穷非空的状态集
  • $\sum:$有穷的输入字母表
  • $t:$映射$Q\times \sum \rightarrow Q$
  • $q_0:\in Q$，是开始状态集
  • $F:\subseteq Q$，非空终止状态集合

• FA的表示

  • 1. 状态转换表
  • 2. 状态转换图
       

• 被$DFA$ $A$识别的字符转集合记为$L(A)$

• 确定的有穷自动机中确定的含义：

  • 1. 只有唯一的一个开始状态
  • 2. 下一个输入字母唯一地确定了下一个状态

2 NFA

• 非确定的有穷自动机地形式定义$NFA$ $NFA=(Q,\sum,t,Q_0,F)$
  • $Q:$有穷非空的状态集
  • $\sum:$有穷的输入字母表
  • $t:$映射$Q\times \sum \rightarrow Q$
  • $Q_0:\in Q$，是开始状态集
  • $F:\subseteq Q$，非空终止状态集合

如果两个有穷自动机$A_1$和$A_2$满足$L(A_1)=L(A_2)$，则称有穷状态自动机$A_1$和$A_2$是等价的

3 NFA到DFA的转换

NFA的确定化

• 基本思想：将状态间的转换关系映射成状态子集间的转换关系
• 方法：子集法，造表法
• NFA存在的问题
  • 1. 开始状态的不确定
  • 2. 状态转换的不确定
  • 3. $\epsilon$的存在的不确定性

1. 状态子集$I$的$\epsilon$闭包:从一个结点出发，经过任意$\epsilon$边所能到达集合
2. $I_a$子集：由$I$的状态出发，经过一条$a$弧，(跳过$a$弧前的任意$\epsilon$弧)可到达的状态的集合称为$J$,则$I_a=\epsilon-CLOSURE(J)$
3. 利用子集法构造确定地有穷自动机DFA

举例：

DFA的最小化

• 寻找一个状态数不比$M$更多的$DFA Mˊ$，使得$M$和$Mˊ$所识别的符号串相同，即$L(M)=L(Mˊ)$。

  • 1. 构造状态集的划分
  • 2. 取每一组中的一个状态作代表
  • 3. 删去多余死状态

• DFA最小化的关键在于把它的状态集分成一些两两互不相交的子集，使得任何两个不同的子集中的状态都是可区别的，而同一子集中的任何两个状态都是等价的。

• 基本思想：如果从状态 p 出发能识别某一符号串 α 而停止于终态，那么从q 出发也能识别 α 而停止于终态；反之亦然。则称状态p 和 q 是等价的。如果 p 和 q 不等价，则说 p 和 q 是可区分的。

• 具体方法：

  • 对已有划分的每个子集进行如下分解，直到不再有新子集产生
    • 分解后的两个状态 p 和 q 属于同一个子集，当且仅当\forall a \in \sum $，t( p, a )$和$t( q, a )$都到达当前划分的同一子集中
  • 1. 构造状态集的划分(初次划分为终点节点和其它节点)
  • 2. 取每一组中的一个状态作代表
  • 3. 删去多余死状态

4 正规文法与FA

• 右线性正规文法构造等价$FA$
  • 令$G$的终结符号集为$A$的字母表；
  • $G$的非终结符号作为$A$的状态，$G$的开始符号为$A$的开始状态；
  • 增加一个终止状态$Z(Z\notin V_N)$
  • 形如$U→aW$的规则，引一条从状态$U$到$W$的$a$弧。
  • 形如$U→a$的规则，引一条从状态$U$到终止状态$Z$的标记为$a$的弧；
  • 例子：
• 左线性正规文法构造等价$FA$
  • 令$G$的终结符号集为$A$的字母表；
  • $G$的非终结符号作为$A$的状态，$G$的开始符号为$A$的终止状态；
  • 增加一个开始状态$S\notin V_N$
  • 形如$U→Wa$的规则，引一条从状态$W$到$U$的$a$弧。
  • 形如$U→a$的规则，引一条从开始状态$S$到状态$U$的标记为$a$的弧；
  • 例子：

5 正规表达式与FA

• 正规表达式到FA：
  
• FA到正规表达式
  • 1. 创建一个起始节点S连向起始点，将所有的终点连接一个节点Z
  • 2. 随后依次去掉中间节点
  • 3. 直到最后只剩开始节点和结束节点
  • 例子
    
    
    
    
    
    
    

4(1)语法分析

1 自上而下语法分析

自上而下语法分析的基本思想

• 推导——从开始/识别符号出发不断建立直接推导，试图构造一个最左推导序列，最终由它推导出与输入符号串相同的符号串
• 程序翻译——从语言文法的开始符号——<程序>出发，试图推导出文法的句子——源程序/与其等价的单词串
• 语法树——以开始/识别符号为根结点，试图向下构造一棵语法树，其末端结点符号串与输入符号串相同

自上而下语法分析中问题的解决方法

• 无限循环：消除左递归
• 回溯：避免回溯

2 左递归的消除

直接左递归的消除

设有产生式 $A \rightarrow Aα_1|Aα_2|…|Aα_m|β_1|β_2|…|β_n$,其中$y_i(i=1，2，…，n)$均不以符号$U$为首，增加新非终结符号$U^{'}$，将上述产生式变换为:
$A→β_1A^{'}|β_2A^{'}|…|β_nA^{'}$
$A^{'}→α_1A^{'}|α_2A^{'}|…|α_mA^{'}|ε$

间接左递归的消除

1. 以某种顺序将文法非终结符排列$U_1 ，U_2 ，…，U_n$
2. 改写文法;
3. 化简由2得到的文法。

3 回溯的避免

避免回溯的条件

• 产生原因：
  • 文法中存在如下形式的产生式$U→α_1|α_2|…|α_n$,且候选式$α_1，α_2，…，α_n$中有相同的终结首符号
• 避免的前提条件：
  • $α_1, α_2, …, α_n$等各符号串的终结首符号集合总是两两互不相交的
  • 但当$a_j \rightarrow^{*}\epsilon$时，仅有上述条件不够，需要达成LL(1)文法条件

LL(1)文法

• 定义：

  • 文法中任一形如$U→α_1|α_2|…|α_n$的产生式满足：
    • 1. $α_1, α_2, …, α_n$的终结首符号集两两互不相交，即$FIRST(α_i)\bigcap FIRST(α_j)=\phi(i!=j)$
    • 2. $a_j\rightarrow^*\epsilon$文法还用是满足$FIRST(α_i)\bigcap FOLLOW(U)=\phi$

• 计算FIRST集合

  • 若 $\alpha=X\in (V_U \bigcup V_T)$,$FIRST(X)$构造为
    • 1. 若$X\in V_T$,则$FIRST(X)=\{X\}$
    • 2. 若$X\in V_N$,相应产生式为$X\rightarrow a...,a\in V_T$,则$a\in FIRST(X)$,若有相应产生式$X\rightarrow \epsilon$，则 $\epsilon \in FIRST(X)$
    • 3. 若$X\in V_N$,相应产生式为$X \rightarrow Y..,Y\in V_N$,则$FIRST(Y)-\{\epsilon\}\subset FIRST(X)$
         如果有产生式$X\rightarrow Y_1Y_2…Y_k$（其中，$Y_1，Y_2，…，Y_{i-1}$都是非终结符，且$Y_1Y_2…Y_{i–1}\rightarrow^*\{\epsilon\}$则$FIRST(Y_i)-\{\epsilon\}\subset FIRST(X);$如果$Y_1Y_2…Y_k\rightarrow^{*}\epsilon$，则$\epsilon \in FIRST(X)$。
  • 若 $\alpha=(V_U \bigcup V_T)^*,\alpha = X_1X_2X_3..X_n$,$FIRST(\alpha)$构造为
    • 1. 若$\alpha=\epsilon$,显然$FIRST(\alpha)=\{\epsilon\}$
    • 2. 若$\alpha\not=\epsilon$,则$则FIRST(X_1)-\{\epsilon\}\subset FIRST(\alpha)；$
    • 3. 若$\alpha\not=\epsilon$,且$X_1X_2..X_n\rightarrow^{*}\epsilon$,则$FIRST(X_i)-\{\epsilon\}\subset FIRST(\alpha)$
    • 4. 若$\alpha\not =\epsilon$,且$X_1X_2..X_n\rightarrow^{*}\epsilon$，则$\epsilon \in FIRST(\alpha)$
         

• 计算FOLLOW集合

  • $FOLLOW(U)$的求法，$FOLLOW(U)=\{a|S\rightarrow^{*}\dots Ua\dots,a\in V_T\}$,该定义中，$U$必须从S推得才能有$FOLLOW集合$
  • 1. 对于文法的开始/识别符号S，令$\$\in FOLLOW(S)$
  • 2. $ A \rightarrow \alpha B \beta $则，$FIRST(\beta)$中的非$\epsilon$元素属于$FOLLOW(B)$
  • 3. $ A \rightarrow \alpha B ，或 $A\rightarrow \alpha B \beta，而 $ FIRST(\beta) 含有 $ \epsilon $ ，则 FOLLOW(A) $ 的元素属于$ FOLLOW(B) $
       

4 预测分析器的构造

递归子程序法

• 基本思想：对真实推导过程的直接模拟
• 约定：每进入一个分析子程序前，已读到该子程序相应的非终结符号推导出的第一个终结符号/终结首符号。
  • 例如，当读到IF语句的第一个单词IF时，便知道将要进行IF语句的识别，于是调用对应于<IF条件语句>的分析子程序进行分析
• 例子：

确定的LL(1)分析器

• LL(1)文法：

  • 从左到右扫描输入符号串，从开始符号出发生成句子的最左推导。对于形如 U→α1|α2|…|αn 的产生式，只要向输入符号串中查看一个输入符号，便能惟一确定当前应选择的产生式，由此而得名LL(1)分析法。
  • 当需要向输入串中查看K个输入符号，才能惟一确定当前应选择的产生式时，称为LL(K)分析法

• 分析器程序结构：一张分析表M和一个符号栈S

  • 分析表的元素$M[U，a]$为一条关于该非终结符号U的产生式，指出当该非终结符号U面临输入符号a时应选择的产生式，分析表的元素也可能是一个出错标志，指出非终结符号U不能面临终结符号a。
  • 符号栈S用于存放文法的符号，当文法和待分析的符号串确定后，符号栈的内容随分析过程而不断变化。开始时，栈底放“$”，假定输入符号串以“$”结束。

• 分析过程：
  
  

• 分析表的构造

  • 1. 对$FIRST(\alpha)$中的每一个终结符号$a$,置$M[A,a]="A\rightarrow\alpha"$
  • 2. 如果$\epsilon \in FIRST(\alpha)$,则对于属于$FOLLOW(A)$的每一个终结符号$b$或$\$$,分别置$M[A,b]="A\rightarrow\alpha"$和$M[A,\$]="A\rightarrow\alpha"$
  • 3. 如有不能按规则1与2构造的元素置出错标志
       

• 二义性文法的分析表中存在冲突项，即通过一个符号由多个产生式

4(2)自下而上的语法分析

自下而上语法分析简介

• 基本思想

  • 推导——从输入的符号串开始逐步向上归约，试图归约到文法的开始/识别符号。
  • 语法树——以输入符号串作为末端结点符号串，向根结点方向构造语法树，使识别符号正好是语法树的根结点。
  • 程序的编译——从该高级语言文法的源程序或与其等价的单词串出发，试图归约到该文法的开始符号——<程序>

• 基本实现技术——移进-归约法

  • 引进一个后进先出的栈来存放符号，按照扫描顺序把当前输入符号下推入栈中(移进)，然后查看栈顶的符号串是否可以被归约。

• 短语： $S\stackrel{*}{ \Rightarrow } \alpha A c$,且 $A\stackrel{+}{ \Rightarrow } \beta$,则称$\beta$是句型$\alpha A c$相对于$A$的短语

  • 若有$A \Rightarrow \beta$,则称$\beta$是句型$\alpha A c$相对于$A$的直接短语

• 句型的最左直接短语称为句柄

• 在一个句型对应的语法树中

  • 以某非终结符为根的两代以上的字数的所有末端节点从左到右排列就是对于该非终结符的一个短语
  • 如果子树只有两代，则短语为直接短语
  • 最左的两代子树末端就是句柄

• LR文法采用句柄进行规约

LR(0)项目

在每个产生式右部添加一个圆点，表示我们在分析过程中已经看到了产生式的哪些部分，以及我们希望下一个字符是什么

• 如$A\rightarrow XYZ$有四个项目

  • $A\rightarrow ·XYZ$
  • $A\rightarrow X·YZ$
  • $A\rightarrow XY·Z$
  • $A\rightarrow XYZ·$

• 称$A\rightarrow \alpha ·$为“规约项目”

  • 规约项目$S^{'}\rightarrow \alpha ·$，称为“接受项目”

• $A\rightarrow \alpha · a \beta$ ,称为“移进项目”

• $A\rightarrow B · a \beta$ ,称为“待约项目”

• 内核项：包括初始项$S^{'}\rightarrow·S$以及点不再最左端的所有项

• 非内核项：除$S^{'}\rightarrow·S$以外的点在最左端的所有项

以LR(0)项目集为基础，构造LR(0)自动机，做出语法分析器

LR(0)自动机的构造

• 构造分析表中的状态
  假设I为文法的任一项目集(开始时仅包含S’→.S，S '为拓广文法的识别符号)，重复下述步骤求CLOSURE(I)：
  1. I的任何项目均属于CLOSURE(I)
  2. 如果A→α.Bβ属于CLOSURE(I)，则所有B→.γ也属于CLOSURE(I)。
     上述工作重复到CLOSURE(I)不再扩大为止，此CLOSURE(I)即为所求的一个项目子集。

活前缀

• 句柄的识别需要借助实际句型中的信息。在得到一个规范句型的完整句柄之前所识别的符号串称为规范句型的活前缀。

• LR(0)自动机本质是DFA，那么就可以识别串，能被该自动机识别的串称为活前缀

LR(0)分析表

• 移进规约冲突
  • 左结合选移进
  • 右结合选归约

5语法制导翻译

语法制导翻译简介

• 属性文法：对某个上下文无关文法，为每个文法符号指定一组属性，且为文法中的每个产生式附加一段属性计算方法——语义规则/语义动作/语义子程序，则称该文法为属性文法。
  原文法称为基础文法
  • 属性值的计算，由语法分析过程中产生的语法分析树相应节点的环境推导出来 — 属性的联编/绑定
    • 静态属性：执行前联编，如数的有效位数
    • 动态属性：在执行期间联编，如表达式的值
• 语法制导定义SDD
  • 定义与文法符号相关联的属性集
  • 定义与产生式相关联的一组语义规则
• (语法制导的)翻译方案
  • 基本思想：在语法分析的过程中，依随分析的过程，根据每个产生式添加的语义动作进行翻译。一旦某个产生式被选用于推导或归约，就执行其相应的语义动作，完成预定的翻译工作

属性分类

• 综合属性（自下而上得传递消息）

  • 语法规则上：根据产生式右部的符号属性计算左部被定义的符号的综合属性
  • 语法树上：根据子节点的属性和父节点自身的属性计算父节点的综合属性

• 继承属性（自上而下传递消息）

  • 语法规则上：根据右部候选式中的符号的属性和左部被定义的符号的属性计算右部候选式中符号的继承属性
  • 语法树上：根据父节点和兄弟节点的属性计算子节点的继承属性

• 终结符只有综合属性，并且这些综合属性由词法分析器提供

• 非终结符既有综合属性也可有继承属性，文法的开始符号没有继承属性，除非另加说明

• 文法符号的综合属性集合和继承属性集合的交集应该为空

• 对出现在产生式右边的继承属性和出现在产生式右边的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性

• 出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则计算，而是由其它产生式的属性规则计算或者由属性计算器的参数提供

SDD求值顺序，属性计算方法

• 依赖图
  用一个有向图描述了某个语法分析树中的属性实例之间的依赖关系，若属性x.a的值依赖于属性y.b的值，则加入一条同y.b到x.a的有向边

SDD 分类

• S-属性定义：仅使用综合属性的SDD
  • 可以按照语法分析树节点的任何自底向上的顺序来计算各个属性值
• L-属性定义
  • 一个SDD是L-属性，当且仅当它的每个属性要么都是综合属性(这里包含了S-属性)，要么是满足以下条件的继承属性
    $A\rightarrow x_1x_2...x_n$,右部符号$x_i$的继承属性仅依赖于：
    1. A的继承属性
    2. 产生式中$x_i$左边$x_1,x_2,...x_{i-1}$的属性
    3. $x_i$本身的属性

SDT 语法制导翻译方案

SDD：只给出了语义规则(属性计算的定义)，并没有给出计算的次序，所以要通过依赖图寻求计算顺序

SDT：既有关于属性计算的定义，又有计算的次序
SDT将语义动作用花括号括起来，作为一种程序片段，插入到产生式右部的合适位置

• 设计翻译模式的原则：必须保证某个语义动作引用一个属性时，该属性已经被定义了

  1. 当语义规则只引用综合属性是，将动作放到产生式末尾
  2. 当语义规则中有继承属性，也有继承属性时
     1. 产生式右部的符号的继承属性必须在符号之前计算出来
     2. 一个动作不能引用这个动作右边的符号的属性
     3. 产生式左部的综合属性只有在它所引用的所有属性都计算出来后才能计算，一般动作放在最右部

• SDT实现了语法分析和语义分析同时进行，基于自下而上的语法分析方式

• 语法分析能得到语法树

  • 仅指明各个文法符号之间的传递关系
  • 不能决定文法符号间应该有什么样的运算，这是由语义分析决定的

期末复习

跌的视频
共7道

第一道 词法分析

1. 求NFA接受字符串的过程
2. NFA转DFA，并画出状态转换图
3. DFA的最小化
4. 自然语言描述NFA的语言
5. NFA/DFA转正规表达式

第二道 自上而下语法分析

1. 最左推导

   1. 总是选择每个句型最左边的非终结字符进行替换

2. 消除左递归

   1. 先消除间接左递归
   2. 再消除直接左递归

3. 求FIRST，FOLLOW集合

   • 计算FOLLOW集合
     • $FOLLOW(U)$的求法，$FOLLOW(U)=\{a|S\rightarrow^{*}\dots Ua\dots,a\in V_T\}$,该定义中，$U$必须从S推得才能有$FOLLOW集合$
     • 1. 对于文法的开始/识别符号S，令$\$\in FOLLOW(S)$
     • 2. $ A \rightarrow \alpha B \beta $则，$FIRST(\beta)$中的非$\epsilon$元素属于$FOLLOW(B)$
     • 3. $ A \rightarrow \alpha B ，或 $A\rightarrow \alpha B \beta，而 $ FIRST(\beta) 含有 $ \epsilon $ ，则 FOLLOW(A) $ 的元素属于$ FOLLOW(B) $

4. 构造LL(1)分析表

• 分析表的构造
  对于产生式$A\rightarrow \alpha$
  • 1. 对$FIRST(\alpha)$中的每一个终结符号$a$,置$M[A,a]="A\rightarrow\alpha"$
  • 2. 如果$\epsilon \in FIRST(\alpha)$,则对于属于$FOLLOW(A)$的每一个终结符号$b$或$\$$,分别置$M[A,b]="A\rightarrow\alpha"$和$M[A,\$]="A\rightarrow\alpha"$

5. 给出分析过程

• 使用分析表的分析过程

  符号栈	输入串	分析和动作
  E$	id + id * id$
  …	…	…

第三道 消除文法二义性

1. 说明二义文法

• 文法对同一语句产生不同的语法树，则文法是二义的
• 二义性产生原因
  • 左右结合性
    • 问题：$E\rightarrow E +E | E*E|id$在$id+id+id$，会产生两个语法树$（id+id）+id$ 和 $id+（id+id）$，这里两个树不同的是扩展方向
    • 解决:
      • 左结合：将可以递归的非终结符放在终结符的左侧，使运算具有左结合性
      • 右结合同
    • $E\rightarrow E+E$改为$E\rightarrow E+F|F,F\rightarrow id$,这样就是左结合
  • 优先级：某个算符所在语法树层数越高，越先被运算，这种算符的优先级越高
    • 问题： $E\rightarrow E +E | E*E|id$在$id+id*id$中会产生两个语法树，这里没有体现*的优先级
    • 解决：引入新非终结符，增加一个新的子结构
    • 低优先级的结构靠近开始符号
    • 高优先级的结构靠近终结符号
    • $E\rightarrow E +E | E*E|id$改写为
      $E \rightarrow E+T|T$
      $T \rightarrow T*F|F$
      $F \rightarrow id$
      这样可以通过设定优先级去除二义性

第四道 自下而上语法分析

1.2 求LR(0)项目集，识别活前缀

• 求LR(0)项目集
  • 如果只求某状态的，仅考虑入边即可
• 构造LR(0)自动机
• 活前缀：跑自动机看能否识别

3,4 构造LR分析表，给出LR分析过程

第五道

• 语法知道定义SDD：是一个上下文无关文法的属性及规则的定义

  • 文法符号具有某些属性$(X.a, X.b 等)$
  • 文法的产生式具有某些语义规则(语义规则用于解释这些值得传递和计算)

• 属性分类

  • 综合属性（自下而上得传递消息）
    • 语法规则上：根据产生式右部的符号属性计算左部被定义的符号的综合属性
    • 语法树上：根据子节点的属性和父节点自身的属性计算父节点的综合属性
  • 继承属性（自上而下传递消息）
    • 语法规则上：根据右部候选式中的符号的属性和左部被定义的符号的属性计算右部候选式中符号的继承属性
    • 语法树上：根据父节点和兄弟节点的属性计算子节点的继承属性

• 带注释的语法树：在语法树的基础上加上属性

第六道

跟汇编很像，不难

第七道

给出错误的C语言程序，指出错误