C语言算数表达式识别算法 - 消除左递归 - 代码详解

#include <stdio.h> #include <stdlib.h> #include <string.h> #include 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("%d ", count); count++; }

void analyze() { if (m < 0) printf(" "); else { for (int i = 0; i <= m; i++) printf("%c", str[i]); printf(" "); } }

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

void remain() { for (int j = n + 1; j <= len; j++) printf("%c", str[j]); printf("\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("步骤 文法 分析串 分析字符 剩余串\n"); E(); if (str[index] == '#') printf("是\n"); else printf("否\n"); return 0; }

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

void X() { if (str[index] == '+') { index++; rank1(); printf("X ->+TX "); m++; n++; analyze(); latter(); remain(); T(); X(); } else if (str[index] == '-') { index++; rank1(); printf("X ->-TX "); m++; n++; analyze(); latter(); remain(); T(); X(); } else { rank1(); printf("X -> ^ "); analyze(); latter(); remain(); } } void T() { rank1(); printf("T -> FY "); analyze(); latter(); remain(); F(); Y(); } void Y() { if (str[index] == '*') { index++; rank1(); printf("Y ->*FY "); m++; n++; analyze(); latter(); remain(); F(); Y(); } else if (str[index] == '/') { index++; rank1(); printf("Y ->/FY "); m++; n++; analyze(); latter(); remain(); F(); Y(); } else { rank1(); printf("Y -> ^ "); analyze(); latter(); remain(); } } void F() { if (str[index] == 'i') { index++; rank1(); printf("F ->i "); m++; n++; analyze(); latter(); remain(); } else if (str[index] == '(') { index++; rank1(); printf("F ->(E) "); m++; n++; analyze(); latter(); remain(); E(); if (str[index] == ')') { index++; rank1(); printf("F ->(E) "); m++; n++; analyze(); latter(); remain(); } else { printf("否\n"); exit(0); } } else { printf("否\n"); exit(0); }