实验五 LL(1)文法识别程序设计
一、实验目的
通过LL(1)文法识别程序的设计理解自顶向下的语法分析思想。
二、实验重难点
理解并实现LL(1)文法
三、实验内容与要求
编写LL(1)文法识别程序
四、实验学时
4课时
五、实验设备与环境
Visual C++ 6.0
六、实验过程
1． 熟悉Visual C++ 6.0集成开发环境，掌握VC下创建工程的方法和步骤；
2． 编写程序能识别文法符号的头符号集；
3． 编写程序能识别文法符号的后继符号集；
4． 设计一个能判断文法是否为LL(1)文法的程序。
参考程序：
/************************************/
/* 程序名称： LL(1)文法分析程序 */
/* E->E+T|E-T|T */
/* T->T*F|T/F|F */
/* F->(E)|i */
/* 程序版本： 1.0 Final */
/************************************/
/********************************************/
/* 程序相关说明 */
/* A=E’ B=T’ */
/* 0=E 1=E’ 2=T 3=T’ 4=F */
/* 0=i 1=+ 2=- 3=* 4=/ 5=( 6=) 7=# */
/************************************/
#include "stdio.h"
#include "malloc.h"
typedef struct Lchar{
char char_ch;
struct Lchar *next;
}Lchar;
Lchar *p,*h,*temp,*top,*base;
char curchar;
char curtocmp;
int right;
int table[5][8]={{1,0,0,0,0,1,0,0},{0,1,1,0,0,0,1,1},{1,0,0,0,0,1,0,0},
{0,1,1,1,1,0,1,1},{1,0,0,0,0,1,0,0}};
int i,j;
void push(char pchar){
temp=(Lchar *)malloc(sizeof(Lchar));
temp->char_ch=pchar;
temp->next=top; top=temp;
}
void pop(void){
curtocmp=top->char_ch;
if(top->char_ch!='#')
top=top->next;
}
void doforpush(int t){
switch(t) {
case 0:
push('A'); push('T'); break;
case 5:
push('A'); push('T'); break;
case 11:
push('A'); push('T'); push('+'); break;
case 12:
push('A'); push('T'); push('-'); break;
case 20:
push('B'); push('F'); break;
case 25: push('B'); push('F'); break;
case 33:
push('B'); push('F'); push('*'); break;
case 34:
push('B'); push('F'); push('/'); break;
case 40:
push('i'); break;
case 45:
push(')'); push('E'); push('(');
}
}
void changchartoint(){
switch(curtocmp){
case 'A':
i=1; break;
case 'B':
i=3; break;
case 'E':
i=0; break;
case 'T':
i=2; break;
case 'F':
i=4;
}
switch(curchar){
case 'i':
j=0; break;
case '+':
j=1; break;
case '-':
j=2; break;
case '*':
j=3; break;
case '/':
j=4; break;
case '(':
j=5; break;
case ')':
j=6; break;
case '#':
j=7;
}
}
void dosome(void){
int t;
for(;;){
pop();
curchar=h->char_ch;
printf("\n%c\t%c\n",curchar,curtocmp);
if(curtocmp=='#' && curchar=='#')
break;
if(curtocmp=='A' ||curtocmp=='B'||curtocmp=='E'||curtocmp=='T'||curtocmp=='F') {
if(curtocmp!='#') {
changchartoint();
if(table[i][j]) {
t=10*i+j;
doforpush(t);
continue;
}
else {
right=0; break;
}
}
else if(curtocmp!=curchar) {
right=0; break;
}
else
break;
}
else if(curtocmp!=curchar)
{
right=0; break;
}
else
{
h=h->next; continue;
}
}
}
void main(void){
char ch;
right=1;
base=(Lchar *)malloc(sizeof(Lchar));
base->next=NULL;
base->char_ch='#';
temp=(Lchar *)malloc(sizeof(Lchar));
temp->next=base;
temp->char_ch='E';
top=temp;
h=(Lchar *)malloc(sizeof(Lchar));
h->next=NULL;
p=h;
do{
ch=getchar();
putchar(ch);
if(ch=='i'||ch=='+'||ch=='-' ||ch=='*' ||ch=='/' ||ch=='(' ||ch==')' ||ch=='#') {
temp=(Lchar *)malloc(sizeof(Lchar));
temp->next=NULL;
temp->char_ch=ch;
h->next=temp;
h=h->next;
}
else {
temp=p->next;
printf("\nInput a wrong char!Input again:\n");
for(;;) {
if (temp!=NULL)
printf("%c",temp->char_ch);
else
break;
temp=temp->next;
}
}
}while(ch!='#');
p=p->next;
h=p;
dosome();
if(right)
printf("\nOK!\n");
else
printf("\nError!\n");
getchar();
}
第二篇：实验二语法设计(LL1文法)
实验二 LL（1）分析法
一、实验目的：
根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析LL（1）分析法的理解。
二、实验预习提示
1、LL（1）分析法的功能
LL（1）分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号以及LL（1）分析表，对输入符号串自上而下的分析过程。
2、LL（1）分析法的前提
改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（1）文法，
3、LL（1）分析法实验设计思想及算法
三、实验过程和指导：
（一）准备：
1.阅读课本有关章节，
2.考虑好设计方案；
3.设计出模块结构、测试数据，初步编制好程序。
（二）上课上机：
将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。
（三）程序要求：
程序输入/输出示例：
对下列文法（要求每位同学文法不同），用LL（1）分析法对任意输入的符号串进行分析：
（1）E->TG
（2）G->+TG|—TG
（3）G->ε
（4）T->FS
（5）S->*FS|/FS
（6）S->ε
（7）F->(E)
（8）F->i
输出的格式如下：
(1)LL（1）分析程序，编制人：姓名，学号，班级
(2)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串
(3)输出过程如下：
(4)输入符号串为非法符号串(或者为合法符号串)
备注：(1)在“所用产生式”一列中如果对应有推导则写出所用产生式；如果为匹配终结符则写明匹配的终结符；如分析异常出错则写为“分析出错”；若成功结束则写为“分析成功”。
(2) 在此位置输入符号串为用户自行输入的符号串。
(3)上述描述的输出过程只是其中一部分的。
注意：1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符i，结束符#；
2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；
3.对学有余力的同学，测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照；
（四）程序思路（仅供参考）：
模块结构：
（1）定义部分：定义常量、变量、数据结构。
（2）初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）；
（3）控制部分：从键盘输入一个表达式符号串；
（4）利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。
（五）练习该实验的目的和思路：
程序相当复杂，需要利用到大量的编译原理，也用到了大量编程技巧和数据结构，通过这个练习可大大提高软件开发能力。
（六）为了能设计好程序，注意以下事情：
1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。
2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。
3.编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。