实验21 语法分析—预测分析方法
实验目
预测分析方法编制分析程序实现词法分析程序提供单词序列语法检查结构分析解预测分析法递子程序法区联系培养动手实践力
二实验容
预测分析法分析段程序代码果符合文法定义程序输出否输出否
预测分析递子程序顶分析方法里出回溯左公子文法左递左公子BNF：
<程序>→<程序首部><分程序>
<程序首部>→PROGRAM 标识符
<分程序>→<常量说明部分><变量说明部分><程说明部分><复合语句>
<常量说明部分>→CONST<常量定义><常量定义缀>|ε
<常量定义>→标识符符号整数
<常量定义缀>→ <常量定义><常量定义缀>|ε
<变量说明部分>→VAR<变量定义><变量定义缀>|ε
<变量定义>→标识符<标识符缀><类型>
<标识符缀>→标识符<标识符缀>|ε
<变量定义缀>→<变量定义><变量定义缀>|ε
<类型>→INTEGER|LONG
<程说明部分>→<程首部><分程序><程说明部分缀>|ε
<程首部>→PROCEDURE 标识符<参数部分>
<参数部分>→(标识符<类型>)|ε
<程说明部分缀>→<程首部><分程序><程说明部分缀>|ε
<语句>→<赋值调语句>|<条件语句>|<型循环语句>|<读语句>|<写语句>|<复合语句>
<赋值调语句>→标识符<缀>
<缀>→<表达式>|(<表达式>)|ε
<条件语句>→IF<条件>THEN<语句>
<型循环语句>→WHILE<条件>DO<语句>
<读语句>→READ (标识符<标识符缀>)
<写语句>→WRITE (表达式<表达式缀>)
<表达式缀>→ <表达式><表达式缀>|ε
<复合语句>→BEGIN <语句><语句缀>END
<语句缀>→ <语句><语句缀>|ε
<条件>→ <表达式><关系运算符><表达式>|ODD<表达式>
<表达式>→+<项><项缀>|<项><项缀>|<项><项缀>
<项缀>→<加型运算符><项><项缀>|ε
<项>→<子><子缀>
<子缀>→<型运算符><子><子缀>|ε
<子>→标识符|符号整数|（<表达式>）
<加型运算符>→+|
<型运算符>→*|
<关系运算符>→|<>|<|<|>|>
非终结符终结符起存入栈非终结符码128开始标记表：
表1 终结符种码表
种码
单词
种码
单词
种码
单词
种码
单词
1
PROGRAM
2
CONST
3
VAR
4
INTEGER
5
LONG
6
PROCEDURE
7
IF
8
THEN
9
WHILE
10
DO
11
READ
12
WRITE
13
BEGIN
14
END
15
ODD
16
+
17
18
*
19
20
21
<>
22
<
23
<
24
>
25
>
26
27
28
29
30
31
(
32
)
33
符号整数
34
标识符
35
#
表2 非终结符函数名表
非终结符
函数名
非终结符
函数名
<程序>
program
<程序首部>
proghead
<分程序>
block
<常量说明部分>
consexpl
<常量定义>
consdefi
<变量说明部分>
varexpl
<常量定义缀>
conssuff
<变量定义>
vardefi
<变量定义缀>
varssuff
<程说明部分>
procdefi
<类型>
typeil
<程首部>
procedh
<程说明部分缀>
procsuff
<赋值调语句>
assipro
<语句>
sentence
<缀>
suffix
<条件语句>
ifsent
<读语句>
read
<型循环语句>
whilesent
<标识符缀>
idsuff
<写语句>
Write
<复合语句>
compsent
<表达式缀>
Exprsuff
<语句缀>
sentsuff
<条件>
Conditio
<项缀>
termsuff
<表达式>
Express
<项>
term
<子缀>
Factsuff
<参数部分>
argument
<子>
Factor
<加型运算符>
addoper
<型运算符>
Muloper
<关系运算符>
respoper
三完整源程序代码
#include
#include
#include
#include
#include
#define lenth1 15
#define lenth2 18
*规表*
int rule[][6]{
{0} 空
{129130260} 程序首部分程序
{134280} program 标识符
{1311341381500}常量说明部分变量说明部分程说明部分复合语句
{2132133280} const 常量定义常量定义缀
{0}
{3420330} 标识符 符号整数
{271321330} 常量定义常量定义缀
{31351360} var 变量定义变量定义缀
{3414729137280}标识符标识符缀：类型
{27341470} 标识符标识符缀
{1351360} 变量定义变量定义缀
{40} integer
{50} long
{139130281400}程首部分程序程说明部分缀
{634158280} procedure 标识符参数部分
{1420} 赋值调语句
{1440} 条件语句
{1450} 型循环语句
{1460} 读语句
{1480} 写语句
{1500} 符合语句
{341430} 标识符缀
{301530} ：表达式
{715281410} if 条件then 语句
{9152101410} while 条件do 语句
{113134147320}read （标识符标识符缀）
{1231153149320}write （表达式表达式缀）
{271531490} 表达式表达式缀
{13141151140} begin 语句语句缀end
{281411510} 语句语句缀
{1531611530} 表达式关系运算符表达式
{151530} odd 表达式
{161551540} + 项项缀
{171551540} 项项缀
{1551540} 项项缀
{1591551540} 加型运算符项项缀
{1571560} 子子缀
{1601571560} 型运算符子子缀
{340} 标识符
{330} 符号整数
{31153320} （表达式）
{26330} 符号整数
{160} +
{170}
{180} *
{190}
{200}
{210} <>
{220} <
{230} <
{240} >
{250} >
{313429137320} 标识符：类型）
}
*预测分析表非零元素*
int pretable[][3]{{12811}{12912}{13023}{13033}
{13063}{130343}{13073}{13093}{130113}{130123}
{130133}{130263}{130283}{13124}{13135}{13165}
{131345}{13175}{13195}{131115}{131125}{131135}
{131265}{131285}{132346}{133277}{133285}{13438}
{13465}{134345}{13475}{13495}{134115}{134125}
{134135}{134265}{134285}{135349}{13665}{136135}
{1363411}{136285}{137412}{137513}{138614}{138345}
{13875}{13895}{138115}{138125}{138135}{138265}
{138285}{139615}{140614}{140345}{14075}{14095}
{140115}{140125}{140135}{140265}{140285}{1413416}
{141717}{141918}{1411119}{1411220}{1411321}{141145}
{141265}{141285}{1423422}{1433023}{1433141}{143285}
{143285}{143145}{143265}{143145}{144724}{145925}
{1461126}{1472710}{147295}{147325}{1481227}{1492728}
{149325}{1501329}{150265}{150285}{1512830}{151145}
{151265}{1512830}{1523431}{1521631}{1521731}{1523431}
{1523331}{1523131}{1521532}{1533435}{1531633}{1531734}
{1533435}{1533335}{1533135}{1541636}{1541736}{15485}
{154105}{154145}{154205}{154215}{154225}{154235}
{154245}{154255}{154265}{154275}{154285}{154325}
{1553437}{1553337}{1553137}{1561838}{1561938}
{15685}{156105}{156145}{156165}{156175}
{156205}{156215}{156225}{156235}{156245}
{156255}{156265}{156275}{156285}{156325}
{1573439}{1573340}{1573141}{1583153}{158285}
{1591643}{1591744}{1601845}{1601946}{1612047}
{1612148}{1612249}{1612350}{1612451}{1612552}{000}}
struct st
{
char name[21]
int code
}sym
struct
{
char name[21]
int type
int addr
}indent[1000] *标识符表*
int table[34][35]
FILE *f1 *f1输入文件指针*
int line1row1val
int lenth0
void getsym()
char getchr()
void error(int n)
void main(int argcchar *argv[])
{
if ((f1fopen(C＼＼Documents and Settings＼＼Administrator＼＼桌面＼＼编译＼＼测试txtr))NULL)
{
printf(cannot open the file＼n)
exit(0)
}
int stack[2000]
int ijxtop1flag1
i0
while(pretable[i][0])*非零元素置预测分析表*
{
table[pretable[i][0]128][pretable[i][1]]pretable[i][2]
i++
}
*#号识符号程序入栈*
补充执行语句
stack[++top]35
stack[++top]128
补充执行语句
getsym()
while(flag)
{
xstack[top] *取栈顶符号*
if(x>128) *x非终结符*
{
if(table[x128][symcode])*果该预测分析表元素空计算规长度规反序入栈*
{
i0
while(rule[table[x128][symcode]][i])
{
i++
}
for(ji1j>0j)
{
stack[++top]rule[table[x128][symcode]][j]
}
}
else error(100)
}
else if(x<35) *x终结符#*
{
if(xsymcode) *栈顶元素输入元素匹配*
{
if(x35)补充判断条件
*栈顶元素输入元素匹配时判断否#结束否继续*
flag0
else
getsym()
}
else
error(101)
}
else
error(102) *栈顶元素输入元素匹配时出错*
}
fclose(f1)
printf(the program is right＼n)
system(pause)
}
void getsym()
{
static char a[lenth1][10]{programconstvarintegerlongprocedureifthenwhiledoreadwritebeginendodd}d[lenth2][3]{+*<><<>>()}str[21]ch＇ ＇
int in
while(isspace(ch))
chgetchr()
if(isalpha(ch))
{
n0
while(isalpha(ch)||isalnum(ch))
{
if(isalpha(ch))
chtolower(ch)
if(n<20)
str[n++]ch
chgetchr()
}
str[n]＇＼0＇
for(i0i if(strcmp(stra[i]))
break
if(i {
strcpy(symnamea[i])
symcodei+1
}
else*否标识符检查标识符表中否已登记该标识符没登记填表*
{
for(i0i if(strcmp(strindent[i]name))
break
if(ilenth)
strcmp(indent[i]namestr)
strcpy(symnameindent[i]name)
补充执行语句
symcode34
}
}
else if(isalnum(ch))
{
val0n0
while(isalnum(ch))
{
valval*10+ch＇0＇
symname[n++]ch
chgetchr()
}
symname[n]＇＼0＇
symcode33
}
else
{
if(ch＇+＇||ch＇＇||ch＇*＇||ch＇＇||ch＇＇||ch＇＇||ch＇＇||ch＇＇||ch＇(＇||ch＇)＇)
{
str[0]ch
str[1]＇＼0＇
chgetchr()
for(i0i {
if(strcmp(strd[i]))补充判断条件
{
strcpy(symnamestr)
symcodei+16
}
}
}
else
{
n0
if(ch＇>＇||ch＇＇)
{
str[n++]ch
if((chgetchr())＇＇)
{
str[n++]chchgetchr()
}
}
else
{
if(ch＇<＇)
{
str[n++]chchgetchr()
if(ch＇＇||ch＇>＇)
{
str[n++]chchgetchr()
}
}
else if(ch1)
{
strcpy(symname)
symcode35
return
}
else
{
error(1)
}
}
str[n]＇＼0＇
for(i0i {
if(strcmp(strd[i]))
{
strcpy(symnamestr)
symcodei+16
}
}
}
}
}
char getchr()
{
char chfgetc(f1)
if(ch＇＼n＇)
{
row1
line++
}
else
if(ch＇ ＇&&ch＇＼t＇)
row++
return(ch)
}
void error(int n)
{
printf(There are d error＼n n)
exit(0)
}
四结果运行
（1）输入：program a
begin
end#
输出：the program is right
（2）输入：program test2
const a34b90
输出：There are 100 error
（3）输入：program test3
procedure test
const s3
输出：There are 100 error
（4）输入：program test
if a>b then a6
end#
输出：There are 100 error
（5）输入：program s
begin
if sym＇+＇ then
begin
s＇
advance
end
else error
输出：There are 100 error
五两种方法较分析
谓递降法指文法非终结符号根相应产生式候选式结构编写子程序 (函数)识该非终结符号表示语法范畴
预测分析方法求文法必须LL（1）文法相较递降分析方法说更难
计算机班
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
实验目
预测分析方法编制分析程序实现词法分析程序提供单词序列语法检查结构分析解预测分析法递子程序法区联系培养动手实践力
二实验容
预测分析法分析段程序代码果符合文法定义程序输出否输出否
预测分析递子程序顶分析方法里出回溯左公子文法左递左公子BNF：
<程序>→<程序首部><分程序>
<程序首部>→PROGRAM 标识符
<分程序>→<常量说明部分><变量说明部分><程说明部分><复合语句>
<常量说明部分>→CONST<常量定义><常量定义缀>|ε
<常量定义>→标识符符号整数
<常量定义缀>→ <常量定义><常量定义缀>|ε
<变量说明部分>→VAR<变量定义><变量定义缀>|ε
<变量定义>→标识符<标识符缀><类型>
<标识符缀>→标识符<标识符缀>|ε
<变量定义缀>→<变量定义><变量定义缀>|ε
<类型>→INTEGER|LONG
<程说明部分>→<程首部><分程序><程说明部分缀>|ε
<程首部>→PROCEDURE 标识符<参数部分>
<参数部分>→(标识符<类型>)|ε
<程说明部分缀>→<程首部><分程序><程说明部分缀>|ε
<语句>→<赋值调语句>|<条件语句>|<型循环语句>|<读语句>|<写语句>|<复合语句>
<赋值调语句>→标识符<缀>
<缀>→<表达式>|(<表达式>)|ε
<条件语句>→IF<条件>THEN<语句>
<型循环语句>→WHILE<条件>DO<语句>
<读语句>→READ (标识符<标识符缀>)
<写语句>→WRITE (表达式<表达式缀>)
<表达式缀>→ <表达式><表达式缀>|ε
<复合语句>→BEGIN <语句><语句缀>END
<语句缀>→ <语句><语句缀>|ε
<条件>→ <表达式><关系运算符><表达式>|ODD<表达式>
<表达式>→+<项><项缀>|<项><项缀>|<项><项缀>
<项缀>→<加型运算符><项><项缀>|ε
<项>→<子><子缀>
<子缀>→<型运算符><子><子缀>|ε
<子>→标识符|符号整数|（<表达式>）
<加型运算符>→+|
<型运算符>→*|
<关系运算符>→|<>|<|<|>|>
非终结符终结符起存入栈非终结符码128开始标记表：
表1 终结符种码表
种码
单词
种码
单词
种码
单词
种码
单词
1
PROGRAM
2
CONST
3
VAR
4
INTEGER
5
LONG
6
PROCEDURE
7
IF
8
THEN
9
WHILE
10
DO
11
READ
12
WRITE
13
BEGIN
14
END
15
ODD
16
+
17
18
*
19
20
21
<>
22
<
23
<
24
>
25
>
26
27
28
29
30
31
(
32
)
33
符号整数
34
标识符
35
#
表2 非终结符函数名表
非终结符
函数名
非终结符
函数名
<程序>
program
<程序首部>
proghead
<分程序>
block
<常量说明部分>
consexpl
<常量定义>
consdefi
<变量说明部分>
varexpl
<常量定义缀>
conssuff
<变量定义>
vardefi
<变量定义缀>
varssuff
<程说明部分>
procdefi
<类型>
typeil
<程首部>
procedh
<程说明部分缀>
procsuff
<赋值调语句>
assipro
<语句>
sentence
<缀>
suffix
<条件语句>
ifsent
<读语句>
read
<型循环语句>
whilesent
<标识符缀>
idsuff
<写语句>
Write
<复合语句>
compsent
<表达式缀>
Exprsuff
<语句缀>
sentsuff
<条件>
Conditio
<项缀>
termsuff
<表达式>
Express
<项>
term
<子缀>
Factsuff
<参数部分>
argument
<子>
Factor
<加型运算符>
addoper
<型运算符>
Muloper
<关系运算符>
respoper
三完整源程序代码
#include
#include
#include
#include
#include
#define lenth1 15
#define lenth2 18
*规表*
int rule[][6]{
{0} 空
{129130260} 程序首部分程序
{134280} program 标识符
{1311341381500}常量说明部分变量说明部分程说明部分复合语句
{2132133280} const 常量定义常量定义缀
{0}
{3420330} 标识符 符号整数
{271321330} 常量定义常量定义缀
{31351360} var 变量定义变量定义缀
{3414729137280}标识符标识符缀：类型
{27341470} 标识符标识符缀
{1351360} 变量定义变量定义缀
{40} integer
{50} long
{139130281400}程首部分程序程说明部分缀
{634158280} procedure 标识符参数部分
{1420} 赋值调语句
{1440} 条件语句
{1450} 型循环语句
{1460} 读语句
{1480} 写语句
{1500} 符合语句
{341430} 标识符缀
{301530} ：表达式
{715281410} if 条件then 语句
{9152101410} while 条件do 语句
{113134147320}read （标识符标识符缀）
{1231153149320}write （表达式表达式缀）
{271531490} 表达式表达式缀
{13141151140} begin 语句语句缀end
{281411510} 语句语句缀
{1531611530} 表达式关系运算符表达式
{151530} odd 表达式
{161551540} + 项项缀
{171551540} 项项缀
{1551540} 项项缀
{1591551540} 加型运算符项项缀
{1571560} 子子缀
{1601571560} 型运算符子子缀
{340} 标识符
{330} 符号整数
{31153320} （表达式）
{26330} 符号整数
{160} +
{170}
{180} *
{190}
{200}
{210} <>
{220} <
{230} <
{240} >
{250} >
{313429137320} 标识符：类型）
}
*预测分析表非零元素*
int pretable[][3]{{12811}{12912}{13023}{13033}
{13063}{130343}{13073}{13093}{130113}{130123}
{130133}{130263}{130283}{13124}{13135}{13165}
{131345}{13175}{13195}{131115}{131125}{131135}
{131265}{131285}{132346}{133277}{133285}{13438}
{13465}{134345}{13475}{13495}{134115}{134125}
{134135}{134265}{134285}{135349}{13665}{136135}
{1363411}{136285}{137412}{137513}{138614}{138345}
{13875}{13895}{138115}{138125}{138135}{138265}
{138285}{139615}{140614}{140345}{14075}{14095}
{140115}{140125}{140135}{140265}{140285}{1413416}
{141717}{141918}{1411119}{1411220}{1411321}{141145}
{141265}{141285}{1423422}{1433023}{1433141}{143285}
{143285}{143145}{143265}{143145}{144724}{145925}
{1461126}{1472710}{147295}{147325}{1481227}{1492728}
{149325}{1501329}{150265}{150285}{1512830}{151145}
{151265}{1512830}{1523431}{1521631}{1521731}{1523431}
{1523331}{1523131}{1521532}{1533435}{1531633}{1531734}
{1533435}{1533335}{1533135}{1541636}{1541736}{15485}
{154105}{154145}{154205}{154215}{154225}{154235}
{154245}{154255}{154265}{154275}{154285}{154325}
{1553437}{1553337}{1553137}{1561838}{1561938}
{15685}{156105}{156145}{156165}{156175}
{156205}{156215}{156225}{156235}{156245}
{156255}{156265}{156275}{156285}{156325}
{1573439}{1573340}{1573141}{1583153}{158285}
{1591643}{1591744}{1601845}{1601946}{1612047}
{1612148}{1612249}{1612350}{1612451}{1612552}{000}}
struct st
{
char name[21]
int code
}sym
struct
{
char name[21]
int type
int addr
}indent[1000] *标识符表*
int table[34][35]
FILE *f1 *f1输入文件指针*
int line1row1val
int lenth0
void getsym()
char getchr()
void error(int n)
void main(int argcchar *argv[])
{
if ((f1fopen(C＼＼Documents and Settings＼＼Administrator＼＼桌面＼＼编译＼＼测试txtr))NULL)
{
printf(cannot open the file＼n)
exit(0)
}
int stack[2000]
int ijxtop1flag1
i0
while(pretable[i][0])*非零元素置预测分析表*
{
table[pretable[i][0]128][pretable[i][1]]pretable[i][2]
i++
}
*#号识符号程序入栈*
补充执行语句
stack[++top]35
stack[++top]128
补充执行语句
getsym()
while(flag)
{
xstack[top] *取栈顶符号*
if(x>128) *x非终结符*
{
if(table[x128][symcode])*果该预测分析表元素空计算规长度规反序入栈*
{
i0
while(rule[table[x128][symcode]][i])
{
i++
}
for(ji1j>0j)
{
stack[++top]rule[table[x128][symcode]][j]
}
}
else error(100)
}
else if(x<35) *x终结符#*
{
if(xsymcode) *栈顶元素输入元素匹配*
{
if(x35)补充判断条件
*栈顶元素输入元素匹配时判断否#结束否继续*
flag0
else
getsym()
}
else
error(101)
}
else
error(102) *栈顶元素输入元素匹配时出错*
}
fclose(f1)
printf(the program is right＼n)
system(pause)
}
void getsym()
{
static char a[lenth1][10]{programconstvarintegerlongprocedureifthenwhiledoreadwritebeginendodd}d[lenth2][3]{+*<><<>>()}str[21]ch＇ ＇
int in
while(isspace(ch))
chgetchr()
if(isalpha(ch))
{
n0
while(isalpha(ch)||isalnum(ch))
{
if(isalpha(ch))
chtolower(ch)
if(n<20)
str[n++]ch
chgetchr()
}
str[n]＇＼0＇
for(i0i
break
if(i
strcpy(symnamea[i])
symcodei+1
}
else*否标识符检查标识符表中否已登记该标识符没登记填表*
{
for(i0i
break
if(ilenth)
strcmp(indent[i]namestr)
strcpy(symnameindent[i]name)
补充执行语句
symcode34
}
}
else if(isalnum(ch))
{
val0n0
while(isalnum(ch))
{
valval*10+ch＇0＇
symname[n++]ch
chgetchr()
}
symname[n]＇＼0＇
symcode33
}
else
{
if(ch＇+＇||ch＇＇||ch＇*＇||ch＇＇||ch＇＇||ch＇＇||ch＇＇||ch＇＇||ch＇(＇||ch＇)＇)
{
str[0]ch
str[1]＇＼0＇
chgetchr()
for(i0i
if(strcmp(strd[i]))补充判断条件
{
strcpy(symnamestr)
symcodei+16
}
}
}
else
{
n0
if(ch＇>＇||ch＇＇)
{
str[n++]ch
if((chgetchr())＇＇)
{
str[n++]chchgetchr()
}
}
else
{
if(ch＇<＇)
{
str[n++]chchgetchr()
if(ch＇＇||ch＇>＇)
{
str[n++]chchgetchr()
}
}
else if(ch1)
{
strcpy(symname)
symcode35
return
}
else
{
error(1)
}
}
str[n]＇＼0＇
for(i0i
if(strcmp(strd[i]))
{
strcpy(symnamestr)
symcodei+16
}
}
}
}
}
char getchr()
{
char chfgetc(f1)
if(ch＇＼n＇)
{
row1
line++
}
else
if(ch＇ ＇&&ch＇＼t＇)
row++
return(ch)
}
void error(int n)
{
printf(There are d error＼n n)
exit(0)
}
四结果运行
（1）输入：program a
begin
end#
输出：the program is right
（2）输入：program test2
const a34b90
输出：There are 100 error
（3）输入：program test3
procedure test
const s3
输出：There are 100 error
（4）输入：program test
if a>b then a6
end#
输出：There are 100 error
（5）输入：program s
begin
if sym＇+＇ then
begin
s＇
advance
end
else error
输出：There are 100 error
五两种方法较分析
谓递降法指文法非终结符号根相应产生式候选式结构编写子程序 (函数)识该非终结符号表示语法范畴
预测分析方法求文法必须LL（1）文法相较递降分析方法说更难
计算机班
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档