Compile_Principle_Review

概念题(不考

• 什么是编译程序

  翻译程序:

• 表达式得形成规则

  ➢ 变量（包括下标变量）、常数是表达式；

  ➢ 若E1、E2为表达式，θ是一个二元算符，则$E_1\ θ\ E_2$是一个表达式；

  ➢ 若E是表达式，θ为一元算符，则$θE（或Eθ）$是表达式；

  ➢ 若E是表达式，则(E)是表达式。

• 运算顺序和结合性(关于运算符优先级的知识)

• 闭包

  某个符号串的闭包运算规则是,但是经过的是有限次的链接而成的,也就是闭包中的每个字符串的长度有限.
  $$
  V^{}=V^{0} \or V^{1} \or V^{2} \or V^{3} \or \cdots
  $$
  正则闭包
  $$
  V^{+}=VV^{}
  $$

• 关于空集与空字的区分!

  空集,即$\varnothing$,代表的是${}$,是集合

  空字,用$\epsilon$表示,代表的是不含有任何符号的序列,是一个集合中的元素

  而${\epsilon}$往往用来代表某个符号串的0次连接积,也就是$V^{0}$

• 关于推导

  最右推导: 推导过程中,总是最先替换最右的非终结符,称之为最右推导

  最右规约:规约时,总是最先规约最右的非终结符,称之为最右规约.

  规范推导(最右推导)

  规范规约(最左规约)

• 知道常见的状态转换图

• 正规式之间的运算规则以及常见的等价正规式

  • 等价的正规式

    例如比较常见的是b(a|b)^^=(ba)^^b , (a|b)^^=(a^^b^^)^^

  • 常用的正规式

    

  • 正规式运算规则

    连接不满足交换律.

    

• 关于自上而下的分析方法存在的问题
  • 可能存在的左递归导致的无线循环
  • 分析过程成,多个候选式导致的回溯,产生一定的开销
  • 虚假匹配问题
  • 使用自上而下的语法分析无法确定具体的出错位置

• 属性文法的杂碎知识

  • 语义规则

    语义规则的形式为$b=f(c_1,c_2,\cdots,c_k)$

  • 综合属性

    综合属性来源于产生式右边的文法符号的属性

    终结符只有综合属性,由词法分析器来提供

    只使用综合属性的文法称为S-属性文法.

    通常通过自底向上的方法计算综合属性值.

  • 继承属性

    继承属性是指产生式右边的文法符号的某个属性,是取决于其兄弟节点后者产生式左侧的非终结符的属性

    文法开始符号的所有继承属性作为属性计算前的初始值

  • 语法制导翻译(软院往年考过!)

    由源程序的语法结构所驱动的处理方法,称为语法制导翻译.

    其语义规则计算可能会产生代码\在符号表中存放信息\给出错误信息\执行任何其他动作.

    为文法的每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则，完成有关语义分析和代码生成的工作。

    ➢ 在自上而下的分析中，当一个产生式匹配输入串成功时执行；

    ➢ 在自下而上的分析中，当一个产生式被用于归约时执行。

  • 依赖图

    如果一个节点的属性b依赖于属性c,则从c绘制向b的有向边.

    注意,这里的节点不是文法符号,而是每个文法符号的每个属性.

  • 一遍扫描的处理方法

  • S-属性文法（只使用综合属性）

    其属性的计算遵循从下到上的计算方法，通常借助LR分析器实现。表现为在LR分析器的【状态栈 | 符号栈】的符号栈中添加符号的属性值。

  • L-属性文法

    概念：如果对于每个产生式𝐴 → 𝑋1𝑋2 … 𝑋𝑛，其语义规则中的每个属性或者是综合属性，或者是𝑋𝑖(1 ≤ 𝑖 ≤ 𝑛)的一个继承属性且这个继承属性仅依赖于：

    ➢ 产生式右部𝑋𝑖 的左边符号𝑋1, 𝑋2, … , 𝑋𝑖−1的属性；

    ➢ 产生式左部𝐴的继承属性。

    S属性文法一定是L属性文法。可以采用自上而下的翻译，也可以采用自下而上的翻译。

  • 翻译模式的设计：

    • 自上而下

      对于既有综合属性又有继承属性的情况：

      ① 产生式右部符号的继承属性，必须在这个符号以前的动作中计算出来；

      ② 一个动作不能引用这个动作右边符号的综合属性；

      ③ 产生式左部的𝑉𝑁的综合属性，只有在它所引用的所有属性都计算出来以后才能计算（放到右边末尾）。

    • 自下而上

      要求语义动作放在产生式末尾

      解决方案：引入空符号产生式（只需要处理动作，不需要处理属性计算）

可能会考到

• 对于上下文无关文法的定义和一些约定

  具体概念表示为:它所定义的文法范畴（或语法单位）是完全独立于这种范畴可能出现的环境的。

  通过一个四元式进行定义:
  $$
  G=(V_T,V_N,S,P)
  $$
  其中从前到后的意义分别是:

  终结符号\非终结符号\开始符号\ 产生式集合

  其中产生式集合中元素的形式如下:
  $$
  P\rarr \alpha
  $$
  其中的P是属于非终结符号,\alpha属于非终结符号与终结符号的闭包.

  一些约定内容:

  使用大写字母代表非终结符

  使用小写字母代表终结符

  使用希腊字母代表终结符和非终结符组成的字符串.

  对于语言的描述: 使用一种形式将文法G所产生的句子的全体是一个语言,表示为集合的形式
  $$
  L(G)={a|S
  \stackrel{+}{\Rarr}
  \alpha }
  $$
  或者也可以使用描述的方式进行书写.

• 形式语言

  相关的形式语言了解.

  • 0型文法(限制最宽松,常见的都是0型),对应0型语言都是递归可枚举的,能力相当于图灵机,半可判定

    

  • 1型文法,又被称之为上下文有关文法.线性有界自动机.在0型文法基础之上的每个$\alpha \rarr \beta$ ,都有$|\beta| \ge |\alpha|$ ,即由小生大, ($S \rarr \epsilon $ 除外),且S不能出现在产生式的右部.

    $L(G)={a^nb^nc^n | n\ge 1}$只能由本文法产生

  • 2型文法,又称为上下文无关文法,对应下推自动机.使用下推表(先进后出栈)的有限自动机是分析的基本手段.满足条件为,在0型基础之上,满足$𝐴 → 𝛽, 𝐴 ∈ 𝑉_𝑁, 𝛽 ∈ (𝑉_𝑁 ∪ 𝑉_𝑇 )^*$

    可以产生S->aSb | ab

  • 3型文法,又称右线性文法/左线性文法.等价于正规式,所以也称为正规文法.在0型基础之上,满足:$𝐴 → 𝛼𝐵或𝐴 → 𝛼，其中，𝛼 ∈ 𝑉_𝑇^∗, 𝐴 ∈ 𝑉_𝑁,𝐵 ∈ 𝑉_N$.

    不能产生语言a^n^b^n^

• 正规式到正规文法的改写规则以及正规文法的概念

  • 正规式的递归定义

    
  

• 翻译句子相关的知识点

  • 后缀式

    运算符在后面

  • 三地址代码(例如X=A+B) 四元式

    种类: 二元算数运算符/逻辑算符;一元算符;赋值语句;无条件转移;条件转移;过程调用;索引赋值;地址与指针赋值;

    四元式=$(op,arg1,arg2,result)$

  • 说明语句的翻译 例如int a,b; 应该得到的名字表中应存储a,b:int (符号表的填写)

    

  • int与real的转换? 课后题

    两者相加的课后题，主要是利用了后缀式。

    • 第一问，求出类型：

      直接写就可以。

    • 第二问，生成代码：

      要注意的是：程序输出时，int2real如果被看作是单个运算符，也需要按照后缀式的形式，先输出具体的值，在输出运算符int2real.

      

    • 课件给定的例子:

      

  • 布尔表达式和控制条件?

    关于布尔表达式中的运算符优先级说明:

    优先级从高到低:非 > 与 > 或

    关系运算符,例如< > <= ... ,内部优先级相同,整体高于布尔算符,低于算数算符.

    布尔表达式的翻译模式:

    

    作为条件控制的布尔表达式:

    对于真假出口对应的链表:

    • 当遇到与时,需要将两个非终结符的falseList合并,
    • 当遇到或时,需要将两个非终结符的trueList合并.

    对于回填函数backpatch:

    • 当遇到与,E2可以确定E1的truelist需要回填的地址
    • 当遇到或,E2可以确定E1的falseList需要回填的地址
    

• 运行时空间组织PPT

必考知识点

• 画图表示编译过程的各阶段

  

  或许有可能要我们解释这个图的具体含义?

  • 词法分析器:

    又称扫描器,输入源程序,从左到右逐个字符地对源程序扫描,进行词法分析,输出单词符号.

  • 语法分析器:

    又称分析器，对单词符号串进行语法分析，识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。

  • 语义分析和中间代码生成器:

    按照语义规则对语法分析器归约（或推导）出的语法单位进行语义分析，并把它们翻译成一定形式的中间代码。

    静态语义检查通常包括: 类型检查,控制流检查,一致性检查,相关名字检查,名字的作用域分析

  • 优化器:

    对中间代码进行优化处理

  • 目标代码生成器:

    把中间代码翻译成目标代码。

• 二义文法

  • 概念

    如果一个文法的某个句子对应两棵不同的语法树，即其最左（最右）推导不唯一，称该文法为二义文法。

  • 文法的二义性与语言的二义性是不同的概念.

    具体而言:

    • 可能存在两个不同的文法G和G’,其中一个是二义的,一个是无二义的,但是有L(G)=L(G’);
    • 对于一个语言,我们常常希望其文法是无二义的,因为我们希望对它每个语句的分析是唯一的；

  • 考点

    证明某个文法是二义的,具体需要自己找出一个例子,推导出两棵不同的语法树.

  • 求解

    (优先级越高越远离开始符号)

  • 例题

    𝐸 → 𝐸 + 𝐸 | 𝐸 ∗ 𝐸 | (𝐸) | 𝑖，构造该文法的无二义文法，使它们表示的语言相同，并给出句子 i*i+i的最右推导。

    

• 形式语言

  相关的形式语言了解.

  • 0型文法(限制最宽松,常见的都是0型),对应0型语言都是递归可枚举的,能力相当于图灵机,半可判定

    

  • 1型文法,又被称之为上下文有关文法.线性有界自动机.在0型文法基础之上的每个$\alpha \rarr \beta$ ,都有$|\beta| \ge |\alpha|$ ,即由小生大, ($S \rarr \epsilon $ 除外),且S不能出现在产生式的右部.

    $L(G)={a^nb^nc^n | n\ge 1}$只能由本文法产生

  • 2型文法,又称为上下文无关文法,对应下推自动机.使用下推表(先进后出栈)的有限自动机是分析的基本手段.满足条件为,在0型基础之上,满足$𝐴 → 𝛽, 𝐴 ∈ 𝑉_𝑁, 𝛽 ∈ (𝑉_𝑁 ∪ 𝑉_𝑇 )^*$

    可以产生S->aSb | ab

  • 3型文法,又称右线性文法/左线性文法.等价于正规式,所以也称为正规文法.在0型基础之上,满足:$𝐴 → 𝛼𝐵或𝐴 → 𝛼，其中，𝛼 ∈ 𝑉_𝑇^∗, 𝐴 ∈ 𝑉_𝑁,𝐵 ∈ 𝑉_N$.

    不能产生语言a^n^b^n^

• 短语和句柄

  • 短语定义:

    对文法𝐺[𝑆]，如果有$𝑆\stackrel{*}{\Rarr}𝛼𝐴𝛿$ 且 $𝐴 \stackrel{+}{\Rarr}𝛽$ ，则称𝛽是句型𝛼𝛽𝛿相对于非终结符号𝐴的短语。

  • 直接短语

    如果有$A\Rarr\beta$,称𝛽是句型𝛼𝛽𝛿相对于𝐴的直接短语

    通常对于直接短语的判断方式是通过对给定的句型,依照文法绘制对应的语法树。如果想要判断短语$\alpha$是不是直接短语，就看其父节点$A$的所有孩子节点（包含$\alpha$ 在内），是否都是叶子节点，如果是，则这里的叶子节点们组成的短语就是直接短语。

  • 句柄

    一个句型的最左直接短语称为该句型的句柄

• FA写正规式

  根据自动机合并为正规式的方式,实际上是对正规式转化为非确定有限自动机的逆过程.

  

• 消除左递归

  常见的/根本的措施就是通过添加非终结符:
  $$
  P \rarr P\alpha | \beta \
  \Darr \
  P \Rarr \beta \alpha ^*\
  \Darr \
  P\rarr \beta P’ \
  P’ \rarr \alpha P’ | \epsilon
  $$
  利用正规式作为媒介,转换为右递归文法.

  同样的道理,可以将上述内容进行推广.
  $$
  P\rarr P\alpha_1 | P\alpha_2|\cdots | P\alpha_n |\beta_1 | \beta_2 | \cdots|\beta_m \
  \Darr\
  P\rarr P(\alpha_1 | \alpha_2| \cdots| \alpha_n)|(\beta_1 | \beta_2| \cdots|\beta_m) \
  \Darr \
  P\rarr (\beta_1 | \beta_2| \cdots|\beta_m) P’ \
  P’\rarr (\alpha_1 | \alpha_2| \cdots| \alpha_n)P’|\epsilon
  $$

除了上述显示的左递归之外,还存在着隐式的左递归,对应于如果从A1推导到A2,那么绘制其对应的图中,节点A1和A2之间存在着一条有向边.

消除隐含左递归的方法就是:

  1. 给定一个非终结符号的排序,例如A1,A2 ... 
  2. 保证每个推导公式中右侧的A_i的对应位置在左侧A_j的右侧.也就是必须从排序较小着推导到排序较大者.
  3. 对满足第2条的,且包含了左递归的进行左递归消除.

如果想要使产生的产生式最少,那么:

如果从开始符号获取到的值依次是A1,A2,…An,

那么排序时最好是按照这个顺序的逆序进行排列,即An,…,A2,A1

????

• 提取公因子

  目的就是消除回溯.

  这里我们使用的提取左公因子的方法如下:
  $$
  P \rarr \alpha A_1 | \alpha A_2 | \cdots | \alpha A_n | \beta_1 | \beta_2 |\dots|\beta_m \
  \Darr \
  P\rarr \alpha (A_1 | A_2 |\cdots| A_n )| \beta_1 | \beta_2 |\dots|\beta_m \
  \Darr\
  P\rarr \alpha A | \beta_1 | \beta_2 |\dots|\beta_m \ ,\
  A\rarr A_1 | A_2 |\cdots| A_n
  $$

• 后缀表达式

  后缀表达式就是逆波兰表示法.这种方法采用的是:将运算量写在前面,将算符写在后面.满足三种:
  $$
  =a \
  <\theta e>=\theta \
  <E_1 \theta E_2> = \theta \
  <(E)>= \
  $$
  后缀式存在的优点:

  ➢ 无括号，形式简洁；

  ➢ 运算符的顺序与运算次序完全相同。

  对应语义规则:

  

• 符号表

  • 符号表起到的作用?

    • 收集符号属性
    • 上下文语义的合法性检查
    • 目标代码生成阶段地址分配的依据

  • 三种组织方式

    • 构造多个符号表,将具有相同属性的种类的符号组织在一起

      优点: 每个符号表中存放符号的属性个数和结构完全相同

      缺点: 一遍编译程序要同时管理若干个符号表

    • 把所有符号都组织在一张符号表中

      优点: 管理集中单一

      缺点: 增加了空间开销

    • 根据符号属性相似程度分类组织成若干张表

      优点: 减少空间开销

      缺点: 增加了表格管理的复杂性

  • 符号表表项的排列

    • 线性组织

      优点：插入快，空间效率高；

      缺点：查询慢，时间效率差。

    • 排序组织及二分法

      优点：查询效率高，空间效率高；

      缺点：插入效率低，算法复杂一些。

    • Hash表

      优点：插入、查询效率都高；

      缺点：空间效率有所降低。

​

• 运行时空间组织

  • 实参传递给形参

    • 地址(变量传递地址,常数/表达式创建临时单元,传递临时单元的地址
    • 传值(将值拿出来,放进被调用过程的形式单元中,使用时类似于使用局部变量
    • 传名字

  • 函数值的返回

    • 将某个函数值保留在某个累加器中

    • /传递结果?

      形参对应两个单元,实参地址+实参值.使用形式参数,对应使用第二个单元;

  • 活动记录的内容

    • 链接数据(返回地址/动态链/静态链)
    • 形式单元(形式单元个数与内容)
    • 局部数据区(局部变量/内情向量,即数组有关信息/临时工作单元)

  • 嵌套过程语言的栈式实现

    • 从下到上,内容依次是:

      动态链(老SP),返回地址,静态链,形参个数,形参单元,局部变量,内情向量,临时单元

    • 如果使用了嵌套层次显示表,其内容应该是:

      动态链,返回地址,全局Display,形参个数,形参单元,display表,局部变量,内情向量,临时单元

  • 堆式内存分配

    分配策略:

    • 首次满足法
    • 最优满足法
    • 最差满足法

• 静态链和动态链

  这里主要是关于静态链内容的确定方式:

  静态链内容填写分为三种情况:

  • 第N层调用第N+1层,也就相当于父亲节点调用孩子节点

    第N+1层的静态链填写调用过程 ( 第 N层过程 ) 的最新活动记录的起始地址 .也就相当于被调用者的静态链=调用者的SP

  • 第N层调用第N层,相当于兄弟节点调用其对应的兄弟节点

    被调用者的静态链内容填写为 调用过程 ( 第 N层过程 ) 的静态链的值。也就是被调用者静态链=调用者的静态链.

  • 第N层调用第N-X层

    相当于第某一个后代节点调用其祖先节点.

    被调用者的静态链填写需要沿着调用者的静态链跳转X次到达的活动记录的静态链内容,即被调用者的静态链内容.

综合题

词法分析

• 词法分析,给定正规式

  构造NFA
  确定化
  最小化

  状态转化图

  • 经常用到的表现形式: 状态转换图

    • 使用结点表示状态,用圆圈表示

    • 状态之间使用箭弧链接,上面的数字代表射出节点状态下可能出现的状态.

    • 一张转换图只包含有限个状态,必然有一个为初态,至少有一个终态.

    • 初态要添加箭头指向表示,终态使用双圆圈表示.

    • 注意到,如果判定时需要添加一个额外的符号来表示转换到终结态,那终结态应该还要退还这个多输入的额外的符号给输入串.使用终态节点上打星号代表多读入了一个不属于标识符的字符.

      

  DFA

  • 什么是DFA

    一个确定有限自动机使用五元式来表示 $M=(S,\Sigma,\delta,s_0,F)$

    其中各个内容的含义:

    • S: 一个有限集,每个元素代表一个状态

    • $\Sigma$: 有穷字母表,每个元素代表一个输入字符

    • $\delta$: 是从$S \times \Sigma$到$S$的单值映射,$\delta (s,a)=s’$代表当 当前状态为s,输入为a时,将转换到下一个状态s’, s’又被称为后继状态.

    • $s_0 \in S$, 代表唯一的初态.(确定有限自动机初态唯一)

    • $F\subseteq S$,是一个终态集,(可以为空集)

    综合来说,就是(状态集,输入集,转换关系,初态,终态集)

  • 一个DFA可以表示为一张状态转换图(最左侧列代表状态),最上面行代表输入.

    若M的初态结点同时又是终态结点，则空字𝜀可为M所识别（或接受）

  • DFA的构造问题:给定一个正规式,将其转化DFA

  • 优缺点:

    编程实现容易,效率高,但是构造困难

  NFA

  • 关于非确定有限自动机NFA

    基本同上,同样使用五元式进行表示,不过不同的是:

    • 原本的$\delta$代表的单值映射,这里是$S \times \Sigma^* 到S$的子集的映射.也就是
      $$
      \delta:S \times \Sigma^{*} \rarr 2^{S}
      $$

    • 原本的初态是唯一的,这里的初态是非空初态集

    • 另外,在这里的弧上可以出现空字**$\epsilon$**

  • 从一个正规式转化为NFA

  • 给定一个NFA,如何将其转化为正规式

  • 优缺点

    NFA构造比较容易,但是编程实现有回溯

  NFA的确定化(转变为DFA)

  • 使得初态和终态唯一(引入新的初态X和终态Y).

    从𝑋 到𝑆0 的任意状态结点连一条𝜀箭弧；

    从𝐹中的任意状态结点连一条𝜀箭弧到𝑌。

  • 分裂

    使得每条箭弧上或为$\epsilon$ ,或者是$\Sigma$中的单个字符

    

  • 寻找可合并状态

    引入闭包的概念,定义I的ε闭包ε_Closure(I)为：

    ➢ 若𝑞 ∈ 𝐼，则𝑞 ∈ 𝜀_𝐶𝑙𝑜𝑠𝑢𝑟𝑒(𝐼)；

    ➢ 若𝑞 ∈ 𝐼, 𝛿(𝑞, 𝜀) = 𝑞′，则𝑞′ ∈ 𝜀_𝐶𝑙𝑜𝑠𝑢𝑟𝑒(𝐼)。(也即是从闭包内的状态接受空字可以转移到的状态)

    具体过程步骤:

    

  • 状态合并

    ➢ 每个状态子集视为新的状态；

    ➢ 初态为首行首列； (而不是含有初态的就是初态!)

    ➢ 终态是含有原终态的状态子集。

  DFA的化简

  • 定义等价状态

    • 如果从𝑠出发能读出某个字𝑤而停在终态，那么从𝑡出发也能读出字𝑤停在终态；

    • 如果从𝑡出发能读出某个字𝑤而停在终态，那么从𝑠出发也能读出字𝑤停在终态。

  • 可区别状态

    • 终态和非终态 可区别的
    • 射出弧不同(一个有a,一个没有a) 可区别的
    • 通过同样的输入得到的输出是可区别的 可区别的
    • 通过某个输入到达的状态及其等价状态,对另一个来说使用某个输入是不可到达的 可区别的

  • 化简时,首先从终态与非终态的区分开始

    每次都要检查原本同一个集合中的元素得到相同的输入后的输出是否在同一个集合中.如果不,将两者剥离.

  • 化简后的弧的创建:

    

LL(1)文法

• LL(1)分析,给出文法

  构造First集合
  否则Follow集合
  构造LL(1)分析表（可能涉及消除二义文法冲突）
  识别句子

  LL(1)文法中最重要的两个概念:

  • 终结首符集 (头符号集)
  • 后继终结符号集(后继符号集)产生原因在于对空字进行匹配时,需要依据这里的判断来决定是否要进行匹配.

  进行LL(1)分析时,需要满足的条件如下,满足以下条件,才称之为LL(1)文法:

  L: From Left to Right

  L: 最左推导

  1: 分析一步,看右侧的一个符号

  • 文法不含左递归； –不含有左递归

  • 对𝐴 → 𝛼1| … |𝛼𝑛的每对候选式，有𝐹𝑖𝑟𝑠𝑡 (𝛼𝑖) ∩ 𝐹𝑖𝑟𝑠𝑡(𝛼𝑗) = ∅，其中𝑖 ≠ 𝑗； 同一个推导式的右侧首符集无公用元素

  • 对非终结符号𝐴，**若𝜀 ∈ 𝐹𝑖𝑟𝑠𝑡(𝐴)**，有𝐹𝑖𝑟𝑠𝑡 (𝐴) ∩ 𝐹𝑜𝑙𝑙𝑜𝑤 (𝐴) = ∅。 同一个非终结符的首符集与后继符号集不相交。

    对与First集合中不含有空字的，无论其First集合与Follow集合相交是否为空，都不影响判断这个文法是否是LL(1)文法。

  分析时:

  

  First集合的求解:

  

  向首符集中添加空字\epsilon的条件:

  • 明确说明了从X能直接推导 epsilon
  • 对于X推导出的某一串连续的非终结符,这一串非终结符都含有空字epsilon

  对于Follow集合:

  • 特别地一个终结符#,在S所在的推导式的右侧添加#,进而为对应的非终结符提供Follow集合中的#

  • 具体求解

    

  构造LL(1)分析表

  

  表格的格式如下所示:

  	$V_{T1}$	$V_{T2}$	$\cdots$	#
  $V_{N1}$				千万不要忘记!
  $V_{N2}$
  $V_{N3}$

  分析过程

  

  进行分析时的表格格式如下所示:

  序号	文法符号栈	输入串	所用产生式

LR分析

• LR分析,给出文法

  构造拓广文法
  构造拓广文法的LR(0)/LR(1)项目集规范族
  构造LR(0)/LR(1)分析表（可能涉及消除二义文法冲突）
  识别句子

  分析法的优点:

  • 多数上下文无关文法描述的语言都可以使用LR分析器识别.
  • LR能分析的文法包括LL(1)能分析的文法.
  • 扫描输入串时可以发现任何错误,并能准确指出出错地点.

  常见的LR分析四种方法包括:

  • LR(0)分析法,局限性大
  • 简单LR(SLR)
  • 规范LR
  • 向前LR(LALR)

  定义LR文法以及相关概念

  • LR文法:文法能够构造一个LR分析表,使得其每一个入口都唯一

  • 规范句型: 包含句柄的可规约句型

  LR（0）分析法

  需要注意一点: $A\rarr \epsilon$只有一个状态$A\rarr \dot{}$

  分析过程:

  1. 首先构造拓广文法

     也就是$G_1=(V_T,V_N,S,P)$构造为$G_2=(V_T,V_N ∪{S’},S’,P∪{S’ \rarr S})$

     我们称G2是G1的拓广文法.

  2. 构造拓广文法的LR(0)项目集规范族

     这里需要使用到闭包的相关概念.

  3. 构造分析表

  4. 识别句子

  认为SLR与LR(1)的主要区别在于:

  SLR避免冲突的方式,是对整个文法中每个非终结符求取其对应的FOLLOW集合内容,从而得到对应的后继终结符,根据决定规约/移进时,对应规约式规约后的非终结符的FOLLOW集合中是否含有下一个要移入的终结符来判断是否选择规约.

  而LR(1)的方法相较于SLR更加细化,也就是其根据的不是宽泛的整个语法中的FOLLOW集合,而是单纯根据对应推导式的FOLLOW集合,具体是指对应·所在的位置后面,看作一个整体,看其整体的FIRST集合.

  三者的差别反映在分析表的构造上:

  • 对于LR(0),如果·到达了式子的末尾,那么对应在分析表的所有终结符对应位置都要填写规约式.

  • 对于SLR,只在规约后的非终结符的FOLLOW对应的终结符的位置填写规约式.

    

  • 对于LR(1),在对应·在式子末尾时,式子的前瞻符号的位置填写规约式.

    

翻译

• 给出翻译模式和高级语言程序，翻译句子

  一般涉及多种类型句子的综合，也可能涉及声明语句填写符号表。

  进行翻译时,这里给出几种方法:

  • 第一种就是按部就班按照PPT给定的方式进行翻译:

    首先根据产生式写出LR(0)分析表,确定运算的优先次序.

    其次按照LR(0)分析,对给定的程序输入串进行分析规约.同时通过设定好的语义规则产生中间代码.

  • 第二种,直接写语法树

    问题在于需要确定运算时的优先级设定.

    如果优先级确定没问题,那么最终结果应该也没问题.

  翻译时,一定务必搞清楚跳转关系啥的!!!

  

  几种常见的类型的句子的翻译:

  • 布尔

  • 控制

  • 说明

    这里说明语句,主要是在符号表中填写,主要填写内容包括:名字\类型\字宽等信息.

    ① 过程中的说明语句形式：𝑖𝑑1, 𝑖𝑑2, … , 𝑖𝑑𝑛 ∶ 𝑡𝑦𝑝𝑒

    ② 每个变量需要记录名字、类型、字宽信息，分别用属性name、type、width记录

    ③ 当新出现一个名字时，需要记录进符号表，用offset记录该名字在符号表中的地址偏移量，在识别前置初值为0 。

    ④ 过程enter(name, type, offset)用来把名字name填入到符号表，并给出该名字的类型type及在过程数据区中的相对地址offset。

    ⑤ 假定整数类型域宽为4，实型域宽为8。

DAG优化

• 给出基本代码块

  对于给定的基本块构造DAG

  按照构造DAG的节点顺序重新写中间代码

  利用节点排序算法对节点排序,并根据排序后的节点顺序写中间代码

  对上一步的中间代码利用简单代码生成算法生成目标代码

  写出优化后的中间代码
  写出DAG目标优化后的中间代码
  根据变量活跃性和寄存器信息，写出目标代码

  基础的内容暂且不表.

  代码块划分

  • 开始
    • 整个代码的开头
    • 跳转语句所能到达的位置
    • 在条件跳转语句之后的第一条语句
  • 结束
    • 另一个开头
    • 转移代码(包含
    • HALT指令(包含

  代码外提

  说一说代码外提的优化策略:

  1. 首先要满足这是一个循环不变量
  2. 要提出去的循环不变量应该是出口节点B的必经节点/或者如果不是必经节点,那么循环之后不能再引用改定点值.
  3. 循环不变量A=… 外提时,需要保证循环中的其它地方不再有A的定值点.
  4. 循环不变量A=…外提时,要求循环中所有关于A的引用点都必须是且仅是这个定值点所能达到的.(也就是不能在要外提的定值点之前出现对A的引用.

  其次是查找循环L中的不变量的算法:

  1. 依次查看每个L的每个基本块的代码,如果其运算对象为常数,或者定值点在L之外,将这个代码标记为不变运算.
  2. 重复后面一一步,直到没有新的代码被标记为不变运算
  3. 依次查看没有被标记为不变运算的代码,如果它的每个运算对象或为常数，或者定值点在L之外，或只有一个能到达的定值点且该点上的代码已标记为“不变运算”，则把查看的代码标记为“不变运算”.

  代码外提算法

  1. 寻找不变运算
  2. 判断能否外提
  3. 按照顺序依次外提

  强度削弱

  完成将循环内的每次的线性乘法分解成循环外的初始赋值和循环内的加法.

  将变量更换为常量.

  目标代码的生成设定

  • 相关设定

    ➢ 建立一个编译时用的寄存器描述数组𝑅𝑣𝑎𝑙𝑢𝑒，动态地记录各寄存器的上述信息

    ➢ 建立一个变量地址描述数组𝐴𝑣𝑎𝑙𝑢𝑒，动态地记录各变量现行值的存放位置：是寄存器中，还是某主存单元，还是既在寄存器又在主存单元。

  • 寄存器获取

    1. 如果𝐵存放在某个寄存器𝑅𝑖，𝑅𝑣𝑎𝑙𝑢𝑒[𝑅𝑖]只包含𝐵，同时，或者𝐵与𝐴是同一标识符，或者中间代码𝑖中𝐵的信息为(−, −)（即后面不再引用），则选取𝑅𝑖为所需寄存器，转(4)。

       (三个条件必须同时满足才行:在寄存器中,只包含,后续不用/同一标识符)

    2. 如果(1)失败，若有空闲寄存器𝑅𝑖，选择其作为所需寄存器，转(4)。

    3. 若(2)也失败，需要从已分配寄存器中选择𝑅𝑖：

    占用该𝑅𝑖的变量也保存在主存中，或者在最远的地方被引用（即待用信息值最大）。

    4. 对𝑅𝑣𝑎𝑙𝑢𝑒[𝑅𝑖]中的每个变量𝑀，如果𝑀 ≠ 𝐴，或者𝑀 = 𝐴 = 𝐶 ≠ 𝐵 ∧ 𝐵 ∉𝑅𝑣𝑎𝑙𝑢𝑒[𝑅𝑖]，则：

       ① 如果𝑀 ∉ 𝐴𝑣𝑎𝑙𝑢𝑒[𝑀]，生成目标代码𝑆𝑇 𝑅𝑖, 𝑀；

       ② 如果𝑀 = 𝐵，或者𝑀 = 𝐶 ∧ 𝐵 ∈ 𝑅𝑣𝑎𝑙𝑢𝑒[𝑅𝑖]，则令𝐴𝑣𝑎𝑙𝑢𝑒 𝑀 = {𝑀, 𝑅}，否则

       令𝐴𝑣𝑎𝑙𝑢𝑒 𝑀 = {𝑀}；

       ③ 删除𝑅𝑣𝑎𝑙𝑢𝑒[𝑅𝑖]中的𝑀；

       ④ 给出𝑅，返回。

       当前已经拿到了要分配的寄存器了,但是不确定要不要将寄存器内容写内存,因此需要判断:

  • 名词

    指令执行代价:：每条指令的执行代价 = 每条指令访问主存单元次数 + 1

  DAG的目标代码

  算法详情:

  

例题

第二章

• 构造语言

  给出语言$L(G)={a^{m}b^{n}|1<=n<=m<=2n}$, 请构造对应文法.

  答:
  $$
  G(S):\
  S=ab | aab\
  S=aSb | aaSb
  $$

• 作业题

  

第七章优先级

第七章说明