编译原理递归下降语法分析器C++实现

80 阅读 0 评论 53 点赞

我是靠谱客的博主畅快钢笔，最近开发中收集的这篇文章主要介绍编译原理递归下降语法分析器C++实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

编译原理递归下降语法分析器C++简单实现

1.递归下降分析法的功能

语法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。

2.递归下降分析法的前提

改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（1）文法。

3.递归下降分析法实验设计思想及算法

为G的每个非终结符号U构造一个递归过程,不妨命名为U。U的产生式的右边指出这个过程的代码结构：

(1)若是终结符号，则和向前看符号对照，若匹配则向前进一个符号；否则出错。

(2)若是非终结符号，则调用与此非终结符对应的过程。当A的右部有多个产生式时,可用选择结构实现, 具体为：（1）对于每个非终结符号U->u1|u2|…|un处理的方法如下

U( )

{

ch=当前符号;

if(ch可能是u1字的开头) 处理u1的程序部分；

else if(ch可能是u2字的开头)处理u2的程序部分；

…..

else error();

}

（2）对于每个右部u1->x1x2…xn的处理架构如下：

处理x1的程序；

处理x2的程序；

……

处理xn的程序；

（3）如果非终结符U有空产生式：Uàε ，则还需考虑ch属于Follow(U)的情况。

引入对空串的非特殊分析

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
using namespace std;
char str[10];
int index = 0;

void E();  // E->TX;
void X();  // X->+TX|-TX|^
void T();  // T->FY
void Y();  // Y->*FY|/FY|^
void F();  // F->(E) | i
int count;
int m ,n;
int len;
void rank1(){
    printf("%dt",count);
    count++;
}

void analyze(){
    if(m<0)
        cout<<' ';
    else{
        for(int i = 0;i <= m;i++)
            cout<<str[i];
    }
    cout<<'t'<<'t'<<'t';
}

void latter(){
    printf("%c",str[index]);
    cout<<'t'<<'t'<<'t';
}

void remain(){
    for(int j = n+1;j <= len;j++)
        cout<<str[j];
    cout<<'n';
}

/*
文法G[E]:
E→E+T|E-T|T
T→T*F|T/F|F
F→(E)|i

消除左递归后：
E→TX
X→+TX|-TX|^
T→FY
Y→*FY| /FY|^
F→(E)|i
*/

int main() {
    count = 0;m = -1,n = -1;index = 0;
    printf("请输入算数表达式：");
    scanf("%s", str);
    len = strlen(str);
    str[len] = '#';
    printf("步骤t 文法tt 分析串ttt分析字符tt剩余串n");
    E();
    if (str[index] == '#')
        printf("正确n");
    else
        printf("分析失败n");
    return 0;
}

void E() {
    rank1();printf("E -> TXtt");analyze();latter();remain();
    T();
    X();
}

void X() {
    if (str[index] == '+') {
        rank1(); printf("X ->+TXtt");m++;n++;analyze();latter();remain();
        index++;
        T();
        X();
    }
    else if (str[index] == '-') {
        rank1(); printf("X ->-TXtt");m++;n++;analyze();latter();remain();
        index++;
        T();
        X();
    }
    else{
        rank1();printf("X -> ^tt");analyze();latter();remain();
    }
}
void T() {
    rank1();printf("T -> FYtt");analyze();latter();remain();
    F();
    Y();
}
void Y() {
    if (str[index] == '*') {
        rank1();printf("Y ->*FYtt");m++;n++;analyze();
        latter();remain();index++;
        F();
        Y();
    }
    else if (str[index] == '/') {
        rank1();printf("Y ->/FYtt");m++;n++;analyze();
        latter();remain();index++;
        F();
        Y();
    }
    else{
        rank1();printf("Y -> ^tt");analyze();latter();remain();
    }
}
void F() {
    if (str[index] == 'i'){
        rank1();printf("F ->itt");m++;n++;analyze();latter();remain();
        index++;
    }
    else if (str[index] == '('){
        rank1();printf("F ->(E)tt"); m++;n++;analyze();latter();remain();
        index++;
        E();
        if (str[index] == ')') {
            rank1();printf("F ->(E)tt");m++;n++;analyze();latter();remain();
            index++;
        }else {
            printf("分析失败n");
            exit(0);
        }
    }
    else{
        printf("分析失败n");
        exit(0);
    }
}

/*
文法G[E]:
E→E+T|E-T|T
T→T*F|T/F|F
F→(E)|i

消除左递归后：
E→TX
X→+TX|-TX|^
T→FY
Y→*FY| /FY|^
F→(E)|i
*/