编译实验指导书文档格式.docx

编译实验指导书文档格式.docx

《编译实验指导书文档格式.docx》由会员分享，可在线阅读，更多相关《编译实验指导书文档格式.docx（14页珍藏版）》请在冰点文库上搜索。

词法分析阶段对源程序进行自左而右的扫描，将其从外部形式（字符串）变换成便于后几个阶段处理的内部形式，即分解出一个个有独立语法意义的单位（单词或符号），同时识别出与其相关的属性。

（1）目的：

通过设计、编制、调试一个具体的词法分析程序，加深对词

法分析原理的理解，并掌握在对程序设计语言源程序进行扫描过程

中将其分解为各类单词的词法分析方法。

（2）要求：

选择某种程序设计语言（如：

C++、C、PASCAL等）的源程序作为词法分析对象；

从所选语言中选取一个适当大小的子集，可以选取一类典型单词，也可以尽可能使各种类型的单词兼顾到，编写一个规模适当的词法分析程序。

（调试例子应有词法正确的，也有错误的或超出设计要求的字符串。

）

词法分析流程图

读无符号数的程序流程图

实验二、逆波兰式生成程序

内容：

掌握语法分析的基本思想，并用高级语言编写逆波兰式生成程序（6学时）

要求：

利用逆波兰式生成算法编写程序，将从键盘上输入的算术表达式（中缀表达式）转化成逆波兰式。

逆波兰表达式的生成过程涉及到运算符的优先级，下表中列出几个常用运算符的优先关系。

+

-

*

/

↑

（

＞

＜

＝

常用运算符优先关系矩阵

如上表所示的优先关系矩阵表示了+，-，*，/，↑，（，）等七种运算符之间的相互优先关系。

“＞、＜、＝”三种符号分别代表“大于”、“小于”、“相等”三种优先关系。

左边的“＝”与右边的“（”之间没有优先关系存在，所以表中为空白。

逆波兰表达式生成算法的关键在于比较当前运算符与栈顶运算符的优先关系，若当前运算符的优先级高于栈顶运算符，则当前运算符入栈，若当前运算符的优先级低于栈顶运算符，则栈顶运算符退栈。

下面给出了逆波兰表达式生成算法的流程图。

（为了便于比较相邻运算符的优

先级，需要设立一个工作栈，用来存放暂时不能处理的运算符，所以又称运算符栈）。

实验三、语法分析程序的设计

语法分析阶段根据程序语言的语法规则，对词法分析产生的单词序列进行语法检查。

凡不合语法者，尽可能多和确切地指出错误（包括出错位置、原因和性质），否则，变换成各类语法范畴。

通过设计、编制、调试一个典型的语法分析程序，实现对词

法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌

握常用的语法分析方法。

选择具有代表性的语法分析方法，如：

LL（K）分析法、递归子程序法、运算符优先数法、LR（K）分析法等方法之一进行设计；

选择对各种常见程序语言都通用的语法结构，如赋值语句（尤指表达式）作为分析对象，并与所选语法分析方法要比较贴切；

先写出BNF定义，如：

〈赋值语句〉:

:

=〈变量〉=〈表达式〉

〈表达式〉:

=〈项〉│〈表达式〉+〈项〉│〈表达式〉-〈项〉

〈项〉:

=〈因子〉│〈项〉*〈因子〉│〈项〉/〈因子〉

〈因子〉:

=〈初等量〉│〈因子〉↑〈初等量〉

〈初等量〉:

=（〈表达式〉）│i

然后编写语法分析程序；

调试：

调试例子应包括符合语法规则的算术表达式，以及分析程序能够判别的若干错例。

1LL

（1）语法分析方法

LL

（1）分析器的逻辑结构

构造LL

（1）分析表的算法如下:

1）对于A:

=Dβ（D∈VN）且select（A:

=Dβ）={b1,b2…bn}

则M[A,bi]=RE（Dβ）/R

表示:

用Dβ的逆替换A,重读当前字符.

2）对于A:

=aβ（a∈VT）

则M[A,a]=RE（β）/C

用β的逆替换A,继续读入下一字符.

3）对于A:

=ε且select（A:

=ε）={b1,b2…bn}

则M[A,bi]=RE（ε）/R=ε/R

4）对所有没出现在规则右部的首部的终结符a,

令M[a,a]=RE（ε）/C=ε/C

5）对于#,令M[#,#]=succ,表示分析成功,结束.

6）其他情况属于出错，在分析表中用空白表示.

2递归下降语法分析法

是一种确定的自顶向下分析法。

又称递归子程序分析法。

思想：

对文法中每个非终结符（代表语法成分）编写一个子程序（或递归过程），用来识别它所表示的语法范畴。

例：

赋值语句S→V:

=E

变量V→i|i（E）

表达式E→E+T|E-T|T

项T→T*F|T/F|F

因子F→F↑P|P

初等量P→（E）|i

消除左递归：

S→V:

V→i|i（E）

E→T{（+|-）T}

T→F{（*|/）F}

F→P{↑P}

P→（E）|i

赋值语句处理流程图:

变量处理流程图

表达式处理流程图

项处理流程图

因子处理流程图

初等量处理流程图

3运算符优先数法

表达式文法G[E]的优先关系矩阵

+

*

（

）

i

#

>

<

=

4SLR

（1）语法分析方法

LR（K）分析器的逻辑结构

表达式文法的SLR

（1）分析表

状态

ACTION

GOTO

#

E

T

F

S0

S5

S4

1

2

3

S1

S6

acc

S2

r2

S7

r2

S3

r4

r4

8

3

r6

r6

S4

9

10

S8

S11

S9

r1

S7

r1

S10

r3

r3

S11

r5

r5

三、基本要求：

学生可以从以上三个实验中选做两个。

学生应在实验课前仔细阅读实验相关内容，明确实验的目的和要求，然后了解词法分析和语法分析的基本方法，利用一种高级语言（如C语言、C++语言、PASCAL语言等），编写无符号数的词法分析程序、逆波兰式生成程序、语法分析程序（一种方法）。

调试程序后，打印程序代码及实验结果，写出实验报告。

四、考核

以学生的实验报告、实验内容和做实验的表现为考核依据。

五、参考资料

崔冬华冯秀芳《编译原理简明教程》电子工业出版社