消除左递归1.c

对给定的文法消除左递归。

/*
  给定表达式文法G，产生式如下：（E为开始符）
  E -> E+T|E-T|T
  T -> T*F|T/F|T%F|F
  F -> -F|+F|(E)|N
  N -> 0N|1N|...|9N|0|1|...|9

  对于任意w$（$为结束符号）,若w属于L(G)，则计算并输出w的值，否则输出error.
  其中"/"为整数除法， "%"为求余除法。
*/
/*
    消除左递归后,翻译模式如下:
    E -> T   {R.in = T.val}
         R   {E.val = R.s}
    R -> +T  {R1.in = R.in + T.val}
         R1  {R.s = R1.s}
    R -> -T  {R1.in = R.in - T.val}
         R1  {R.s = R1.s}
    T -> F   {P.in = F.val}
         P   {T.val = P.s}
    P -> *F  {P1.in = P.in * F.val}
         P1  {P.s = P1.s}
    P -> /F  {P1.in = P.in / F.val}
         P1  {P.s = P1.s}
    P -> %F  {P1.in = P.in % F.val}
         P1  {P.s = P1.s}
    P -> ε  {P.s = P.in}
    F -> -F  {F.val = -F.val}
    F -> +F  {F.val = F.val}
    F -> (E) {F.val = E.val}
    F -> N   {F.val = N.val}
    N -> 0N|1N|...|9N|0|1|...|9  {N.val = get_integer()}
    最后一个产生式没有使用正常的翻译模式来做.由于N.val是一个从用户的输入字符串
中得到的整数,函数get_integer()用一个很简单的方法将字符串转换成整数后返回. 
*/

#include <stdio.h>
#include <stdlib.h>

char ch;

int E(void);
int R(int);
int T(void);
int P(int);
int F(void);

void getnc(void)
{
  do
  {
    ch = getchar();
  }
  while (ch == ' ' || ch =='\n');
}

/*取整数*/
int get_integer(void)
{
  int result = 0;
  while (ch >= '0' && ch <= '9')
  {
    result = result * 10 + ch - '0';
    ch = getchar(); /*由于一个整数的各个位间不能有空格或回车,这里用C语言的
                      getchar(),而不用getnc(). */
  }
  if (ch == ' ' || ch == '\n')
    getnc();     /*返回前取下一个不为空格且不为回车的字符*/
  return result;
}

void error(void)
{
  puts("\nerror.");
  exit(0);
}

int E()
{
  return R(T());
}

int R(int r_in)
{
  if (ch == '+')
  {
    getnc();
    return R(r_in + T());
  }
  else if (ch == '-')
  {
    getnc();
    return R(r_in - T());
  }
  else
    return r_in;
}

int T()
{
  return P(F());
}

int P(int p_in)
{
  if (ch == '*')
  {
    getnc();
    return P(p_in * F());
  }
  else if (ch == '/')
  {
    getnc();
    return P(p_in / F());
  }
  else if (ch == '%')
  {
    getnc();
    return P(p_in % F());
  }
  else
   return p_in;
}

int F()
{
  if (ch == '-')
  {
    getnc();
    return -F();
  }
  else if (ch == '+')
  {
    getnc();
    return F();
  }
  else if (ch == '(')
  {
    int result;
    getnc();
    result = E();
    if (ch != ')')
      error();
    getnc();
    return result;
  }
  else if (ch >= '0' && ch <= '9') /*如果下面是整数,则调用get_integer()取它*/
    return get_integer();
  else
    error();
}

void main()
{
  int result;
  getnc();
  result = E();
  if (ch != '$')
    error();
  printf("%d",result);
}