lex 和 yacc 程序将中缀转换为前缀

Question

我是 lex 和 yacc 程序的新手。我一直在尝试编写一个 yacc 程序，该程序将算术表达式作为输入并给出前缀表示法作为输出。 这是我的 lex 代码。

%{
#include<string.h>
#include"pre.tab.h"
%}
%%
"*"|"/"|"+"|"-"|"("|")" {return yytext[0];}
[0-9]+ {yylval.name=(char*)malloc(yyleng+1);
   strcpy(yylval.name,yytext);
   return NUM;}
\n {return(0);}
[a-zA-Z][a-zA-Z]* {yylval.name=(char*)malloc(yyleng+1);
      strcpy(yylval.name,yytext);
      return ID;}
. {}
%%
int yywrap()
{
return 1;
}

这是我的 YACC 代码

%{
#include<stdio.h>
#include<string.h>
char buf[10];
%}

%union
{
  char *name;
}
%token<name>NUM ID
%type<name>E 
%left'+''-'
%left'*''/'
%nonassoc UMINUS
%%
S:E  {printf("\n%s",$1);}
;
E:E'*'E {buf[0]='\0';strcpy($$,strcat(strcpy(buf,"*"),strcat($1,$3)));}
|E'/'E {buf[0]='\0';strcpy($$,strcat(strcpy(buf,"/"),strcat($1,$3)));}
|E'+'E {buf[0]='\0';strcpy($$,strcat(strcpy(buf,"+"),strcat($1,$3)));}
|E'-'E {buf[0]='\0';strcpy($$,strcat(strcpy(buf,"-"),strcat($1,$3)));}
|ID
|NUM
|'('E')'{strcpy($$,$2);}
;
%%
main()
{
yyparse();
}
int yyerror(char *s) {fprintf(stderr,"%s\n",s);}

当我在括号中输入算术表达式时，我没有得到任何输出。例如：输入：1+(2*3) 输出：+*23*23。我多次尝试修改代码但没有成功。

Answer 1

在 C 语言中，字符串不会像其他语言那样神奇地扩展。 （或者，更好地说，确实不存在字符串对象。）除非您已经确保字符数组

strcat(a, b)

在 NUL 终止符后面有足够的空间来附加

a

，否则您无法调用

b

。

你不能

strcat

到字符串文字，因为不仅没有足够的空间，而且字符串文字可能位于只读内存中。

并且您不能对未分配的变量进行 strcpy 并期望自动分配足够的内存。 （虽然

$$

实际上并不是一个未初始化的变量，因为它被初始化为

$1

的值。）

所以你的代码充满了缓冲区溢出，这是未定义的行为。

Answer 2

感谢您提出这个问题。我正在寻找适用于中缀到后缀的代码，这看起来很简单。我不知道你是否解决了这个问题。我使用

strdup

函数将内容复制到

$$

而不是

strcpy

。这对我来说效果很好。