语义分析中间代码的产生和属性文法语法制导翻译

1.语义分析的任务

(1)审查每一个语法结构的静态语义,即验证语法正确的结构是否有意义。如:赋值语句:x:=x+y,左边变量类型与右边变量类型是否一致;(2)在语义正确的基础上生成一种中间代码或目标代码。

2.语义分析的范围
(1)确定类型:确定标识符所关联的数据类型。
(2)类型检查:按语言的类型规则,检查运算的合法性与运算分量类型的一致性,必要时作类型转换。

(3)识别含义:根据语言的语义定义(形式或非形式),识别程序中各构造成分组合到一起的含义,并作相应的语义处理(生成中间代码或目标代码)。

(4)控制流检查:控制流语句必须转移到合法的地方。如C中,break语句规定跳出最内层的循环或switch语句。

(5)一致性检查:在很多场合要求对象只能被说明一次。如:pascal语言规定同一个标识符在一个分程序中只能被说明一次等。(6)相关名字检查:如:Ada,循环或块可以有一个名字,它出现在这些结构的开头或结尾。编译程序必须检查这两个地方用的名字是否相同。

其它:如名字的作用域分析等也是语义分析的工作。

3.说明语句的翻译: 程序语言中的说明语句都是给编译程序提供信息的,诸如类型、维数、每维的界种类等,因此一般不生成目标,只是在编译时把有关信息填入相应表格即可。

 (1)简单说明句:用一个基本字来定义一串名字,其语法描述一般为:
     D→integer namelist∣real namelist
     namelist→namelist,i∣i
     直接用这种文法来制导翻译有点麻烦,就是只能在把所有名字规约成namelist之后才能把性质登记到符号表中。这就意味着在扫描名字时,应把名字用一个队列(或栈)保存起来,然后再处理。
我们可以对文法稍做改动,就可以免去建立队列或栈的过程。修改文法如下:     

           D→D,i∣integer i∣real i

(2)数组说明

语义分析中间代码的产生和属性文法语法制导翻译

4.数组元素的地址计算公式: 若数组A的元素存放在一片连续单元里,则可以较容易的访问数组的每个元素。假定数组的每个元素的宽度为w,则一维数组A[i] 这个元素的起始地址为:
                            base + (i – low)*w 
            其中,low为数组下标的下界, base是分配给数组的相对地址,即base为A的第一个元素A[low]的相对地址。
        base + (i – low)*w   可整理为:  i*w + (base –low*w)
  其中:
     (1) i*w  是随数组下标变量而变化的部分,记为VARPART ;

    (2)(base – low*w)是在数组中不变化的常数记为CONSPART

5.二维数组:若二维数组A按行存放,则可用如下公式计算A[i1,i2]的相对地址:
    base + (( i1 – l1)*d2 + i2 – l2) *w
    其中,l1、l2分别为i1、i2的下界;di界差。若ui为i的上界,则di=ui – li +1.
假定i1,i2是编译时唯一尚未知道的值,我们可以重写上述表达式为:( base –( (l1 *d2) + l2) *w)+ ( (i1*d2) + i2) *w          
                  CONSPART                   VARPART
       其中:前一项子表达式( base – ((l1 *d2) + l2) *w )的值是可以在编译时确定的记为常数CONSPART。

      后一子项随i1, i2 而改变是一个变数记VARPART。

6.循环与分情况语句的翻译:

大多数程序语言中都有如下形式的循环句:
      S→for i:=E1 step E2 until E3 do S1
   其语义各语言可能有所不同,主要区别在先判断、后执行还是先执行、后判断。按Algol语言的解释:
              i:=E1;
              goto over;
      again:  i:=i+E2;
      over:   if i<=E3 then 

                begin  S1; goto again  end;

 于是为了产生四元式,描述文法改写如下:
          F1→for i:=E1
      F2→F1 step E2
      F3→F2 until E3
      S→F3 do S1

    根据前面的解释,i在几处都用到,故ENTRY(i)必须保留下来,而该文法正是基于这样的考虑而写出来的。

7..属性文法是在上下文无关文法的基础上为每个文法符号(终结符或非终结符)配备若干个相关的“值”(称为属性)。

8.属性的分类:

(1)综合属性:用于“自下而上”传递信息,在语法树中,一个结点的综合属性的值,由其子结点的属性值确定

  (2)继承属性:用于“自上而下”传递信息。在语法树中,一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定

9.语义规则:属性计算的过程即是语义处理的过程,对于文法的每一个产生式配备一组属性的计算规则,则称为语义规则。在一个属性文法中,对应于每个产生式A都有一套与之相关联的语义规则,每条语义规则的形式为:b:=f(c1,c2,…,ck)  这里f是一个函数,而且或者(1)b是A的一个综合属性并且c1,c2,…ck是产生式右边文法符号的属性;或者(2)b是产生式右边某个文法符号的一个继承属性并且c1,c2,…ck是A或产生式右边任何文法符号的属性,在这两种情况下,我们都说属性b依赖于属性c1,c2,…,ck.A-》=>b1b2…bn,b:=f(c1,c2,…,ck)(1)b是A的一个综合属性(2)b是bi的一个继承属性

10.基于属性文法的处理过程:输入串->语法树->依赖图->语义规则计算次序->计算结果

11.依赖图的构造算法:for分析树中每一个结点n
for 结点的文法符号的每一个属性a
为a在依赖图中建立一个结点;
        for分析树中每一个结点n
for结点n所用产生式对应的每一个语义规则
b:=f(c1,c2,…ck)
for i :=1 to k

从ci结点到b结点构造一条有向边

12.L属性文法:如果每个产生式A X1 X2 … Xn 的每条语义规则计算的属性是A的综合属性;或者是Xj 的继承属性, 1  j  n, 但它仅依赖:该产生式中Xj左边符号X1, X2, …, Xj-1的属性;A的继承属性,S属性文法包含于L属性文法

13.翻译模式:翻译模式是语法制导定义的一种便于翻译的书写形式。其中属性与文法符号相对应,语义规则或语义动作用花括号{ }括起来,可被插入到产生式右部的任何合适的位置上。


语义分析中间代码的产生和属性文法语法制导翻译