解題區►解題區 - UVa

Yacc 與 Lex 練習 - UVa 11291

contents

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

Problem

詳細題目請參考 UVa 11291 - Smeech

語法

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 形態處理：

1
2
3
4
%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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
%{
#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
1
2
3
4
5
6
7
8
9
10
11
12
13
%{
#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
1
2
3
4
5
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

產生的結果如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
$ 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

參考範例輸入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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))

參考範例輸出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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