l 实验三 词法分析语法分析程序设计
．实验目
基掌握计算机语言词法分析程序语法分析程序设计方法
二．实验求容步骤
实验求：
1根正规式画出状态图
标识符：<字母>(<字母>|<数字字符>)*
关键字：if then else while do
十进制整数：0 | （1|2|3|4|5|6|7|8|9）（0|1|2|3|4|5|6|7|8|9）*
运算符分隔符：+ * > < ( )
2根状态图设计词法分析函数int scan( )键盘读入数分析出单词
3含+*运算算术表达式文法编写相应语法分析程序求LL(1)分析表实现id+id*id例进行测试：
E —＞ TE′
E′—＞ +TE′|ε
T —＞ FT′
T′—＞ *FT′|ε
F —＞（E）| id
实验步骤：
1根状态图设计词法分析算法
2采C++语言实现该算法
3调试程序：输入组单词检查输出结果
4编制定文法非递预测分析程序加测试
三．实验设备
计算机Windows 操作系统Visual C++ 程序集成环境
四． 实验原理
1 词法分析器读入输入串转换成语法分析器分析词法单元序列产生述语言单词序列语言单词符号种编码部值表：
单词符号
种编码
助记符
码值
DIM
IF
DO
STOP
END
标识符
常数（整）
+
*
**
（
）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
DIM
IF
DO
STOP
END
ID
INT
ASSIGN
PLUS
STAR
POWER
COMMA
LPAR
RPAR
部字符串
标准二进形式
语言点重限制：
首先关键字（IF﹑WHILE等）保留字谓保留字意思户作定义标示符例面写法绝禁止：IF（5）x
次关键字作保留字关键字作类特殊标示符处理说关键字专设应转换图（种编码）预先安排张表格中（表作保留字表）转换图识出标识符时查张表确定否关键字
次果关键字标识符常数间没确定运算符界符作间隔必须少空白符作间隔（时空白符完全没意义）例条件语句应写IF i>0 i 1绝写成IFi>0 i1者分析器条件IFI成标识符
语言单词符号状态转换图图：
2语法分析决定文法生成终结符串程
语法分析器 识加+ 减 * 方^ 括号（）操作数组成算术表达式文法：
E→E+T|ET|T
T→T*F|TF|F
F→P^F|P
p→(E)|i
算法：预测分析法递降分析法算符优先分析法LR分析法等
分析表格式：
id
+
*
(
)
E
E —＞ TE′
E —＞ TE′
E′
E′—＞ +TE′
E′—＞ ε
E′—＞ ε
T
T —＞ FT′
T —＞ FT′
T′
T′—＞ ε
T′—＞ *FT′
T′—＞ ε
T′—＞ ε
F
F —＞id
F —＞(E)
3中间代码生成器 产生述算术表达式中间代码（四元式序列）
五．实验代码结果
词法分析代码：
#include
#include
using namespace std
char prog[100]token[10]
char ch
int synpm0nrowsum0
char *rwtab[20]{dimifdostopend andbeginboolcasechar
falseforintnotorsetthentrueuntilwhile
}
void scaner()
{
for(n0n<9n++) token[n]NULL
chprog[p++]
while(ch＇ ＇)
{
chprog[p]
p++
}
if((ch>＇a＇&&ch<＇z＇)||(ch>＇A＇&&ch<＇Z＇))
{
m0
while((ch>＇0＇&&ch<＇9＇)||(ch>＇a＇&&ch<＇z＇)||(ch>＇A＇&&ch<＇Z＇))
{
token[m++]ch
chprog[p++]
}
token[m++]＇＼0＇
p
syn21
for(n0n<20n++)
{
if(strcmp(tokenrwtab[n])0)
{
synn+1
break
}
}
}
else if((ch>＇0＇&&ch<＇9＇))
{
{
sum0
while((ch>＇0＇&&ch<＇9＇))
{
sumsum*10+ch＇0＇
chprog[p++]
}
}
p
syn7+15
if(sum>32767)
syn1
}
else switch(ch)
{
case＇＇syn8+15token[0]chbreak
case＇+＇syn9+15token[0]chbreak
case＇*＇
m0
token[m++]ch
chprog[p++]
if(ch＇*＇)
{
syn11+15
token[m++]ch
}
else
{
syn10+15
p
}
break
case＇＇syn12+15token[0]chbreak
case＇(＇syn13+15token[0]chbreak
case＇)＇syn14+15token[0]chbreak
case＇#＇syn0token[0]chbreak
case＇<＇m0token[m++]ch
chprog[p++]
if(ch＇>＇)
{
syn17+15
token[m++]ch
}
else if(ch＇＇)
{
syn16+15
token[m++]ch
}
else
{
syn15+15
p
}
break
case＇>＇m0token[m++]ch
chprog[p++]
if(ch＇＇)
{
syn19+15
token[m++]ch
}
else
{
syn18+15
p
}
break
case＇＇m0token[m++]ch
chprog[p++]
if(ch＇＇)
{
syn21+15
token[m++]ch
}
else
{
syn20+15
p
}
break
case＇＇syn22+15token[0]chbreak
case＇＇syn23+15token[0]chbreak
case＇＇syn24+15token[0]chbreak
default syn1break
}
}
void main()
{
p0
row1
cout< cout<<词法分析< cout<<请输入段程序（#结束）
do
{
cinget(ch)
prog[p++]ch
}
while(ch＇#＇)
p0
cout< cout<<种编码 身值< do
{
scaner()
switch(syn)
{
case 22 cout<< (< case 1 cout<< Error in row< default cout<< (< }
}
while (syn0)
}
词法分析结果：
语法分析代码：
#include
#include
#include
using namespace std
typedef struct table 分析表存储结构
{
char m[100]
}table
table M[100][100] 定义分析表
typedef struct stacknode 定义栈元素节点 (带头结点（空）)
{
char data
struct stacknode *next
}stackk
void initlink(stackk *&s) 初始化新栈
{
s(stackk *)malloc(sizeof(stackk))
s>nextNULL
}
void poplink(stackk *&s) 顶元素出栈
{
stackk *pchar v
if(s>nextNULL)
{
ps>next
vp>data
s>nextp>next
}
free(p)
}
void pushlink(stackk *&schar x) 新 元 素 入 栈
{
stackk *p
p(stackk *)malloc(sizeof(stackk))
p>datax
p>nexts>next
s>nextp
}
void display(stackk *s) 印 现实显示 栈元素
{
stackk *p
int i0j
char st[100]
ps>next
while(pNULL)
{
st[i++]p>data
pp>next
}
for(ji1j>0j)
printf(cst[j])
for(j0j<16ij++) 印 齐格式
printf(c＇ ＇)
}
char gettop(stackk *s) 返 回 栈 顶 元 素 值
{
if(s>nextNULL)
return 0
else
return s>next>data
}
int find(char cchar array[]) 查找函数
{
int i
int flag0
for(i0i<100i++)
{
if(carray[i])
flag1
}
return flag
}
int location(char cchar array[]) 定位函数指出字符位置
{
int i
for(i0i<100i++)
{
if(carray[i])
return i
}
}
void error() 出错函数定义
{
printf(15c出错＼n＇ ＇)
}
void analyse(char Vn[]char Vt[])
{
int ijmpqlengthth
char wX
char str[100]
opt0
scanf(sstr)
for(i0i {
if(find(str[i]Vt))
{
printf(输入字符串误请重新输入)
goto opt0
break
}
}
stackk *st
initlink(st)
pushlink(st＇#＇)
pushlink(stVn[0]) #识符号入栈
j0
h1
wstr[0]
printf(步骤12c分析栈24c剩余输入串12c产生式＼n＇ ＇＇ ＇＇ ＇)
opt1
printf(16dh) 显示步骤
h++
display(st) 显示分析栈中容
Xgettop(st) 托栈顶符号放入X
poplink(st)
for(int k0k<14+jk++) 印齐格式
printf(c＇ ＇)
for(tjt {
printf(cstr[t]) 显示剩余字符串
}
if(find(XVt)&& X＇#＇) 分析栈栈顶元素剩余输入串第元素相较
{
if(Xw)
{
printf(15c匹配＼nX)
j++
wstr[j]
goto opt1
}
else
error()
}
else
{
if(X＇#＇)
{
if(Xw)
{
printf(8c该文法句子＼n＇ ＇)
}
else
error()
}
else
{
plocation(XVn)
qlocation(wVt)
char *S1null*S2NULL
if(strcmp(M[p][q]mS1)0||strcmp(M[p][q]mS2)0) 查找产生式
error()
else
{
char str0[100]
strcpy(str0M[p][q]m)
printf(15c>s＼nXstr0) 显示应产生式
if(strcmp(str0)0)
goto opt1
else
{
lengthstrlen(str0) 逆序进栈
for(mlength1m>0m)
{
pushlink(ststr0[m])
}
goto opt1
}
}
}
}
}
int main()
{
int iknr
char Vn[100]Vt[100]select
printf(意输入LL(1)文法分析表判断验证字符串否该文法句子 ＼n)
printf(出分析演示程 ＼n)
printf(******************************************************************＼n)
opt2
printf(请输入终结符（#号表示结束 ）Vt[i]＼n)
for(i0i<100i++)
{
scanf(c&Vt[i])
if(Vt[i]＇#＇)
{
ri
break
}
}
printf(请输入非终结符数＼n)
scanf(d&n)
getchar()
for (i0i {
printf(请输入非终结符Vn[d]＼ni)
scanf(c&Vn[i])
getchar()
printf(请输入非终结符应终结符产生式右部(nullNULL表示出错表示空串)＼n)
for(k0k {
scanf(sM[i][k]m)
getchar()
}
}
opt3
printf(请输入分析字符串#结束＼n)
analyse(Vn Vt)
printf(请选择＼n)
printf(1 输入字符串＼n)
printf(2 输入新分析表＼n)
printf(0 退 出＼n)
opt4
cin>>select
switch(select)
{
case ＇1＇ {goto opt3break}
case ＇2＇ {goto opt2}
case ＇0＇ {break}
default {printf(输入错误请重新选择)
goto opt4
break}
}
return 0
}
语法分析结果：
六．实验结
通实验解词法分析语法分析二者：
1词法规通常非常简单必动强文法描述
2词法记号正规式文关文法提供更简洁易理解定义
3正规式动构造出效词法分析器文法难构造词法分析器
4语言语法结构分成词法非词法两部分编译器前端模块划分提供方便途径
目
<<编译技术>>理实践重课程实验课综合运二年级学门课程容完成型编译程序巩固加强词法分析语法分析语义分析代码生成报错处理等理认识理解培养学生完整系统独立分析设计力进步培养学生独立编程力
二务求
基求：
1． 词法分析器 产生述语言单词序列
语言单词符号种编码部值表：
单词符号
种编码
助记符
码值
DIM
IF
DO
STOP
END
标识符
常数（整）
+
*
**
（
）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
DIM
IF
DO
STOP
END
ID
INT
ASSIGN
PLUS
STAR
POWER
COMMA
LPAR
RPAR
部字符串
标准二进形式
语言点重限制：
首先关键字（IF﹑WHILE等）保留字谓保留字意思户作定义标示符例面写法绝禁止：
IF（5）x
次关键字作保留字关键字作类特殊标示符处理说关键字专设应转换图（种编码）预先安排张表格中（表作保留字表）转换图识出标识符时查张表确定否关键字
次果关键字标识符常数间没确定运算符界符作间隔必须少空白符作间隔（时空白符完全没意义）例条件语句应写
IF i>0 i 1
绝写成
IFi>0 i1
者分析器条件IFI成标识符
语言单词符号状态转换图图：
2． 语法分析器 识加+ 减 * 方^ 括号（）操作数组成算术表达式文法：
E→E+T|ET|T
T→T*F|TF|F
F→P^F|P
p→(E)|i
算法：预测分析法递降分析法算符优先分析法LR分析法等
3． 中间代码生成器 产生述算术表达式中间代码（四元式序列）
三实现程说明
出题目详细算法描述数结构函数说明流程图
1词法分析器流程图
2语法分析器程序图
3中间代码生成器流程图：
四源程序清单
词法分析器
#include stdafxh
#include Wordh
构造函数数成员初始化关键字运算符读入
WordWord()
{开关键字文件
fstream keywordfile(keywordtxt)
if(keywordfile)
{
cout< system(pause)
exit(1)
}
设置时变量关键字符号文件中容存储
string tempword
int tempencode
string tempre
int tempvalue
开始读关键字文件
while((keywordfileeof()))
{ keywordfile>>tempword>>tempencode>>tempre>>tempvalue
keywordlistpush_back(tempword)
keywordencodepush_back(tempencode)
keywordrepush_back(tempre)
keywordcodevaluepush_back(tempvalue)
}
关闭关键字文件
keywordfileclose()
for(int i0i {cout< }
fstream signwordfile(signwordtxt)
if(signwordfile)
{ cout< system(pause)
exit(1)
}
开始读符号文件
while((signwordfileeof()))
{
signwordfile>>tempword>>tempencode>>tempre>>tempvalue
signlistpush_back(tempword)
signencodepush_back(tempencode)
signrepush_back(tempre)
signcodevaluepush_back(tempvalue)
}
关闭符号文件
signwordfileclose()
for(int i0i {cout< }
}
token中字符串character中字符连接作token中新字符串
void Wordconcatentation()
{for(int i0i<100i++)
{if(token[i]NULL)
{token[i]s
break
}
}
}
判断character中字符否字母数字布尔函数返回true否返回false
bool Wordletter()
{ if(s<＇z＇ && s>＇a＇ )
return true
else if(s<＇Z＇ && s>＇A＇)
return true
else
return false
}
bool Worddigit()
{ if(s<＇9＇ && s>＇0＇)
return true
return false
}
token数组中字符串中前五项(判否保留字)保留字返回编码
int Wordreserve()
{
int leng记录token数组中单词长度
for(int i0i<100i++)计算token数组中单词长度
{
if(token[i]NULL)
{
lengi
break
}
}
for(int i0i {
for(int j0j {
if(keywordlist[i][j]token[j])某字符等终止次循环
break
if(j+1keywordlist[i]length())较字符全部相等判断两者否长度相等
{
if(lengkeywordlist[i]length())
{return i+1}
else
return 0
}
}
}
return 0
}
标识符登录符号表中常数登录常数表中
void Wordbuildlist()
{设置时变量标识符助记符保存
string tempword
int tempencode
string tempre标识符助记
int tempvalue
int tempconstre常数助记
stoken[0]
if(letter())第字符果字母标识符登录符号表中
{ fstream chartostring(converttxt)
if(chartostring)
{
cout< system(pause)
}
for(int i0i<100i++)
{
if(token[i]NULL)
break
else
{chartostring< }
chartostring< chartostringclose()
chartostringopen(converttxt)
if(chartostring)
{
cout< system(pause)
}
chartostring>>tempre
chartostringclose()
indentityrepush_back(tempre)
tempword标识符
tempencode6
tempvalueindentityresize()
indentitylistpush_back(tempword)
indentityencodepush_back(tempencode)
indentitycodevaluepush_back(tempvalue)
fstream indentityfile(indentitywordtxt)
if(indentityfile)
{ cout< system(pause)
}
先文件指针移写入endl
indentityfileseekg(0iosend)
indentityfile< indentityfileseekg(0iosend)
indentityfile< indentityfileclose()
}
elsetoken中存储常数
{
token中字符数字转换int类型
fstream chartoint(converttxt)
if(chartoint)
{
cout< system(pause)
}
for(int i0i<100i++)
{ if(token[i]NULL)
break
else
{
chartoint< }
}
chartoint< chartointclose()
chartointopen(converttxt)
if(chartoint)
{ cout< system(pause)
exit(1)
}
chartoint>>tempconstre
chartointclose()
constlistpush_back(tempword)
tempword常数
tempencode7
tempvalueindentityresize()
constencodepush_back(tempencode)
constrepush_back(tempconstre)
constvaluepush_back(tempvalue)
fstream constdigit(constdigittxt)
if(constdigit)
{
cout< system(pause)
exit(1)
}
先文件指针移写入endl
constdigitseekg(0iosend)
constdigit< constdigitseekg(0iosend)
constdigit< constdigitclose()
cout< }
}
出现非法字符显示错误信息
void Worderror()
{
cout< system(pause)
}
void Wordsigninfor()
{
token数组中字符串中前五项(判否保留字)保留字返回编码
int leng记录token数组中单词长度
for(int i0i<100i++)计算token数组中单词长度
{
if(token[i]NULL)
{
lengi
break
}
}
for(int i0i {
for(int j0j {
if(signlist[i][j]token[j])某字符等终止次循环
break
if(j+1signlist[i]length())较字符全部相等判断两者否长度相等
{
if(lengsignlist[i]length())
{
cout< }
}
}
}
}
词法分析函数
void Wordrun()
{
cout< fstream file(wordtxt)
if(file)
{
cout< system(pause)
exit(1)
}
fileunsetf(iosskipws)
while(s＇#＇ && fileeof())
{
for(int i0i<100i++)
{
token[i]NULL
}
file>>s
while(s＇ ＇)
{
file>>s
}
switch(s)
{
case ＇a＇
case ＇b＇
case ＇c＇
case ＇d＇
case ＇e＇
case ＇f＇
case ＇g＇
case ＇h＇
case ＇i＇
case ＇j＇
case ＇k＇
case ＇l＇
case ＇m＇
case ＇n＇
case ＇o＇
case ＇p＇
case ＇q＇
case ＇r＇
case ＇s＇
case ＇t＇
case ＇u＇
case ＇v＇
case ＇w＇
case ＇x＇
case ＇y＇
case ＇z＇
while(letter()||digit())
{
concatentation()前读入字符送入token数组
file>>s继续读字符直字符数字字母止
}
扫描指针回退字符
fileseekg(1ioscur)
codereserve()
if(code)
{ buildlist()}
else
{
cout< }
break
case ＇0＇
case ＇1＇
case ＇2＇
case ＇3＇
case ＇4＇
case ＇5＇
case ＇6＇
case ＇7＇
case ＇8＇
case ＇9＇
while(digit())
{
concatentation()前读入字符送入token数组
file>>s继续读字符直字符数字止
}
扫描指针回退字符
fileseekg(1ioscur)
buildlist()
break
case ＇+＇
concatentation()
signinfor()
break
case ＇＇
concatentation()
signinfor()
break
case ＇*＇
concatentation()
signinfor()
break
case ＇<＇
concatentation()
file>>s
if(s＇＇)
{扫描指针回退字符
fileseekg(1ioscur)
signinfor()
}
else
{
concatentation()
signinfor()
}
break
case ＇＇
concatentation()
file>>s
if(s＇＇)
{
扫描指针回退字符
fileseekg(1ioscur)
signinfor()
}
else
{
concatentation()
signinfor()
}
break
case ＇＇
concatentation()
signinfor()
break
case ＇#＇
cout< cout< cout< system(pause)
exit(1)
default
error()
}
}
fileclose()
}
void main()
{
Word word
wordrun()
system(pause)
}
运行结果：
语法分析器 源程序：
#include
#include
#include
typedef struct
{
char R
char r
int flag
}array
typedef struct
{
char E
char e
}charLode
typedef struct
{
charLode *base
int top
}charstack
char str[80][80]arr[80][80]brr[80][80]
array F[20]
int mkkppppFF1
char r[10]
int crr[20][20]FLAG0
char ccrr1[1][20]ccrr2[20][1]
void Initstack(charstack &s)定义栈
{
sbasenew charLode[20]
stop1
}
void push(charstack &scharLode w)
{
stop++
sbase[stop]EwE
sbase[stop]ewe
}
void pop(charstack &scharLode &w)
{
wEsbase[stop]E
wesbase[stop]e
stop
}
int IsEmpty(charstack s)
{
if(stop1)
return 1
else return 0
}
int IsLetter(char ch)
{
if(ch>＇A＇&&ch<＇Z＇)
return 1
else return 0
}
judge1判断否算符文法：产生式中含两相继非终结符算符文法
int judge1(int n)
{
int j3flag0
for(int i0i while(str[i][j]＇＼0＇)
{
char astr[i][j]
char bstr[i][j+1]
if(IsLetter(a)&&IsLetter(b))
{flag1break}
else j++
}
if(flag1)
return 0
else
return 1
}
judge2判断文法G否算符优先文法：算符文法文法中含空字终结符优先级唯算符优先文法
void judge2(int n)
{
for(int i0i if(str[i][3]＇~＇||judge1(n)0||FLAG1)＇~＇代表空字
{cout<<文法G算符优先文法< if(i>n)
cout<<文法G算符优先文法<}
search1查存放终结符数组r中否含重复终结符
int search1(char r[]int kkchar a)
{
for(int i0i if(r[i]a)
break
if(ikk) return 0
else return 1
}
createF函数F数组存放终结符非终结符组合值队标志位0F数组结构体
void createF(int n)
{
int k0i1char g
char t[10]t数组存放非终结符
t[0]str[0][0]
while(i{
if(t[k]str[i][0])
{k++t[k]str[i][0]gt[k]i++}
else i++
}
kk0
char c
for(i0i{ int j3
while(str[i][j]＇＼0＇)
{
cstr[i][j]
if(IsLetter(c)0)
{
if(search1(rkkc))
r[kk]ckk++r数组存放终结符
}
j++
}
}
m0
for(i0i for(int j0j {
F[m]Rt[i]
F[m]rr[j]
F[m]flag0
m++
}
}
search函数F数组中寻找终结符非终结符标志位值1
void search(charLode w)
{
for(int i0i if(F[i]RwE&&F[i]rwe)
{F[i]flag1break}
}
void FirstVT(int n)求FirstVT
{
charstack sta
charLode w
int i0
Initstack(sta)
while(i{
int k3
wEstr[i][0]
char astr[i][k]
char bstr[i][k+1]
if(IsLetter(a))产生式选式第字符终结符情况
{
wea
push(staw)
search(w)
i++
}
else if(IsLetter(a)&&b＇＼0＇&&IsLetter(b))产生式选式第字符非终结符情况
{
web
push(staw)
search(w)
i++
}
else i++
}
charLode ww
while(IsEmpty(sta))
{
pop(staww)
for(i0i {
wEstr[i][0]
if(str[i][3]wwE&&str[i][4]＇＼0＇)
{
wewwe
push(staw)
search(w)
break
}
}
}
p0int k1i1
while(i{
if(F[i1]flag1)
{
arr[p][0]F[i1]R
arr[p][k]F[i1]r
}
while(F[i]flag0&&i i++
if(F[i]flag1)
{
if(F[i]Rarr[p][0])
k++
else {arr[p][k+1]＇＼0＇p++k1}
i++
}
}
}
void LastVT(int n)求LastVT
{
charstack sta
charLode w
for(int i0i F[i]flag0
i0
Initstack(sta)
while(i{
int kstrlen(str[i])
wEstr[i][0]
char astr[i][k1]
char bstr[i][k2]
if(IsLetter(a))
{
wea
push(staw)
search(w)
i++
}
else if(IsLetter(a)&&IsLetter(b))
{
web
push(staw)
search(w)
i++
}
else i++
}
charLode ee
while(IsEmpty(sta))
{
pop(staee)
for(i0i {
wEstr[i][0]
if(str[i][3]eeE&&str[i][4]＇＼0＇)
{
weeee
push(staw)
search(w)
}
}
}
int k1i1
ppp0
while(i{
if(F[i1]flag1)
{
brr[ppp][0]F[i1]R
brr[ppp][k]F[i1]r
}
while(F[i]flag0&&i i++
if(F[i]flag1)
{
if(F[i]Rarr[ppp][0])
k++
else {brr[ppp][k+1]＇＼0＇ppp++k1}
i++
}
}
}
void createYXB(int n)构造优先表
{
int ij
for(j1j ccrr1[0][j]r[j1]
for( i1i ccrr2[i][0]r[i1]
for(i1i for(j1j crr[i][j]0
int I0J3
while(I {
if(str[I][J+1]＇＼0＇)
{I++J3}
else
{
while(str[I][J+1]＇＼0＇)
{
char aastr[I][J]
char bbstr[I][J+1]
if(IsLetter(aa)&&IsLetter(bb))优先等情况1值表示等
{
for(i1i {
if(ccrr2[i][0]aa)
break
}
for(j1j {
if(ccrr1[0][j]bb)
break
}
if(crr[i][j]0)
crr[i][j]1
else {FLAG1In+1}
J++
}
if(IsLetter(aa)&&IsLetter(bb)&&str[I][J+2]＇＼0＇&&IsLetter(str[I][J+2]))优先等情况
{
for(i1i {
if(ccrr2[i][0]aa)
break
}
for(int j1j {
if(ccrr1[0][j]str[I][J+2])
break
}
if(crr[i][j]0)
crr[i][j]1
else {FLAG1In+1}
}
if(IsLetter(aa)&&IsLetter(bb))优先情况2值表示
{
for(i1i {
if(aaccrr2[i][0])
break
}
for(j0j {
if(bbarr[j][0])
break
}
for(int mm1arr[j][mm]＇＼0＇mm++)
{
for(int pp1pp {
if(ccrr1[0][pp]arr[j][mm])
break
}
if(crr[i][pp]0)
crr[i][pp]2
else {FLAG1In+1}
}
J++
}
if(IsLetter(aa)&&IsLetter(bb))优先情况3值表示
{
for(i1i {
if(ccrr1[0][i]bb)
break
}
for(j0j {
if(aabrr[j][0])
break
}
for(int mm1brr[j][mm]＇＼0＇mm++)
{
for(int pp1pp {
if(ccrr2[pp][0]brr[j][mm])
break
}
if(crr[pp][i]0)
crr[pp][i]3
else {FLAG1In+1}
}
J++
}
}
}
}
}
judge3返回约程中两非终结符相较值
int judge3(char schar a)
{
int i1j1
while(ccrr2[i][0]s)
i++
while(ccrr1[0][j]a)
j++
if(crr[i][j]3) return 3
else if(crr[i][j]2)
return 2
else if(crr[i][j]1)
return 1
else return 0
}
void print(char s[]char STR[][20]int qint uint iiint k)印约程
{
cout<for(int i0i cout<cout<<
for(iqi cout<cout<<
}
void process(char STR[][20]int ii)输入字符串进行约程
{
cout<<步骤<< <<符号栈<< <<输入串<< <<动作<int k0q0u0bij
char s[40]a
s[k]＇#＇
print(sSTRquiik)
cout<<预备<k++u++
s[k]STR[0][q]
q++
print(sSTRquiik)
cout<<移进<while(q{
aSTR[0][q]
if(IsLetter(s[k])) jk
else jk1
bjudge3(s[j]a)
if(b3)情况进行约
{
while(IsLetter(s[j1]))
j
for(iji s[i]＇＼0＇
kjs[k]＇N＇u++
print(sSTRquiik)
cout<<约< }
else if(b2||b1)等情况移进
{
k++
s[k]a
u++
q++
print(sSTRquiik)
if(s[0]＇#＇&&s[1]＇N＇&&s[2]＇#＇)
cout<<接受< else cout<<移进< }
else
{cout<<出错<}
if(s[0]＇#＇&&s[1]＇N＇&&s[2]＇#＇)
cout<<约成功<else cout<<约失败<}
void main()
{
int nij
cout<<请输入定义文法G产生式数n
cin>>n
for(i0i{
gets(str[i])
jstrlen(str[i])
str[i][j]＇＼0＇
}
str[i][0]＇Q＇
str[i][1]＇＇
str[i][2]＇>＇
str[i][3]＇#＇
str[i][4]str[0][0]
str[i][5]＇#＇
str[i][6]＇＼0＇
cout<<定义产生式< for(i0i cout<if(judge1(n)0)判断文法G否算符文法
cout<<文法G算符文法<if(judge1(n)1)
{
cout<<文法G算符文法< createF(n)
FirstVT(n)
LastVT(n)
createYXB(n)
}
judge2(n)判断文法G否算符优先文法
if(FLAG0)
{
for(i0i {
cout< for(int l1arr[i][l+1]＇＼0＇l++)
cout< cout< }
cout< for(i0i {
cout< for(int l1brr[i][l+1]＇＼0＇l++)
cout< cout< }
cout< cout<<优先表< for(i1i {
cout<<
cout< }
cout< for(i1i {
cout< for(j1j {
if(crr[i][j]0)
cout<<
else if(crr[i][j]1)
cout<<
else if(crr[i][j]2)
cout<<<
else if(crr[i][j]3)
cout<<>
cout<<
}
cout< }
}
if(FF1)
{
char STR[1][20]
cout<<请输入规约字符串<gets(STR[0])
int iistrlen(STR[0])
STR[0][ii]＇#＇
cout<<面规约程<process(STRii)
}
}
运算结果：
中间代码生成器源程序：
*
表达式生成四元式
递子程序法
*
#include
#include
#include
#include
#include
#define STACK_INIT_SIZE 50
#define STACKINCREMENT 5
#define ERROR 0
#define OVERFLOW 2
#define TRUE 1
#define FALSE 0
#define OK 1
#define NULL 0
void sub_E()
void sub_F()
void sub_T()
void sub_G()
void GEQ(char m)
void PRINT()
typedef struct Stack
{
char *base
char *top
int stacksize
}Stack
int num0
char QT[10][4]T＇A＇c
struct Stack SEM
struct initStack(Stack s)
{
sbase(char *)malloc(STACK_INIT_SIZE*sizeof(char))
if(sbase)
exit(OVERFLOW)
stopsbase
sstacksizeSTACK_INIT_SIZE
return OK
}
初始化堆栈
char pop(Stack &s)
{
char e
if(stopsbase)
{printf(栈中已元素)
exit(ERROR)
}
e*stop
return e
}
出栈
struct push(Stack &schar e)
{
if(stopsbase>sstacksize)
{
sbase(char *)realloc(sbase(sstacksize+STACKINCREMENT)*sizeof(char))
if(sbase)
exit(OVERFLOW)
stopsbase+sstacksize
sstacksize+STACKINCREMENT
}
*stop++e
return OK
}
入栈
void main()
{
initStack(SEM)
printf(表达式应写字母运算符括号组成＼#＼结束＼n)
printf(请输入表达式)
cgetchar()
sub_E()
if(c＇#＇)
PRINT()
else
{
printf(结束符漏写运算符)
exit(0)
}
getchar()
}
void sub_E()
{
sub_T()
R1 if(c＇+＇)
{
cgetchar()
sub_T()
GEQ(＇+＇)
goto R1
}
else if(c＇＇)
{
cgetchar()
sub_T()
GEQ(＇＇)
goto R1
}
else
}
void sub_T()
{
sub_G()
R4 if(c＇*＇)
{ cgetchar()
sub_F()
GEQ(＇*＇)
goto R4
}
else if(c＇＇)
{
cgetchar()
sub_F()
GEQ(＇＇)
goto R4
}
}
void sub_F()
{
sub_G()
R5 if(c＇^＇)
{
cgetchar()
sub_G()
GEQ(＇^＇)
goto R5
}
}
void sub_G()
{
if(c>＇a＇&&c<＇z＇)
{
push(SEMc)
cgetchar()
}
else if(c＇(＇)
{
cgetchar()
sub_E()
if(c＇)＇)
cgetchar()
else
{
printf(括号匹配)
exit(0)
}
}
else
{
printf(非法符号)
exit(0)
}
}
void GEQ(char m)
{
QT[num][0]m
QT[num][2]pop(SEM)
QT[num][1]pop(SEM)
QT[num][3]T
push(SEMT)
num++
T++
}
void PRINT()
{
printf(您输入表达式应四元式＼n)
for(int i0i{
printf(()
printf(cQT[i][0])
if(QT[i][1]<＇Z＇&&QT[i][1]>＇A＇)
printf(＼tcd＇t＇QT[i][1]＇A＇+1)
else
printf(＼tcQT[i][1])
if(QT[i][2]<＇Z＇&&QT[i][1]>＇A＇)
printf(＼tcd＇t＇QT[i][2]＇A＇+1)
else
printf(＼tcQT[i][2])
if(QT[i][3]<＇Z＇&&QT[i][1]>＇A＇)
printf(＼tcd＇t＇QT[i][3]＇A＇+1)
else
printf(＼tcQT[i][3])
printf()＼n)
}
}
六总结
谈谈收获体会
1 通次实验词法分析器进步解理知识应实验中重新熟悉C语言相关容加深C语言知识深化途理解通次语义分析实验 高级语言学更深认识 解更透彻
2 解高级语言转化目标代码汇编指令程学起作编程帮助 次实验然完成简单程序程序框架课出组织程序结构深入确学加深编译原理理解掌握编译程序实现方法技术巩固前面学知识
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
．实验目
基掌握计算机语言词法分析程序语法分析程序设计方法
二．实验求容步骤
实验求：
1根正规式画出状态图
标识符：<字母>(<字母>|<数字字符>)*
关键字：if then else while do
十进制整数：0 | （1|2|3|4|5|6|7|8|9）（0|1|2|3|4|5|6|7|8|9）*
运算符分隔符：+ * > < ( )
2根状态图设计词法分析函数int scan( )键盘读入数分析出单词
3含+*运算算术表达式文法编写相应语法分析程序求LL(1)分析表实现id+id*id例进行测试：
E —＞ TE′
E′—＞ +TE′|ε
T —＞ FT′
T′—＞ *FT′|ε
F —＞（E）| id
实验步骤：
1根状态图设计词法分析算法
2采C++语言实现该算法
3调试程序：输入组单词检查输出结果
4编制定文法非递预测分析程序加测试
三．实验设备
计算机Windows 操作系统Visual C++ 程序集成环境
四． 实验原理
1 词法分析器读入输入串转换成语法分析器分析词法单元序列产生述语言单词序列语言单词符号种编码部值表：
单词符号
种编码
助记符
码值
DIM
IF
DO
STOP
END
标识符
常数（整）
+
*
**
（
）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
DIM
IF
DO
STOP
END
ID
INT
ASSIGN
PLUS
STAR
POWER
COMMA
LPAR
RPAR
部字符串
标准二进形式
语言点重限制：
首先关键字（IF﹑WHILE等）保留字谓保留字意思户作定义标示符例面写法绝禁止：IF（5）x
次关键字作保留字关键字作类特殊标示符处理说关键字专设应转换图（种编码）预先安排张表格中（表作保留字表）转换图识出标识符时查张表确定否关键字
次果关键字标识符常数间没确定运算符界符作间隔必须少空白符作间隔（时空白符完全没意义）例条件语句应写IF i>0 i 1绝写成IFi>0 i1者分析器条件IFI成标识符
语言单词符号状态转换图图：
2语法分析决定文法生成终结符串程
语法分析器 识加+ 减 * 方^ 括号（）操作数组成算术表达式文法：
E→E+T|ET|T
T→T*F|TF|F
F→P^F|P
p→(E)|i
算法：预测分析法递降分析法算符优先分析法LR分析法等
分析表格式：
id
+
*
(
)
E
E —＞ TE′
E —＞ TE′
E′
E′—＞ +TE′
E′—＞ ε
E′—＞ ε
T
T —＞ FT′
T —＞ FT′
T′
T′—＞ ε
T′—＞ *FT′
T′—＞ ε
T′—＞ ε
F
F —＞id
F —＞(E)
3中间代码生成器 产生述算术表达式中间代码（四元式序列）
五．实验代码结果
词法分析代码：
#include
#include
using namespace std
char prog[100]token[10]
char ch
int synpm0nrowsum0
char *rwtab[20]{dimifdostopend andbeginboolcasechar
falseforintnotorsetthentrueuntilwhile
}
void scaner()
{
for(n0n<9n++) token[n]NULL
chprog[p++]
while(ch＇ ＇)
{
chprog[p]
p++
}
if((ch>＇a＇&&ch<＇z＇)||(ch>＇A＇&&ch<＇Z＇))
{
m0
while((ch>＇0＇&&ch<＇9＇)||(ch>＇a＇&&ch<＇z＇)||(ch>＇A＇&&ch<＇Z＇))
{
token[m++]ch
chprog[p++]
}
token[m++]＇＼0＇
p
syn21
for(n0n<20n++)
{
if(strcmp(tokenrwtab[n])0)
{
synn+1
break
}
}
}
else if((ch>＇0＇&&ch<＇9＇))
{
{
sum0
while((ch>＇0＇&&ch<＇9＇))
{
sumsum*10+ch＇0＇
chprog[p++]
}
}
p
syn7+15
if(sum>32767)
syn1
}
else switch(ch)
{
case＇＇syn8+15token[0]chbreak
case＇+＇syn9+15token[0]chbreak
case＇*＇
m0
token[m++]ch
chprog[p++]
if(ch＇*＇)
{
syn11+15
token[m++]ch
}
else
{
syn10+15
p
}
break
case＇＇syn12+15token[0]chbreak
case＇(＇syn13+15token[0]chbreak
case＇)＇syn14+15token[0]chbreak
case＇#＇syn0token[0]chbreak
case＇<＇m0token[m++]ch
chprog[p++]
if(ch＇>＇)
{
syn17+15
token[m++]ch
}
else if(ch＇＇)
{
syn16+15
token[m++]ch
}
else
{
syn15+15
p
}
break
case＇>＇m0token[m++]ch
chprog[p++]
if(ch＇＇)
{
syn19+15
token[m++]ch
}
else
{
syn18+15
p
}
break
case＇＇m0token[m++]ch
chprog[p++]
if(ch＇＇)
{
syn21+15
token[m++]ch
}
else
{
syn20+15
p
}
break
case＇＇syn22+15token[0]chbreak
case＇＇syn23+15token[0]chbreak
case＇＇syn24+15token[0]chbreak
default syn1break
}
}
void main()
{
p0
row1
cout<
do
{
cinget(ch)
prog[p++]ch
}
while(ch＇#＇)
p0
cout<
{
scaner()
switch(syn)
{
case 22 cout<< (<
}
while (syn0)
}
词法分析结果：
语法分析代码：
#include
#include
#include
using namespace std
typedef struct table 分析表存储结构
{
char m[100]
}table
table M[100][100] 定义分析表
typedef struct stacknode 定义栈元素节点 (带头结点（空）)
{
char data
struct stacknode *next
}stackk
void initlink(stackk *&s) 初始化新栈
{
s(stackk *)malloc(sizeof(stackk))
s>nextNULL
}
void poplink(stackk *&s) 顶元素出栈
{
stackk *pchar v
if(s>nextNULL)
{
ps>next
vp>data
s>nextp>next
}
free(p)
}
void pushlink(stackk *&schar x) 新 元 素 入 栈
{
stackk *p
p(stackk *)malloc(sizeof(stackk))
p>datax
p>nexts>next
s>nextp
}
void display(stackk *s) 印 现实显示 栈元素
{
stackk *p
int i0j
char st[100]
ps>next
while(pNULL)
{
st[i++]p>data
pp>next
}
for(ji1j>0j)
printf(cst[j])
for(j0j<16ij++) 印 齐格式
printf(c＇ ＇)
}
char gettop(stackk *s) 返 回 栈 顶 元 素 值
{
if(s>nextNULL)
return 0
else
return s>next>data
}
int find(char cchar array[]) 查找函数
{
int i
int flag0
for(i0i<100i++)
{
if(carray[i])
flag1
}
return flag
}
int location(char cchar array[]) 定位函数指出字符位置
{
int i
for(i0i<100i++)
{
if(carray[i])
return i
}
}
void error() 出错函数定义
{
printf(15c出错＼n＇ ＇)
}
void analyse(char Vn[]char Vt[])
{
int ijmpqlengthth
char wX
char str[100]
opt0
scanf(sstr)
for(i0i
if(find(str[i]Vt))
{
printf(输入字符串误请重新输入)
goto opt0
break
}
}
stackk *st
initlink(st)
pushlink(st＇#＇)
pushlink(stVn[0]) #识符号入栈
j0
h1
wstr[0]
printf(步骤12c分析栈24c剩余输入串12c产生式＼n＇ ＇＇ ＇＇ ＇)
opt1
printf(16dh) 显示步骤
h++
display(st) 显示分析栈中容
Xgettop(st) 托栈顶符号放入X
poplink(st)
for(int k0k<14+jk++) 印齐格式
printf(c＇ ＇)
for(tjt
printf(cstr[t]) 显示剩余字符串
}
if(find(XVt)&& X＇#＇) 分析栈栈顶元素剩余输入串第元素相较
{
if(Xw)
{
printf(15c匹配＼nX)
j++
wstr[j]
goto opt1
}
else
error()
}
else
{
if(X＇#＇)
{
if(Xw)
{
printf(8c该文法句子＼n＇ ＇)
}
else
error()
}
else
{
plocation(XVn)
qlocation(wVt)
char *S1null*S2NULL
if(strcmp(M[p][q]mS1)0||strcmp(M[p][q]mS2)0) 查找产生式
error()
else
{
char str0[100]
strcpy(str0M[p][q]m)
printf(15c>s＼nXstr0) 显示应产生式
if(strcmp(str0)0)
goto opt1
else
{
lengthstrlen(str0) 逆序进栈
for(mlength1m>0m)
{
pushlink(ststr0[m])
}
goto opt1
}
}
}
}
}
int main()
{
int iknr
char Vn[100]Vt[100]select
printf(意输入LL(1)文法分析表判断验证字符串否该文法句子 ＼n)
printf(出分析演示程 ＼n)
printf(******************************************************************＼n)
opt2
printf(请输入终结符（#号表示结束 ）Vt[i]＼n)
for(i0i<100i++)
{
scanf(c&Vt[i])
if(Vt[i]＇#＇)
{
ri
break
}
}
printf(请输入非终结符数＼n)
scanf(d&n)
getchar()
for (i0i
printf(请输入非终结符Vn[d]＼ni)
scanf(c&Vn[i])
getchar()
printf(请输入非终结符应终结符产生式右部(nullNULL表示出错表示空串)＼n)
for(k0k
scanf(sM[i][k]m)
getchar()
}
}
opt3
printf(请输入分析字符串#结束＼n)
analyse(Vn Vt)
printf(请选择＼n)
printf(1 输入字符串＼n)
printf(2 输入新分析表＼n)
printf(0 退 出＼n)
opt4
cin>>select
switch(select)
{
case ＇1＇ {goto opt3break}
case ＇2＇ {goto opt2}
case ＇0＇ {break}
default {printf(输入错误请重新选择)
goto opt4
break}
}
return 0
}
语法分析结果：
六．实验结
通实验解词法分析语法分析二者：
1词法规通常非常简单必动强文法描述
2词法记号正规式文关文法提供更简洁易理解定义
3正规式动构造出效词法分析器文法难构造词法分析器
4语言语法结构分成词法非词法两部分编译器前端模块划分提供方便途径
目
<<编译技术>>理实践重课程实验课综合运二年级学门课程容完成型编译程序巩固加强词法分析语法分析语义分析代码生成报错处理等理认识理解培养学生完整系统独立分析设计力进步培养学生独立编程力
二务求
基求：
1． 词法分析器 产生述语言单词序列
语言单词符号种编码部值表：
单词符号
种编码
助记符
码值
DIM
IF
DO
STOP
END
标识符
常数（整）
+
*
**
（
）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
DIM
IF
DO
STOP
END
ID
INT
ASSIGN
PLUS
STAR
POWER
COMMA
LPAR
RPAR
部字符串
标准二进形式
语言点重限制：
首先关键字（IF﹑WHILE等）保留字谓保留字意思户作定义标示符例面写法绝禁止：
IF（5）x
次关键字作保留字关键字作类特殊标示符处理说关键字专设应转换图（种编码）预先安排张表格中（表作保留字表）转换图识出标识符时查张表确定否关键字
次果关键字标识符常数间没确定运算符界符作间隔必须少空白符作间隔（时空白符完全没意义）例条件语句应写
IF i>0 i 1
绝写成
IFi>0 i1
者分析器条件IFI成标识符
语言单词符号状态转换图图：
2． 语法分析器 识加+ 减 * 方^ 括号（）操作数组成算术表达式文法：
E→E+T|ET|T
T→T*F|TF|F
F→P^F|P
p→(E)|i
算法：预测分析法递降分析法算符优先分析法LR分析法等
3． 中间代码生成器 产生述算术表达式中间代码（四元式序列）
三实现程说明
出题目详细算法描述数结构函数说明流程图
1词法分析器流程图
2语法分析器程序图
3中间代码生成器流程图：
四源程序清单
词法分析器
#include stdafxh
#include Wordh
构造函数数成员初始化关键字运算符读入
WordWord()
{开关键字文件
fstream keywordfile(keywordtxt)
if(keywordfile)
{
cout<
exit(1)
}
设置时变量关键字符号文件中容存储
string tempword
int tempencode
string tempre
int tempvalue
开始读关键字文件
while((keywordfileeof()))
{ keywordfile>>tempword>>tempencode>>tempre>>tempvalue
keywordlistpush_back(tempword)
keywordencodepush_back(tempencode)
keywordrepush_back(tempre)
keywordcodevaluepush_back(tempvalue)
}
关闭关键字文件
keywordfileclose()
for(int i0i
fstream signwordfile(signwordtxt)
if(signwordfile)
{ cout<
exit(1)
}
开始读符号文件
while((signwordfileeof()))
{
signwordfile>>tempword>>tempencode>>tempre>>tempvalue
signlistpush_back(tempword)
signencodepush_back(tempencode)
signrepush_back(tempre)
signcodevaluepush_back(tempvalue)
}
关闭符号文件
signwordfileclose()
for(int i0i
}
token中字符串character中字符连接作token中新字符串
void Wordconcatentation()
{for(int i0i<100i++)
{if(token[i]NULL)
{token[i]s
break
}
}
}
判断character中字符否字母数字布尔函数返回true否返回false
bool Wordletter()
{ if(s<＇z＇ && s>＇a＇ )
return true
else if(s<＇Z＇ && s>＇A＇)
return true
else
return false
}
bool Worddigit()
{ if(s<＇9＇ && s>＇0＇)
return true
return false
}
token数组中字符串中前五项(判否保留字)保留字返回编码
int Wordreserve()
{
int leng记录token数组中单词长度
for(int i0i<100i++)计算token数组中单词长度
{
if(token[i]NULL)
{
lengi
break
}
}
for(int i0i
for(int j0j
if(keywordlist[i][j]token[j])某字符等终止次循环
break
if(j+1keywordlist[i]length())较字符全部相等判断两者否长度相等
{
if(lengkeywordlist[i]length())
{return i+1}
else
return 0
}
}
}
return 0
}
标识符登录符号表中常数登录常数表中
void Wordbuildlist()
{设置时变量标识符助记符保存
string tempword
int tempencode
string tempre标识符助记
int tempvalue
int tempconstre常数助记
stoken[0]
if(letter())第字符果字母标识符登录符号表中
{ fstream chartostring(converttxt)
if(chartostring)
{
cout<
}
for(int i0i<100i++)
{
if(token[i]NULL)
break
else
{chartostring<
chartostring<
chartostringopen(converttxt)
if(chartostring)
{
cout<
}
chartostring>>tempre
chartostringclose()
indentityrepush_back(tempre)
tempword标识符
tempencode6
tempvalueindentityresize()
indentitylistpush_back(tempword)
indentityencodepush_back(tempencode)
indentitycodevaluepush_back(tempvalue)
fstream indentityfile(indentitywordtxt)
if(indentityfile)
{ cout<
}
先文件指针移写入endl
indentityfileseekg(0iosend)
indentityfile<
indentityfile<
}
elsetoken中存储常数
{
token中字符数字转换int类型
fstream chartoint(converttxt)
if(chartoint)
{
cout<
}
for(int i0i<100i++)
{ if(token[i]NULL)
break
else
{
chartoint<
}
chartoint<
chartointopen(converttxt)
if(chartoint)
{ cout<
exit(1)
}
chartoint>>tempconstre
chartointclose()
constlistpush_back(tempword)
tempword常数
tempencode7
tempvalueindentityresize()
constencodepush_back(tempencode)
constrepush_back(tempconstre)
constvaluepush_back(tempvalue)
fstream constdigit(constdigittxt)
if(constdigit)
{
cout<
exit(1)
}
先文件指针移写入endl
constdigitseekg(0iosend)
constdigit<
constdigit<
cout<
}
出现非法字符显示错误信息
void Worderror()
{
cout<
}
void Wordsigninfor()
{
token数组中字符串中前五项(判否保留字)保留字返回编码
int leng记录token数组中单词长度
for(int i0i<100i++)计算token数组中单词长度
{
if(token[i]NULL)
{
lengi
break
}
}
for(int i0i
for(int j0j
if(signlist[i][j]token[j])某字符等终止次循环
break
if(j+1signlist[i]length())较字符全部相等判断两者否长度相等
{
if(lengsignlist[i]length())
{
cout<
}
}
}
}
词法分析函数
void Wordrun()
{
cout<
if(file)
{
cout<
exit(1)
}
fileunsetf(iosskipws)
while(s＇#＇ && fileeof())
{
for(int i0i<100i++)
{
token[i]NULL
}
file>>s
while(s＇ ＇)
{
file>>s
}
switch(s)
{
case ＇a＇
case ＇b＇
case ＇c＇
case ＇d＇
case ＇e＇
case ＇f＇
case ＇g＇
case ＇h＇
case ＇i＇
case ＇j＇
case ＇k＇
case ＇l＇
case ＇m＇
case ＇n＇
case ＇o＇
case ＇p＇
case ＇q＇
case ＇r＇
case ＇s＇
case ＇t＇
case ＇u＇
case ＇v＇
case ＇w＇
case ＇x＇
case ＇y＇
case ＇z＇
while(letter()||digit())
{
concatentation()前读入字符送入token数组
file>>s继续读字符直字符数字字母止
}
扫描指针回退字符
fileseekg(1ioscur)
codereserve()
if(code)
{ buildlist()}
else
{
cout<
break
case ＇0＇
case ＇1＇
case ＇2＇
case ＇3＇
case ＇4＇
case ＇5＇
case ＇6＇
case ＇7＇
case ＇8＇
case ＇9＇
while(digit())
{
concatentation()前读入字符送入token数组
file>>s继续读字符直字符数字止
}
扫描指针回退字符
fileseekg(1ioscur)
buildlist()
break
case ＇+＇
concatentation()
signinfor()
break
case ＇＇
concatentation()
signinfor()
break
case ＇*＇
concatentation()
signinfor()
break
case ＇<＇
concatentation()
file>>s
if(s＇＇)
{扫描指针回退字符
fileseekg(1ioscur)
signinfor()
}
else
{
concatentation()
signinfor()
}
break
case ＇＇
concatentation()
file>>s
if(s＇＇)
{
扫描指针回退字符
fileseekg(1ioscur)
signinfor()
}
else
{
concatentation()
signinfor()
}
break
case ＇＇
concatentation()
signinfor()
break
case ＇#＇
cout<
exit(1)
default
error()
}
}
fileclose()
}
void main()
{
Word word
wordrun()
system(pause)
}
运行结果：
语法分析器 源程序：
#include
#include
#include
typedef struct
{
char R
char r
int flag
}array
typedef struct
{
char E
char e
}charLode
typedef struct
{
charLode *base
int top
}charstack
char str[80][80]arr[80][80]brr[80][80]
array F[20]
int mkkppppFF1
char r[10]
int crr[20][20]FLAG0
char ccrr1[1][20]ccrr2[20][1]
void Initstack(charstack &s)定义栈
{
sbasenew charLode[20]
stop1
}
void push(charstack &scharLode w)
{
stop++
sbase[stop]EwE
sbase[stop]ewe
}
void pop(charstack &scharLode &w)
{
wEsbase[stop]E
wesbase[stop]e
stop
}
int IsEmpty(charstack s)
{
if(stop1)
return 1
else return 0
}
int IsLetter(char ch)
{
if(ch>＇A＇&&ch<＇Z＇)
return 1
else return 0
}
judge1判断否算符文法：产生式中含两相继非终结符算符文法
int judge1(int n)
{
int j3flag0
for(int i0i
{
char astr[i][j]
char bstr[i][j+1]
if(IsLetter(a)&&IsLetter(b))
{flag1break}
else j++
}
if(flag1)
return 0
else
return 1
}
judge2判断文法G否算符优先文法：算符文法文法中含空字终结符优先级唯算符优先文法
void judge2(int n)
{
for(int i0i
{cout<<文法G算符优先文法<
cout<<文法G算符优先文法<
search1查存放终结符数组r中否含重复终结符
int search1(char r[]int kkchar a)
{
for(int i0i
break
if(ikk) return 0
else return 1
}
createF函数F数组存放终结符非终结符组合值队标志位0F数组结构体
void createF(int n)
{
int k0i1char g
char t[10]t数组存放非终结符
t[0]str[0][0]
while(i
if(t[k]str[i][0])
{k++t[k]str[i][0]gt[k]i++}
else i++
}
kk0
char c
for(i0i
while(str[i][j]＇＼0＇)
{
cstr[i][j]
if(IsLetter(c)0)
{
if(search1(rkkc))
r[kk]ckk++r数组存放终结符
}
j++
}
}
m0
for(i0i
F[m]Rt[i]
F[m]rr[j]
F[m]flag0
m++
}
}
search函数F数组中寻找终结符非终结符标志位值1
void search(charLode w)
{
for(int i0i
{F[i]flag1break}
}
void FirstVT(int n)求FirstVT
{
charstack sta
charLode w
int i0
Initstack(sta)
while(i
int k3
wEstr[i][0]
char astr[i][k]
char bstr[i][k+1]
if(IsLetter(a))产生式选式第字符终结符情况
{
wea
push(staw)
search(w)
i++
}
else if(IsLetter(a)&&b＇＼0＇&&IsLetter(b))产生式选式第字符非终结符情况
{
web
push(staw)
search(w)
i++
}
else i++
}
charLode ww
while(IsEmpty(sta))
{
pop(staww)
for(i0i
wEstr[i][0]
if(str[i][3]wwE&&str[i][4]＇＼0＇)
{
wewwe
push(staw)
search(w)
break
}
}
}
p0int k1i1
while(i
if(F[i1]flag1)
{
arr[p][0]F[i1]R
arr[p][k]F[i1]r
}
while(F[i]flag0&&i
if(F[i]flag1)
{
if(F[i]Rarr[p][0])
k++
else {arr[p][k+1]＇＼0＇p++k1}
i++
}
}
}
void LastVT(int n)求LastVT
{
charstack sta
charLode w
for(int i0i
i0
Initstack(sta)
while(i
int kstrlen(str[i])
wEstr[i][0]
char astr[i][k1]
char bstr[i][k2]
if(IsLetter(a))
{
wea
push(staw)
search(w)
i++
}
else if(IsLetter(a)&&IsLetter(b))
{
web
push(staw)
search(w)
i++
}
else i++
}
charLode ee
while(IsEmpty(sta))
{
pop(staee)
for(i0i
wEstr[i][0]
if(str[i][3]eeE&&str[i][4]＇＼0＇)
{
weeee
push(staw)
search(w)
}
}
}
int k1i1
ppp0
while(i
if(F[i1]flag1)
{
brr[ppp][0]F[i1]R
brr[ppp][k]F[i1]r
}
while(F[i]flag0&&i
if(F[i]flag1)
{
if(F[i]Rarr[ppp][0])
k++
else {brr[ppp][k+1]＇＼0＇ppp++k1}
i++
}
}
}
void createYXB(int n)构造优先表
{
int ij
for(j1j
for( i1i
for(i1i
int I0J3
while(I
if(str[I][J+1]＇＼0＇)
{I++J3}
else
{
while(str[I][J+1]＇＼0＇)
{
char aastr[I][J]
char bbstr[I][J+1]
if(IsLetter(aa)&&IsLetter(bb))优先等情况1值表示等
{
for(i1i
if(ccrr2[i][0]aa)
break
}
for(j1j
if(ccrr1[0][j]bb)
break
}
if(crr[i][j]0)
crr[i][j]1
else {FLAG1In+1}
J++
}
if(IsLetter(aa)&&IsLetter(bb)&&str[I][J+2]＇＼0＇&&IsLetter(str[I][J+2]))优先等情况
{
for(i1i
if(ccrr2[i][0]aa)
break
}
for(int j1j
if(ccrr1[0][j]str[I][J+2])
break
}
if(crr[i][j]0)
crr[i][j]1
else {FLAG1In+1}
}
if(IsLetter(aa)&&IsLetter(bb))优先情况2值表示
{
for(i1i
if(aaccrr2[i][0])
break
}
for(j0j
if(bbarr[j][0])
break
}
for(int mm1arr[j][mm]＇＼0＇mm++)
{
for(int pp1pp
if(ccrr1[0][pp]arr[j][mm])
break
}
if(crr[i][pp]0)
crr[i][pp]2
else {FLAG1In+1}
}
J++
}
if(IsLetter(aa)&&IsLetter(bb))优先情况3值表示
{
for(i1i
if(ccrr1[0][i]bb)
break
}
for(j0j
if(aabrr[j][0])
break
}
for(int mm1brr[j][mm]＇＼0＇mm++)
{
for(int pp1pp
if(ccrr2[pp][0]brr[j][mm])
break
}
if(crr[pp][i]0)
crr[pp][i]3
else {FLAG1In+1}
}
J++
}
}
}
}
}
judge3返回约程中两非终结符相较值
int judge3(char schar a)
{
int i1j1
while(ccrr2[i][0]s)
i++
while(ccrr1[0][j]a)
j++
if(crr[i][j]3) return 3
else if(crr[i][j]2)
return 2
else if(crr[i][j]1)
return 1
else return 0
}
void print(char s[]char STR[][20]int qint uint iiint k)印约程
{
cout<
for(iqi
}
void process(char STR[][20]int ii)输入字符串进行约程
{
cout<<步骤<< <<符号栈<< <<输入串<< <<动作<
char s[40]a
s[k]＇#＇
print(sSTRquiik)
cout<<预备<
s[k]STR[0][q]
q++
print(sSTRquiik)
cout<<移进<
aSTR[0][q]
if(IsLetter(s[k])) jk
else jk1
bjudge3(s[j]a)
if(b3)情况进行约
{
while(IsLetter(s[j1]))
j
for(iji
kjs[k]＇N＇u++
print(sSTRquiik)
cout<<约<
else if(b2||b1)等情况移进
{
k++
s[k]a
u++
q++
print(sSTRquiik)
if(s[0]＇#＇&&s[1]＇N＇&&s[2]＇#＇)
cout<<接受<
else
{cout<<出错<
if(s[0]＇#＇&&s[1]＇N＇&&s[2]＇#＇)
cout<<约成功<
void main()
{
int nij
cout<<请输入定义文法G产生式数n
cin>>n
for(i0i
gets(str[i])
jstrlen(str[i])
str[i][j]＇＼0＇
}
str[i][0]＇Q＇
str[i][1]＇＇
str[i][2]＇>＇
str[i][3]＇#＇
str[i][4]str[0][0]
str[i][5]＇#＇
str[i][6]＇＼0＇
cout<<定义产生式<
cout<<文法G算符文法<
{
cout<<文法G算符文法<
FirstVT(n)
LastVT(n)
createYXB(n)
}
judge2(n)判断文法G否算符优先文法
if(FLAG0)
{
for(i0i
cout<
cout<
cout<
cout<
cout<
cout<
cout<<
cout<
cout<
cout<
if(crr[i][j]0)
cout<<
else if(crr[i][j]1)
cout<<
else if(crr[i][j]2)
cout<<<
else if(crr[i][j]3)
cout<<>
cout<<
}
cout<
}
if(FF1)
{
char STR[1][20]
cout<<请输入规约字符串<
int iistrlen(STR[0])
STR[0][ii]＇#＇
cout<<面规约程<
}
}
运算结果：
中间代码生成器源程序：
*
表达式生成四元式
递子程序法
*
#include
#include
#include
#include
#include
#define STACK_INIT_SIZE 50
#define STACKINCREMENT 5
#define ERROR 0
#define OVERFLOW 2
#define TRUE 1
#define FALSE 0
#define OK 1
#define NULL 0
void sub_E()
void sub_F()
void sub_T()
void sub_G()
void GEQ(char m)
void PRINT()
typedef struct Stack
{
char *base
char *top
int stacksize
}Stack
int num0
char QT[10][4]T＇A＇c
struct Stack SEM
struct initStack(Stack s)
{
sbase(char *)malloc(STACK_INIT_SIZE*sizeof(char))
if(sbase)
exit(OVERFLOW)
stopsbase
sstacksizeSTACK_INIT_SIZE
return OK
}
初始化堆栈
char pop(Stack &s)
{
char e
if(stopsbase)
{printf(栈中已元素)
exit(ERROR)
}
e*stop
return e
}
出栈
struct push(Stack &schar e)
{
if(stopsbase>sstacksize)
{
sbase(char *)realloc(sbase(sstacksize+STACKINCREMENT)*sizeof(char))
if(sbase)
exit(OVERFLOW)
stopsbase+sstacksize
sstacksize+STACKINCREMENT
}
*stop++e
return OK
}
入栈
void main()
{
initStack(SEM)
printf(表达式应写字母运算符括号组成＼#＼结束＼n)
printf(请输入表达式)
cgetchar()
sub_E()
if(c＇#＇)
PRINT()
else
{
printf(结束符漏写运算符)
exit(0)
}
getchar()
}
void sub_E()
{
sub_T()
R1 if(c＇+＇)
{
cgetchar()
sub_T()
GEQ(＇+＇)
goto R1
}
else if(c＇＇)
{
cgetchar()
sub_T()
GEQ(＇＇)
goto R1
}
else
}
void sub_T()
{
sub_G()
R4 if(c＇*＇)
{ cgetchar()
sub_F()
GEQ(＇*＇)
goto R4
}
else if(c＇＇)
{
cgetchar()
sub_F()
GEQ(＇＇)
goto R4
}
}
void sub_F()
{
sub_G()
R5 if(c＇^＇)
{
cgetchar()
sub_G()
GEQ(＇^＇)
goto R5
}
}
void sub_G()
{
if(c>＇a＇&&c<＇z＇)
{
push(SEMc)
cgetchar()
}
else if(c＇(＇)
{
cgetchar()
sub_E()
if(c＇)＇)
cgetchar()
else
{
printf(括号匹配)
exit(0)
}
}
else
{
printf(非法符号)
exit(0)
}
}
void GEQ(char m)
{
QT[num][0]m
QT[num][2]pop(SEM)
QT[num][1]pop(SEM)
QT[num][3]T
push(SEMT)
num++
T++
}
void PRINT()
{
printf(您输入表达式应四元式＼n)
for(int i0i
printf(()
printf(cQT[i][0])
if(QT[i][1]<＇Z＇&&QT[i][1]>＇A＇)
printf(＼tcd＇t＇QT[i][1]＇A＇+1)
else
printf(＼tcQT[i][1])
if(QT[i][2]<＇Z＇&&QT[i][1]>＇A＇)
printf(＼tcd＇t＇QT[i][2]＇A＇+1)
else
printf(＼tcQT[i][2])
if(QT[i][3]<＇Z＇&&QT[i][1]>＇A＇)
printf(＼tcd＇t＇QT[i][3]＇A＇+1)
else
printf(＼tcQT[i][3])
printf()＼n)
}
}
六总结
谈谈收获体会
1 通次实验词法分析器进步解理知识应实验中重新熟悉C语言相关容加深C语言知识深化途理解通次语义分析实验 高级语言学更深认识 解更透彻
2 解高级语言转化目标代码汇编指令程学起作编程帮助 次实验然完成简单程序程序框架课出组织程序结构深入确学加深编译原理理解掌握编译程序实现方法技术巩固前面学知识
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档