东北大学编译原理实验报告材料二

实用文档

编译原理程序设计实验报告

——表达式语法分析器的设计与实现

班级：

姓名：

学号：

实验目标：用两种不同的方法设计一个表达式的语法分析器 实验内容： ①LL(1) 分析法

LL（1）文法是一种自上而下的语法分析方法，它是从文法的识别符号出发，生成句子的最左推导，从左到右扫描源程序，每次向前查看1个字符，便能确定当前应该选择的产生式。

LL（1）分析需要用到一个分析表M和一个符号栈S，分析表M是一个矩阵，它的元素可以存放一个非终结符的产生式，表明当符号栈S的栈顶元素非终结符遇到当前输入字符时，所应选择的产生式；M的元素还可以是存放一个出错标志，说明符号栈S的栈顶元素非终结符不应该遇到当前输入字符（终结符）。 重复调用LL（1）分析方法对每一个输入字符进行分析，直到输入栈为空为止。

②递归下降子程序

递归下降分析法，在判断一个表达式时首先进入E然后调用T在调用F，判断是否为“（”或字符或常数，如果不是报错，是“（”的话再进入E，是字符或常数的话跳出递归。然后进入T中下一步，判断是否为“*”，是的话进入T子递归，不是的话跳出，进入E的下一步判断是否为“+”，是的话进入E的子递归，不是的话跳出回到主程序。当ch标识符为#时结束。

标准

实用文档

源程序代码：（加入注释） LL(1) 分析算法：

#include

标准

实用文档

#include using namespace std; #define STACKSIZE 50

#define STACKINCREMENT 10 #define OK 1 #define error 0

#define overflow -1 typedef char SElemType; typedef int Status;

typedef struct {

SElemType *base; SElemType *top; Int stacksize; }SqStack;

Status InitStack(SqStack &S) {

S.base = (SElemType * )malloc(STACKSIZE * sizeof(SElemType)); if (!S.base) exit(overflow); S.top=S.base;

S.stacksize=STACKSIZE; return OK; }

Status Push(SqStack &S, SElemType e) {

if (S.top - S.base >= S.stacksize) {

S.base = (SElemType * )realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType)); if (!S.base) exit(overflow);

S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } (S.top)++; *(S.top) = e; return OK; }

Status Pop(SqStack &S, SElemType &e) {

if (S.top == S.base) return error; e = *(S.top); S.top--;

标准

实用文档 return OK; }

Status GrammerAnalysis(SqStack &S, char *ch, char c) {

SElemType e;

Push(S, '#'); Push(S, 'E'); while (!((*(S.top) == '#') && (c == '#'))){ Pop(S, e); {

Push(S , 'A'); Push(S , 'T'); }

else if ((e == 'A') && (c == '+')) {

Push(S , 'A'); Push(S , 'T'); ch++; c = *ch; }

else if ((e == 'A') && ((c == ')')||(c == '#')));

else if ((e == 'T') && (((c >= '0') && (c <= '9')) ||(c>='a'&&c<='z')|| (c == '('))) Push(S , 'B'); Push(S , 'F'); }

else if ((e == 'B') && (c == '*')) { Push(S , 'B'); Push(S , 'F'); ch++; c = *ch; }

else if ((e == 'B') && ((c == '+')||(c == ')')||(c == '#'))); else if ((e == 'F') && ((c>='0'&&c<='9')||(c>='a'&&c<='z'))) { ch++;

while (((c = *ch) >= '0') && (c <= '9')||(c>='a'&&c<='z')) ch++; }

else if ((e == 'F') && (c == '(')) { Push(S, ')'); Push(S, 'E'); ch++; c = *ch;

if ((e == 'E') && (((c >= '0') && (c <= '9')) ||(c>='a'&&c<='z')|| (c == '(')))

标准

实用文档 }

else if ((e == ')') && (c == ')')) {ch++; c = *ch; }

else return error; } return OK; } int main() {

char str[50]; char c;

system(\SqStack S; InitStack(S);

printf(\

printf(\ 请输入表达式，以#键结束: printf(\scanf(\

c = *str; if (GrammerAnalysis(S,str,c)) {

printf(\语法分析通过\\n\printf(\表达式正确 \\n\} else{

printf(\语法分析未通过\\n\printf(\表达式错误 \\n\main(); return 0; }

递归下降

#include using namespace std; int a=1; char ch; int i=0; char str[80];

void T(void); void F(void); void E(void); void Error(void);

标准

|\\n\