編譯原理作業(第一次)-完成retinf.c(閹割版)

首先，作業要求概括如下：根據首碼表達式文法，實現statements() 和expression() 兩個函數。並且要求使得語義分析在完成分析首碼表達式並輸出中間代碼的同時，也能夠將首碼表達式翻譯為中綴表達式, 且要求翻譯後的中綴表達式中儘可能少用括弧。舉例如下：輸入"+ a * b c;" ...

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

根據首碼表達式文法，實現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