编译原理大作业：3-非递归预测分析-洪萨配资

1.实验目的

设计一个非递归预测分析器，实现对表达式语言的分析，理解自上而下语法分析方法的基本思想，掌握设计非递归预测分析器的基本方法。

2.实验要求

建立文法及其LL(1)分析表表示的数据结构，设计并实现相应的预测分析器，对源程序经词法分析后生成的二元式代码流进行预测分析，如果输入串是文法定义的句子则输出“是”，否则输出“否”。

3.实验内容

（1）文法描述及其 LL(1)分析表

表达式语言（XL）的语法规则如下：

1．程序 → 表达式；
2． |表达式；程序
3．表达式→ 表达式 + 项
4． |项
5．项 → 项 * 因式
6． |因式
7．因式 → num_or_id
8． | (表达式)

将该语言的文法转换为如下的LL(1)文法：

1 prgm → expr;prgm ’ 8 term → factor
term ’
2 prgm ’ → prgm 9 term ’ → *factor
term ’
3 prgm ’ → ε 10 term ’ → ε
4 expr → term expr ’ 11 factor → (expr)
5 expr → ε 12 f actor → num
6 expr ’ → +term expr ’ 13 system_goal → prgm
7 expr ’ → ε

该LL(1)文法的LL(1)分析表如下：

对文法中每个文法符号指定一个常数值，符号编码表如下：

（2）文法及其LL(1)分析表的数据结构

文法的产生式可用数组Yy_pushtab[]存放。数组的第一个下标是产生式号，第一个产生式的序号为0；每列按逆序存放该产生式右部各符号的常数值，并以0结束。对于该表达式语言XL的LL(1)分析表，可用数组Yy_d[]存放。第一个下标是非终结符数值，第二个下标是终结符数值，数组元素的值为：0（表示接受），1（表示产生式号），-1（表示语法错）。

数组Yy_pushtab[]的具体内容及表示如下：

数组Yy_d[]的具体内容及表示如下：

（3）预测分析器总控程序结构

预测分析器总控程序使用上面的两个表Yy_pushtab、Yy_d和一个分析栈（元素类型为int），其结构如下：

初始化；/* 把开始符号的常数值压入分析栈，输入指向第一个输入符号 */ while(分析栈非空) { if(栈顶常数表示一个终结符) if(该常数与输入符号的常数不等) 报语法错； else { 把一个数从栈顶弹出； advance 读下一输入符； } else { /* 栈顶的常数表示一个非终结符 */ what_to_do=Yy_d[栈顶常数][当前输入符号的常数]； if(what_to_do==-1) 报语法错； else { 把栈顶元素弹出栈； 把Yy_pushtab[what_to_do]中列出的全部常数压入分析栈； } } }

请实现该程序。在程序中添加输出栈内容的功能，以便和手工模拟分析过程作比较。