2014-05-12

Yacc 與 Lex 練習 - UVa 11291

1. Problem
2. Yacc
3. Lex
4. make file
5. 執行
1. 5.1. 參考範例輸入
2. 5.2. 參考範例輸出
6. Reference
7. 指導

Problem

語法

1 2	<E[x]> -> <Integer> \| (p <E[x]> <E[x]>) <Integer> -> #number

目標計算出 E[X] = p * (e1 + e2) + (1 - p) * (e1 - e2)

Yacc

Yacc 主要是根據 CFG 進行解析。

其中，要對於 Yacc 語法的回傳值明白操作情況。

對於語法回傳值，我們來個最簡單的範例：

1 2	expression -> LEFT_P NUMBER expression expression RIGHT_P $$ $1 $2 $3 $4 $5

其中 $$ 是回傳值，其中的 $1、$2 … 等，都是得到的回傳值。

對於 yylval 形態處理：

%union {
    float 	floatVal;
    int 	intVal;
}

通常使用 union 的方式來共用記憶體，在 lex 那邊就可以根據 yylval.floatVal 進行操作。

當然，我們也要對於每一個 nonterminal 定義回傳的型態

1
2
3

%type <floatVal> NUMBER
%type <floatVal> expression
%type <floatVal> startsymbol

基本上就大功告成了。

接著要考慮如何去完成多組測資組的問題，在這裡可以利用 kleene star 來完成。

但是對於輸出順序，使用 input -> input startsymbol 跟 input -> startsymbol input 輸出順序是不同的，如果要順著輸出，請選擇前者。

file: a.y

%{
#include <stdio.h>
int yylex();
double ans = 0;
void yyerror(const char* message) {
    ans = -2147483647;
    printf("Invaild format\n");
};
%}
%union {
    float 	floatVal;
    int 	intVal;
}
%type <floatVal> NUMBER
%type <floatVal> expression
%type <floatVal> startsymbol
%token LEFT_P RIGHT_P NUMBER
%%
input
    : input startsymbol {
        ans = $2;
        printf("%.2f\n", ans);
    }
    | {
    }
startsymbol
    : expression {
        $$ = $1;
    }
    ;
expression
    : NUMBER {
        $$ = $1;
    } 
    | LEFT_P NUMBER expression expression RIGHT_P {
        $$ = $2 * ($3 + $4) + (1.0f - $2) * ($3 - $4);
    }
    ;
%%
int main() {
    yyparse();
    return 0;
}

Lex

Lex 主要是扮演切出所有的 token 的角色，相當於 Scanner。同時要將值紀錄再 yylval 中，在 Yacc 那邊則會在 $NUMBER 中得到變數值。

在 Lex 語法上要特別小心，如果兩條的前綴 (prefix) 相同時 (解析上會產生相同的 token)，則會選擇長的那一條為優先。如果長度仍相同的話，請自行測試，這裡無法給予解答。而為什麼要這麼設計？為了保證後綴不會塞入奇怪的字符，因此可以先檢查隨後接的字符情況。

file: a.l

%{
#include "a.tab.h"
#include <stdio.h>
%}
%%
([-]?)[0-9]*\.[0-9]*		{sscanf(yytext, "%f", &yylval.floatVal); return NUMBER;}
([-]?)[0-9]+				{sscanf(yytext, "%f", &yylval.floatVal); return NUMBER;}
"("					{return LEFT_P;}
")"					{return RIGHT_P;}
\n					{}
.					{}
%%

make file

請用以下方法建造

1	morris $ sh make.sh

代碼如下

file: make.sh

bison -d a.y
flex a.l
gcc -c a.tab.c
gcc -c lex.yy.c
gcc lex.yy.o a.tab.o -lfl

產生的結果如下

$ tree 
. ├── a.l
  ├── a.out 
  ├── a.tab.c 
  ├── a.tab.h 
  ├── a.tab.o 
  ├── a.y 
  ├── input~ 
  ├── lex.yy.c 
  ├── lex.yy.o 
  ├── make.sh 
  ├── make.sh~ 
  ├── testdata 
  │   ├── ac_output 
  │   └── input

執行

執行的時候就跟標準輸入串流一樣。

1	morris $ ./a.out <input

參考範例輸入

7
(.5 3 9)
(0.3 2 (1 1 -10))
(1.0 (1.0 (1.0 -1 -2) (1.0 -1 -2)) (1.0 (1.0 1 2) 2))
(0.99 82 (0.76 50 (0.85 (0.07 (0.88 28 (0.98 79 (0.09 77 51))) (0.30 (0.29 36 (0.36 (0.51 27 (0.68 (0.47 87 35) (0.25 85 59))) 31)) 64)) (0.14 (0.84 (0.77 29 71) (0.50 (0.99 (0.81 (0.78 (0.87 50 7) 71) 72) 14) (0.30 (0.50 9 37) (0.67 21 (0.73 86 (0.08 31 14)))))) (0.94 (0.96 (0.50 27 (0.94 (0.54 62 (0.63 89 29)) (0.81 24 (0.94 20 72)))) 4) (0.44 9 (0.59 (0.70 48 40) (0.64 (0.27 97 71) 43))))))))
(0.15 12 60)
(0.55 18 (0.95 (0.79 95 (0.97 (0.11 (0.96 (0.70 (0.38 73 66) (0.38 (0.06 (0.02 88 66) (0.39 35 37)) 69)) (0.81 3 (0.45 5 61))) (0.44 (0.67 (0.23 82 7) 38) (0.24 49 74))) 76)) (0.46 19 44)))
(0.56 62 77)
(0.03 (0.90 19 35) (0.17 50 (0.13 (0.96 74 (0.07 (0.51 78 (0.77 (0.78 (0.84 64 (0.41 7 59)) 21) (0.73 (0.95 (0.13 2 85) (0.08 29 50)) (0.24 (0.12 43 99) 71)))) 84)) (0.31 69 (0.82 31 24)))))
(0.78 73 44)
(0.09 (0.80 14 62) (0.57 (0.57 95 (0.33 94 31)) (0.70 (0.92 32 (0.13 20 (0.44 87 (0.45 83 26)))) (0.43 40 (0.51 (0.57 29 (0.65 13 (0.40 74 56))) 56)))))
(0.96 (0.96 (0.65 (0.01 (0.98 (0.34 86 (0.68 87 21)) 27) (0.26 68 68)) (0.42 28 29)) 9) 99)
(0.99 (0.60 53 27) (0.35 23 (0.15 (0.50 85 (0.73 56 (0.34 (0.44 (0.10 (0.62 (0.20 58 15) 56) (0.57 74 (0.23 20 78))) 62) (0.92 (0.72 (0.82 75 (0.08 35 93)) 43) (0.55 10 (0.45 (0.25 52 91) 71)))))) (0.61 39 (0.49 (0.92 87 (0.13 52 (0.69 (0.46 (0.82 27 72) 96) (0.27 51 99)))) (0.36 99 (0.60 68 (0.49 (0.25 (0.92 54 7) (0.48 47 32)) (0.08 (0.69 97 11) 34)))))))))
(0.87 (0.32 (0.42 (0.66 69 (0.98 0 (0.46 94 (0.25 (0.57 (0.72 25 59) (0.35 91 (0.42 29 28))) 3)))) 19) 81) (0.72 (0.06 (0.66 (0.07 22 87) 44) (0.18 33 14)) 49))
(0.72 (0.01 67 (0.13 (0.22 (0.88 11 86) (0.04 40 (0.41 (0.86 (0.81 (0.08 84 95) (0.88 19 67)) 8) 96))) 13)) (0.13 45 (0.19 (0.83 85 (0.77 (0.37 78 (0.44 44 59)) 37)) 56)))
(0.51 (0.36 2 72) 25)
(0.32 51 87)
(0.06 (0.23 (0.70 93 47) (0.22 20 (0.90 (0.03 (0.48 (0.84 18 (0.29 (0.02 (0.06 52 49) 67) (0.49 (0.69 60 74) (0.59 92 0)))) 32) 80) (0.76 78 (0.66 8 94))))) 31)
(0.29 (0.54 70 (0.64 (0.48 (0.50 25 (0.38 (0.07 (0.14 (0.44 (0.76 44 45) 67) 41) (0.15 (0.86 (0.89 87 42) (0.43 85 58)) (0.98 44 (0.48 34 28)))) (0.84 81 60))) 28) 16)) (0.84 (0.21 34 (0.78 (0.76 (0.51 82 (0.07 (0.78 (0.52 (0.65 51 58) 12) (0.05 52 (0.98 0 30))) (0.01 27 3))) (1.00 15 (0.53 (0.91 (0.38 62 (0.75 92 69)) (0.85 53 (0.84 92 83))) (0.70 (0.12 (0.24 23 83) 58) (0.62 56 38))))) 36)) (0.66 41 13)))
(0.94 (0.47 30 56) (0.78 6 (0.45 (0.45 15 94) (0.77 (0.57 25 (0.33 66 12)) (0.66 74 (0.82 (0.14 75 50) (0.22 45 43)))))))
(0.66 (0.58 (0.85 75 26) 45) (0.04 (0.94 82 (0.59 34 (0.02 (0.09 11 (0.31 (0.05 (0.92 (0.14 51 45) (0.47 25 46)) 6) 5)) 33))) (0.81 (0.09 15 (0.91 (0.77 (0.59 44 (0.57 (0.39 (0.81 18 75) (0.37 41 67)) 18)) (0.77 (0.68 (0.71 (0.31 87 94) 85) (0.00 35 (0.55 81 22))) 56)) 3)) (0.43 7 (0.98 94 3)))))
(0.13 22 80)
(0.77 45 81)
(0.61 (0.21 (0.32 (0.32 (0.81 8 60) 78) (0.19 (0.92 68 (0.56 (0.22 79 32) (0.32 72 63))) 41)) (0.30 94 31)) (0.80 59 33))

參考範例輸出

7.00
3.00
5.60
-1.00
241.55
-30.00
32.05
71.24
25.80
97.64
-37.98
153.38
67.92
35.81
-10.21
-17.66
19.68
60.84
92.20
30.61
157.62
-37.20
88.74
-48.46

Reference

Yacc 与 Lex 快速入门

指導

Inker

Morris' Blog