实验四 LL(1) 语法分析实验
一、实验目的
1. 了解 LL(1)语法分析是如何根据语法规则逐一分析词法分析所得到的单词，检查语法错误，即掌握语法分析过程。
2. 掌握LL(1)文法判别调剂和 LL(1)语法分析器的设计与调试。
二、实验内容
针对任意的文法，编写相应的左递归消除、左公共因子提取程序，求解相应的FIRST、FOLLOW集，构造预测分析表，并编写LL(1)语法分析程序，并给出测试句子的分析过程。（注：左递归消除和左公共因子如果在实验三里做了，可以直接拿过来用）
判断LL(1)文法部分：
1. 输入：文法
2. 处理：左递归消除、左公共因子提取，FIRST、FOLLOW等集合构造，判断LL(1)
3. 输出：是LL(1)的情况输出预测分析表，否则判断不是LL(1)
LL(1)分析程序部分：
1. 输入：诸如对应文法的符号串，以$结束。
2. 处理：基于分析表进行 LL(1)语法分析，判断其是否符合文法。
3. 输出：串是否合法。
三、实验要求
1. 构建合适的数据结构来表示文法符号和文法规则。
2. 设计恰当的数据结构存储预测分析表。（ε可用#代替）
3. 任选 C/C++/Java 或其他高级语言中的一种作为编程语言，要求所编程序结构清晰。
实验一、一个简单的C–词法分析器
一、 实验目的
设计、编制并调试一个自定义语言C–的词法分析程序，加深对词法分析原理的理解。
二、 实验内容
2.1 自定义语言C–的词法系统
1)类型系统：支持int、char、void基本类型，分别用词法记号表示为关键字int、char和void。
2)常量：字符常量(用单引号括起来)、字符串常量（用双引号括起来）、八/十/六进制整数常量（0开头表示八进制，0x开头表示十六进制）。分别用词法记号表示为ch、str和num。
3)变量：与常量对应，使用标识符表示，词法记号表示为id。
4)表达式运算符：支持加减乘除、求余、取负、自增、自减算术运算，大于、大于等于、小于、小于等于、等于、不等于关系运算，与、或、非逻辑运算，表示为词法记号：‘+’，‘-’，‘*’，‘/’，‘%’，‘-’，‘++’，‘–’，‘>’，‘>=’，‘<’，‘<=’，‘==’，‘！=’，‘&&’， ‘||’，‘！’。注意：取负运算和减法运算在词法分析器里是被看做是同一个词法记号。
5)语句：支持赋值语句、do-while、while、for循环语句，if-else、switch-case条件分之语句、函数调用、函数返回、跳转等语句。涉及的词法记号表示为赋值号‘=’，关键字do, while, for, if, else, switch, case, default, return ,break, continue。语句和函数体要求用大括号括起来，case和default后面需要跟冒号，因此需要包括各种分界符作为词法记号：‘{’，‘}’，‘;’，‘:’，‘(’，‘)’，‘,’。
所有的词法单元总结如下表所示：
表1 C—语言的词法构成
|
类别 |
记号 |
含义定义 |
类别 |
记号 |
含义定义 |
|
标识符 |
id |
同C语言标识符 |
运算符 |
div |
/ |
|
常量 |
num |
数字 |
mod |
% |
|
|
ch |
字符 |
inc |
++ |
||
|
str |
字符串 |
dec |
— |
||
|
关键字 |
kw_int |
int |
not |
! |
|
|
kw_char |
char |
and |
&& |
||
|
kw_void |
void |
or |
|| |
||
|
kw_if |
if |
assign |
= |
||
|
kw_else |
else |
gt |
> |
||
|
kw_switch |
switch |
ge |
>= |
||
|
kw_case |
case |
lt |
< |
||
|
kw_default |
default |
le |
<= |
||
|
kw_while |
while |
equ |
== |
||
|
kw_do |
do |
nequ |
!= |
||
|
kw_for |
for |
分界符 |
comma |
, |
|
|
kw_break |
break |
colon |
: |
||
|
kw_continue |
continue |
simcon |
; |
||
|
kw_return |
return |
lparen |
( |
||
|
运算符 |
add |
+ |
rparen |
) |
|
|
sub |
– |
lbrac |
{ |
||
|
mul |
* |
rbrac |
} |
2.2 单词符号编码
表1只是给出了建议分类，你可以根据自己程序的需要来给各种类别单词编码（可以给每个词法记号一个编码，也可以给一个类别里所有符号都编同一个编码）
2.3 词法分析程序的功能：
输入：所给文法的源程序字符串。
输出：二元组（编码，值）构成的序列。（能清楚表示识别出来的单词和它的类别）
三、实验要求
1. 写出程序框图、自动机。
2．写出程序源代码，并调试通过，输出实验结果。
3．完成实验报告及总结。
所有程序需要在上机时间验收过后才有效，实验报告中必须写清楚至少3个以上的测试数据结果
实验二 有限自动机的确定化和最小化
一、实验内容
利用状态表和有限自动机的运行原理编写和设计程序，判断输入的自动机是DFA还是NFA，如果是NFA，利用子集法将其确定化，然后利用求同法或求异法将所得的DFA最小化。
二、实验目的
1. 理解有限自动机的作用，进一步理解有限自动机理论
2. 设计有限自动机的表示方式，采用合理的数据结构表示自动机的五个组成部分
3.掌握ε闭包的求法和子集构造算法，以程序实现NFA到DFA的转换，并且最小化DFA，提高算法的理解和实现能力
三、实验步骤
1.可以采用任何语言来完成，如：C、C++或JAVA等
2.建议以文本文件形式来描述自动机，例如：
第一行：表示状态个数
第二行开始表示为状态转换表
最后一行给出接受状态列表
3.根据读进去的自动机内容，判断其类别（NFA还是DFA？）
4.若是NFA，利用子集法将其确定化
5.将DFA最小化
6.输入测试符号串，输出测试结果。
四、实验要求
1. 写出程序框图，具体算法流程
2．写出程序源代码，并调试通过，输出实验结果。
3．完成实验报告及总结。
