语义分析和中间代码产生

第七章语义分析和中间代码产生

本章概述

上一章我们介绍了属性文法和语法制导翻译，本章我们将把上章所介绍的方法和技术应用于语义分析和中间代码产生中。

主要学习内容：中间语言的形式——后缀式、图表示法、三地址代码，说明语句的语义分析，赋值语句的翻译，布尔表达式的翻译，控制语句的翻译，过程调用的处理，类型检查。

学习目标：熟悉几种中间语言的描述，掌握各种语句的翻译方法，会给出各种语句的语义规则和语义子程序。

学习重点和难点：如何把属性文法和语法制导翻译的方法和技术应用于语义分析和中间代码产生中，特别是表达式和控制语句的翻译。

7.1 中间语言

7.1.1 中间语言

虽然源程序可以直接翻译为目标语言代码。但是许多编译程序都采用了独立于机器的、复杂性介于源语言和机器语言之间的中间语言。常见的中间语言形式包括：后缀式，三地址代码（包括三元式，四元式，间接三元式），DAG图表示和抽象语法树等。

1. 后缀式

后缀式表示法是波兰逻辑学家卢卡西维奇（Lukasiewicz）发明的一种表示表达式的方法，因此又称逆波兰表示法。这种表示法是，把运算量（操作数）写在前面，把算符写在后面（后缀）。例如，把a+b写成ab+，把a*b写成ab*。

2. 抽象语法树

在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。这种经变换后的语法树称之为抽象语法树（Abstract Syntax Tree）。

3. DAG

与抽象语法树一样，对表达式中的每个子表达式，DAG（Directed Acyclic Graph）中都有一个结点。一个内部结点代表一个操作符，它的孩子代表操作数。两者不同的是，在一个DAG 中代表公共子表达式的结点具有多个父结点，而在一棵抽象语法树中公共子表达式被表示为重复的子树。

4. 三地址代码

三地址代码是由下面一般形式的语句构成的序列：

x:=y op z

其中x,y,z为名字、常数或编译时产生的临时变量，op代表运算符号如定点运算符、浮点运算符、逻辑运算符等等。每个语句的右边只能有一个运算符。例如，源语言表达式x+y*z 可以被翻译为如下语句序列：

T1:=y*z

T2:=x+T1

其中T1,T2为编译时产生的临时变量。之所以称为三地址代码是因为每条语句通常包含三个地址，两个用来表示操作数，一个用来存放结果。

三地址语句类似于汇编语言代码。语句可以带有符号标号，而且存在各种控制流语句。符号标号代表存放中间代码的数组中三地址代码语句的下标。下面是常用的三地址语句的种类：

(1) 形如x:=y op z的赋值语句，其中op为二元算术算符或逻辑算符。

(2) 形如x:=op y的赋值语句，其中op为一元算符，如一元减uminus、逻辑非not、移位算符及转换算符（如将定点数转换成浮点数）。

(3) 形如x:=y的复制语句，它将y的值赋给x。

(4) 形如goto L的无条件转移语句，即下一条将被执行的语句是带标号L的三地址语句。

(5) 形如if x relop y goto L或if a goto L的条件转移语句。第一种形式语句施用关系运算符号relop（如<, =, >, =等等）于x和y，若x与y满足关系relop，那么下面就执行带标号L的语句，否则下面就继续执行if语句之后的语句。第二种形式的语句中，a为布尔变量或常量，若a为真，则执行带标号L的语句，否则执行后一条语句。

(6) 用于过程调用的语句param x和call p,n，以及返回语句return y。源程序中的过程调用语句p(x1,x2,…,x n)通常产生如下的三地址代码：

param x1

param x2

……

param x n

call p,n

其中n表示实参个数。过程返回语句return y中y为过程返回的一个值。

(7) 形如x:=y[i]及x[i]:=y的索引赋值。前者把相对于地址y的后面第i个单元里的值赋给x。后者把y的值赋给相对于地址x后面的第i个单元。

(8) 形如x:=&y, x:=*y和*x:=y的地址和指针赋值。其中第一个赋值语句把y的地址赋给x。第二个赋值语句x:=*y执行的结果是把y所指示的地址单元里存放的内容赋给x。第三个赋值语句*x:=y，将把x所指向的对象的右值赋为y的右值。

三地址语句可看成中间代码的一种抽象形式。编译程序中，三地址代码语句的具体实现可以用记录表示，记录中包含表示运算符和操作数的域。通常有三种表示方法：四元式、三元式、间接三元式。

1. 四元式

一个四元式是一个带有四个域的记录结构，这四个域分别称为op, arg1, arg2及result。域op包含一个代表运算符的内部码。三地址语句x:=y op z可表示为：将y置于arg1域，z 置于arg2域，x置于result域，:=为算符。带有一元运算符的语句如x:=-y或者x:=y的表示中不用arg2。而象param这样的运算符仅使用arg1域。条件和无条件转移语句将目标标号置于result域中。

2. 三元式

为了避免把临时变量填入到符号表，我们可以通过计算这个临时变量值的语句的位置来引用这个临时变量。这样表示三地址代码的记录只需三个域：op、arg1和arg2。因为用了三个域，所以称之为三元式。

3. 间接三元式

为了便于代码优化处理，有时不直接使用三元式表，而是另设一张指示器（称为间接码表），它将按运算的先后顺序列出有关三元式在三元表中的位置。换句话说就是，我们用一张间接码表辅以三元式表的办法来表示中间代码。这种表示法称为间接三元式。

7.2说明语句

7.2.1 说明语句

当考查一个过程或分程序的一系列说明语句时，便可为局部于该过程的名字分配存储空间。对每个局部名字，我们都将在符号表中建立相应的表项，并填入有关的信息如类型、在存储器中的相对地址等。相对地址是指对静态数据区基址或活动记录中局部数据区基址的一个偏移量。

当产生中间代码地址时，对目标机一些情况做到心中有数是有好处的。例如，假定在一个以字节编址的目标机上，整数必须存放在4的倍数的地址单元，那么，计算地址时就应以4的倍数增加。

在C、Pascal及FORTRAN等语言的语法中，允许在一个过程中的所有说明语句作为一个组来处理，把它们安排在一所数据区中。从而我们需要一个全程变量如offset来跟踪下一个可用的相对地址的位置。

允许嵌套过程的语言，对于每一个过程，其中局部名字的相对地址计算与前述一样。而当遇到一个嵌入的过程说明时，则应当暂停包围此过程的外围过程说明语句的处理。

对于记录中的域名同样可以类似地给它建立一张符号表。

7.3 赋值语句的翻译

7.3.1 赋值语句的翻译

对于简单算术表达式及赋值语句,把它们翻译为三地址代码的翻译模式是比较好理解的,如下所示。

S→id:=E {p:=lookup(https://www.doczj.com/doc/165280104.html,);

if p nil then

emit(p ‘:=’ E.place)

else error}

E→E1+E2{E.place:=newtemp;

emit(E.place ‘:=’ E1.place ‘+’ E2.place)}

E→E1*E2 {E.place:=newtemp;

emit(E.place ‘:=’ E 1.place ‘*’ E 2.place)}

E→E1{E.place:=newtemp;

emit(E.place‘:=’ ‘uminus’E 1.place)}

E→(E1) {E.place:=E1.place}

E→id {p:=lookup(https://www.doczj.com/doc/165280104.html,);

if p nil then

E.place:=p

else error }

产生简单算术表达式及赋值语句三地址代码的翻译模式

如果表达式和赋值句中包含数组元素的引用，则编译程序要根据数组元素的地址计算公式产生相应的代码。为了便于翻译，我们把包含数组元素引用的表达式和赋值句的产生式改写成如下形式：

(1) S→L:=E

(2) E→E+E

(3) E→(E)

(4) E→L

(5) L→Elist ]

(6) L→id

(7) Elist→Elist, E

(8) Elist→id [ E

相应的翻译模式如下所示。

S→L:=E

{if L.offset=null then /*L是简单变量*/

emit(L.place ‘:=’ E.place)

else emit(L.place ‘ [’ L.offset‘]’ ‘:=’ E.place)}

E→E1 +E2

{E.place:=newtemp;

emit(E.place ‘:=’ E 1.place ‘+’ E 2.place)}

E→(E1)

{E.place:=E1.place}

E→L

{if L.offset=null then

E.place:=L.place

else begin

E.place:=newtemp;

emit(E.place ‘:=’ L.place ‘[’ L.offset ‘]’)

end }

L→Elist ]

{L.place:=newtemp;

emit(L.place ‘:=’ Elist.array ‘－’ C);{C的定义见（7.7）} L.offset:=newtemp;

emit(L.offset ‘:=’ w ‘*’ Elist.place)}

L→id

{ L.place:=id.place; L.offset:=null }

Elist→Elist1, E

{t:=newtemp;

m:=Elist1.ndim+1;

emit(t ‘:=’ Elist1.place ‘*’ limit(Elist1.array,m));

emit(t ‘:=’t ‘+’ E.place);

Elist.array:= Elist1.array;

Elist.place:=t;

Elist.ndim:=m}

Elist→id [ E

{Elist.place:=E.place;

Elist.ndim:=1;

Elist.array:=id.place}

含数组元素引用的表达式和赋值句的翻译模式

7.4 布尔表达式的翻译

7.4.1 布尔表达式的翻译

在程序设计语言中，布尔表达式有两个基本的作用：一个是用作计算逻辑值；另一个，也是更多地是用作控制流语句如if-then、if-then-else和while-do等之中的条件表达式。

作为逻辑求值的布尔表达式的翻译与简单算术表达式的翻译类似，较易理解。

重点是作为条件控制的布尔表达式的翻译。

出现在条件语句

if E then S1 else S2

中的布尔表达式E，它的作用仅在于控制对S

1和S

2

的选择。只要能够完成这一使命，E的值

就无须最终保留在某个临时单元之中。因此，作为转移条件的布尔式E，我们可以赋予它两

种“出口”。一是“真”出口，出向S

1；一是“假”出口，出向S

2

。

对于作为转移条件的布尔式，我们可以把它翻译为一串跳转指令。例如，可把语句if a>c or b

翻译成如下一串三地址代码：

if a>c goto L2

goto L1

L1: if b

goto L3

L2: （关于S1的三地址代码序列）

goto Lnext

L3: （关于S2的三地址代码序列）

Lnext:

在翻译过程中，我们假定可以用符号标号来标识一条三地址语句，并且假定每次调用函数newlabel后都返回一个新的符号标号。

对于一个布尔表达式E，我们引用两个标号：E.true是E为‘真’时控制流转向的标号，E.false是E为‘假’时控制流转向的标号。

基本翻译思想如下：

假定E形如a

if a

goto E.false

假定E形如E1 or E2。若E1为真，则立即可知E为真，于是E1.true与E.true是相同的。若E1为假，则必须对E2求值，因此我们置E1.false为E2的代码的第一条指令的标号。而E2的真、假出口可以分别与E的真、假出口相同。类似可考虑形如E1 and E2的E的翻译。至于形如not E1的布尔表达式E不必生成新的代码，只要把E1的假、真出口作为E的真、假出口即可。

现在要考虑的是，如果希望通过一遍扫描来产生布尔表达式的代码，如何处理？

为了便于讨论，我们假设下面在实现三地址代码时，采用四元式形式实现。

通过一遍扫描来产生布尔表达式和控制流语句的代码的主要问题在于，当生成某些转移语句时我们可能还不知道该语句将要转移到的标号究竟是什么。为了解决这个问题，我们可以在生成形式分支的跳转指令时暂时不确定跳转目标，而建立一个链表，把转向这个目标的跳转指令的标号连入这个链表。一旦目标确定之后再把它填入有关的跳转指令中。这种技术称为“回填”技术。

按照这个思想，我们为非终结符E赋予两个综合属性E.truelist和E.falselist。它们分别记录布尔表达式E所应的四元式中需回填“真”、“假”出口的四元式的标号所构成的链表。具体实现时，我们可以借助于需要回填的跳转四元式的第四区段来构造这种链。例如，假定

E的四元式中需回填“真”出口的有p、q和r三个四元式，这三个四元式可连成如下图所示的一条“真”链（truelist），作为E.truelist之值的是链首（r）：

0为链末标志，地址（r）是truelist链之首

为了便于处理，需用到下面几个变量或函数（过程）：

1. 变量nextquad，它指向下一条将要产生但尚未形式的四元式的地址（标号）。nextquad 的初值为1，每当执行一次emit之后，nextquad将自动增1。

2. 函数makelist(i)，它将创建一个仅含i的新链表，其中i是四元式数组的一个下标（标号）；函数返回指向这个链的指针。

3. 函数merge(p1,p2)，把以p1和p2为链首的两条链合并为一，作为函数值，回送合并后的链首。

4. 过程backpatch(p, t)，其功能是完成“回填”，把p所链接的每个四元式的第四区段都填为t。

现在，我们来构造一个翻译模式，使之能在自底向上的分析过程中生成布尔表达式的四元式代码，如下所示。我们在文法中插入了标记非终结符M，以便在适当的时候执行一个语义动作，记下下一个将要产生的四元式标号。

E→E1 or M E2{ backpatch(E1.falselist, M.quad);

E.truelist:=merge(E1.truelist, E2.truelist);

E.falselist:=E2.falselist }

E→E1 and M E2{ backpatch(E1.truelist, M.quad);

E.truelist:=E2.truelist;

E.falselist:=merge(E1.falselist,E2.falselist) }

E→not E1{ E.truelist:=E1.falselist;

E.falselist:=E1.truelist}

E→(E1) { E.truelist:=E1.truelist;

E.falselist:=E1. falselist}

E→id1 relop id2 { E.truelist:=makelist(nextquad);

E.falselist:=makelist(nextquad+1);

emit(‘j’ relop.op ‘,’ id 1.place ‘,’ id 2.place‘,’‘0’);

emit(‘j, －, －, 0’)

E→id { E.truelist:=makelist(nextquad);

E.falselist:=makelist(nextquad+1);

emit(‘jnz’ ‘,’ id.place ‘,’ ‘－’ ‘,’‘0’)

emit(‘ j, -, -, 0’) }

M→ { M.quad:=nextquad }

作为转移条件的布尔式的翻译模式

7.5 控制语句的翻译

7.5.1 控制语句的翻译

这里考虑if-then,if-then-else,while-do语句的翻译。文法如下：

S→if E then S1

| if E then S1 else S2

| while E do S1

其中E为布尔表达式。

与上一节一样，我们先讨论对这些语句进行翻译的一般的语义规则。然后讨论如何通过一遍扫描产生上述语句的代码，给出相应的翻译模式。

关于这三条语句的代码结构如下图所示。条件语句S的语义规则允许控制从S的代码S.code之内转移到紧接S.code之后的那一条三地址指令。但是，有时此条紧接S.code之后的指令是一条无条件转移指令，它转移到标号为L的指令。通过使用继承属性S.next可以避免上述连续转移的情况发生，而从S.code之内直接转移到标号为L的指令。S.next之值是一个标号，它指出继S的的代码之后将被执行的第一条三地址指令。

(a) (b) (c)

图7.1 关于if-then,if-then-else和while-do语句的代码结构

在翻译if-then语句S→if E then S1时，我们建立了一个新的标号E.true，并且用它来标识S1的代码的第一条指令，如上图(a)所示。下表给出了一个属性文法。在E的代码中将有这样的转移指令：若E为真则转移到E.true，并且若E为假则转移到S.next。因此我们置E.false 为S.next。

在翻译if-then-else语句S→if E then S1 else S2时，布尔表达式E的代码中有这样的转移指令：若E为真则转移到S1的第一条指令，若E为假则转移到S2的第一条指令。如上图(b)所示。与if-then语句一样，继承属性S.next给出了紧接着S的代码之后将被执行的三地址指令的标号。在S1的代码之后有一条明显的转移指令goto S.next，但S2之后没有。请读者注意，考虑到语句的相互嵌套，S.next未必是紧跟在S2.code之后的那条代码的标号。如：

if E1 then if E2 then S1 else S2 else S3

说明了这种情况。

while-do语句S→while E do S1的代码结构如上图(c)所示。我们建立了一个新的标号S.begin，并用它来标识E的代码的第一条指令。另一个标号E.true标识S1的代码的第一条指令。在E的代码中有这样的转移指令：若E为真则转移到标号为E.true的语句，若E为假则转移到S.next。同前面一样，我们置E.false为S.next。在S1的代码之后我们放上指令goto S.begin，用来控制转移到此布尔表达式的代码的开始位置。注意，我们置S1.next为标

号S.begin，这样在S1.code之内的转出指令就能直接转移到S.begin。表控制流语句的属性文法

S.code:=gen(S.begin ‘:’) || E.code ||

gen(E.true ‘:’) || S1.code ||

gen(‘goto’S.begin)

现在，我们来看如何使用回填技术并通过一遍扫描翻译控制流语句。考虑下面文法对应的翻译模式。

(1) S→if E then S

(2) | if E then S else S

(3) | while E do S

(4) | begin L end

(5) | A

(6) L→L;S

(7) | S

这里，S表示语句，L表示语句表，A为赋值语句，E为一个布尔表达式。实际上还应有一些其它的产生式如生成赋值语句的产生式，然而这里所给出的已足够用来说明翻译控制流语句的技术。

与讨论布尔表达式的翻译时一样，我们仍然采用四元式来实现三地址代码。

非终结符号E有两个属性E.truelist和E.falselist。同样，表示语句的S和表示语句表的L也分别需要一个未填写目标标号而在以后需要回填的转移指令的链。这些链表分别由属性L.nextlist和S.nextlist指示。指针S.nextlist （L.nextlist）指向一个转移指令链表。表中相应的指令将控制流转移到紧接语句S（L）之后要执行的代码处。

如上图(c)所示关于产生式S→while E do S1的代码结构中，标号S.begin和E.true分别标记整个语句S的代码的头一条指令和其中的循环体S1的代码的头一条指令。因此，在下面产生式中引入了标记非终结符M，以记录这些位置的四元式标号：

S→while M1 E do M2 S1

M的产生式为M ，其语义动作是把下一条四元式的标号赋给属性M.quad。当while语句中S1的代码执行完毕以后，控制流转向S语句的开始处。因此，当我们归约while M1 E do M2

S1为S时，我们回填表S1.nextlist中所有相应的转移指令的目标标号为M.quad。自然，我们需要在S1的代码之后增加一条转移到E的代码的开始位置的目标指令。另外，我们回填表E.truelist中相应的转移指令的目标标号为M2.quad，即S1的代码的开始位置。

考虑条件语句if E then S1 else S2的代码生成，执行完S1的代码后，应跳过S2的代码。因此，在S1的代码之后应有一条无条件转移指令。我们用一个标记非终结符N来生成这么一条跳转指令，N的产生式为N→ε，它具有属性N.nextlist，它是一个链，链中包含由N的语义动作所产生的跳转指令的标号。根据以上讨论，我们给出改写后的文法的翻译模式，如下。

S→if E then M1 S1 N else M2 S2

{backpatch(E.truelist, M1.quad);

backpatch(E.falselist, M2.quad);

S.nextlist:=merge(S1.nextlist, N.nextlist, S2.nextlist)}

N→ε{N.nextlist:=makelist(nextquad);

emit(‘j,－,－,－’) }

M→ε{M.quad:=nextquad}

S→if E then M S1{backpatch(E.truelist, M.quad);

S.nextlist:=merge(E.falselist, S1.nextlist)}

S→while M1 E do M2 S1{backpatch(S1.nextlist, M1.quad);

backpatch(E.truelist, M2.quad);

S.nextlist:=E.falselist

emit(‘j,－,－,’ M1.quad)}

S→begin L end {S.nextlist:=L.nextlist}

S→A{S.nextlist:=makelist( )}

7.6过程调用的处理

7.6.1 过程调用的处理

过程是程序设计语言中最常用的一种结构。我们这节所讨论的也包括函数，实际上函数可以看作是返回结果值的过程。

我们考虑过程调用文法如下：

(1) S→call id (Elist)

(2) Elist→Elist, E

(3) Elist→E

过程调用的实质是把程序控制转移到子程序（过程段）。在转子之前必须用某种办法把实在参数的信息传递给被调用的子程序，并且应该告诉子程序在它工作完毕后返回到什么地方。现在计算机的转子指令大多在实现转移的同时就把返回地址（转子指令之后的那个单元地址）放在某个寄存器或内存单元之中。因此，在返回方面并没有什么需要特殊考虑的问题。关于传递实在参数信息方面有种种不同的处理方法。我们这里只讨论最简单的一种，即传递实在参数地址（传地址）的处理方式。

如果实在参数是一个变量或数组元素，那么，就直接传递它的地址。如果实参是其它表达式，如A＋B或2，那么，就先把它的值计算出来并存放在某个临时单元T中，然后传送T的地址。所有实在参数的地址应存放在被调用的子程序能够取得到的地方。在被调用的子程序（过程）中，相应每个形式参数都有一个单元（称为形式单元）用来存放相应的实在参数的地址。在子程序段中对形式参数的任何引用都当作是对形式单元的间接访问。当通过转子指令进入子程序后，子程序段的第一步工作就是把实在参数的地址取到对应的形式单元中，然后，再开始执行本段中的语句。

传递实在参数地址的一个简单办法是，把实参的地址逐一放在转子指令的前面。例如，过程调用

CALL S(A+B,Z)

将被翻译成：

计算A＋B置于T中的代码/*T:=A+B*/

par T /*第一个实参地址*/

par Z /*第二个实参地址*/

call S /*转子指令*/

当通过执行转子指令call而进入子程序S之后，S就可根据返回地址（假定为k，它是call 后面的那条指令地址）寻找到存放实在参数地址的单元（分别为k-3和k-2）。

根据上述关于过程调用的目标结构，我们现在来讨论如何产生反映这种结构的代码。为了在处理实在参数串的过程中记住每个实参的地址，以便最后把它们排列在call指令之前，我们需要把这些地址存放起来。用来存放这些地址的一个方便的数据结构是队列，一个先进先出表。我们将赋予产生式Elist→Elist，E的语义动作是；将表达式E的存放地址E.place 放入队列queue中。产生式S→call id (Elist)的语义动作是：对队列queue中的每一项生成一条param语句，并让这些语句接在对参数表达式求值的那些语句之后。对参数表达式求值的语句已在将它们归约为E时产生。下面的翻译模式体现了上述思想。

1. S→call id (Elist)

{for 队列queue中的每一项p do

emit(‘param’ p);

emit(‘call’ id.place)}

S的代码包括：首先是Elist的代码（即对各参数表达式求值的代码），其次是顺序为每一个参数对应一条param语句，最后是一个call语句。

2. Elist→Elist, E

{将E.place加入到queue的队尾}

3. Elist→E

{初始化queue仅包含E.place}

这里，初始化queue为一个空队列，然后将E.place送入queue。

7.7 类型检查

7.7.1 类型检查

类型检查是静态语义分析的重要内容。大多数静态语义分析的工作都可以用语法制导技术实现,有些工作可以合并到其它工作中。例如，当我们把一个名字填入到符号表的时候，我们就可以检查这个名字是否只说明了一次。又如，在进行算术表达式的翻译时，就可考虑

类型转换的问题。

类型检查验证一种结构的类型是否匹配其上下文要求的类型。例如，Pascal的算术运算符mod要求整型的操作数，所以，类型检查器必须验证mod的操作数是整数类型的。还有：下标只能用于数组；调用用户定义的函数或过程时，实参的个数和类型要与形参一致；等等。

生成目标代码时，需要类型检查时收集的类型信息。像算术运算符＋通常用于整型或实型的数据；但还可能用于其它类型的数据，这要根据上下文来验证操作的合法性。如果一个运算符在不同的上下文中表示不同的运算，则称该运算符为重载运算符（overloading operator）。Pascal的＋运算符就是一个重载运算符，它根据上下文确定进行加法运算还是集合的并运算。重载可以伴随类型强制，编译程序按照运算符把操作数转换成上下文要求的类型。

还有一种与重载有所不同的表示——“多态性”。具有多态性的函数可以根据不同类型的参数从而执行不同的动作。多态性是面向对象语言的重要特点之一。

为了设计类型检查器，需要首先考虑的是关于语法结构、表示类型的记号和把类型赋给语法结构的规则。为此，引入类型表达式的概念。一个类型表达式或者是基本类型，或者由类型构造符施于其他类型表达式组成。基本类型和类型构造符都取决于具体的语言。

所谓类型系统就是把类型表达式赋给语言各相关结构成分的规则的集合。

如果类型检查在编译时进行，则称之为静态的；而如果类型检查在程序运行时进行，则称为动态的。

如果消除了动态检查类型错误的需要，则为良类型系统。良类型系统允许我们静态地确定目标程序运行时不会发生类型错误。一个语言称为强类型的，如果它的编译器能保证编译通过的程序运行时不会出现类型错误。

为了便于理解，我们给出一种简单语言类型检查器的规格说明。这种语言要求每个标识符在使用之前都必须预先说明。类型检查器可以处理简单类型、数组、指针、语句和函数。这个简单语言的文法如下：

P→D;E

D→D;D | id:T

T→char | integer | array[num]of T | ↑T

E→literal | num | id | E mod E | E [E] | E↑

文法中，P代表程序、D代表说明、E代表表达式。

我们给出确定标识符类型的部分翻译模式，如下：

P→D;E

D→D;D

D→id:T {addtype (id.entry, T.type)}

T→char {T.type:=char}

T→integer {T.type:=integer}

T→↑T1 {T.type:=pointer (T1.type)}

T→array [num] of T1{T.type:=array (num.val, T1.type)}关于表达式的类型检查的翻译模式如下：

E→literal {E.type:=char}

E→num {E.type:=integer}

E→id {E.type:=lookup (id.entry)}

E→E1 mod E2{ if E1.type=integer and E2.type=integer

then E.type:=integer

else E.type:=type_error}

E→E1 [E2] { if E2.type=integer and E1.type=array(s,t)

then E.type:=t

else E.type:=type_error}

E→E1↑ { if E1.type=pointer (t)

then E.type:=t

else E.type:=type_error}

关于语句的类型检查的翻译模式如下：

S→id:=E { if id.type=E.type

then S.type:=void

else S.type:=type_error}

S→if E then S1{ if E.type=boolean

then S.type:=S1.type

else S.type:=type_error}

S→while E do S1{ if E.type=boolean

then S.type:=S1.type

else S.type:=type_error}

S→S1;S2{ if S1.type=void and S2.type=void

then S.type:=void

else S.type:=type_error}

最后，考虑函数的类型检查。

下面产生式可以使关于函数的类型表达式和非终结符T结合，其语义动作允许在说明中出现函数的类型。

T→T1 ‘→’ T 2{T.type:=T1.type →T2.type}

其中，用引号括起来的箭头用作函数的类型构造符，表示由类型T1.type映射成类型T2.type，结果T.type是函数的类型表达式。

关于函数引用的类型检查规则如下：

E→E1（E2）{ if E2.type=s and E1.type=s→t

then E.type:=t

else E.type:=type_error}

这一规则表示，在函数调用E1（E2）形成的表达式中，当E2的类型为s，E1的类型为s→t 时，结果E1（E2）的类型为t，即由类型s经E1映射出的结果类型。

本章内容总结

通过学习我们掌握了下面三方面的重要内容：

1.对于高级语言语句, 我们能够把它翻译为中间代码, 如三地址代码(四元式、三元式﹑间接三元式),或后缀式等。

2.对于给定的一个属性文法（或语法制导定义，或翻译模式）及该文法的一个句子，我们能够确定按属性文法（或语法制导定义，或翻译模式）对句子进行翻译的结果。

3.给定一个文法(一个语法成分)和语义规范，我们能够构造出对它进行语义分析和翻译的语义子程序(语义动作)或属性文法(语法制导定义)或翻译模式(翻译方案)。

编译原理语义分析实验报告——免费!

语义分析实验报告 一、实验目的： 通过上机实习，加深对语法制导翻译原理的理解，掌握将语法分析所识别的语法成分变换为中间代码的语义翻译方法。 二、实验要求： 采用递归下降语法制导翻译法，对算术表达式、赋值语句进行语义分析并生成四元式序列。 三、算法思想： 1、设置语义过程。 （1）emit(char *result,char *ag1,char *op,char *ag2) 该函数的功能是生成一个三地址语句送到四元式表中。 四元式表的结构如下： struct { char result[8]; char ag1[8]; char op[8]; char ag2[8]; }quad[20]; (2) char *newtemp() 该函数回送一个新的临时变量名，临时变量名产生的顺序为T1，T2，… char *newtemp(void) { char *p; char m[8]; p=(char *)malloc(8); k++; itoa(k,m,10); strcpy(p+1,m); p[0]=’t’; return(p); } 2、函数lrparser 在原来语法分析的基础上插入相应的语义动作：将输入串翻译成四元式序列。在实验中我们只对表达式、赋值语句进行翻译。

四、源程序代码： #include #include #include #include struct { char result[12]; char ag1[12]; char op[12]; char ag2[12]; }quad; char prog[80],token[12]; char ch; int syn,p,m=0,n,sum=0,kk; //p是缓冲区prog的指针，m是token的指针char *rwtab[6]={"begin","if","then","while","do","end"}; void scaner(); char *factor(void); char *term(void); char *expression(void); int yucu(); void emit(char *result,char *ag1,char *op,char *ag2); char *newtemp(); int statement(); int k=0; void emit(char *result,char *ag1,char *op,char *ag2) { strcpy(quad.result,result); strcpy(quad.ag1,ag1); strcpy(quad.op,op); strcpy(quad.ag2,ag2);

语义分析

语义分析 1.语义分析？ 机器机和人不一样的地方是人可以直接理解词的意思，文章的意思，机器机不能理解。 人看到苹果这两个字就知道指的是那个圆圆的，挺好吃的东西，搜索引擎却不能从感性上理解。但搜索引擎可以掌握词之间的关系，这就牵扯到语义分析。 可参考：https://www.doczj.com/doc/165280104.html,/dispbbs.asp?boardID=2&ID=74541 2.为什么要使用语义分析？ 我国中文自然语言处理普遍采用西基于拉丁语系的“关键词”技术，以此来分析理解中文。然而，中文本身的特点决定它与西语之间巨大的区别，所以从汉语信息处理的需要看，当前急迫需要突破的是语义问题。 可参考： https://www.doczj.com/doc/165280104.html,/dicksong2008/blog/item/88fb751e9ac9501a4134 17f4.html 2.1中文与西语不同决定我们无法采用西语的架构体系来处理中文，具体区别在于： 西语词间有间隔，汉语词间无间隔。众所周知，英文是以词为单位的，词和词之间是靠空格隔开，而中文是以字为单位，句子中所有的字连起来才能描述一个意思。 例如，英文句子I am a student，用中文则为：“我是一个学生”。计算机可以很简单通过空格知道student是一个单词，但是不能很容易明白“学”、“生”两个字合起来才表示一个词。把中文的汉字序列切分成有意义的词，就是中文分词，有些人也称为切词。 “我是一个学生”，分词的结果是：“我是一个学生”。中文分词就成了计算机处理的难题。 汉语形态不发达，句尾没有形态标记。英语动词、名词很清楚，加上词尾可以是副词；西语有时态，过去式、现在式等等非常清楚，中文则依靠词语或者依靠自己的判断来确定时态。 同音字多增加了机器识别的难度。 汉语语义灵活，由于形态不发达，所以语序无规律。在一次学术会议上，一位著名的人工智能专家说：“按…主－谓－宾?或…名－动－名?这一规则，计算机可显出…牛吃草?，也可显出…草吃牛?。从语法格式上看，…草吃牛?也不错，但这句话是说不通的。 人依靠自己的经验可以判断，机器如何来判断呢？

语义分析和中间代码产生

第七章语义分析和中间代码产生 本章概述 上一章我们介绍了属性文法和语法制导翻译，本章我们将把上章所介绍的方法和技术应用于语义分析和中间代码产生中。 主要学习内容：中间语言的形式——后缀式、图表示法、三地址代码，说明语句的语义分析，赋值语句的翻译，布尔表达式的翻译，控制语句的翻译，过程调用的处理，类型检查。 学习目标：熟悉几种中间语言的描述，掌握各种语句的翻译方法，会给出各种语句的语义规则和语义子程序。 学习重点和难点：如何把属性文法和语法制导翻译的方法和技术应用于语义分析和中间代码产生中，特别是表达式和控制语句的翻译。 7.1 中间语言 7.1.1 中间语言 虽然源程序可以直接翻译为目标语言代码。但是许多编译程序都采用了独立于机器的、复杂性介于源语言和机器语言之间的中间语言。常见的中间语言形式包括：后缀式，三地址代码（包括三元式，四元式，间接三元式），DAG图表示和抽象语法树等。 1. 后缀式 后缀式表示法是波兰逻辑学家卢卡西维奇（Lukasiewicz）发明的一种表示表达式的方法，因此又称逆波兰表示法。这种表示法是，把运算量（操作数）写在前面，把算符写在后面（后缀）。例如，把a+b写成ab+，把a*b写成ab*。 2. 抽象语法树 在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。这种经变换后的语法树称之为抽象语法树（Abstract Syntax Tree）。 3. DAG 与抽象语法树一样，对表达式中的每个子表达式，DAG（Directed Acyclic Graph）中都有一个结点。一个内部结点代表一个操作符，它的孩子代表操作数。两者不同的是，在一个DAG 中代表公共子表达式的结点具有多个父结点，而在一棵抽象语法树中公共子表达式被表示为重复的子树。 4. 三地址代码 三地址代码是由下面一般形式的语句构成的序列：

编译原理课程设计报告

2011-2012学年第二学期 《编译原理》课程设计报告 学院：计算机科学与工程学院 班级： 学生姓名：学号： 成绩： 指导教师： 时间：2012年5 月

目录 一、课程设计的目的 ---------------------------------------------------------------- - 1 - 二、课堂实验及课程设计的内容 -------------------------------------------------- - 1 - 2.1、课堂实验内容-------------------------------------------------------------- - 1 - 2.2、课程设计内容-------------------------------------------------------------- - 1 - 三、visual studio 2008 简介------------------------------------------------------- - 2 - 四、问题分析及相关原理介绍 ----------------------------------------------------- - 3 - 4.1、实验部分问题分析及相关原理介绍 ---------------------------------- - 3 - 4.1.1、词法分析功能介绍及分析------------------------------------- - 3 - 4.1.2、语法分析功能介绍及分析------------------------------------- - 3 - 4.1.3、语义分析功能介绍及分析------------------------------------- - 4 - 4.2、课程设计部分问题分析及相关原理介绍 ---------------------------- - 5 - 4.2.1、编译程序介绍 ----------------------------------------------------- - 5 - 4.2.2、对所写编译程序的源语言的描述（C语言） -------------- - 6 - 4.2.3、各部分的功能介绍及分析 -------------------------------------- - 7 - 4.3、关键算法：单词的识别-------------------------------------------------- - 8 - 4.3.1、算法思想介绍 ----------------------------------------------------- - 8 - 4.3.2、算法功能及分析 -------------------------------------------------- - 8 - 五、设计思路及关键问题的解决方法 ------------------------------------------ - 10 - 5.1、编译系统------------------------------------------------------------------ - 10 - 5.1.1、设计思路 --------------------------------------------------------- - 10 - 5.2、词法分析器总控算法--------------------------------------------------- - 12 - 5.2.1、设计思路 --------------------------------------------------------- - 12 - 5.2.2、关键问题及其解决方法 --------------------------------------- - 13 - 六、结果及测试分析-------------------------------------------------------------- - 14 - 6.1、软件运行环境及限制--------------------------------------------------- - 14 - 6.2、测试数据说明------------------------------------------------------------ - 14 - 6.3、运行结果及功能说明--------------------------------------------------- - 16 - 6.4、测试及分析说明--------------------------------------------------------- - 16 - 七、总结及心得体会 --------------------------------------------------------------- - 17 - 7.1、设计过程------------------------------------------------------------------ - 17 - 7.2、困难与收获 ------------------------------------------------------------- - 17 - 八、参考文献 ------------------------------------------------------------------------ - 18 -

编译原理知识点汇总

编译原理的复习提纲 1.编译原理=形式语言+编译技术 2.汇编程序： 把汇编语言程序翻译成等价的机器语言程序 3.编译程序： 把高级语言程序翻译成等价的低级语言程序 4.解释执行方式： 解释程序，逐个语句地模拟执行 翻译执行方式： 翻译程序，把程序设计语言程序翻译成等价的目标程序 5.计算机程序的编译过程类似，一般分为五个阶段： 词法分析、语法分析、语义分析及中间代码生成、代码优化、目标代码生成 词法分析的任务： 扫描源程序的字符串，识别出的最小的语法单位（标识符或无正负号数等） 语法分析是： 在词法分析的基础上的，语法分析不考虑语义。语法分析读入词法分析程序识别出的符号，根据给定的语法规则，识别出各个语法结构。 语义分析的任务是检查程序语义的正确性，解释程序结构的含义，语义分析包括检查变量是否有定义，变量在使用前是否具有值，数值是否溢出等。

语法分析完成之后，编译程序通常就依据语言的语义规则，利用语法制导技术把源程序翻译成某种中间代码。所谓中间代码是一种定义明确、便于处理、独立于计算机硬件的记号系统，可以认为是一种抽象机的程序 代码优化的主要任务是对前一阶段产生的中间代码进行等价变换，以便产生速度快、空间小的目标代码 编译的最后一个阶段是目标代码生成，其主要任务是把中间代码翻译成特定的机器指令或汇编程序 编译程序结构包括五个基本功能模块和两个辅助模块 6.编译划分成前端和后端。 编译前端的工作包括词法分析、语法分析、语义分析。编译前端只依赖于源程序，独立于目标计算机。前端进行分析 编译后端的工作主要是目标代码的生成和优化后端进行综合。独立于源程序，完全依赖于目标机器和中间代码。 把编译程序分为前端和后端的优点是： 可以优化配置不同的编译程序组合，实现编译重用，保持语言与机器的独立性。 7.汇编器把汇编语言代码翻译成一个特定的机器指令序列 第二章 1.符号，字母表，符号串，符号串的长度计算P18，子符号串的含义，符号串的简单运算XY，Xn， 2.符号串集合的概念，符号串集合的乘积运算，方幂运算，闭包与正闭包的概念P19，P20A0 ={ε} 3.重写规则，简称规则。非xx（V

北邮大三上-编译原理-语义分析实验报告

编译原理第六章语义分析 班级：09211311 学号： 姓名：schnee

目录 1. 实验题目和要求 (3) 2. 实验分析和思考 (3) 3. 翻译方案 (4) 4. LR实现自底向上分析（摘自语法分析实验） (5) 4.1.构造识别所有活前缀的DFA (5) 4.2.构造LR分析表 (6) 5. S属性定义的自底向上实现 (7) 5.1.扩充分析栈 (7) 5.2.改造分析程序 (7) 5.3.编程实现 (7) 6. 运行结果截图： (13)

1. 实验题目和要求 题目：语义分析程序的设计与实现。 实验内容：编写语义分析程序，实现对算术表达式的类型检查和求值。要求所分析算术表达式由如下的文法产生。 num E id F F F T F T T T T E T E E |)(||/|*||→→-+→ 实验要求：用自底向上的语法制导翻译技术实现对表达式的分析和翻译。 (1) 写出满足要求的语法制导定义或翻译方案。 (2) 编写分析程序，实现对表达式的类型进行检查和求值，并输出： ① 分析过程中所有产生式。 ② 识别出的表达式的类型。 ③ 识别出的表达式的值。 (3) 实验方法：可以选用以下两种方法之一。 ① 自己编写分析程序。 ② 利用YACC 自动生成工具。 2. 实验分析和思考 由于要求进行类型检查和求值，所以可以定义两个综合属性，一个记录值一个记录类型，存放在结构中，一并传入传出。 输出的产生式可以作为虚拟综合属性，在产生式的最后打印出来。 id 认为是定义的变量名，假设是26个小写字母，它们的值存于一个数组里。 将类型检查和求值归于一次扫描，当检查类型出错时则停止，否则继续。 哈希实现输入的映射，模拟词法分析的记号流。 输入格式为每个num 和id 对应两个输入字符，其他运算符仍对应一个字符。比如第4个num,输入为num4。 由于只具有综合属性，故可以用S 属性的自底向上翻译实现，利用LR 分析程序来实现，只需扩充分析站和改造分析程序。 PS:这次实验我只是简单模拟了最简单的显式严格匹配，即没有实现隐式类型转换。

编译原理课程设计(词法分析,语法分析,语义分析,代码生成)

编译原理课程设计(词法分析，语法分析，语义分析，代码 生成） #include #include #include #include #include #include using namespace std; /************************************************/ struct token// token { int code;// int num;// token *next; }; token *token_head,*token_tail;//token struct str// string { int num;// string word;// str *next; }; str *string_head,*string_tail;//string struct ivan// {

char left;// string right;// int len;// }; ivan css[20];// 20 struct pank// action { char sr;// int state;// }; pank action[46][18];//action int go_to[46][11];// go_to struct ike// { ike *pre; int num;// int word;// ike *next; }; ike *stack_head,*stack_tail;// struct L// { int k; string op;// string op1;// string op2;// string result;// L *next;// L *Ltrue;//true L *Lfalse;//false };

现代汉语语法的五种分析方法

现代汉语语法的五种分析方法

现代汉语语法的五种分析方法 很有用，请好好学习之。 北语之声论坛专业精华转贴 现代汉语语法的五种分析方法是语法学基础里 很重要的一个内容,老师上课也会讲到,我在这 里把最简略的内容写在下面，希望能对本科生的专业课学习有所帮助 详细阐释中心词分析法、层次分析、变换分析法、语义特征分析法和语义指向分析的具体内涵：一. 中心词分析法： 分析要点： 1．分析的对象是单句； 2．认为句子又六大成分组成——主语、谓语（或述语）、宾语、补足语、形容词附加语（即定语）和副词性附加语（即状语和补语）。 这六种成分分为三个级别：主语、谓语（或述语）是主要成分，宾语、补足语是连 带成分，形容词附加语和副词性附加语是附加成分； 3．作为句子成分的只能是词； 4．分析时，先找出全句的中心词作为主语和谓

语，让其他成分分别依附于它们； 5．分析步骤是，先分清句子的主要成分，再决定有无连带成分，最后指出附加成分。 标记： 一般用║来分隔主语部分和谓语部分，用══标注主语，用——标注谓语，用~~~~~~标注宾语，用（）标注定语，用[ ]标注状语，用< >标注补语。 作用： 因其清晰明了得显示了句子的主干，可以一下子把握住一个句子的脉络，适合于中小学语文教学，对于推动汉语教学语法的发展作出了很大贡献。 还可以分化一些歧义句式。比如：我们五个人一组。 （1）我们║五个人一组。（2）我们五个人║一组。 总结：中心词分析法可以分化一些由于某些词或词组在句子中可以做不同的句子成分而造成的歧义关系。 局限性： 1．在一个层面上分析句子，

层次性不强； 2．对于一些否定句和带有修饰成分的句子，往往难以划分； 如：我们不走。≠我们走。 封建思想必须清除。≠思想清除。 3. 一些由于句子的层次关系 不同而造成的歧义句子无法分析； 如：照片放大了一点儿。咬死了猎人的狗。 二. 层次分析： 含义： 在分析一个句子或句法结构时，将句法构造的层次性考虑进来，并按其构造层次逐层进行分析，在分析时，指出每一层面的直接组成成分，这种分析就叫层次分析。 朱德熙先生认为，层次分析不能简单地将其看作是一种分析方法，而是应当看做一种分析原则，是必须遵守的。（可以说说为什么） 层次分析实际包含两部分内容：一是切分，一是定性。切分，是解决一个结构的直接组成成分到底是哪些；而定性，是解决切分所得的直接组成成分之间在句法上是什么关系。

编译原理课程设计(词法分析,语法分析,语义分析,代码生成)

#include #include #include #include #include #include using namespace std; /*********************下面是一些重要数据结构的声明***************************/ struct token//词法token结构体 { int code;//编码 int num;//递增编号 token *next; }; token *token_head,*token_tail;//token队列 struct str//词法string结构体 { int num;//编号 string word;//字符串内容 str *next; }; str *string_head,*string_tail;//string队列 struct ivan//语法产生式结构体 { char left;//产生式的左部 string right;//产生式的右部 int len;//产生式右部的长度 }; ivan css[20];//语法20个产生式 struct pank//语法action表结构体 { char sr;//移进或归约 int state;//转到的状态编号 }; pank action[46][18];//action表 int go_to[46][11];//语法go_to表 struct ike//语法分析栈结构体，双链 { ike *pre; int num;//状态 int word;//符号编码 ike *next;

编译原理实验三-自下而上语法分析及语义分析.docx

上海电力学院 编译原理 课程实验报告 实验名称：实验三自下而上语法分析及语义分析 院系：计算机科学和技术学院 专业年级： 学生姓名：学号： 指导老师： 实验日期： 实验三自上而下的语法分析 一、实验目的： 通过本实验掌握LR分析器的构造过程，并根据语法制导翻译，掌握属性文法的自下而上计算的过程。 二、实验学时： 4学时。 三、实验内容

根据给出的简单表达式的语法构成规则（见五），编制LR分析程序，要求能对用给定的语法规则书写的源程序进行语法分析和语义分析。 对于正确的表达式，给出表达式的值。 对于错误的表达式，给出出错位置。 四、实验方法 采用LR分析法。 首先给出S-属性文法的定义（为简便起见，每个文法符号只设置一个综合属性，即该文法符号所代表的表达式的值。属性文法的定义可参照书137页表6.1），并将其改造成用LR分析实现时的语义分析动作（可参照书145页表6.5）。 接下来给出LR分析表。 然后程序的具体实现： ● LR分析表可用二维数组（或其他）实现。 ●添加一个val栈作为语义分析实现的工具。 ●编写总控程序，实现语法分析和语义分析的过程。 注：对于整数的识别可以借助实验1。 五、文法定义 简单的表达式文法如下： (1)E->E+T (2)E->E-T (3)E->T

(4)T->T*F (5)T->T/F (6)T->F (7)F->(E) (8)F->i 状态ACTION（动作）GOTO（转换） i + - * / ( ) # E T F 0 S5 S4 1 2 3 1 S6 S1 2 acc 2 R 3 R3 S7 S13 R3 R3 3 R6 R6 R6 R6 R6 R6 4 S 5 S4 8 2 3 5 R8 R8 R8 R8 R8 R8 6 S5 S4 9 3 7 S5 S4 10 8 S6 R12 S11 9 R1 R1 S7 S13 R1 R1 10 R4 R4 R4 R4 R4 R4 11 R7 R7 R7 R7 R7 R7 12 S5 S4 14 3 13 S5 S4 15 14 R2 R2 S7 S13 R2 R2 15 R5 R5 R5 R5 R5 R5 五、处理程序例和处理结果例 示例1：20133191*(20133191+3191)+ 3191#

编译原理--词法分析,语法分析,语义分析(C语言)

词法分析 #include #include #include using namespace std; #define MAXN 20000 int syn,p,sum,kk,m,n,row; double dsum,pos; char index[800],len;//记录指数形式的浮点数 char r[6][10]={"function","if","then","while","do","endfunc"}; char token[MAXN],s[MAXN]; char ch; bool is_letter(char c) { return c>='a' && c<='z' || c>='A' && c<='Z'; } bool is_digtial(char c) { return c>='0' && c<='9'; } bool is_dot(char c) { return c==',' || c==';'; } void identifier()//标示符的判断 { m=0; while(ch>='a' && ch<='z' || ch>='0' && ch<='9') { token[m++]=ch; ch=s[++p]; } token[m]='\0';

ch=s[--p]; syn=10; for(n=0;n<6;n++) if(strcmp(token,r[n])==0) { syn=n+1; break; } } void digit(bool positive)//数字的判断{ len=sum=0; ch=s[p]; while(ch>='0' && ch<='9') { sum=sum*10+ch-'0'; ch=s[++p]; } if(ch=='.') { dsum=sum; ch=s[++p]; pos=0.1; while(ch>='0' && ch<='9') { dsum=dsum+(ch-'0')*pos; pos=pos*0.1; ch=s[++p]; } if(ch=='e') { index[len++]=ch; ch=s[++p]; if(ch=='-' || ch=='+') { index[len++]=ch; ch=s[++p]; } if(!(ch>='0' && ch<='9')) { syn=-1; } else

义素分析法分析“看的方式”语义场

义素分析法分析“看的方式”语义场 摘要：“看的方式”的语义场可以归为同义语义场。通过义素分析的方法，并写出 每个词的基本义的义素表达式，来分析该语义场内的词之间的异同。词不仅有理 性意义还有感性意义，通过感性意义能更好的区别和运用同义词。 关键字：义素分析法，同义词辨析，看的方式 一、义素分析法在同义词辨析中的运用 同义词辨析一直以来都是语言研究的重要方面，不仅是在语言研究，还是在 语言运用中，甚至在语言的教学中都具有特殊的意义。义素分析法是准确描写和 掌握词义的有效方法。词义并不是一个整体，而是有若干层次的结构，义素是构 成词义的最小意义单位。将义素分析法引入对外汉语词汇教学，可以对词义的微 观层面进行准确有效的分析，把词义分割成若干个义素的组合，不仅有利于准确 掌握同义词之间的大同小异，还能提高人们对语言的运用能力，有利于第二语言 学习者在语言学习中理解两个及两个以上抽象的同义词，加深对汉语词汇的理解 和运用。 本文主要通过义素分析法来分析比较“看的方式”的语义场，来说明义素分析 法在同义词比较中的运用。运用义素分析法的表达式来研究“看的意义相同或相近的词”。本文研究的看的方式词有：看、望、顾、瞪、瞥、瞅、盯、窥、伺、瞟、瞰。 二、“看的方式”的语义场义素分析的方法和步骤 1.确立语义场 语义场是通过不同词之间的对比，根据它们词义的共同特点或关系划分出来 的类。同义语义场相当于一些论著中讲的一组广义的同义词（即不包括等义词），它所包括的各个义位间大同小异。所谓的同，表现为基本义相同或者是基本义有 一部分相同。所谓的异，就是附加义不同，或者是基本义有一部分不同，又或是 不只是基本义有一部分不同附加义也不一样。“看的方式”语义场内的词是眼部动 作描写都有“用眼睛看”这一基本义项，因此，这些看的方式词都可以看作是“看” 这个词的同义词。那么“看的方式”就构成了一个眼部动作的同义语义场。根据义 素分析法的分析并通过表达式的比较，可以准确的辨析出同义语义场内各个词之 间的细微区别，有利于第二语言的学习。 2.通过义素的具体对比分析“看的方式：看、望、顾、瞪、瞥、瞅、盯、窥、伺、瞟、瞰”的异同。 这些字从现代汉语词典第七版中查到“看的方式”词的意义如下所示： (1)看： [动] 使视线接触人或物：~书|~电影|~了他一眼。 [动] 观察并加以判断：我~他是个可靠的人l你~这个办法好不好。 [动] 取决于；决定于：这件事能 不能成功全~你了|飞机能否准时起飞，要~天气如何。 [动] 访问；探望：~望|~朋友。 [动] 对待：~待|另眼相~|别拿我当外人~。 [动] 诊治：王大夫把我的病~好了。照料：照~l衣帽自~。 [动] 用在表示动作或变化的词或词组前面，表示预见到某 种变化趋势，或者提醒对方注意可能发生或将要发生的某种不好的事情或情况： 行情~涨|别跑！~摔着！|~饭快凉了，快吃吧。 [助] 用在动词或动词结构后面， 表示试一试（前面的动词常用重叠式）：想想~I找找~|等一等~l评评理~先做几 天~。 (2)望： [动] 向远处看：登山远~|一~无际的稻田。观看；察看：~风！观~|~ 闻问切。探望：拜~|看~。盼望；希望①：~子成龙l~准时到会。盼头；希望②：

北邮 编译原理 语义分析实验报告

编译原理 第六章语义分析 目录 1. 实验题目和要求 (2) 2. 实验分析和思考 (3) 3. 翻译方案 (4) 4. LR实现自底向上分析（摘自语法分析实验） (5) 4.1.构造识别所有活前缀的DFA (5)

5.1. 扩充分析栈 ................................................................................................................ 7 5.2. 改造分析程序 ............................................................................................................ 7 5.3. 编程实现 .................................................................................................................... 7 6. 运行结果截图： (13) 1. 实验题目和要求 题目：语义分析程序的设计与实现。 实验内容：编写语义分析程序，实现对算术表达式的类型检查和求值。要求所分析算术表达式由如下的文法产生。 num E id F F F T F T T T T E T E E |)(||/|*||→→-+→ 实验要求：用自底向上的语法制导翻译技术实现对表达式的分析和翻译。 (1) 写出满足要求的语法制导定义或翻译方案。 (2) 编写分析程序，实现对表达式的类型进行检查和求值，并输出： ① 分析过程中所有产生式。 ② 识别出的表达式的类型。 ③ 识别出的表达式的值。 (3) 实验方法：可以选用以下两种方法之一。 ① 自己编写分析程序。 ② 利用YACC 自动生成工具。

语义分析

三、词法、语法、语义分析结合 一、实验目的与要求 在实现词法、语法分析程序的基础上，编写相应的语义子程序，进行语义处理，加深对语法制导翻译原理的理解，进一步掌握将语法分析所识别的语法范畴变换为某种中间代码（四元式）的语义分析方法，并完成相关语义分析器的代码开发。 二、实验内容 语法制导翻译模式是在语法分析的基础上，增加语义操作来实现的。对于给定文法中的每一产生式，编写相应的语义子程序。在语法分析过程中，每当用一个产生式进行推导或归约时，语法分析程序除执行相应的语法分析动作之外，还要调用相应的语义子程序，以便完成生成中间代码、查填有关表格、检查并报告源程序中的语义错误等工作。每个语义子程序需指明相应产生式中各个符号的具体含义，并规定使用该产生式进行分析时所应采取的语义动作。这样，语法制导翻译程序在对源程序从左到右进行的一遍扫描中，既完成语法分析任务，又完成语义分析和中间代码生成方面的工作。 输入：包含测试用例，如由无符号数和+、?、*、/、(、)构成的算术表达式的源程序文件。 输出：将源程序转换为中间代码形式表示，并将中间代码序列输出到文件中。若源程序中有错误，应指出错误信息。 三、实验设计 语法制导翻译模式实际上是对前后文无关文法的一种扩展。一般而言，首先需要根据进行的语义工作，完成对文法的必要拆分和语义动作的编写，从而为每个产生式都配备相应的语义子程序，以便在进行语法分析的同时进行语义解释。要求从编译器的整体设计出发，重点通过对实验二中语法分析程序的扩展，完成一个编译器前端程序的编写、调试和测试工作，形成一个将源程序翻译为中间代码序列的编译系统。 对文法G3[<算术表达式>]中的产生式添加语义处理子程序，完成无符号数的四则运算的计值处理，将输入的四则运算转换为四元式形式的中间代码。本实验只进行了算术表达式四元式的翻译。 四、源代码 1、在.h文件中添加了 //语义分析部分 #define PMAX 5//define 后面不加括号，定义产生式符号属性字符串的长度 int NXQ=0; /*全局变量NXQ用于指示所要产生的下一个四元式的编号*/ int NXTemp=1;//整型变量NXTemp指示临时变量的编号 int SentenceCount=1;//存放文件中句子的个数 struct QUATERNION /*四元式表的结构*/ { char op[PMAX]; /*操作符*/ char arg1[PMAX]; /*第一个操作数*/ char arg2[PMAX]; /*第二个操作数*/ char result[PMAX]; /*运算结果*/ }pQuad[256]; /*存放四元式的数组*/ char EBracket_Place[PMAX];//(E)的语义属性

《编译原理》总复习-07级

《编译原理》总复习-07级 第一章编译程序的概述 （一）内容 本章介绍编译程序在计算机科学中的地位和作用，介绍编译技术的发展历史，讲解编译程序、解释程序的基本概念，概述编译过程，介绍编译程序的逻辑结构和编译程序的组织形式等。 （二）本章重点 编译（程序），解释（程序），编译程序的逻辑结构。 （三）本章难点 编译程序的生成。 （四）本章考点 全部基本概念。 编译程序的逻辑结构。 （五）学习指导 引论部分主要是解释什么是编译程序以及编译的总体过程。因此学习时要对以下几个点进行重点学习：翻译、编译、目标语言和源语言这几个概念的理解；编译的总体过程：词法分析，语法分析、语义分析与中间代码的生成、代码优化、目标代码的生成，以及伴随着整个过程的表格管理与出错处理。 第三章文法和语言课外训练 （一）内容 本章是编译原理课程的理论基础，主要介绍与课程相关的形式语言的基本概念，包括符号串的基本概念和术语、文法和语言的形式定义、推导与归约、句子和句型、语法分析树和二义性文法等定义、文法和语言的Chomsky分类。 （二）本章重点 上下文无关文法，推导，句子和句型，文法生成的语言，语法分析树和二义性文法。（三）本章难点 上下文无关文法，语法分析树，文法的分类。 （四）本章考点 上下文无关文法的定义。 符号串的推导。 语法分析树的构造。 （五）学习指导 要构造编译程序，就要把源语言用某种方式进行定义和描述。学习高级语言的语法描述是学习编译原理的基础。上下文无关文法及语法树是本章学习的重点。语法与语义的概念；程序的在逻辑上的层次结构；文法的定义，文法是一个四元组：终结符号集，非终结符号集，开始符号、产生式集；与文法相关的概念，字符，正则闭包，积（连接），或，空集，产生式，推导，直接推导，句子，句型，语言，最左推导，最右推导（规范推导）；学会用文法来描述语言及通过文法能分析该文法所描述的语言；语法树及二义性的概念、能通过画语法树来分析一个文法描述的语言是否具有二义性；上下文无关文法的定义和正规文法的定义，能判断一个语言的文法是哪一类文法。 附训练试题：

编译原理实验报告-语义分析

编译原理课程实验报告实验3：语义分析

图2-1 本程序根据之前两个实验的结果进一步进行语义分析，主要是通过在第二个实验句法分析过程中添加语义分析功能完成的。 在代码编写之前，我将程序的功能模块分为界面及主控程序，实体类和工具类三大部分。 MyCompiler是整个程序运行的入口，是主控程序；ComplierFrame完成程序的界面，以及界面里事件的响应；Token是词法分析中词法单元的实体类；ErrorToken是错误的词法单元实体类；Symbol是句法分析中符号的实体类；Production是产生式的实体类；ErrorProduction是句法分析中产生错误的时候使用的产生式实体类；Id是标示符实体类，保存了语义分析后的标识符表；Node是语法分析树的节点类，帮助完成语法分析树的构造；LL类使用LL(1)分析法完成句法分析，同时完成语义分析；MyScanner完成了词法分析。

图2-2 得分 三、详细设计及实现 要求：对如下工作进行展开描述 (1)核心数据结构的设计 本程序使用了两个新的实体类，分别是Id和Node。 Id是标识符，里面也包含了该标识符在本程序中存储的地址和长度等信息。Id的属性如下： private String name; //名 private String type;//基本类型 private int offset;//起始地址 private int length;//长度

开始 输入 词法分析 读入Token 尝试匹配 是否错误存储错误记录，处理栈顶与Token 序列 是否为语义符号 存储产生式，处理栈顶与Token 序列 判断动作符号执行语义动作 是否读到Token 末尾 打印结果 结束

编译原理第二版课后习答案

《编译原理》课后习题答案第一章 第 1 章引论 第 1 题 解释下列术语： （1）编译程序 （2）源程序 （3）目标程序 （4）编译程序的前端 （5）后端 （6）遍 答案： （1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。 （2）源程序：源语言编写的程序称为源程序。 （3）目标程序：目标语言书写的程序称为目标程序。 （4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。 （5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。 （6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 第 2 题 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程 序的总体结构图。 答案： 一个典型的编译程序通常包含 8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机表达形式。 语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。 语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。 中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式 的中间语言代码，如三元式或四元式。 中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。 目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。 表格管理程序：负责建立、填写和查找等一系列表格工作。表格的作用是记录源程序的 各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。可以说整个编译过程就是造表、查表的工作过程。需要指出的是，这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块，而是指编译程序具有的表格管理功能。 错误处理程序：处理和校正源程序中存在的词法、语法和语义错误。当编译程序发现源

编译原理实验报告(词法分析器语法分析器)

编译原理实验报告

实验一 一、实验名称：词法分析器的设计 二、实验目的：1，词法分析器能够识别简单语言的单词符号 2，识别出并输出简单语言的基本字.标示符.无符号整数.运算符.和界符。 三、实验要求：给出一个简单语言单词符号的种别编码词法分析器 四、实验原理： 1、词法分析程序的算法思想 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 2、程序流程图 （1 （2）扫描子程序

3

五、实验内容： 1、实验分析 编写程序时，先定义几个全局变量a[]、token[]（均为字符串数组),c,s( char型)，i,j,k（int型），a[]用来存放输入的字符串，token[]另一个则用来帮助识别单词符号，s用来表示正在分析的字符。字符串输入之后，逐个分析输入字符，判断其是否‘#’，若是表示字符串输入分析完毕，结束分析程序，若否则通过int digit(char c)、int letter(char c)判断其是数字，字符还是算术符,分别为用以判断数字或字符的情况，算术符的判断可以在switch语句中进行，还要通过函数int lookup(char token[])来判断标识符和保留字。 2 实验词法分析器源程序： #include #include #include int i,j,k; char c,s,a[20],token[20]={'0'}; int letter(char s){ if((s>=97)&&(s<=122)) return(1); else return(0); } int digit(char s){ if((s>=48)&&(s<=57)) return(1); else return(0); } void get(){ s=a[i]; i=i+1; } void retract(){ i=i-1; } int lookup(char token[20]){ if(strcmp(token,"while")==0) return(1); else if(strcmp(token,"if")==0) return(2); else if(strcmp(token,"else")==0) return(3); else if(strcmp(token,"switch")==0) return(4); else if(strcmp(token,"case")==0) return(5); else return(0); } void main() { printf("please input string :\n"); i=0; do{i=i+1; scanf("%c",&a[i]);