词法的正规式描述；2、变换后的状态图；3、词法分析程序的数据结构与算法。
八、思考题
1、词法分析能否采用空格来区分单词？2、程序设计中哪些环节影响词法分析的效率？如何提高效率？
6
f实验3
一、实验目的
LL（1）文法构造
熟悉LL（1）文法的分析条件，了解LL（1）文法的构造方法。
二、实验内容
1、编制一个能够将一个非LL（1）文法转换为LL（1）文法；2、消除左递归；3、消除回溯。
三、实验要求
1、将一个可转换非LL（1）文法转换为LL（1）文法，要经过两个阶段，1）消除文法左递归，2）提取左因子，消除回溯。2、提取文法左因子算法：1）对文法G的所有非终结符进行排序2）按上述顺序对每一个非终结符Pi依次执行forj1；ji1；j将Pj代入Pi的产生式（若可代入的话）；消除关于Pi的直接左递归：PiPiαβ，其中β不以Pi开头，则修改产生式为：Pi＞βPi′Pi′＞αPi′ε3）化简上述所得文法。3、提取左因子的算法：A＞δβ1δβ2δβ
γ1γ2γm其中每个γ不以δ开头那么可以把这些产生式改写成A＞δA′γ1γ2γmA′＞β1β2β
4、利用上述算法，实现构造一个LL（1）文法：1）从文本文件gtxt中读入文法，利用实验1的结果，存入实验1设计的数据结构；2）设计函数remove_left_recursio
（）和remove_left_ge
e（）实现消除左递归和提取左因子算法，分别对文法进行操作，消除文法中的左递归和提出左因子；3）整理得到的新文法；4）在一个新的文本文件
ewgtxt输出文法，文法输出按照一个非终结符号一行，开始符号引出的产生式写在第一行，同一个非终结符号的候选式用“”分隔的方式输出。
四、实验环境
PC微机
7
fDOS操作系统或Wi
dows操作系统TurboC程序集成环境或VisualC程序集成环境
五、实验步骤
1、学习LL（1）文法的分析条件；2、学习构造LL（1）文法的算法；3、结合实验1给出的数据结构，编程实现构造LL（1）文法的算法；4、结合实验1编程和调试实现对一个具体文法运用上述算法，构造它的LL（1）文法形式；5、把实验结果写入一个新建立的文本文件。
六、测试数据
输入数据：编辑一个文本文文件gtxt，在文件中输入如下内容：SQcccabQRbbRSaa
正确结果：本实验的输出结果是不唯一的，根据消除左递归是选择非终结符号的顺序不同，或选择新的非终结符号的不同，可能会得到不同的结果，下面只是可能的一个结果：SQccTTab由于无法输出ε，用代替QRbbRbcaUcaUcabaUaUUbcaU
七、r