实验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次执行
for( j1 j< i1j++)
Pj代入Pi产生式（代入话）
消关Pi直接左递：
Pi > Piα|β 中βPi开头修改产生式：
Pi —＞ βPi′
Pi′—＞ αPi′|ε
3）化简述文法
3 提取左子算法：
A —＞ δβ1|δβ2|…|δβn|γ1|γ2|…|γm
(中γδ开头)
产生式改写成
A —＞ δA′|γ1| γ2…|γm
A′—＞β1|β2|…|βn
4 利述算法实现构造LL（1）文法：
1） 文文件gtxt中读入文法利实验1结果存入实验1设计数结构
2） 设计函数remove_left_recursion（）remove_left_gene（）实现消左递提取左子算法分文法进行操作消文法中左递提出左子
3） 整理新文法
4） 新文文件newgtxt输出文法文法输出非终结符号行开始符号引出产生式写第行非终结符号候选式|分隔方式输出
四实验环境
PC微机
DOS操作系统 Windows 操作系统
Turbo C 程序集成环境 Visual C++ 程序集成环境
五实验步骤
1学LL（1）文法分析条件
2学构造LL（1）文法算法
3结合实验1出数结构编程实现构造LL（1）文法算法
4结合实验1编程调试实现具体文法运述算法构造LL（1）文法形式
5 实验结果写入新建立文文件
六测试数
输入数：
编辑文文文件gtxt文件中输入容：
S>Qc|c|cab
Q>Rb|b
R>Sa|a
正确结果：
实验输出结果唯根消左递选择非终结符号序选择新非终结符号会结果面结果：
S>Qc|cT
T>@|ab 法输出ε@代
Q>Rb|b
R>bcaU|caU|cabaU|aU
U>bcaU|@
七实验报告求
实验报告应包括部分：
1 满足LL（1）文法分析条件
转换前求文法中含回路（推导形P>P类）含ε右部产生式
文法进行LL（1）分析文法应该满足：二义性左递左公子
首先需定义规：
1 程序运行前文法必须输入进文文件中输入文法包含中产生式默认转换非LL（1）文法通消左递反复提取公左子转换成LL（1）文法
2 输入产生式原实验1结果非终结符条产生式候选间|隔开
3 产生式产生式间换行符分号隔开
4 开始符号应产生式必须第输入默认输入第产生式左部写字母开始符号
5 输入输出会保存文文件中文件名分gtxtnewgtxt实验测试数时两文放桌面
6 ε@代输入输出@
7 新产生非终结符统没非终结符集合中出现写字母
8 规定产生式20
2 构造LL（1）文法算法
算法：
1) 文文件gtxt中读入文法存入结构体中第读写字母记开始符号S读包括开始符号写字母判定非终结符第次出现存入文法非终结符集合中终结符写字母样换行符分号隔开字符串判断条产生式存入文法中实现函数scanP()
2) 文法中产生式消左递实现函数remove_left_recursion()
3) 文法中产生式反复提取公左子实现函数remove_left_gene ()
4) newgtxt中输出文法产生式
3 消左递文法提取左子算法实现方法
消左递文法（包括中子函数）：
*字符串分割函数产生式右部候选返回识|’pos位开始分割*
string strsplit(string strTokint pos ) {
string str
size_t position
position strTokfind(|pos)
if (position stringnpos) { 找|’
str strToksubstr(posposition pos)
}
else { 没找
str strToksubstr(pos strToksize() pos)
}
return str
}
*获文法中尚未定义非终结符特定写字母*
char GetWord(char *p) {
char chword[] { ＇A＇ ＇B＇ ＇C＇ ＇D＇ ＇E＇ ＇F＇ ＇G＇ ＇H＇ ＇I＇ ＇J＇ ＇K＇ ＇L＇ ＇M＇ ＇N＇ ＇O＇ ＇P＇ ＇Q＇
＇R＇ ＇S＇ ＇T＇ ＇U＇ ＇V＇ ＇W＇ ＇X＇ ＇Y＇ ＇Z＇ }
int wx
for (w 0 w < 26 w++) {
ch word[w]
for (x 0 x < m x++) {
if (ch p[x]) {
break
}
}
if (x m) break
}
return ch
}
*判断非终结符否已存*
bool checkWord(char ch string Vn) {
int i
bool flag true
for (i 0 i < Vnsize() i++) {
if (ch Vn[i])
flag false
}
return flag
}
*化简产生式*
void simplify(struct grammar *gp) {
string str 存储开始符号达非终结符序列
int sVn[20] 标记产生式
sVn[0] 0
strinsert(0 1 gp>Vn[0]) 初始化设置开始符号
bool flag[20]
flag[0] false 标记产生式需删
char ch
int ijklo
for (i 0 i < strsize() i++) {
for (j 3 j < gp>P[sVn[i]]size() j++) {
for (k 0 k < mk++) {
if (gp>P[sVn[i]][j] < ＇A＇ || gp>P[sVn[i]][j] > ＇Z＇) break 非终结符需判断
if (gp>P[sVn[i]][j] gp>Vn[k]) { 判断开始符号达非终结符Vn位置
flag[k] false
if (checkWord(gp>Vn[k] str)) { str中没非终结符插入str
int e strsize()
sVn[e] k
strinsert(strsize() 1 gp>Vn[k])
}
break
}
}
}
}
for (l 0 l < m l++) { 删产生式相应非终结符
char ch
if (flag[l]) {
gp>Vn[l] ＇ ＇
for (o l + 1 o < m o++) {
ch gp>Vn[o 1]
gp>Vn[o 1] gp>Vn[o]
gp>Vn[o] ch
gp>P[o 1]clear()
gp>P[o 1]swap(gp>P[o])
}
m
}
}
}
void remove_left_recursion(struct grammar *gp) { 子函数消文法左递
int i jnum_inum_jiposjpos
char ch_i ch_j
for (i 1 i < m + 1i++) {
bool repeat true 标记相轮循环轮程产生式否变化需重新分割候选
num_i 0ipos 3
string str_i[20]restr_i[20] ex a
ch_i gp>Vn[i 1] 获取前处理非终结符Pi
分割产生式右部候选
while (ipos gp>P[i 1]size() + 1) {
str_i[num_i] strsplit(gp>P[i 1] ipos)
restr_i[num_i] str_i[num_i]
ipos ipos + str_i[num_i]size() + 1
num_i++
}
for (j 1 j < i 1 j++) {
if (repeat) {
num_i 0 ipos 3
ch_i gp>Vn[i 1] 重新获取前处理非终结符Pi
分割产生式右部候选
while (ipos gp>P[i 1]size() + 1) {
str_i[num_i] strsplit(gp>P[i 1] ipos)
restr_i[num_i] str_i[num_i]
ipos ipos + str_i[num_i]size() + 1
num_i++
}
}
repeat true
string str_j[20]
int l
jpos 3
num_j 0
ch_j gp>Vn[j 1] 获取前换非终结符Pj
分割产生式右部候选
while (jpos gp>P[j 1]size() + 1) {
str_j[num_j] strsplit(gp>P[j 1] jpos)
jpos jpos + str_j[num_j]size() + 1
num_j++
}
for (l 0 l < num_i l++) { 逐判断Pi候选中否含Pj进行换
string change
ex[0] ch_j
size_t pos restr_i[l]find(ex)
if (pos stringnpos) { continue } 需换
else if (pos 0){ Pj该候选第字符
repeat false
string s str_i[l]substr(1 str_i[l]size() 1) 候选中Pj外剩余部分
str_i[l]swap(change) 清空字符串
int link 0
while (1) { Pj候选Pi中匹配候选剩余部分连接中间添加|
if (link num_j) break
str_j[link] + s
if (link num_j 1) str_i[l] + str_j[link]
else str_i[l] str_i[l] + str_j[link] + |
link++
}
}
else if (pos str_i[l]size() 1) { Pj该候选字符
repeat false
string s str_i[l]substr(0 str_i[l]size() 1)
str_i[l]swap(change)
int link 0
while (1) {
if (link num_j) break
str_j[link] s + str_j[link]
if (link num_j 1) str_i[l] + str_j[link]
else str_i[l] str_i[l] + str_j[link] + |
link++
}
}
else { Pj该候选中间
repeat false
string s1 str_i[l]substr(0pos 1) 该候选中Pj前字符串
string s2 str_i[l]substr(pos + 1 str_i[l]size() pos 1)该候选中Pj字符串
str_i[l]swap(change)
int link 0
while (1) {
if (link num_j) break
str_j[link] s1 + str_j[link] + s2
if (link num_j 1) str_i[l] + str_j[link]
else str_i[l] str_i[l] + str_j[link] + |
link++
}
}
}
string stri >
striinsert(01ch_i)
int index 0
while (1) { 换Pi候选进行重组存进文法中
if (index num_i) break
if (index num_i 1) stri stri + str_i[index]
else stri stri + str_i[index] + |
index++
}
gp>P[i 1] stri
}
消直接左递
string splitstr[30] resplitstr[30]
int s 0ps 3h 0
while (1) { 分割换产生式
splitstr[s] strsplit(gp>P[i 1] ps)
resplitstr[s] splitstr[s]
ps ps + splitstr[s]size() + 1
if (ps gp>P[i 1]size() + 1) break
s++
}
string Pi >Pichange >
Pi ch_i + Pi
int link 0flag 1
bool flagpos[30]
char newWord
for ( link < s link++) { 遍历候选校验中否左递
size_t posi
posi resplitstr[link]find(ch_i)
if (posi 0) { 存直接左递
flag++ 候选标记左递
if (flag 0) { 处理出现左递第候选
newWord GetWord(gp>Vn) 获取新非终结符
gp>Vn[m] newWord
Pichange newWord + Pichange
m++
splitstr[link] splitstr[link]substr(1) + newWord
flagpos[link] false
gp>P[m 1] Pichange + splitstr[link] + |
}
if (flag > 0) {
splitstr[link] splitstr[link]substr(1) + newWord
flagpos[link] false
gp>P[m 1] gp>P[m 1] + splitstr[link] + |
}
}
}
消直接左递候选进行重组成产生式存入文法
if (flag > 1) {
gp>P[i 1] >
gp>P[i 1]insert(0 1 ch_i)
for ( h < s h++) {
if (flagpos[h]) {
splitstr[h] + newWord
gp>P[i 1] gp>P[i 1] + splitstr[h] + |
}
}
gp>P[m 1] + @
gp>P[i 1]erase(gp>P[i 1]size() 1 1)
}
}
simplify(gp) 化简产生式
}
提取左子（包括辅助函数）：
字符串数组排序
void str_sort(string *str int num) {
int i j
for (i 0 i < num i++) {
for (j i + 1 j < num j++) {
if (str[i] > str[j])
str[i]swap(str[j])
}
}
}
*子函数提取左子*
void remove_left_gene(struct grammar *gp) {
int rule_a i j k l matchnumoldmatchnum resizesize
char ch newWord
for (rule_a 0 rule_a < m rule_a++) { 遍历产生式
int bre 1 标记已产生式进行左子提取
int oldpo 0
int num 0 ps 3
string str[30]restr[30] 前者判断需保持原样者公左子候选进行提取变
while (ps gp>P[rule_a]size() + 1) { 分割换产生式
str[num] strsplit(gp>P[rule_a] ps)
restr[num] str[num]
ps ps + str[num]size() + 1
num++
}
str_sort(str num) 候选ASCII码进行排序便简化公左子判断需先前面候选判断
str_sort(restr num)
int ca_i
string Pa >
Painsert(0 1 gp>Vn[rule_a])
for (ca_i 0 ca_i < num ca_i++) { 排序候选进行重组存入文法
if (ca_i num 1)
Pa + str[ca_i]
else
Pa + str[ca_i] + |
}
gp>P[rule_a] Pa
int ipo 0 辅助免已判断左子候选遍历
for (i 0 i < num i++i + ipo) { 遍历候选
ipo 0
size 0
resize 0
oldmatchnum 0
int i_s str[i]size()
for (j 0 j < i_s j++) { 候选逐字符遍历
matchnum 0 标记身候选公左子
ch str[i][j]
int kf num
for (k i + 1 k < num && k < kf k++) { i候选进行判断否i应公左子
if (str[k][j] ch) { 公左子
matchnum++
}
else {
break
}
}
if (j 0) { 判断否公左子i第字符情况特处理
if (matchnum 0) break
else { oldmatchnum matchnum kf i + 1 + oldmatchnum }
}
else {
if (oldmatchnum matchnum) break
}
}
*公左子处理程*
if (matchnum oldmatchnum || j i_s) {
bre ++
string match repstr can newP
match str[i]substr(0 j) 获取公左子
newWord GetWord(gp>Vn) 新非终结符
gp>Vn[m] newWord 新非终结符存入文法
m++
newP >
newPinsert(0 1 newWord)
repstr match + newWord 换公左子候选
int renum num
if (bre > 0) { 产生式存公左子（前提取次左子）需进行特处理
size resize 0
renum 0
ps 3
while (ps gp>P[rule_a]size() + 1) { 分割变化产生式
restr[renum] strsplit(gp>P[rule_a] ps)
ps ps + restr[renum]size() + 1
renum++
}
}
*已提取左子候选单位字符串重新组合成产生式（包括新产生式）*
for (l 0 l < i oldpo + oldmatchnum l++) {
if (l > i oldpo) {
size + restr[l]size()
can restr[l]substr(j)
if (can ) can @
if (l i oldpo + oldmatchnum) newP + can
else newP newP + can + |
gp>P[m 1] newP
}
else {
resize + restr[l]size()
resize++
}
}
gp>P[rule_a]replace(resize + 3 size + oldmatchnum repstr) 原产生式换方式进行改变
if (i + 1 + oldmatchnum > num) { break }
else oldpo ipo oldmatchnum
}
}
}
}
4 程序代码
#include
#include
using namespace std
struct grammar { 结构体定义文法
char Vn[20] 非终结符
char Vt[20] 终结符
char S 开始符号
string P[20] 产生式
}
int m 0 n 0 全局变量分表示存入结构体非终结符终结符字符数组第位置
char GetBC(FILE* fpi) { 子函数读取非空格字符
char ch
do {
ch fgetc(fpi)
} while (ch ＇ ＇)
return ch
}
* 整型函数读入行产生式分析出文法成员参数分输入文文件指针文法结构体指针
第行产生式 *
void scanP(FILE* fpistruct grammar *gp) {
char ch
string str 存入条产生式
if (feof(fpi)) return 达文件尾返回
ch GetBC(fpi)
if (ch > ＇A＇ && ch < ＇Z＇) { 读入产生式左部非终结符
str + ch
gp>Vn[m] ch 非终结符存入结构体
m++
ch GetBC(fpi)
if (ch ＇＇) {
str + ch
ch GetBC(fpi)
if (ch ＇>＇) {
str + ch
while (1) {
ch GetBC(fpi)
if (ch ＇＼n＇ || ch ＇＇) break 读入换行符分号退出循环
str + ch
if (ch > ＇a＇ && ch < ＇z＇) { 读入终结符
int num
for (num 0 num < n num++) { 判断该终结符前结构体中否已存
if (gp>Vt[num] ch)
break
}
if (num n) { 存入结构体中未出现终结符
gp>Vt[n] ch
n++
}
}
}
}
}
gp>P[m 1] + str 产生式存入结构体
}
}
int main() {
FILE* fpi 定义输入文指针
FILE* fpo 定义输出文指针
errno_t err
if ((err fopen_s(&fpiC＼＼Users＼＼Administrator＼＼Desktop＼＼gtxt r)) 0) { 读方式开文件
printf(file can not open＼n) 开文件出错提示
exit(0) 安全退出程序
}
struct grammar g *gp
gp &g 定义结构体指针
读取第写字母作开始符号
char ch
do {
ch GetBC(fpi)
} while (ch < ＇A＇ || ch > ＇Z＇)
gp>S ch
fseek(fpi 1L 1) 搜索指示器回调字符
while (feof(fpi)) { 文文件中读入产生式文法四部分存入结构体中
scanP(fpigp)
}
fclose(fpi) 关闭fpi指文件
fpi NULL 避免指非法存
remove_left_recursion(gp)
remove_left_gene(gp)
err fopen_s(&fpoC＼＼Users＼＼Administrator＼＼Desktop＼＼newgtxt w) 写方式开文件存动建立
if (err 0) {
printf(file can not open＼n) 开文件出错提示
exit(0) 安全退出程序
}
int i
for (i 0 i < m i++) { 输出处理文法文中
fputs(gp>P[i]data() fpo)
fputs(＼n fpo)
}
fclose(fpo) 关闭fpi指文件
fpo NULL 避免指非法存
}
5 整测试程序流程
gtxt中输入文法
启动程序
main()反复调scanP()
达文件尾完成文法输入
调remove_left_recursion()
调remove_left_gene()
文法输出newgtxt
程序结束
查结果文法
6 程序测试结果问题
实验源文法：
文法：
书文法调换序改变开始符号R结果会删关Q产生式：
实验中遇问题：
1 开始设计程序时候没运数结构简化问题实验数结构构造结构体实验部分处理程需文法产生式结构体中产生式字符串数组存储中夹杂着>|分析时符号（迭代时前面变化重新分割候选）候选处理程增加复杂度果产生式外设计结构体左部非终结符右部候选候选数进行封装极简化代码者直接定义类样中成员函数程更加清晰条理
2 代码重性问题缺乏C++编程验没类象更优越技术实现外方诸重新候选进行分割外设置存储位置作缓等等没设置子函数处理程变冗余
3 C字符数组运熟练存储字符串时灵活相应库函数处理问题已C++string类实关字符数组许库函数非常高效
4 编程时VS2015前直DevC++编程时软件功熟悉浪费时间查说明认识快捷键需VS编写C
5 编程验足导致查阅者量修改降低效率
6 调试程序时变量太查错费少时间没子函数带弊端
7 实验总结
实验身较麻烦关键remove_left_recursion（）remove_left_gene（）两子函数提供算法加身理课提供量额外知识容易思路实现两子函数具体程两函数实现程文法数结构关系密切果首先设计数结构工夫够设计数结构绝事半功倍相复杂问题首先设计数结构次慢慢完成算法完成算法代码编写调试高效完成项工作需解IDE关调试种功样助软件功调试会更加容易然中免会发现错误需修改程序时候觉特注意修改状态转换程修改前程序程修改程达程究竟否修改修改时特需修改部分软件身动相变量调亮功进行标记免漏改旦漏改容易进入思维误区觉刚修改方法出错实漏改点错误变量达十二十时容易犯调试时重点关注修改
八思考题
1 文法通述程序构造LL（1）文法？
答：文法身够转换转换前含回路含空字右部产生式转换时提取公左子时存某文法限步骤提取完左公子
例：
S>Ap|Bq
A>aAp|d
B>aBq|e
转换判断终确认否LL（1）文法
2 LL（1）文法整语法分析中作？
答：语法分析包括两类：类分析法类分析法
旨输入串试图切办法文法开始符号出发输入串建立棵语法树者说输入串寻找左推倒种分析程质种试探程反复产生式谋求匹配输入串程程分析法中研究LL(1)分析法
3 实验1中设计文法数结构实验影响？
答：数结构身够简化问题具体算法思路倾性程序处理程更加条理外实验1数结构完整开始符号终结符非终结符产生式存储消左递提取左子非终结符产生式进行更加效处理较没数结构没存储非终结符言迭代时单处理需步骤完成进行统处理
4 更组合实验1实验3具更高效率？
答：结构体定义文法包括文法四部分终结符非终结符string类便调string类成员函数处理问题产生式C++类定义存储文法时左部非终结符右部候选候选ASCII码排序存储数非终结符候选候选数成员函数够查增加修改删成员果候选链表样增加换删更加简单高效实验1中回路右部空字产生式进行判断提示输入文法合理外实验3定义规定转接实验1样文法结构定义文法完整输入转换非LL（1）文法判断输入提示出错检测全部集中原实验1完成部分原实验3部分关注文法进行转换输出消左递提取左子输出文文件中
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
实验目
熟悉LL（1）文法分析条件解LL（1）文法构造方法
二实验容
1编制够非LL（1）文法转换LL（1）文法
2消左递
3消回溯
三实验求
1 转换非LL（1）文法转换LL（1）文法两阶段1）消文法左递2）提取左子消回溯
2 提取文法左子算法：
1）文法G非终结符进行排序
2）述序非终结符Pi次执行
for( j1 j< i1j++)
Pj代入Pi产生式（代入话）
消关Pi直接左递：
Pi > Piα|β 中βPi开头修改产生式：
Pi —＞ βPi′
Pi′—＞ αPi′|ε
3）化简述文法
3 提取左子算法：
A —＞ δβ1|δβ2|…|δβn|γ1|γ2|…|γm
(中γδ开头)
产生式改写成
A —＞ δA′|γ1| γ2…|γm
A′—＞β1|β2|…|βn
4 利述算法实现构造LL（1）文法：
1） 文文件gtxt中读入文法利实验1结果存入实验1设计数结构
2） 设计函数remove_left_recursion（）remove_left_gene（）实现消左递提取左子算法分文法进行操作消文法中左递提出左子
3） 整理新文法
4） 新文文件newgtxt输出文法文法输出非终结符号行开始符号引出产生式写第行非终结符号候选式|分隔方式输出
四实验环境
PC微机
DOS操作系统 Windows 操作系统
Turbo C 程序集成环境 Visual C++ 程序集成环境
五实验步骤
1学LL（1）文法分析条件
2学构造LL（1）文法算法
3结合实验1出数结构编程实现构造LL（1）文法算法
4结合实验1编程调试实现具体文法运述算法构造LL（1）文法形式
5 实验结果写入新建立文文件
六测试数
输入数：
编辑文文文件gtxt文件中输入容：
S>Qc|c|cab
Q>Rb|b
R>Sa|a
正确结果：
实验输出结果唯根消左递选择非终结符号序选择新非终结符号会结果面结果：
S>Qc|cT
T>@|ab 法输出ε@代
Q>Rb|b
R>bcaU|caU|cabaU|aU
U>bcaU|@
七实验报告求
实验报告应包括部分：
1 满足LL（1）文法分析条件
转换前求文法中含回路（推导形P>P类）含ε右部产生式
文法进行LL（1）分析文法应该满足：二义性左递左公子
首先需定义规：
1 程序运行前文法必须输入进文文件中输入文法包含中产生式默认转换非LL（1）文法通消左递反复提取公左子转换成LL（1）文法
2 输入产生式原实验1结果非终结符条产生式候选间|隔开
3 产生式产生式间换行符分号隔开
4 开始符号应产生式必须第输入默认输入第产生式左部写字母开始符号
5 输入输出会保存文文件中文件名分gtxtnewgtxt实验测试数时两文放桌面
6 ε@代输入输出@
7 新产生非终结符统没非终结符集合中出现写字母
8 规定产生式20
2 构造LL（1）文法算法
算法：
1) 文文件gtxt中读入文法存入结构体中第读写字母记开始符号S读包括开始符号写字母判定非终结符第次出现存入文法非终结符集合中终结符写字母样换行符分号隔开字符串判断条产生式存入文法中实现函数scanP()
2) 文法中产生式消左递实现函数remove_left_recursion()
3) 文法中产生式反复提取公左子实现函数remove_left_gene ()
4) newgtxt中输出文法产生式
3 消左递文法提取左子算法实现方法
消左递文法（包括中子函数）：
*字符串分割函数产生式右部候选返回识|’pos位开始分割*
string strsplit(string strTokint pos ) {
string str
size_t position
position strTokfind(|pos)
if (position stringnpos) { 找|’
str strToksubstr(posposition pos)
}
else { 没找
str strToksubstr(pos strToksize() pos)
}
return str
}
*获文法中尚未定义非终结符特定写字母*
char GetWord(char *p) {
char chword[] { ＇A＇ ＇B＇ ＇C＇ ＇D＇ ＇E＇ ＇F＇ ＇G＇ ＇H＇ ＇I＇ ＇J＇ ＇K＇ ＇L＇ ＇M＇ ＇N＇ ＇O＇ ＇P＇ ＇Q＇
＇R＇ ＇S＇ ＇T＇ ＇U＇ ＇V＇ ＇W＇ ＇X＇ ＇Y＇ ＇Z＇ }
int wx
for (w 0 w < 26 w++) {
ch word[w]
for (x 0 x < m x++) {
if (ch p[x]) {
break
}
}
if (x m) break
}
return ch
}
*判断非终结符否已存*
bool checkWord(char ch string Vn) {
int i
bool flag true
for (i 0 i < Vnsize() i++) {
if (ch Vn[i])
flag false
}
return flag
}
*化简产生式*
void simplify(struct grammar *gp) {
string str 存储开始符号达非终结符序列
int sVn[20] 标记产生式
sVn[0] 0
strinsert(0 1 gp>Vn[0]) 初始化设置开始符号
bool flag[20]
flag[0] false 标记产生式需删
char ch
int ijklo
for (i 0 i < strsize() i++) {
for (j 3 j < gp>P[sVn[i]]size() j++) {
for (k 0 k < mk++) {
if (gp>P[sVn[i]][j] < ＇A＇ || gp>P[sVn[i]][j] > ＇Z＇) break 非终结符需判断
if (gp>P[sVn[i]][j] gp>Vn[k]) { 判断开始符号达非终结符Vn位置
flag[k] false
if (checkWord(gp>Vn[k] str)) { str中没非终结符插入str
int e strsize()
sVn[e] k
strinsert(strsize() 1 gp>Vn[k])
}
break
}
}
}
}
for (l 0 l < m l++) { 删产生式相应非终结符
char ch
if (flag[l]) {
gp>Vn[l] ＇ ＇
for (o l + 1 o < m o++) {
ch gp>Vn[o 1]
gp>Vn[o 1] gp>Vn[o]
gp>Vn[o] ch
gp>P[o 1]clear()
gp>P[o 1]swap(gp>P[o])
}
m
}
}
}
void remove_left_recursion(struct grammar *gp) { 子函数消文法左递
int i jnum_inum_jiposjpos
char ch_i ch_j
for (i 1 i < m + 1i++) {
bool repeat true 标记相轮循环轮程产生式否变化需重新分割候选
num_i 0ipos 3
string str_i[20]restr_i[20] ex a
ch_i gp>Vn[i 1] 获取前处理非终结符Pi
分割产生式右部候选
while (ipos gp>P[i 1]size() + 1) {
str_i[num_i] strsplit(gp>P[i 1] ipos)
restr_i[num_i] str_i[num_i]
ipos ipos + str_i[num_i]size() + 1
num_i++
}
for (j 1 j < i 1 j++) {
if (repeat) {
num_i 0 ipos 3
ch_i gp>Vn[i 1] 重新获取前处理非终结符Pi
分割产生式右部候选
while (ipos gp>P[i 1]size() + 1) {
str_i[num_i] strsplit(gp>P[i 1] ipos)
restr_i[num_i] str_i[num_i]
ipos ipos + str_i[num_i]size() + 1
num_i++
}
}
repeat true
string str_j[20]
int l
jpos 3
num_j 0
ch_j gp>Vn[j 1] 获取前换非终结符Pj
分割产生式右部候选
while (jpos gp>P[j 1]size() + 1) {
str_j[num_j] strsplit(gp>P[j 1] jpos)
jpos jpos + str_j[num_j]size() + 1
num_j++
}
for (l 0 l < num_i l++) { 逐判断Pi候选中否含Pj进行换
string change
ex[0] ch_j
size_t pos restr_i[l]find(ex)
if (pos stringnpos) { continue } 需换
else if (pos 0){ Pj该候选第字符
repeat false
string s str_i[l]substr(1 str_i[l]size() 1) 候选中Pj外剩余部分
str_i[l]swap(change) 清空字符串
int link 0
while (1) { Pj候选Pi中匹配候选剩余部分连接中间添加|
if (link num_j) break
str_j[link] + s
if (link num_j 1) str_i[l] + str_j[link]
else str_i[l] str_i[l] + str_j[link] + |
link++
}
}
else if (pos str_i[l]size() 1) { Pj该候选字符
repeat false
string s str_i[l]substr(0 str_i[l]size() 1)
str_i[l]swap(change)
int link 0
while (1) {
if (link num_j) break
str_j[link] s + str_j[link]
if (link num_j 1) str_i[l] + str_j[link]
else str_i[l] str_i[l] + str_j[link] + |
link++
}
}
else { Pj该候选中间
repeat false
string s1 str_i[l]substr(0pos 1) 该候选中Pj前字符串
string s2 str_i[l]substr(pos + 1 str_i[l]size() pos 1)该候选中Pj字符串
str_i[l]swap(change)
int link 0
while (1) {
if (link num_j) break
str_j[link] s1 + str_j[link] + s2
if (link num_j 1) str_i[l] + str_j[link]
else str_i[l] str_i[l] + str_j[link] + |
link++
}
}
}
string stri >
striinsert(01ch_i)
int index 0
while (1) { 换Pi候选进行重组存进文法中
if (index num_i) break
if (index num_i 1) stri stri + str_i[index]
else stri stri + str_i[index] + |
index++
}
gp>P[i 1] stri
}
消直接左递
string splitstr[30] resplitstr[30]
int s 0ps 3h 0
while (1) { 分割换产生式
splitstr[s] strsplit(gp>P[i 1] ps)
resplitstr[s] splitstr[s]
ps ps + splitstr[s]size() + 1
if (ps gp>P[i 1]size() + 1) break
s++
}
string Pi >Pichange >
Pi ch_i + Pi
int link 0flag 1
bool flagpos[30]
char newWord
for ( link < s link++) { 遍历候选校验中否左递
size_t posi
posi resplitstr[link]find(ch_i)
if (posi 0) { 存直接左递
flag++ 候选标记左递
if (flag 0) { 处理出现左递第候选
newWord GetWord(gp>Vn) 获取新非终结符
gp>Vn[m] newWord
Pichange newWord + Pichange
m++
splitstr[link] splitstr[link]substr(1) + newWord
flagpos[link] false
gp>P[m 1] Pichange + splitstr[link] + |
}
if (flag > 0) {
splitstr[link] splitstr[link]substr(1) + newWord
flagpos[link] false
gp>P[m 1] gp>P[m 1] + splitstr[link] + |
}
}
}
消直接左递候选进行重组成产生式存入文法
if (flag > 1) {
gp>P[i 1] >
gp>P[i 1]insert(0 1 ch_i)
for ( h < s h++) {
if (flagpos[h]) {
splitstr[h] + newWord
gp>P[i 1] gp>P[i 1] + splitstr[h] + |
}
}
gp>P[m 1] + @
gp>P[i 1]erase(gp>P[i 1]size() 1 1)
}
}
simplify(gp) 化简产生式
}
提取左子（包括辅助函数）：
字符串数组排序
void str_sort(string *str int num) {
int i j
for (i 0 i < num i++) {
for (j i + 1 j < num j++) {
if (str[i] > str[j])
str[i]swap(str[j])
}
}
}
*子函数提取左子*
void remove_left_gene(struct grammar *gp) {
int rule_a i j k l matchnumoldmatchnum resizesize
char ch newWord
for (rule_a 0 rule_a < m rule_a++) { 遍历产生式
int bre 1 标记已产生式进行左子提取
int oldpo 0
int num 0 ps 3
string str[30]restr[30] 前者判断需保持原样者公左子候选进行提取变
while (ps gp>P[rule_a]size() + 1) { 分割换产生式
str[num] strsplit(gp>P[rule_a] ps)
restr[num] str[num]
ps ps + str[num]size() + 1
num++
}
str_sort(str num) 候选ASCII码进行排序便简化公左子判断需先前面候选判断
str_sort(restr num)
int ca_i
string Pa >
Painsert(0 1 gp>Vn[rule_a])
for (ca_i 0 ca_i < num ca_i++) { 排序候选进行重组存入文法
if (ca_i num 1)
Pa + str[ca_i]
else
Pa + str[ca_i] + |
}
gp>P[rule_a] Pa
int ipo 0 辅助免已判断左子候选遍历
for (i 0 i < num i++i + ipo) { 遍历候选
ipo 0
size 0
resize 0
oldmatchnum 0
int i_s str[i]size()
for (j 0 j < i_s j++) { 候选逐字符遍历
matchnum 0 标记身候选公左子
ch str[i][j]
int kf num
for (k i + 1 k < num && k < kf k++) { i候选进行判断否i应公左子
if (str[k][j] ch) { 公左子
matchnum++
}
else {
break
}
}
if (j 0) { 判断否公左子i第字符情况特处理
if (matchnum 0) break
else { oldmatchnum matchnum kf i + 1 + oldmatchnum }
}
else {
if (oldmatchnum matchnum) break
}
}
*公左子处理程*
if (matchnum oldmatchnum || j i_s) {
bre ++
string match repstr can newP
match str[i]substr(0 j) 获取公左子
newWord GetWord(gp>Vn) 新非终结符
gp>Vn[m] newWord 新非终结符存入文法
m++
newP >
newPinsert(0 1 newWord)
repstr match + newWord 换公左子候选
int renum num
if (bre > 0) { 产生式存公左子（前提取次左子）需进行特处理
size resize 0
renum 0
ps 3
while (ps gp>P[rule_a]size() + 1) { 分割变化产生式
restr[renum] strsplit(gp>P[rule_a] ps)
ps ps + restr[renum]size() + 1
renum++
}
}
*已提取左子候选单位字符串重新组合成产生式（包括新产生式）*
for (l 0 l < i oldpo + oldmatchnum l++) {
if (l > i oldpo) {
size + restr[l]size()
can restr[l]substr(j)
if (can ) can @
if (l i oldpo + oldmatchnum) newP + can
else newP newP + can + |
gp>P[m 1] newP
}
else {
resize + restr[l]size()
resize++
}
}
gp>P[rule_a]replace(resize + 3 size + oldmatchnum repstr) 原产生式换方式进行改变
if (i + 1 + oldmatchnum > num) { break }
else oldpo ipo oldmatchnum
}
}
}
}
4 程序代码
#include
#include
using namespace std
struct grammar { 结构体定义文法
char Vn[20] 非终结符
char Vt[20] 终结符
char S 开始符号
string P[20] 产生式
}
int m 0 n 0 全局变量分表示存入结构体非终结符终结符字符数组第位置
char GetBC(FILE* fpi) { 子函数读取非空格字符
char ch
do {
ch fgetc(fpi)
} while (ch ＇ ＇)
return ch
}
* 整型函数读入行产生式分析出文法成员参数分输入文文件指针文法结构体指针
第行产生式 *
void scanP(FILE* fpistruct grammar *gp) {
char ch
string str 存入条产生式
if (feof(fpi)) return 达文件尾返回
ch GetBC(fpi)
if (ch > ＇A＇ && ch < ＇Z＇) { 读入产生式左部非终结符
str + ch
gp>Vn[m] ch 非终结符存入结构体
m++
ch GetBC(fpi)
if (ch ＇＇) {
str + ch
ch GetBC(fpi)
if (ch ＇>＇) {
str + ch
while (1) {
ch GetBC(fpi)
if (ch ＇＼n＇ || ch ＇＇) break 读入换行符分号退出循环
str + ch
if (ch > ＇a＇ && ch < ＇z＇) { 读入终结符
int num
for (num 0 num < n num++) { 判断该终结符前结构体中否已存
if (gp>Vt[num] ch)
break
}
if (num n) { 存入结构体中未出现终结符
gp>Vt[n] ch
n++
}
}
}
}
}
gp>P[m 1] + str 产生式存入结构体
}
}
int main() {
FILE* fpi 定义输入文指针
FILE* fpo 定义输出文指针
errno_t err
if ((err fopen_s(&fpiC＼＼Users＼＼Administrator＼＼Desktop＼＼gtxt r)) 0) { 读方式开文件
printf(file can not open＼n) 开文件出错提示
exit(0) 安全退出程序
}
struct grammar g *gp
gp &g 定义结构体指针
读取第写字母作开始符号
char ch
do {
ch GetBC(fpi)
} while (ch < ＇A＇ || ch > ＇Z＇)
gp>S ch
fseek(fpi 1L 1) 搜索指示器回调字符
while (feof(fpi)) { 文文件中读入产生式文法四部分存入结构体中
scanP(fpigp)
}
fclose(fpi) 关闭fpi指文件
fpi NULL 避免指非法存
remove_left_recursion(gp)
remove_left_gene(gp)
err fopen_s(&fpoC＼＼Users＼＼Administrator＼＼Desktop＼＼newgtxt w) 写方式开文件存动建立
if (err 0) {
printf(file can not open＼n) 开文件出错提示
exit(0) 安全退出程序
}
int i
for (i 0 i < m i++) { 输出处理文法文中
fputs(gp>P[i]data() fpo)
fputs(＼n fpo)
}
fclose(fpo) 关闭fpi指文件
fpo NULL 避免指非法存
}
5 整测试程序流程
gtxt中输入文法
启动程序
main()反复调scanP()
达文件尾完成文法输入
调remove_left_recursion()
调remove_left_gene()
文法输出newgtxt
程序结束
查结果文法
6 程序测试结果问题
实验源文法：
文法：
书文法调换序改变开始符号R结果会删关Q产生式：
实验中遇问题：
1 开始设计程序时候没运数结构简化问题实验数结构构造结构体实验部分处理程需文法产生式结构体中产生式字符串数组存储中夹杂着>|分析时符号（迭代时前面变化重新分割候选）候选处理程增加复杂度果产生式外设计结构体左部非终结符右部候选候选数进行封装极简化代码者直接定义类样中成员函数程更加清晰条理
2 代码重性问题缺乏C++编程验没类象更优越技术实现外方诸重新候选进行分割外设置存储位置作缓等等没设置子函数处理程变冗余
3 C字符数组运熟练存储字符串时灵活相应库函数处理问题已C++string类实关字符数组许库函数非常高效
4 编程时VS2015前直DevC++编程时软件功熟悉浪费时间查说明认识快捷键需VS编写C
5 编程验足导致查阅者量修改降低效率
6 调试程序时变量太查错费少时间没子函数带弊端
7 实验总结
实验身较麻烦关键remove_left_recursion（）remove_left_gene（）两子函数提供算法加身理课提供量额外知识容易思路实现两子函数具体程两函数实现程文法数结构关系密切果首先设计数结构工夫够设计数结构绝事半功倍相复杂问题首先设计数结构次慢慢完成算法完成算法代码编写调试高效完成项工作需解IDE关调试种功样助软件功调试会更加容易然中免会发现错误需修改程序时候觉特注意修改状态转换程修改前程序程修改程达程究竟否修改修改时特需修改部分软件身动相变量调亮功进行标记免漏改旦漏改容易进入思维误区觉刚修改方法出错实漏改点错误变量达十二十时容易犯调试时重点关注修改
八思考题
1 文法通述程序构造LL（1）文法？
答：文法身够转换转换前含回路含空字右部产生式转换时提取公左子时存某文法限步骤提取完左公子
例：
S>Ap|Bq
A>aAp|d
B>aBq|e
转换判断终确认否LL（1）文法
2 LL（1）文法整语法分析中作？
答：语法分析包括两类：类分析法类分析法
旨输入串试图切办法文法开始符号出发输入串建立棵语法树者说输入串寻找左推倒种分析程质种试探程反复产生式谋求匹配输入串程程分析法中研究LL(1)分析法
3 实验1中设计文法数结构实验影响？
答：数结构身够简化问题具体算法思路倾性程序处理程更加条理外实验1数结构完整开始符号终结符非终结符产生式存储消左递提取左子非终结符产生式进行更加效处理较没数结构没存储非终结符言迭代时单处理需步骤完成进行统处理
4 更组合实验1实验3具更高效率？
答：结构体定义文法包括文法四部分终结符非终结符string类便调string类成员函数处理问题产生式C++类定义存储文法时左部非终结符右部候选候选ASCII码排序存储数非终结符候选候选数成员函数够查增加修改删成员果候选链表样增加换删更加简单高效实验1中回路右部空字产生式进行判断提示输入文法合理外实验3定义规定转接实验1样文法结构定义文法完整输入转换非LL（1）文法判断输入提示出错检测全部集中原实验1完成部分原实验3部分关注文法进行转换输出消左递提取左子输出文文件中
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档