编译原理作业(第一次)-完成retinf.c(阉割版)

来源：cnblogs　　作者：恶魔人Crybaby　　时间：2019/3/7 8:52:58　　对本文有异议

首先，作业要求概括如下：

根据前缀表达式文法，实现statements() 和expression() 两个函数。

并且要求使得语义分析在完成分析前缀表达式并输出中间代码的同时，也能够将前缀表达式翻译为中缀表达式, 且要求翻译后的中缀表达式中尽可能少用括号。

1 statements -> expression SEMI
2                 |  expression SEMI statements
3    
4 expression -> PLUS expression expression
5                |  MINUS expression expression
6                |  TIMES expression expression
7                |  DIVISION expression expression
8                |  NUM_OR_ID

举例如下：输入"+ a * b c;"时，应输出中缀式为" a + b * c", 而不是"a + (b * c)"或"(a) + (b * c)"等。

最后测试效果如下：

其中未实现河流命名算法故为阉割版。为方便读者阅读并理解后自行更改，这里只提供初版(low版)，其代码如下(DDL后会更新)：

  1 //retinf.c
  2 #include <stdio.h>
  3 #include <string.h>
  4 #include <stdlib.h>
  5 #include <stdbool.h>
  6 
  7 #include "lex.h"
  8 
  9 char err_id[] = "error";
 10 char * midexp;
 11 extern char * yytext;
 12 
 13 struct YYLVAL {
 14     int last_op;  /* last operation of expression
 15          for elimination of redundant parentheses */
 16 
 17     char * val;  /* 记录表达式中间临时变量 */
 18     char * expr; /* 记录表达式后缀式 */
 19 };
 20 
 21 typedef struct YYLVAL Yylval;
 22 
 23 Yylval * expression(void);
 24 
 25 char *newname(void); /* 在name.c中定义 */
 26 
 27 extern void freename(char *name);
 28 
 29 void statements(void) {
 30     Yylval *temp;
 31     printf("Please input an infix expression and ending with \";\"\n");
 32     while (!match(EOI)) {
 33 
 34         temp = expression();
 35 
 36         printf("The Expression Is %s\n", temp->expr);
 37         freename(temp->val);
 38 
 39         free(temp->expr);
 40         free(temp);
 41         if (match(SEMI)) {
 42             printf("Please input an infix expression and ending with \";\"\n");
 43             advance();
 44 
 45         }
 46         else {
 47             fprintf(stderr, "%d: Inserting missing semicolon\n", yylineno);
 48         }
 49     }
 50 }
 51 
 52 Yylval * expression(void) {
 53     Yylval *tempToReturn;
 54     tempToReturn = (Yylval *)malloc(sizeof(Yylval));
 55 
 56     Yylval *temp0, *temp1;
 57     while (match(PLUS) || match(MINUS) || match(TIMES) || match(DIVISION)) {
 58 
 59         char op = yytext[0];
 60         advance();
 61         temp0 = expression();
 62 
 63         temp1 = expression();
 64         
 65         bool tempToReturnIsPro = op == '*' || op == '/';
 66         bool temp0IsLower = temp0->last_op == PLUS || temp0->last_op == MINUS;
 67         bool temp1IsLower = temp1->last_op == PLUS || temp1->last_op == MINUS;
 68 
 69 
 70         if (tempToReturnIsPro) {
 71             if (temp0IsLower && temp1IsLower) {
 72                 tempToReturn->expr = (char*)malloc(strlen(temp0->expr) + strlen(temp1->expr) + 12);
 73                 sprintf(tempToReturn->expr, "( %s ) %c ( %s )", 
 74                     temp0->expr, op, temp1->expr);
 75             }
 76             else if (temp0IsLower) {
 77                 tempToReturn->expr = (char*)malloc(strlen(temp0->expr) + strlen(temp1->expr) + 8);
 78                 sprintf(tempToReturn->expr, "( %s ) %c %s",
 79                     temp0->expr, op, temp1->expr);
 80             }
 81             else if (temp1IsLower) {
 82                 tempToReturn->expr = (char*)malloc(strlen(temp0->expr) + strlen(temp1->expr) + 8);
 83                 sprintf(tempToReturn->expr, "%s %c ( %s )",
 84                     temp0->expr, op, temp1->expr);
 85             }
 86             else {
 87                 tempToReturn->expr = (char*)malloc(strlen(temp0->expr) + strlen(temp1->expr) + 4);
 88                 sprintf(tempToReturn->expr,  "%s %c %s",
 89                     temp0->expr, op, temp1->expr);
 90             }
 91         }
 92         else {
 93             tempToReturn->expr = (char*)malloc(strlen(temp0->expr) + strlen(temp1->expr) + 4);
 94             sprintf(tempToReturn->expr, "%s %c %s",
 95                 temp0->expr, op, temp1->expr);
 96         }
 97         switch (op)
 98         {
 99         case '+':tempToReturn->last_op = PLUS; break;
100         case '-':tempToReturn->last_op = MINUS; break;
101         case '*':tempToReturn->last_op = TIMES; break;
102         case '/':tempToReturn->last_op = DIVISION; break;
103         default:
104             break;
105         }
106 
107         printf("    %s %c= %s\n", temp0->val, op, temp1->val);
108         freename(temp1->val);
109         tempToReturn->val = temp0->val;
110         return tempToReturn;
111 
112     }
113 
114     if (match(NUM_OR_ID)) {
115         printf("    %s = %0.*s\n", tempToReturn->val = newname(), yyleng, yytext);
116         tempToReturn->expr = (char*)malloc(yyleng + 1);
117         strncpy(tempToReturn->expr, yytext, yyleng);
118         advance();
119         tempToReturn->last_op = TIMES;
120         return tempToReturn;
121     }
122     else if (match(SEMI)){
123         printf("111");
124         return;    
125     }
126     else {
127         tempToReturn->val = newname();
128         advance();
129         fprintf(stderr, "%d: Number or identifier expected\n", yylineno);
130         return;
131     }
132 }

另：

1 /*main.c XL分析器 */
2 
3 main()
4 {
5     statements();
6 }

 1 /*lex.c     XL分析器 */
 2 
 3 
 4 #include "lex.h"
 5 #include <stdio.h>
 6 #include <ctype.h>
 7 
 8 char       *yytext = "";  /* 当前词形,注意由于是直接指向
 9                    行缓冲区input_buffer,因此不是以'\0'结尾,
10                    因此使用时要小心, 设初值为0, 表示缓冲区为空,
11                    需要重新读行 */
12 int        yyleng = 0;   /* 词形的长度     */
13 int        yylineno = 0;   /* 输入的行号    */
14 
15 lex()
16 {
17     static char input_buffer[128];
18     char        *current;
19 
20     current = yytext + yyleng;      /* 跳过以读过的词形 */
21 
22     while (1) {                  /* 读下一个词形     */
23         while (!*current) {
24             /* 如果当前缓冲区已读完,重新从键盘读入新的一行.
25            并且跳过空格
26             */
27 
28             current = input_buffer;
29             /* 如果读行有误,返回 EOI */
30             if (!fgets(input_buffer, 127, stdin)) {
31                 *current = '\0';
32                 return EOI;
33             }
34 
35             ++yylineno;
36 
37             while (isspace(*current))
38                 ++current;
39         }
40 
41         for (; *current; ++current) {
42             /* Get the next token */
43 
44             yytext = current;
45             yyleng = 1;
46 
47             /* 返回不同的词汇代码 */
48             switch (*current) {
49             case ';': return SEMI;
50             case '+': return PLUS;
51             case '-': return MINUS;
52             case '/': return DIVISION;
53             case '*': return TIMES;
54             case '(': return LP;
55             case ')': return RP;
56 
57             case '\n':
58             case '\t':
59             case ' ': break;
60 
61             default:
62                 if (!isalnum(*current))
63                     fprintf(stderr, "Ignoring illegal input <%c>\n", *current);
64                 else {
65                     while (isalnum(*current))
66                         ++current;
67 
68                     yyleng = current - yytext;
69                     return NUM_OR_ID;
70                 }
71 
72                 break;
73             }
74         }
75     }
76 }
77 
78 static int Lookahead = -1;      /* 向前查看的词汇,设初值为-1
79                    表示第一次调用match函数时
80                    必须要读取一个词汇 */
81 
82 int match(int token)
83 {
84     /* 判断token是否和当前向前查看的词汇相同. */
85 
86     if (Lookahead == -1)
87         Lookahead = lex();
88 
89     return token == Lookahead;
90 }
91 
92 void advance()
93 {
94     /* 向前都一个词汇 */
95     Lookahead = lex();
96 }

 1 /* lex.h      XL分析器*/
 2 #define EOI           0        /*  end of input                */
 3 #define SEMI          1        /*       ;                      */
 4 #define PLUS          2        /*       +                      */
 5 #define TIMES         3        /*       *                      */
 6 #define LP            4        /*       (                      */
 7 #define RP            5        /*       )                      */
 8 #define NUM_OR_ID     6        /* decimal number or identifier */
 9 #define MINUS         7
10 #define DIVISION      8
11 extern char *yytext;        /* in lex.c                     */
12 extern int  yyleng;
13 extern int  yylineno;

/*name.c XL分析器 */
#include <stdio.h>
 
char  *Names[] = { "t0", "t1", "t2", "t3", "t4", "t5", "t6", "t7",
           "t8", "t9", "t10", "t11", "t12", "t13", "t14", "t15" };
char  **Namep = Names;
extern int yylineno;
char  *newname()
{
    if (Namep >= &Names[sizeof(Names) / sizeof(*Names)]) {
        fprintf(stderr, "%d: Expression too complex\n", yylineno);
        exit(1);
    }
    return(*Namep++);
}
freename(s)
char    *s;
{
    if (Namep > Names)
        *--Namep = s;
    else
        fprintf(stderr, "%d: (Internal error) Name stack underflow\n",
            yylineno);
}

具体生成方法不一，使用makefile方式最好。

这里只提供基本的gcc 方式（部分linux中没有自带，自行安装）。

 1 gcc -c lex.c
 2 
 3 gcc -c retinf.c
 4 
 5 gcc -c name.c
 6 
 7 gcc -c main.c
 8 
 9 gcc -o namebalabala lex.o retinf.o name.o main.o
10 //gcc -o namebalabala *.o
11 
12 ./namebalabala