MPP II 习题2.5.5.d 的awk实现

题目:

随机句子生成,本程序的输入是一个如下的上下文无关文法： S → NP VPNP → AL N | NN → John | MaryAL→ A | A ALA → Big | Little | TinyVP → V AvLV → runs | walksAvL → Av | AvL AvAv → quickly | slowly 程序应当生成随机的句子，如“John walks quickly”或“Big Little Mary runs slowly quickly slowly” .

 

本来想用递归,但是AWK里没有局部变量（只有全局），又不支持数组做参数传递。决定采用堆栈实现

CODE:

1 function createsen(sentense) 2 { 3         srand() 4         initsyntac() 5         while(1)       6         { 7                 if (!( sentense in syntax)) 8                 { 9                         10                         if (! match(output,sentense)) 11                             { 12                                 output=sentense " " output 13                         } 14                 } 15                 else 16                 { 17                         split(syntax[sentense],A_sen,"|") 18                         A_sen_length=0 19                         for(A_sen_index in A_sen) 20                         { 21                                 A_sen_length = A_sen_length +1 22                         } 23                         A_s_index=int(rand()*A_sen_length+1) 24                         split(A_sen[A_s_index],A_senten," ") 25                         for(A_senten_index in A_senten) 26                                 push(A_senten[A_senten_index]); 27                 } 28                 if(stackindex > 0) pop() 29                 else break 30                 sentense=popval 31         } 32          print output 33 } 34 function pop() 35 { 36         popval=stack[stackindex] 37         stackindex – 38 } 39 function push(pushstr) 40 { 41         stackindex ++ 42         stack[stackindex]=pushstr 43 } 44 function initsyntac() 45 { 46         syntax["S"]   = "NP VP NT" 47         syntax["NP"]  = "AL N|N" 48         syntax["N"]   = "Jiang|Luke" 49         syntax["AL"]  = "A|A AL" 50         syntax["A"]   = "Stupid|Foolish|Lucky" 51         syntax["VP"]  = "V AvL|is N2" 52         syntax["V"]   = "get|win" 53         syntax["AvL"] = "Av|AvL Av" 54         syntax["Av"]  = "slowly|quickly|fucking" 55         syntax["NT"]  = "AL N2" 56         syntax["N2"]  = "pig|dog|bitch|asshole" 57         58 } 59 BEGIN{ 60         print createsen("S") 61 }

 

运行结果

>awk  -f CreatSenten.awk Stupid Stupid JiangZhou get quickly fucking foolish dog