第1页 / 共12页
第2页 / 共12页
第3页 / 共12页
第4页 / 共12页
第5页 / 共12页
第6页 / 共12页
第7页 / 共12页
第8页 / 共12页
编译原理课程设计（LL(1),LR(1) 逆波兰 算符优先）.doc
1 正则表达式
1.1 正则表达式
1.2 确定化(化简)后的状态转换图
1.3 分析程序代码
1.4 程序运行截图
1.5 小结
2 LL(1)分析
2.1 LL(1)文法
2.2 LL(1)预测分析表
2.3 分析程序代码
2.4 程序运行截图
2.5 小结
3 算符优先分析
3.1 算符优先文法
3.2 算符优先关系表
3.3 分析程序代码
3.4 程序运行截图
3.5 小结
4 LR分析
4.1 LR文法
4.2 LR分析表
4.3 分析程序代码
4.4 程序运行截图
4.5 小结
5 转换成逆波兰表达式
5.1 分析程序代码
5.2 程序运行截图
5.3 小结
总结
参考文献：
目
录
2
1 正则表达式 ·································································································· 1
1.1 正则表达式 ··························································································1
1.2 确定化(化简)后的状态转换图 ·································································· 1
1.3 分析程序代码 ·······················································································1
1.4 程序运行截图 ·······················································································2
1.5 小结 ···································································································· 2
LL(1)分析 ··································································································· 3
2.1 LL(1)文法 ··························································································· 3
2.2 LL(1)预测分析表 ·················································································· 3
2.3 分析程序代码 ·······················································································3
2.4 程序运行截图 ·······················································································4
2.5 小结 ···································································································4
3 算符优先分析 ·······························································································5
3.1 算符优先文法 ·······················································································5
3.2 算符优先关系表 ··················································································· 5
3.3 分析程序代码 ·······················································································5
3.4 程序运行截图 ·······················································································7
3.5 小结 ···································································································7
LR 分析 ······································································································· 8
4.1 LR 文法 ······························································································ 8
4.2 LR 分析表 ··························································································· 8
4.3 分析程序代码 ·······················································································8
4.4 程序运行截图 ·······················································································9
4.5 小结 ···································································································9
5 转换成逆波兰表达式 ······················································································10
5.1 分析程序代码 ·······················································································10
5.2 程序运行截图 ·······················································································11
5.3 小结 ···································································································11
总结 ·············································································································· 11
4
参考文献： ····································································································· 11
1 正则表达式
1.1 正则表达式
(a|b)*(aa|bb)(a|b)*
1.2 确定化(化简)后的状态转换图
A
a
b
B
b
a
a
C
a
b
D
b
1.3 分析程序代码
#include
int exch[4][2]={1,2,3,2,1,3,3,3};
void judge(char *s)
{
int cur = 0, i = 0;
while(s[i])
{
if(s[i]-'a' > 1 || s[i] < 'a')
break;
cur=exch[cur][ s[i++] - 'a'];
}
if(s[i] == 0 && cur == 3)
printf ("%s √ Right！\n\n",s);
else printf ("%s × Wrong！\n\n",s);
}
void main()
{
char str[100];
while(1)
{
printf("有限自动机，判断是否符合 (a|b)*(aa|bb)(a|b)*\n");
printf("请输入字符串： ");
gets(str);
judge(str);
}
}
1
1.4 程序运行截图
1.输入正确的：
2.输入错误的：
1.5 小结
2
2
LL(1)分析
2.1 LL(1)文法
E→TE'
E'→+TE'|ε
T→FT'
T'→*FT'|ε
F→(E)|i
2.2 LL(1)预测分析表
+
*
E'→+TE'
T'→ε
T'→*FT'
i
E→TE'
T→FT'
F→i
(
E→TE'
T→FT'
F→(E)
E
E'
T
T'
F
)
#
E'→ε
E'→ε
T'→ε
T'→ε
2.3 分析程序代码
#include
#include
"12","","","12","","",
"","12+","","","-","-",
"34","","","34","","",
"","-","34*","","-","-",
"i","","",")0(","","",
};// 第一维 0-4 分别代表 EE'TT'F ，第二维 0-5 代表 i+*()# -代表ε
char data[5][6][10]={
int exch(char ch)
{
switch(ch)
{
case 'i': return 0;
case '+': return 1;
case '*': return 2;
case '(': return 3;
case ')': return 4;
case
default: return -1;
0 : return 5; //字符串结束标志代表‘#'.
}
}
void judge(char *s)
{
int tot=0,i=0,cur,k=exch(s[0]);
char sta[100];;
sta[++tot]='0';
while(tot>0)
{
cur = sta[tot] - '0';
if(s[i] == ' ')
// 去空格
3
// 推导出相同字符，出栈
else if(k < 0 || data[cur][k][0] == 0) // 踩空，或者出现非法字符
++tot,k=exch(s[++i]);
else if(cur+'0' == s[i])
k=exch(s[++i]);
break;
else if(data[cur][k][0] != '-')
{
strcpy(sta+tot,data[cur][k]);
tot+=strlen(data[cur][k]);
//不是ε，进栈继续推导
}
--tot;
}
if(tot==0)
printf("
printf("
else
}
int main()
{
judge(str);
return 0;
}
2.4 程序运行截图
%s √ Right！\n\n",s);
%s × Wrong！\n\n",s);
char str[100];
printf("判断符号串是否符合文法：\n\n\tE→TE'\n\t");
printf("E'→+TE'|ε\n\tT→FT'\n\tT'→*FT'|ε\n\tF→(E)|i\n\n");
while(printf("输入符号串: ")&&gets(str)&&str[0])
2.5 小结
4
3 算符优先分析
3.1 算符优先文法
E→T | E+T | E-T
T→F | T*F | T/F
F→(E) | i
3.2 算符优先关系表
-
＞
+
＞
+
-
*
/
(
)
i
#
＞
＞
＞
＜
＞
＞
＜
＞
＞
＞
＜
＞
＞
＜
*
＜
＜
＞
＞
＜
＞
＞
＜
/
＜
＜
＞
＞
＜
＞
＞
＜
(
＜
＜
＜
＜
＜
＜
)
＞
＞
＞
＞
＝
＞
＞
i
＜
＜
＜
＜
＜
＜
#
＞
＞
＞
＞
＞
＞
＝
3.3 分析程序代码
#include
#include
char com[8][8]={
'>', '>', '<', '<', '<', '>', '<', '>',
'>', '>', '<', '<', '<', '>', '<', '>',
'>', '>', '>', '>', '<', '>', '<', '>',
'>', '>', '>', '>', '<', '>', '<', '>',
'<', '<', '<', '<', '<', '=', '<', ' ',
'>', '>', '>', '>', '-', '>', '-', '>',
'>', '>', '>', '>', '-', '>', '-', '>',
'<', '<', '<', '<', '<', '-', '<', '=',
}; // 0-7 分别代表 + - * / ( ) i #
int exch(char ch)
{
switch(ch)
{
case '+': return 0;
case '-': return 1;
case '*': return 2;
case '/': return 3;
case '(': return 4;
case ')': return 5;
case 'i': return 6;
case 0 : return 7; //字符串结束标志代表‘#'.
default: return -1;
}
}
char expre[6][5]={"N+N","N-N","N*N","N/N","(=N)","i"};
//为了挽回因忽略语法变量而产生的错误，在规约时检验终结符是否带了应有的操作对象。
int confirm(char *sta,int t) //检验终结符是否带了应有的变量。
5
if(memcmp(expre[i],sta+n+1,sizeof(char)*(t-n))==0)
{
// 说明是有应有的操作对象，所以进行规约。
sta[n] = 'N';
return n;
{
int i,n=t;
while( n>0&&sta[n]!='<')
n--;
if(n>0)
for(i=0;i<6;i++)
}
return 0;
}
void judge(char *s)
{
char sta[100];
int tot=0,cur,m,k,i=0;
sta[++tot]=0;
while(tot>0)
{
m=tot;
do {
cur=exch(sta[m--]);
}while(cur<0);
while(s[i] == ' ')
// 要忽略变量，直接对终结符进行比较优先级。
// 跳过空格
i++;
k = exch(s[i]);
if( cur==k&&cur==7)
tot = 0;
// 规约成功，结束标记。
else if( k<0 || com[cur][k] == '-' ) // 踩空或者输入非法符
tot = -1;
else if( com[cur][k] != '>' )
{
// 遇到‘>'，准备规约
if(sta[tot] == 'N')
// 这里一个小问题就是变量 N 是要在'<'左边还是右边呢，这要取决
//于终结符是什么，左右两边有几个变量，不过针对本程序方法，只需全部放在右边。
{
sta[tot] = com[cur][k];
sta[++tot] = 'N';
}
else
sta[++tot] = com[cur][k];
sta[++tot] =s[i++];
}
else if( (tot = confirm( sta,tot ))==0 ) //检验终结符是否带了应有的变量。没有，就规约失败
tot = -1;
}
if(tot==0)
printf("
else printf("
}
int main()
{
judge(str);
return 0;
}
%s √ Right！\n\n",s);
%s × Wrong！\n\n",s);
6
char str[100];
printf("判断符号串是否符合文法：\n\n\tE→T | E+T | E-T\n\tT→F | T*F | T/F\n\tF→(E) | i\n\n");
while(printf("输入符号串: ")&&gets(str)&&str[0])
3.4 程序运行截图
可以输入几个易错的加以检验：
3.5 小结
7
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
