1、实验任务二、实验介绍1、实验目的2、词法分析器的设计

一、实验任务二、实验介绍1、实验目的2、词法分析器的设计3、语法分析器的设计4、程序设计举例Tiny语言上机辅导一、实验任务1、实验流程：词法分析遍历并打印语法树TOKEN序列语法树语法分析源程序（（根据TINY文法所写2、任务分配每一小组由5－6人组成，具体任务分配如下：词法分析器部分由1－2个人完成，输入的根据TINY文法写的源程序，输出的是单词的TOKEN序列及单词具体属性值和所在行号，分别存放在数组中；语法分析部分由2－3人完成，从数组中输入TOKEN序列，进行语法分析，并在内存中构造出一颗语法树，输出的是指向这颗语法树的根结点的指针；语法树的遍历与打印由1个人完成，输入的是指向语法树的根结点指针，输出的是按一定格式缩排的语法树结构图；

最后写一个编译原理课程设计报告，总结一下实验过程中的体会。二、实验介绍1、实验目的通过实现小型编译器TINY，了解并掌握编译器设计过程和实现方法，从而进一步了解编译的一般原理，并提高自己的编程能力。2、词法分析器的设计•·

词法分析目的：词法分析主要是把源程序的字符串序列序列逐个拚出单词，转换成所谓的TOKEN序列，其中TOKEN是单词的内部表示。这样以字符为但单位的源程序就变成了以单词为单位的内部表示。此后的语法分析和语义分析的扫描对象是词法分析器产生的TOKEN序列。1)构造TINY语言的保留字表(共有8个)a、数据结构：define

maxReservered=8/*保留字的数*/static

struct{char

*str;tokentype

tok;}reservedWords[maxReservered]={{“if”,IF},{“thenTHEN},{“else”,ELSE},{“repeat”,REPEAT},{“until”,UNTIL},{“read”,READ},{“write”,WRITE},{“end”,END};b、T

I

N

Y对保留字的识别是通过首先将它们看作是标识符，之后再在保留字表中查找它们是否是保留字。查找保留字的函数设计如下：static

TokenType

reservedLookUp(char

*s){int

I;for

(i=0;i<maxReserved,i++)if

(!strcmp(s,reservedWords[I].str)return

reservedWords[I].tok;return

ID;////如果不在集合中则返回ID表示它是标识符；}2）构造标记集合每一个保留字（如read,write…）特殊符号（如+,-…）都有其对应的标记TOKEN的定义如下：Typedef

enum{/*保留字标记*/IF,THEN,ELSE,REPEAT,UNTIL,READ,WRITE,END,/*数字及标识符*/ID,NUM,/*特殊符号*/＋－

*

/

＝

：=

;

(

)

<ASSIGN,EQ,LT,PLUS,MINUS,TIMES,OVER,LPAREN,RPAREN,SEMI,/*文件结束标记，错误标记*/ENDFILE,ERROR}tokentype;记号ENDFILE（当达到文件的末尾时）和E

R

R

O

R（实际上，未列在特殊符号中的所有单个字符既不是空白格或注释，也不是数字或字母，它们应被作为错误而接受，我们将它们与单个字符符号混合在一起。）3)构造DFA状态集合、实现取词操作根据DFA可以构造出DFA状态集合，主要用来在程序中实现状态的转换typedef

enum{START,INASSIGN,INCOMMENT,INNUM,INID,DONE}statetype;DFA的实现可以使用下面的模State:=START;State=START;While

state<>DONE

do式：Case

state

of·Start

:

case

inputchar

of··letter；指针向前走一步，取下一个字符；state:=INID;INID

:

………………end;4)构造TOKEN的数据结构由于扫描程序必须计算每一个记号的若干属性，所以将所有的属性收集到一个单独构造的数据类型中是很有用的，这种数据类型称作记号记录（

tokenrecord）。可在C中将这样的记录说明为：typedef

struct{TokenType

tokenval;char

*

stringval;int

numval;}TokenRecord;或可能作为一个联合typedef

struct{TokenType

tokenval;u

n

i

o

n{char

*

stringval;int

numval;}

attribute;}

TokenRecord;·左边的假设只有标识符要串值属性，只有数字需要数值属性）。·对于扫描程序一个更普通的安排是只返回记号值并将变量的其他属性放在编译器的其他部分访问得到的地方。5)词法分析的扫描过程的实现扫描程序使用了2个全程变量：文件变量s

o

u

r

c

e整型变量l

i

n

e

n

o其中SOURCE是源代码；LINENO是标记在源代码中的行号；扫描程序的字符串输入由g

e

t

N

e

x

tline函数，该函数每次从source中每一次都获取了一个新的源代码行存入一个256-字符缓冲区l

i

n

eB

u

f中。指针currentRun指向当前读入字符的位置；扫描程序的单个字符输入由g

e

t

N

e

x

tchar函数完成，从缓冲区中返回当前指针所指地字符。词法分析SCAN中最主要的函数是g

e

t

T

o

k

e

n，它从缓冲区中读入字符并根据DFA返回下一个被识别的记号。记号本身被定义成枚举类型。其定义如下：tokentype

gettoken(void)/*返回下一个被识的记号*/

扫描程序还需总地计算出每个记号的特性（如果有的话），在T

I

N

Y扫描程序中，所要计算的唯一特性是词法或是被识别的记号的串值，它位于全局变量t

o

k

e

n

S

t

r

i

n

g之中。这个变量在ge

t

T

o

k

e

n函数中就得到，一同被返回，它们的定义是extern

char

tokenstring[maxtokenlen+1],maxtokeknlen是TOKEN的最大度。

由g

e

t

T

o

k

e

n过程还要完成的额外的工作如下：由子过程r

es

e

r

v

e

d

L

o

o

k

u

p完成位于由g

e

t

T

o

k

e

n识别的标识符之后的保留字的查找，c

u

r

r

e

n

t

T

o

k

e

n的值也随之改变，如果是保留字则赋予保留字标记，否则赋予标识符标记。。（currenttoken是当前标记的TOKEN值）3、语法分析器的设计1)语法分析目的：分析的任务是确定程序的语法，或称作结构，也正是这个原因，它又被称作语法分析（syntax

analysis）。按照它们构造分析树或语法树的方式，算法大致可分为两种：自顶向下分析（

top-down

parsing）和由底向上分析（bottom-up

parsing）程序计语言的语法通常是由上下文无关（

context-free

grammar）的文法规则（grammar

rule）给出，其方式同扫描程序识别的由正则表达式提供的记号的词法结构相类似。上下文无关文法的确利用了与正则表达式中极为类似的命名惯例和运算。二者的主要区别在于上下文无关文法的规则是递归的（

r

e

c

u

r

s

i

v

e）。2)分析过程分析程序的任务是从由扫描程序产生的记号中确定程序的语法结构，以及或隐式或显式地构造出表示该结构的语法树。因此，可将分析程序看作一个函数，该函数把由扫描程序生成的记号序列作为输入，并生成语法树作为它的输出：记号序列通过分析程序生成语法树。TOKEN序列通常不是显式输入参数，但是当分析过程需要下一个记号时，分析程序就调用诸如g

e

t

T

o

k

e

n的扫描程序过程获得。因此，编译器的分析步骤可减为对分析程序的一个调用，如下所示：syntaxTree

=

parse();3)TINY编译器的语法树结构a、现在需要将语法树结构的描述用图形表示出来在的子树由点线和三角形表示）。则该图如下：b、从TINY语言的文法可以看出T

I

N

Y有两种基本的结构类

型：语句和表达式。语句共有5类（i

f语句、r

e

p

e

a

t语句、a

s

s

in语句、r

e

a

d语句和w

r

i

t

e语句），表达式共有3类（算符表达式、常量表达式和标识符表达式）。因此，语法树节点首先按照它是语

句还是表达式来分类，接着根据语句或表达式的种类进行再次分类。树节点最大可有3个孩子的结构（仅在带有e

l

s

e部分的i

f语句中才需要它们）。必须将树节点中的属性保留如下（除了前面所提到过

的域之外）：每一种表达式节点都需要一个特殊的属性。常数节点

需要它所代表的整型常数的域；标识符节点应包括了标识符名称的

域；而算符节点则需要包括了算符名称的域。语句节点通常不需要

属性（除了它们的节点类型之外）。但为了简便起见，在a

s

s

i

g

n语句和r

e

a

d语句中，却要保留在语句节点本身中。还要记录l

i

n

en

o，它允许在转换的以后步骤中出现错误时能够打印源代码行数。C、一个T

I

N

Y语法树节点的C声明typedef

enum

{StmtK,ExpK}NodeKind;/*语法树结点是语句还是表达式；*/typedef

enum

{IfK,RepeatK,AssignK,ReadK,WriteK}Stmtkind;语句共有5类：i

f语句、r

e

p

e

a

t语句、a

s

s

i

g

n语句、r

e

a

d语句和w

r

i

t

e语句*/typedef

enum

{OpK,ConstK,IdK}ExpKind;/*表达式共有3类（算符表达式、常量表达式和标识符表达式）*/#define

MAXCHILEREN

3;/*树节点最大可有3个孩子的结构（仅在带有e

l

s

e部分的i

f语句中才需要它们）*/typedef

struct

treeNode{struct

treeNode

*

child[MAXCHILDREN];//孩子结点；struct

treeNode

*

sibling;//兄弟结点；int

lineno;//为了错误的处理，显示错误的行号NodeKind

nodekind;//结点的类型union

{StmtKind

stmt;Expkind

exp};//结点的类型；union

{TokenType

OP;/*算符节点需要包括了算符名称的域*/int

val;/*常数节点需要它所代表的整型常数的域；*/;char

*

name;/*标识符节点应包括了标识符名称的域*/;}attr;}TreeNode;这个分析程序很简单：主分析例程TreeNode

*

parse

(void)e，pa

r

s

e又返回一个指向由分析程序构造的语法树的指针。它由11个相互递归的过程组成，这些过程与的E

B

N

F文法直接对应。分析程序代码还包括了查找特殊记号的m

a

t

c

h过程，当它找

到匹配时就调用g

e

t

T

o

k

e

n取下一个单词，否则就声明出错；递归分析过程使用2种实用函数：n

e

w

S

t

m

t

N

o

d

e，它的输入参数语句种类（5种），生成一个语句结点，并且返回一个指向新分配的节点的指针。n

e

w

E

x

p

N

o

d

e，它的输入参数表达式种类（3种），生成一个表达式结点，并且返回一个指向新分配的节点的指针。还有一个通过打印节点信息的操作p

r

i

n

t

T

r

e

e过程；附：语法匹配子程序：static

void

match(TokenType

expected){if

(token==expected)

token=getToken();else{报错！}}分析子程序一个：TreeNode

*

stmt_sequence(void){TreeNode

*

t

=statement();//生成一条语句，由t指向语句的根结点；TreeNode*p=t;While

(token!=ENDFILE)do//如果有多条语句；{TreeNode

*

q;match(SEMI);//匹配分号；q=statement();q指向新生成的语句结点；if

q!=null{p->sibling:=q;p=q;}}return

t;}TreeNode

*

statement(void){

TreeNode

*

t=null;switch(token){case

IF

:t=if_stmt();

break;case

REPEAT

:

t:=repeat_stmt();break;case

IDcase

READ:

t=assign_stmt();break;:t=read_stmt();break;case