编译原理
实
验
指
导
书
作者：莫礼平
2011年3月
实验一简单词法分析程序设计
一、实验目的
了解词法分析程序的基本构造原理，掌握词法分析程序的手工构造方法。
二、实验内容
1、了解编译程序的词法分析过程。
2、根据PASCAL语言的说明语句形式，用手工方法构造一个对说明语句进行词法分析的程序。
该程序能对从键盘输入或从文件读入的形如：
“const count=10,sum=81.5,char1=’f’,string1=”hj”, max=169；”
的常量说明串进行处理，分析常量说明串中各常量名、常量类型及常量值，并统计各种类型常量个数。
三、实验要求
1、输入的常量说明串，要求最后以分号作结束标志；
2、根据输入串或读入的文本文件中第一个单词是否为“const”判断输入串或文本文件是否为常量说明内容；
3、识别输入串或打开的文本文件中的常量名。
常量名必须是标识符，定义为字母开头，后跟若干个字母，数字或下划线；
4、根据各常量名紧跟等号“=”后面的内容判断常量的类型。
其中：字符型常量定
义为放在单引号内的一个字符；字符串常量定义为放在双引号内所有内容；整型常量定
义为带或不带+、- 号，不以0开头的若干数字的组合；实型常量定义为带或不带+、- 号，
不以0开头的若干数字加上小数点再后跟若干数字的组合；
5、统计并输出串或文件中包含的各种类型的常量个数；
6、以二元组(类型,值)的形式输出各常量的类型和值；
7、根据常量说明串置于高级语言源程序中时可能出现的错误情况，模仿高级语言编
译器对不同错误情况做出相应处理。
四、运行结果
1、输入如下正确的常量说明串：
const count=10,sum=81.5,char1=‘f’,max=169,str1=“h*54 2..4S!AAsj”, char2=‘@’,str2=“aa!+h”；
输出：
count(integer,10)
sum(float,81.5)
char1(char, ‘f’)
max(integer,169)
str1(string,“h*54 2..4S!AAsj”)
char2(char, ‘@’)
str2(string,“aa!+h”)
int_num=2; char_num=2; string_num=2; float_num=1.
2、输入类似如下的保留字const错误的常量说明串：
Aconstt count=10,sum=81.5,char1=‘f’;
输出类似下面的错误提示信息：
It is not a constant declaration statement!
Please input a string again!
3、输入类似如下含常量名或常量值错误的常量说明串：
const count=10,12sum=81.5,char1=‘ff’,max=0016；
输出类似下面的错误提示信息：
count(integer,10)
12sum(Wrong! It is not a identifier!)
char1(Wrong! There are more than one char in ‘’.)
max(Wrong! The integer can’t be started with ‘0’.)
int_num=1; char_num=0; string_num=0; float_num=0.
4、其他类型的错误处理情况（略）。
五、提示
本实验重点有三个：一是作为常量名的标识符的识别；二是如何根据“=”后出现的内容来判断常量类型；三是对各种错误的处理。
难点是对整型和实型常量的判断必须综合考虑多种可能情况。
建议：1、用指针或数组与指针相结合来处理输入的常量说明串；2、对整型和实型常
量处理时，重点考虑常数中‘0’的位置。
六、分析与讨论
1、若考虑用E或e的科学计数法来表示整数和实数，应该如何实现？
2、若考虑布尔型常量，且规定其值只能为true或false，应该如何实现？
3、如何对手工构造的词法分析程序做进一步的优化，以提高代码质量和运行效率？
实验二基于预测方法的语法分析程序的设计
一、实验目的
了解预测分析器的基本构成及用自顶向下的预测法对表达式进行语法分析的方法，掌握预测语法分析程序的手工构造方法。
二、实验内容
1、了解编译程序的基于预测方法的语法分析过程。
2、根据预测分析原理设计一个基于预测方法的语法分析程序。
三、实验要求
对给定文法G[S]：
S->AT A->BU T->+AT|$ U->*BU|$ B->(S)|m
其中，$表示空串。
1、判断上述文法G[S]是否LL(1)文法，若不是，将其转变为LL(1)文法；
2、对转变后的LL(1)文法建立预测分析表；
3、根据清华大学出版编译原理教材教材第五章P94的图5.11手工构造预测分析程序；
4、用预测分析程序对任意给定的键盘输入串m+m*m#进行语法分析，并根据栈的变化状态输出给定串的具体分析过程。
四、运行结果
从任意给定的键盘输入串：
m+m*m#；
输出：
用预测分析法分析符号串m+m*m#的过程
Step Stack String Rule Step Stack String Rule
1 #S m+m*m# S->AT 10 #TUm m*m# M匹配
2 #TA m+m*m# A->BU 11 #TU *m# U->*BU
3 #TUB m+m*m# B->m 12 #TUB* *m# *匹配
4 #TUm m+m*m# M匹配13 #TUB m# B->m
5 #TU +m*m# U->$ 14 #TUm m# M匹配
6 #T +m*m# T->+AT 15 #TU # U->$
7 #TA+ +m*m# +匹配16 #T # T->$
8 #TA m*m# A->BU 17 # # 接受
9 #TUB m*m# B->m
五、提示
本实验重点有两个：一是如何用适当的数据结构实现预测分析表存储和使用；二是如何实现各规则右部串的逆序入栈处理。
建议：使用结构体数组。
六、分析与讨论
1、若输入串不是指定文法的句子，会出现什么情况？
2、总结预测语法分析程序的设计和实现的一般方法。
实验三基于算符优先法的语法分析程序的设计
一、实验目的
了解用算符优先分析法对表达式进行语法分析的方法，掌握算符优先语法分析程序的手工构造方法。
二、实验内容
1、了解编译程序的基于算符优先分析方法的语法分析过程。
2、根据算符优先分析原理设计一个算符优先语法分析程序。
三、实验要求
1、对下列简单表达式文法G[ E’]构造算符优先关系表。
E’→# E #
E → E + T | T
T → T * F | F
F → P / F ｜P
P → ( E )｜i
2、根据清华大学出版编译原理教材P117的图6.8手工构造算符优先语法分析程序。
3、用该算符优先语法分析程序对任意给定的键盘输入串i+i#进行语法分析，并根据栈的变化状态输出给定串的具体分析过程。
四、运行结果
从任意给定的键盘输入串：
i+i#
输出：
用算符优先语法分析程序分析串i+i#的过程
五、提示
本实验重点有两个：一是如何用适当的数据结构实现算符优先关系表的存储和使用；二是如何实现去掉了单非终结符之间的归约处理。
六、分析与讨论
1、若输入串不是指定文法的句子，会出现什么情况？
2、总结算符优先语法分析程序的设计和实现的一般方法。
实验四基于LR分析方法的语法分析程序的设计
一、实验目的
了解LR分析器的基本构成及用LR方法对表达式进行语法分析的方法，掌握LR分析程序的手工构造方法。
二、实验内容
1、了解编译程序的基于LR分析方法的语法分析过程。
2、根据LR(0)分析方法设计一个LR(0)语法分析程序。
三、实验要求
1、已知文法G[S']:
S'→E[0] E→aA[1] E→bB[2]A→cA[3]
A→d[4]B→cB[5] B→d[6]
建立文法G[S']的LR(0)分析表。
2、根据清华大学出版编译原理教材P136的描述的LR(0)分析器的工作过程手工构造LR(0)语法分析程序。
3、用该LR(0)语法分析程序对任意给定的键盘输入串bccd#进行语法分析，并根据栈的变化状态输出给定串的具体分析过程。
四、运行结果
从任意给定的键盘输入串：
bccd#
输出：
用LR(0)分析法分析符号串bccd#的过程
五、提示
本实验重点有两个：一是如何用适当的数据结构实现LR(0)分析表的存储和使用；二是如何实现遇到rj值时的归约处理。
建议：使用结构体数组。
六、分析与讨论
1、若输入串不是指定文法的句子，会出现什么情况？
2、总结LR语法分析程序的设计和实现的一般方法。