How To Build a Yacc(1)
Yacc 是什么？
編譯器的編譯器。
簡單來說，Yacc讀入一套語法定義規(guī)格(syntax rules), 然后分析一段代碼(source code), 判斷代碼是否符合定義好的syntax rules。
語法定義規(guī)格是由形式化的BNF表達(dá)式來定義；目前大多數(shù)語言都可以用它來定義。
一個(gè)BNF表達(dá)式由一個(gè)NONTERMINAL（非終結(jié)符）和它的產(chǎn)生式組成，產(chǎn)生式可以是終結(jié)符（TERMINAL）和非終結(jié)符組成的序列。比如，我們定義一個(gè)函數(shù)聲明:
function_decl := function func_name ( argment_list );
func_name := id
argument_list := argument_list , id
argument_list := id
斜體字表示非終結(jié)符，而粗體的是終結(jié)符。
一套完整的BNF文法意味著每一個(gè)NONTERMINAL最終都可以推導(dǎo)為一系列的TERMINAL。
一套文法定義了什么樣的語言？如上面的function_decl, 非形式化的來說，一個(gè)function_decl 開頭是一個(gè)function關(guān)鍵字,然后緊接著一個(gè)func_name，也就是一個(gè)id,表示函數(shù)名字，然后是一個(gè)'(', 加上一個(gè)參數(shù)列表，再加上一個(gè)')'
參數(shù)列表是由','分隔的id列表。
例如：function foo (kick, so, by);
BNF或是擴(kuò)展EBNF(擴(kuò)展BNF)表達(dá)式有幾下幾種表達(dá)方式:
S := A B C (S 推導(dǎo)出A B C 三個(gè)部分)
S := A | B | C (S推導(dǎo)出A 或 B 或 C三個(gè)符號(hào))
S := { A } (S推導(dǎo)出一個(gè)或多個(gè)A}
How To Build a Yacc(2)
如何識(shí)別一段代碼是否符合定義的文法？
如上面的例子：
function foo(kick, so, by);
首先，技術(shù)上來說，代碼文本是一段字符流，f, u, n, c....，而我們文法識(shí)別的最小級(jí)別是符號(hào)(token), 所以需要將其轉(zhuǎn)化為符號(hào)流，這個(gè)功能可以很容易的用lex實(shí)現(xiàn)，這個(gè)步驟不是講述重點(diǎn)，不加詳細(xì)敘述。
最直接的識(shí)別方法，以function_decl文法為例,我們從符號(hào)流中取一個(gè)當(dāng)前符號(hào)，然后判斷這個(gè)符號(hào)是否屬于開始符號(hào)(function_decl)的某個(gè)產(chǎn)生式的第一個(gè)符號(hào), 如果找到了這樣一個(gè)產(chǎn)生式，那么認(rèn)為應(yīng)該按照這個(gè)產(chǎn)生式進(jìn)行展開，匹配并丟棄當(dāng)前這個(gè)符號(hào)，并期望符號(hào)流中余下的符號(hào)能匹配該產(chǎn)生式剩余的符號(hào)；那么繼續(xù)從符號(hào)流中取去下一個(gè)符號(hào)，繼續(xù)上面的步驟。
如果要用一個(gè)算法來描述它，那么看起來，象這個(gè)樣子。
// 匹配一個(gè)符號(hào)token...
void match(token)
{
if (current_token == token) current_token = get_next_token();
else error("expect {token}, but give {current_token}")
}
// function_decl 用來匹配一個(gè)函數(shù)聲明語句；
// function_decl 的產(chǎn)生式為:
// function_decl := function func_name ( argment_list );
void function_decl( )
{
current_token = get_next_token(); // 取出一個(gè)符號(hào)
match(function); // 匹配function
func_name(); // 如果已經(jīng)匹配，那么接下來應(yīng)該匹配函數(shù)名字了
match('('); // 匹配'('
argument_list(); // 接下來應(yīng)該參數(shù)列表
match(')'); // 匹配')'
}
void func_name()
{
match(id);
}
void argument_list()
{
while (current_token == id) {
match(",");
}
}
如此簡單？是不是？
以上的分析技術(shù)被稱為遞歸下降分析技術(shù)，它對大多數(shù)簡單的語法規(guī)則非常有效。
這種分析方法可以很容易的被歸納成一些簡單的規(guī)則，根據(jù)這些規(guī)則，我們可以方便的編制分析程序。
在闡述這些規(guī)則之前，有必要介紹一個(gè)概念：fisrt集合。
什么是fisrt集合？
一個(gè)產(chǎn)生式的first項(xiàng)目就是這個(gè)產(chǎn)生式(production)的匹配第一個(gè)非終結(jié)符號(hào)。一套文法的所有產(chǎn)生式的first項(xiàng)目組成了first集合。求解first集合的方法：對于production: S = ABC
first(ABC) ， 如果A是一個(gè)terminal, 那么first(ABC)= A, 如果A是一個(gè)NONTERMINAL, 那么first(ABC) = first(A), 如果A最終被推出一個(gè)空的符號(hào)，那么first(ABC) = first(BC), 依次類推。
這個(gè)概念之所以重要，是因?yàn)樵谶f歸下降算法中，在匹配一個(gè)非終結(jié)符的過程中，需要檢測當(dāng)前符號(hào)流中的符號(hào)是否屬于該非終結(jié)符的所有產(chǎn)生式的first集合；如果屬于，則用該產(chǎn)生式來擴(kuò)展這個(gè)非終結(jié)符。
如何編寫遞歸下降解析程序？
是時(shí)候總結(jié)一下規(guī)律了，對于每個(gè)產(chǎn)生式a來說，我們定義T(a) 是匹配a的程序代碼：
when: a = A (A是terminal)
T(a):
if (t == A) t = get_next_token();
else error (t 是當(dāng)前符號(hào)，get_next_token取得下一個(gè)符號(hào))
when: a = X (X是nonterminal)
T(a): X(); 定義一個(gè)X的函數(shù)，實(shí)現(xiàn)由X的產(chǎn)生式定義。
when: a = a1 | a2 | a3 | ... | aN
T(a):
if (t <- First(a1) ) T(a1)
else if (t <- First(a2)) T(a2)
...
else if (t <- First(aN)) T(aN)
else error
when: a = a1 a2 ... aN
T(a): T(a1) T(a2) ... T(aN)
when: a = {a1}
T(a): while (t <- First(a1)) T(a1)
How To Build a Yacc(3)
在(2)中，我們闡述了一個(gè)簡單高效的分析方法，最終產(chǎn)生一個(gè)文法的最左推導(dǎo)(即每次優(yōu)先擴(kuò)展左邊的NONTERMINAL)
但是遞歸下降算法有些許局限性，比如：對于兩個(gè)不同的NONTERMINAL，如果他們的FIRST集合有交集的話，就會(huì)產(chǎn)生歧義，很顯然，當(dāng)目前的符號(hào)分別屬于兩個(gè)不同的NONTERMINAL的FIRST集合時(shí)，就無法決定采用哪個(gè)產(chǎn)生式了。
我們來考慮另外一種分析方法，與遞歸下降相反，它最終產(chǎn)生一個(gè)文法的最右推導(dǎo)。我們稱這種方法為LR分析。
LR分析基于一種有窮確定性自動(dòng)機(jī)（DFA）原理，根據(jù)語法規(guī)則來創(chuàng)建一個(gè)DFA， 然后判斷輸入的符號(hào)流是否最后落入這個(gè)DFA的ACCEPT狀態(tài)。
如何根據(jù)語法規(guī)則建立DFA？
DFA是一個(gè)狀態(tài)集合，這些狀態(tài)由某些確定的有向邊連接；DFA由一個(gè)初始狀態(tài)開始，接受一個(gè)符號(hào)，進(jìn)入下一個(gè)狀態(tài)。那么LR分析中的DFA狀態(tài)是什么？想象一個(gè)當(dāng)前推導(dǎo)狀態(tài)這個(gè)概念，即對于一個(gè)文法來說，當(dāng)它識(shí)別了一些符號(hào)流以后，進(jìn)入到一個(gè)什么樣的狀態(tài)。這個(gè)狀態(tài)要么還剩下一些符號(hào)有待識(shí)別，要么已經(jīng)完成。
以前面的文法為例：
初始時(shí)候：
一個(gè)符號(hào)都沒有識(shí)別，DFA需要識(shí)別整個(gè)文法的初始符號(hào)。我們標(biāo)記為：
S = # function_decl (I1)
將'#'定義為“當(dāng)前識(shí)別位置”，S是一個(gè)虛擬符號(hào)，我們將這個(gè)表達(dá)式定義為一個(gè)項(xiàng)目(item) ,這個(gè)項(xiàng)目認(rèn)為，沒有識(shí)別一個(gè)符號(hào)，DFA需要識(shí)別的是整個(gè)function_decl代表的符號(hào)串。
由于我們每次只從符號(hào)流中取出一個(gè)符號(hào)，因此將DFA一步就將整個(gè)function_decl全部識(shí)別是不可能的，只能將function_decl展開，看看function_decl下一個(gè)要識(shí)別的TERMINAL是什么，這就引出了閉包(closure)的概念: 一個(gè)狀態(tài)的closure集合這樣定義的，遍歷這個(gè)狀態(tài)中的所有item,如果#后面緊接的是一個(gè)NONTERMINAL，那么將這個(gè)NONTERMINAL的所有產(chǎn)生式的初始化項(xiàng)目加入到這個(gè)集合中。
比如I1的closure集合S1為：
S := # function_decl (I1)
function_decl := # function func_name ( argment_list ); (I2)
這就是初始狀態(tài)(S1)
繼續(xù)推導(dǎo)(S1)以后的狀態(tài)，我們要求解后續(xù)狀態(tài)，主要方法是看當(dāng)前位置(#)后面緊接的符號(hào),如果符號(hào)流中下一個(gè)符號(hào)與之相同，那么當(dāng)前位置后移一位，DFA進(jìn)入了下一個(gè)狀態(tài)(S2), 而由狀態(tài)(S1)到(S2)的邊的輸入符號(hào)，就是#后面的符號(hào)。
那么如果下一個(gè)符號(hào)是 function , 那么（S1）進(jìn)入下一個(gè)狀態(tài)(S2):
function_decl := function # func_name ( argment_list ); (I3)
對S2求closure:得出：
function_decl := function # func_name ( argment_list ); (I3)
func_name := # id (I4)
目前，DFA成為如下的狀況：
S1 (function) --> S2 (意思是：狀態(tài)S1當(dāng)輸入符號(hào)function后變遷到S2)
新的問題產(chǎn)生了：S1中還有一個(gè)I1 中#后面是NONTERMINAL function_decl,
每次只取一個(gè)符號(hào)，如何才能從 S := # function_decl 直接輸入一個(gè) function_decl而直接進(jìn)入到 S := function_decl # ? （DFA的終止?fàn)顟B(tài)）
也就是說，當(dāng)我們處于狀態(tài)S1(S := # function_decl)時(shí)，什么時(shí)候才能認(rèn)為已經(jīng)輸入了 function_decl這個(gè)NONTERMINAL了呢。這涉及到另外一個(gè)概念：規(guī)約(reduction):
當(dāng)DFA運(yùn)行到一個(gè)狀態(tài)(SX)，SX中含有一個(gè)Item已經(jīng)到達(dá)末尾，諸如：
function_decl := function func_name ( argment_list ); # 那么我們認(rèn)為DFA已經(jīng)識(shí)別/輸入了一個(gè)等同的NONTERMINAL：function_decl。
先不考慮reduction在什么時(shí)候進(jìn)行，一會(huì)在討論分析算法的時(shí)候再討論它。
那么由S1，我們還能推導(dǎo)出另一個(gè)狀態(tài)S3：
S := function_decl # (I5)
這是DFA的終止接受狀態(tài)。
根據(jù)上面的規(guī)則，我們由S2可以一直往下推導(dǎo)DFA中所有的狀態(tài)，一直到新的狀態(tài)中每個(gè)ITEM都是終止?fàn)顟B(tài)(#在末尾)。
How To Build a Yacc(4)
有了DFA,接下來的事情好辦多了，只要寫一個(gè)DFA識(shí)別算法就完了，通常我們把這個(gè)算法稱為移進(jìn)-規(guī)約算法(shift-reduction)。
借助一個(gè)stack來描述shift-reduction：
1) 初始時(shí)，stack存放初始狀態(tài)S1
2) 取符號(hào)流中下一個(gè)符號(hào)(token)，在DFA中查找是否有邊S1(token) --> SX，如果有，將符號(hào)(token)移進(jìn)stack, 并將狀態(tài)(SX)也移進(jìn)stack。
3) 如果當(dāng)前stack頂部的狀態(tài)(SX)中的所有Item都是非終止?fàn)顟B(tài)，那么繼續(xù)步驟2), 反之，如果含有一個(gè)Item(N := ABC#)到達(dá)了終止?fàn)顟B(tài) (#在末尾)，那么查看當(dāng)前符號(hào), 如果當(dāng)前符號(hào)屬于follow(S), 那么進(jìn)行reduction,將stack中頂部的符號(hào)和狀態(tài)彈出(一個(gè)2* length of (ABC)個(gè)符號(hào)), 執(zhí)行文法N := ABC的附加動(dòng)作，并將NONTERMINAL (N) 移進(jìn)stack, 然后在DFA中查找是否有邊SP(N) --> SX ，其中SP是當(dāng)前stack頂部的狀態(tài)，即stack[-1]。如果DFA中存在這條邊，那么把SX移進(jìn)stack.繼續(xù)進(jìn)行步驟2)
4) 如果當(dāng)前stack頂部到達(dá)接受狀態(tài)SE，算法結(jié)束。
5) 算法在運(yùn)行中如果發(fā)現(xiàn)DFA中沒有可以匹配的邊，則算法失敗。
How To Build a Yacc(5)
現(xiàn)在是時(shí)候來討論How To Build a Yacc?(1)中的最初提出的問題了。。
如何判斷一段代碼是否符合預(yù)定義的syntax rules，毫無疑問：用你的眼睛和大腦配合也能完成這個(gè)任務(wù)，或許你還需要一張白紙，以計(jì)算syntax rules生成的DFA和stack。但是在有計(jì)算機(jī)的情況下，誰還會(huì)用人腦去代替計(jì)算機(jī)呢？
用計(jì)算機(jī)來實(shí)現(xiàn)這個(gè)功能，有了上面的討論后，一切似乎很明了：讀入syntax rules，生成DFA, 然后讀入源代碼，運(yùn)用shift-reduction算法進(jìn)行識(shí)別。
首先要花些時(shí)間來考慮用哪種語言來完成這個(gè)工作；因?yàn)樯蒁FA需要進(jìn)行很多集合運(yùn)算，我選擇使用ruby, 如果你不想被那些糟糕的細(xì)節(jié)拖入地獄，最好用比較高級(jí)一點(diǎn)的工具。
在興奮的往鍵盤上胡亂敲擊代碼之前，先轉(zhuǎn)換一下身份，想象自己是這個(gè)程序的使用者，該如何調(diào)用它？
或許我們會(huì)寫下如下的代碼：
compiler = Compiler.new("syntax.rule", "src")
assert ( compiler.run() == true )
Compiler類ctor有兩個(gè)參數(shù)：語法規(guī)則文件syntax.rule, 源代碼src。Compiler類還有一個(gè)run方法，它用來決定src是否符合syntax.rule定義的規(guī)則。true表示符合，false表示不符合。
運(yùn)行它，不奇怪，它失敗了；好象還沒寫Compiler類呢！
為了使這個(gè)test case通過，僅僅為了使它編譯通過，寫一個(gè)Compiler類：
class Compiler
def initialize(rule_file, src_file)
end
def run
return true
end
end
run方法實(shí)際上什么也沒做，但是足夠了，test case已經(jīng)通過了。一切看起來都很棒，我們邁出相當(dāng)不錯(cuò)的第一步。
畢竟，現(xiàn)在還沒有任何有意義的代碼，我們想要點(diǎn)漂亮的東西，就得實(shí)實(shí)在在的干點(diǎn)活，不是嗎？不過我們已經(jīng)掌握了一個(gè)辦法：在編寫代碼前先編寫它的測試代碼?？雌饋碛悬c(diǎn)本末倒置，但是一旦你習(xí)慣了它，就會(huì)覺得這是個(gè)非常cool的想法。
測試優(yōu)先 ---- 來自敏捷方法。
How To Build a Yacc(6)
顯然，Compiler至少分為兩個(gè)明顯的部分：一部分是讀入源代碼，將其轉(zhuǎn)換成符號(hào)流，一部分是讀入語法規(guī)則文件，生成DFA。
先來討論字符流轉(zhuǎn)換成符號(hào)流的部分，由于這部分不是討論的重點(diǎn)，就利用了目前已經(jīng)相當(dāng)通用的技術(shù)lex。
如果要想在ruby環(huán)境中利用lex工具生成的c代碼，只有把c代碼封裝成ruby的擴(kuò)展庫。
lex怎么工作的？
首先編寫一個(gè)lex的輸入文件：
// prog.l
%{
#include <string.h>
#include "prog.h"
char token_string[MAX_ID_LENGTH];
%}
whitespace [ /t]+
newline /n
digit [0-9]
number [+-]?{digit}+(/.{digit}+)?
bool true|false
lbrace "("
rbrace ")"
semicolon ";"
comma ","
assignment "="
string /"[^"]*/"
comment ////.*{newline}
letter [a-zA-Z]
identifier {letter}(/_|{letter}|{digit})*
constant {bool}|{number}|{string}
%%
{lbrace} { return LBRACE; }
{rbrace} { return RBRACE; }
function { return FUNCTION; }
{semicolon} { return SEMICOLON; }
{comma} { return COMMA; }
{assignment} { return ASSIGNMENT; }
{identifier} { return IDENTIFIER; }
{constant} { return CONSTANT; }
{whitespace} { }
{comment} { }
{newline} { }
. { return ERR; }
%%
int yywrap(void)
{
return 1;
}
int get_next_token()
{
int t_id = yylex();
strcpy(token_string, yytext);
return t_id;
}
輸入文件分三部分，第1部分是%{ %}之間的代碼，純粹的C代碼，將被copy到目標(biāo)C文件中，接下來是正則表達(dá)式定義；第2部分是模式，表示匹配表達(dá)式需要執(zhí)行什么操作。第3部分是幾個(gè) C函數(shù)，最終也是被copy到目標(biāo)C文件中，其中最核心的就是get_next_token()了，這個(gè)是提供給外部的函數(shù)。
關(guān)于lex的更多信息，需要參考更多的參考書，滿大街都是。
好了，基礎(chǔ)的知道了解這么多就夠了，不要忘了我們的游戲規(guī)則：測試優(yōu)先。那么，假若有了這樣一個(gè)lex的封裝如何使用它？
lex = Lex.new(src)
while (true)
token = lex.get_next_token
ts = lex.get_token_string
assert(token == current_token && ts == current_token_string)
if (token == EOF) break
end
那么我們的Lex類需要至少提供兩個(gè)方法：
get_next_token取得下一個(gè)符號(hào)
get_token_string取得當(dāng)前識(shí)別符號(hào)的字符串
Lex類是一個(gè)ruby的擴(kuò)展類，創(chuàng)建這個(gè)擴(kuò)展類的方法如下：
1) 按prog.l的規(guī)則生成prog.c
flex -t prog.l >prog.c
2) prog.h定義一些constant和外部接口
#ifndef PROG_H_
#define PROG_H_
#define MAX_ID_LENGTH 256
enum {LBRACE = 1, RBRACE = 2, FUNCTION=3, SEMICOLON=4,
COMMA=5, ASSIGNMENT= 6, IDENTIFIER=7, CONSTANT=8, ERR=9};
extern char token_string[];
int get_next_token(void);
#endif /*PROG_H_*/
3) 編寫ruby擴(kuò)展程序lex.c
// lex.c
#include <ruby.h>
#include <string.h>
#include "prog.h"
extern FILE* yyin;
static VALUE lex_init(VALUE self, VALUE file)
{
long length = 0 ;
char* name = rb_str2cstr(file, &length);
yyin = fopen(name, "r");
rb_iv_set(self, "@file", file);
return self;
}
static VALUE lex_get_next_token(VALUE self)
{
VALUE t = INT2NUM(get_next_token());
return t;
}
static VALUE lex_get_token_string(VALUE self)
{
VALUE ts = rb_str_new2(token_string);
return ts;
}
static VALUE cTest;
void __declspec(dllexport)
Init_lex() {
cTest = rb_define_class("Lex", rb_cObject);
rb_define_method(cTest, "initialize", lex_init, 1);
rb_define_method(cTest, "get_next_token", lex_get_next_token, 0);
rb_define_method(cTest, "get_token_string", lex_get_token_string, 0);
}
4) 編寫extconf.rb
require 'mkmf'
dir_config('lex')
create_makefile("lex")
5) 生成makefile
ruby extconf.rb --with-lex-dir=[include path]
6) 運(yùn)行nmake ,生成lex.so
這些步驟順利進(jìn)行以后，只需要require 'lex.so', 就擁有了一個(gè)好用的Lex類。
關(guān)于如何編寫ruby擴(kuò)展的更多信息，請參考更多的資料:) 很快，他們就會(huì)滿大街都是了。
How To Build a Yacc(7)
代碼，還是代碼！
要完成一個(gè)這樣相對復(fù)雜的功能，是需要寫一些代碼，不過我保證，他最終將比你想象的少的多。
我對Lex類還有些不盡滿意，實(shí)際上，我更希望lex.get_token_string能取得當(dāng)前符號(hào)流中的任何一個(gè)符號(hào)，而不僅僅是當(dāng)前的一個(gè)符號(hào)。。
lex = Lex.new(src)
lex.get_next_token
assert ( lex.get_token_string(0) == current_token_string && lex.get_token_string(-1) == prev_token_string )
設(shè)計(jì)一個(gè)類ExtendLex, 在初始化時(shí)將source code文件全部分解成符號(hào)流讀入，保存在成員里。然后建立一個(gè)內(nèi)部迭代變量。
class ExtendLex
ERROR = 9
EOF = 0
def read_file
while true
t_id = @lex.get_next_token
if ERROR == t_id
raise "lex error: '#{super.get_token_string}' is unknown character"
end
@token_ids.push(t_id)
@token_defs.push(@@token_match[t_id])
@token_strs.push(@lex.get_token_string)
break if t_id == EOF
end
end
def initialize(file)
@lex = Lex.new(file)
@token_ids = Array.new
@token_defs = Array.new
@token_strs = Array.new
@current_pos = -1
read_file
end
@@token_match = {
1 => "(",
2 => ")",
3 => "function",
4 => ";",
5 => ",",
6 => "=",
7 => "id",
8 => "constant",
9 => "error",
0 => "$"
}
def get_next_token
@current_pos = @current_pos + 1
return @token_ids[@current_pos]
end
def get_next_token2
@current_pos = @current_pos + 1
return @token_defs[@current_pos]
end
def get_token_string(index)
return @token_strs[@current_pos+index]
end
attr_reader :token_ids, :token_defs, :token_strs
end
如上面的代碼：read_file調(diào)用lex的get_next_token方法分析整個(gè)文件，將所有識(shí)別的符號(hào)存儲(chǔ)在一個(gè)數(shù)組:
token_ids里面，而將所有的符號(hào)字符串存儲(chǔ)在一個(gè)數(shù)組: token_strs里面。
get_token_string方法帶了一個(gè)參數(shù)，如果對象擁有文件中所有的符號(hào)，那么可以根據(jù)index來取得任何一個(gè)位置的符號(hào)，符號(hào)字符串。
How To Build a Yacc(8)
搞定lex后，很顯然，我們要將它加入到Compiler中。
class Compiler
def initialize(rule_file, src_file)
@lex = ExtendLex.new(src_file)
end
def run
return true
end
end
要想在run里面真正的干點(diǎn)事，就需要一個(gè)shift-reduction算法來識(shí)別src_file中的符號(hào)流是否能符合rule_file
中所定義的規(guī)則。
我們目前只有@lex, 從它那兒我們只能得到符號(hào)流，要進(jìn)行shift-reduction分析，我們需要從rule_file生成DFA,這一點(diǎn)才是關(guān)鍵。為了達(dá)到這個(gè)目的，得重新寫一個(gè)類來完成這個(gè)功能。
根據(jù)這個(gè)類的功能，一個(gè)緊迫的工作是定義規(guī)則文件的格式，以function_decl文法為例：
##### File: ican.y ###############
%%
%token function id
%token ; , = ( )
%%
nil := function_decl :
function_decl := function function_name ( argument_list ) ; :
function_name := id : p @lex.get_token_string(-1)
argument_list := argument_list , id : p @lex.get_token_string(-1)
argument_list := id : p @lex.get_token_string(-1)
以'%%'為分割符，第1個(gè)'%%'后面是terminal定義，第2個(gè)‘%%’后面定義的是rule, rule的寫法就是普通的BNF表達(dá)式，后面跟著一個(gè):引出的action表達(dá)式，目前我們只執(zhí)行ruby表達(dá)式。這里有幾個(gè)特定約束：每個(gè)NONTERMINAL最終總能推出TERMINAL序列。開始符號(hào)由nil := Start_Symbol來定義。
好了，假設(shè)我們已經(jīng)有了一個(gè)Yacc類，它所完成的工作就是讀入rule_file生成DFA，我們該如何使用(測試)它？
#### test.rb
require 'rubyunit'
class TestCompiler < Test::Unit::TestCase
def create_rule_file
File.open("rulefile","w") do |file|
file.puts "%%/n%token function id/n%token ; , = ( )/n"
file.puts "%%/nnil := function_decl : /n"
file.puts "function_decl := function function_name ( argument_list ) ; : /n"
file.puts "function_name := id : /n"
file.puts "argument_list := argument_list , id : /n"
file.puts "argument_list := id :"
end
end
def test_yacc
create_rule_file
yacc = Yacc.new("rulefile")
yacc.generate
assert(yacc.state[0].size == 2)
end
end
在我們上面所定義的rulefile中，DFA的state[0]（開始狀態(tài)）應(yīng)該是2個(gè)item：
item1:[nil = # function_decl]
item2:[function_decl = # function function_name ( argument_list ) ;]
當(dāng)然我們可以編寫更多的assert, 不過對于一個(gè)想象中的類，還是不要對它要求過多。
How To Build a Yacc(9)
考慮該怎么樣設(shè)計(jì)Yacc類。
顯然，Yacc面臨的第1個(gè)問題就是分析rule_file的內(nèi)容。Yacc類本身不應(yīng)該實(shí)現(xiàn)這個(gè)功能，因?yàn)檫€有一個(gè)功能是生成DFA，這是兩個(gè)沒有多大關(guān)系的功能，按照SRP（單一職責(zé)原則），不應(yīng)該在一個(gè)類里實(shí)現(xiàn)。
按照這個(gè)設(shè)計(jì)原則，很容易做出的決定，需要一個(gè)類Vocab識(shí)別rule_file定義的所有符號(hào)(TERMINAL,NONTERMINAL,EOF,START_SYMBOL)。另外需要一個(gè)類識(shí)別每一個(gè)Rule定義。
這兩個(gè)類的功能很單一，接口也不會(huì)太復(fù)雜。
class TestCompiler < Test::Unit::TestCase
def test_vocab
vocab = Vocab.new
assert( vocab.identify("nil") == Vocab::NULL )
assert( vocab.identify("$") == Vocab::EOF )
assert( vocab.identify("function") == Vocab::UNKNOWN )
vocab.add_terminal("%token )")
assert( vocab.identify(")") == Vocab::TERMINAL )
vocab.add_terminal("%token function id")
assert( vocab.identify("function") == Vocab::TERMINAL )
assert( vocab.identify("id") == Vocab::TERMINAL )
assert( vocab.identify("ids") == Vocab::UNKNOWN )
vocab.add_nonterminal("proc")
assert( vocab.identify("proc") == Vocab::NONTERMINAL )
vocab.add_nonterminals(%w{kick sanf})
assert( vocab.identify("kick") == Vocab::NONTERMINAL )
assert( vocab.identify("sanf") == Vocab::NONTERMINAL )
end
def test_rule
rule = Rule.parse("function_decl := /
function function_name ( argument_list ) ; : decl")
assert(rule, "parse rule failed")
assert(rule.vocabs.include?("function_decl"))
assert(rule.vocabs.include?("function"))
assert(rule.vocabs.include?("function_name"))
assert(rule.vocabs.include?("argument_list"))
assert(rule.lt == "function_decl")
assert(rule.rt == %w{function function_name ( argument_list ) ;})
assert(rule.action == "decl")
end
end
同樣，實(shí)現(xiàn)他們也很簡單。
###### File : algo.rb #############
##############################
# Vocab
# 該類會(huì)存儲(chǔ)一個(gè)syntax define中的
# 所有符號(hào)，包括terminal, nonterminal
# nil(空), $(結(jié)束)
##############################
class Vocab
### @types
TERMINAL = 1
NONTERMINAL = 2
NULL = 3
EOF = 4
UNKNOWN = 5
### @vocabs list
@@nulls = ["nil"]
@@eofs = ["$"]
###
@@terminal_match = /^%token/s+(.*)$/
# @terminals 終結(jié)符的集合
# @nonterminals 非終結(jié)符的集合
def initialize
@terminals = Array.new
@nonterminals = Array.new
end
# @identify
# 判斷一個(gè)符號(hào)名字屬于哪一種符號(hào)
def identify(name)
return TERMINAL if @terminals.include?(name)
return NULL if @@nulls.include?(name)
return EOF if @@eofs.include?(name)
return NONTERMINAL if @nonterminals.include?(name)
return UNKNOWN
end
def Vocab.type_name(type)
Vocab.constants.each do |x|
return x if eval(x) == type
end
return "error type"
end
def Vocab.nulls
@@nulls
end
def Vocab.eofs
@@eofs
end
# 分析一個(gè)token定義語句并將其定義的所有符號(hào)加入集合
# 如果定義語句有錯(cuò)誤,返回nil
def add_terminal(term_def_text)
# %token term1, term2, term3 ...
matches = @@terminal_match.match(term_def_text.strip())
return nil if !matches
# then tokens--matches[1] be (term1, term2, term3 ...)
tokens = matches[1].strip()
# erase all whitespaces in tokens
#tokens.gsub!(//s+/, "")
# split to singleton token
@terminals.concat(tokens.split(//s+/))
@terminals.uniq!
@terminals
end
# 加入非終結(jié)符集合
def add_nonterminal(name)
@nonterminals.push(name) if identify(name) == UNKNOWN &&
!@nonterminals.include?(name)
@nonterminals.uniq!
@nonterminals
end
def add_nonterminals(tokens)
tokens.each {|x| add_nonterminal(x)}
end
def tokens
return @terminals + @nonterminals + @@nulls + @@eofs
end
## traverse vocabs methods.
def each_terminal(&block)
@terminals.each(&block)
end
def each_nonterminal(&block)
@nonterminals.each(&block)
end
def each_token(&block)
tokens().each(&block)
end
end # end Vocab
將"%token id , ( )"這一行內(nèi)容識(shí)別為四個(gè)TERMINAL是由函數(shù)add_terminal完成的，它使用了正則表達(dá)式。容易推測，Rule也使用了這種方法：
###### File : algo.rb #############
##################################
# 一個(gè)Rule對象即代表一個(gè)語法規(guī)則(生成式)
##################################
class Rule
# lt : Nonterminal & NULL
# rt : sequence of Vocab
@@match_rule = /(/w+)/s*:=/s*(.*):(.*)/
def initialize(lt, rt, action)
@lt, @rt, @action = lt, rt, action
end
def Rule.parse(rule_plain_text)
matches = @@match_rule.match(rule_plain_text)
return nil if !matches
begin
lts = matches[1]
rts = matches[2].strip()
action = matches[3].strip()
rta = rts.split(//s+/)
return Rule.new(lts, rta, action)
rescue
return nil
end
end
def vocabs
tokens = Array.new
tokens.push(@lt)
tokens.concat(@rt)
tokens.uniq!
return tokens
end
def to_s
"#{@lt} = #{@rt.join(" ")} : #{@action}"
end
def eql?(other)
return @lt.eql?(other.lt) && @rt.eql?(other.rt)
end
alias :== eql?
attr_reader :lt, :rt, :action
end
How To Build a Yacc(10)
將Vocab和Rule功能組合起來作為一個(gè)RuleParser類來提供分析rule_file的功能是個(gè)不錯(cuò)的主意，因?yàn)閷@兩個(gè)類而言并沒有太大的重用的意義，只不過是為了將錯(cuò)誤的出現(xiàn)盡可能的控制在局部。
class TestCompiler < Test::Unit::TestCase
def test_rule_parser
create_rule_file
p = RuleParser.new("rulefile")
assert(p.rules[0].lt == "nil")
assert(p.rules[0].rt == ["function_decl"])
assert(p.vocabs.identify("function") == Vocab::TERMINAL)
end
end
有了Vocab和Rule，實(shí)現(xiàn)RuleParser只是舉手之勞。
class RuleParser
def initialize(file_name)
@vocabs = Vocab.new
@rules = Array.new
compile(file_name)
end
@@directive = 0
DIRECTIVE = "%%"
####################################################
# 對于 yacc的輸入規(guī)則文件進(jìn)行解析
# 將文件中定義的token和rule分別存入@vocabs, @rules
# 定義文件分兩段:
# %%
# {第一段：token definition}
# %%
# {第二段：rule definition}
# %%
####################################################
def compile(file_name)
file = File.open(file_name, "r")
no = 0
begin
file.each do |line|
no = no+1
if line.strip().chomp() == DIRECTIVE
@@directive = @@directive + 1
next
end
# @@directive == 0 not started, continue
# @@directive == 1 start parse terminals
# @@directive == 2 start parse rules
# @@directive == 3 end parse
case @@directive
when 0
next
when 1
if !add_terminal(line)
error(no, line, "parse terminal error")
end
when 2
rule = parse_rule(line)
if !rule
error(no, line, "parse nonterminal error")
end
add_nonterminal(rule)
when 3
break
end # end when
end # end for each
rescue
raise
ensure
file.close()
end # end begin...
end
def add_terminal(line)
@vocabs.add_terminal(line)
end
def add_nonterminal(rule)
@vocabs.add_nonterminals(rule.vocabs())
end
def parse_rule(line)
rule = Rule.parse(line)
@rules.push(rule)
return rule
end
def error(no, line, msg)
raise "Error #{msg} in Line #{no}, #{line}."
end
private :error
attr_reader :rules, :vocabs
end
實(shí)際上，對RuleParser的test case的設(shè)計(jì)，無意中凸顯了一個(gè)事實(shí)，那就是應(yīng)該將RuleParser設(shè)計(jì)為一個(gè)interface, 對外提供至少兩個(gè)方法：get_rules（分析rule_file得到的rule集合）；get_vocabs（分析rule_file得到的vocab集合）。這樣，Yacc類就不必依賴于RuleParser的實(shí)現(xiàn)，意味著Yacc不必知曉rule_file的特定格式，這些細(xì)節(jié)只應(yīng)該由RuleParser的實(shí)現(xiàn)類來關(guān)心。
在ruby這種動(dòng)態(tài)語言里。。只要你設(shè)計(jì)出一個(gè)類提供rules,vocabs兩個(gè)屬性就好。。
How To Build a Yacc(11)
分析完rule_file, 最后一個(gè)關(guān)鍵的步驟是生成DFA。
這是一個(gè)比較復(fù)雜的過程，首先我們要建立一個(gè)Item結(jié)構(gòu)，這樣才能構(gòu)造狀態(tài)(states)
item 應(yīng)該是一個(gè)rule和一個(gè)相關(guān)的position(當(dāng)前識(shí)別位置)組成。
class TestCompiler < Test::Unit::TestCase
def test_item
rule = Rule.parse("function_decl := /
function function_name ( argument_list ) ; : decl")
assert(rule)
item = Item.new(rule, 0)
assert(item.current_token == "function_decl")
assert(item.next_token == "function")
item = item.step
assert(item.current_token == "function")
assert(item.next_token == "function_name")
assert(item.is_end? == false)
item.step!(5)
assert(item.is_end? == true)
end
end
##################################
# 一個(gè)Item即NFA中一個(gè)狀態(tài)集合中的成員
##################################
class Item
def initialize(rule, pos)
@rule, @pos = rule, pos
end
def current_token
return token(@pos)
end
def next_token
return token(@pos + 1)
end
def step(distance = 1)
return Item.new(@rule, @pos + distance)
end
def step!(distance = 1)
@pos = @pos + distance
end
def is_end?
return @pos >= @rule.rt.length
end
def token(pos)
return nil if pos < 0 || pos > @rule.rt.length
return @rule.lt if 0 == pos
return @rule.rt.at(pos-1)
end
def to_s
rta = rule.rt.dup
#shift_pos = @pos-1 < 0 ? 0 : @pos - 1
rta.insert(@pos, "#")
"[#{rule.lt} = #{rta.join(" ")}]"
end
def eql?(other)
#p "#{self.to_s} eql? #{other.to_s}, #{@rule.eql?(other.rule) && @pos.eql?(other.pos)}"
return @rule.eql?(other.rule) && @pos.eql?(other.pos)
end
alias :== eql?
attr_reader :rule, :pos
end
How To Build a Yacc(12)
生成DFA的第1步，計(jì)算first集合和follow集合。
first_set和follow_set都是一個(gè)hast set結(jié)構(gòu)，這個(gè)hash的key是一個(gè) vocab,而
value是一個(gè)集合，用一個(gè)array表示，這與普通的hash不同，因此寫了一個(gè)HashDup的
module,其中重寫了hash的store方法，用來滿足上述要求：
###### hashdup.rb ###########
module HashDup
def store(key, value)
return if !value
if self.has_key?(key)
self[key].push(value)
else
self[key] = [value]
end
self[key].flatten!
self[key].uniq!
end
def eql?(other)
self.each_pair do |key, value|
if !other[key].eql?(value)
return false
end
end
return true
end
end
其中eql?方法十分有用，在計(jì)算first和follow集合時(shí)，每遍循環(huán)都要檢查集合是否有
變化以決定集合是否計(jì)算終止。
class DFA
def initialize()
@first_set = Hash.new
@follow_set = Hash.new
@first_set.extend(HashDup)
@follow_set.extend(HashDup)
end
########################################################
# 計(jì)算token的first集合
# 對于terminal, first(terminal) = [terminal]
# 對于nonterminal S, 如果有S = aBC, first(S) = first(aBC)
# if a -> nil , first(aBC) = first(BC), 依次類推
# if a not-> nil, first(aBC) = first(a).
########################################################
def calc_first_set(parser)
parser.vocabs.each_terminal do |terminal|
@first_set.store(terminal, terminal)
end
begin
old_first_set = @first_set.dup
parser.vocabs.each_nonterminal do |nonterminal|
parser.rules.each do |rule|
if rule.lt == nonterminal
if !rule.rt.empty? && @first_set[rule.rt[0]]
@first_set.store(nonterminal, @first_set[rule.rt[0]])
end
end
end
end
end while @first_set.eql?(old_first_set)
return @first_set
end
########################################################
# 計(jì)算token的follow集合
# 對每個(gè)rule(產(chǎn)生式進(jìn)行遍歷)
# S = aBC, 每個(gè)rule右邊的產(chǎn)生序列(rule.rt=aBC)的每一個(gè)非結(jié)尾符號(hào)
# 比如a,B; follow集合對于緊鄰符號(hào)的first集合;follow(a) = fisrt(B).
# 而每一個(gè)結(jié)尾符號(hào)，其follow集合等于左邊非終結(jié)符的follow集合
# follow(C) = follow(S)
########################################################
def calc_follow_set(parser)
begin
old_follow_set = @follow_set.dup
parser.rules.each do |rule|
if token_type(rule.lt, parser) == Vocab::NULL
@follow_set.store(rule.lt, Vocab.eofs)
end
for i in 0...rule.rt.length
if i < rule.rt.length-1
@follow_set.store(rule.rt[i], @first_set[rule.rt[i+1]])
else
@follow_set.store(rule.rt[i], @follow_set[rule.lt])
end
end #end for
end #end parser.rules.each
end while !@follow_set.eql?(old_follow_set)
return @follow_set
end
end
How To Build a Yacc(13)
實(shí)際上，有了上面的準(zhǔn)備后，計(jì)算DFA的算法很清楚：
class DFA
SHIFT = 1
REDUCE = 2
ERROR = 3
ACCEPT = 4
def initialize()
@state_set = Array.new
@current_state = 0
@max_state = 0
@action_table = Hash.new
@first_set = Hash.new
@follow_set = Hash.new
@first_set.extend(HashDup)
@follow_set.extend(HashDup)
end
def token_type(token, parser)
parser.vocabs.identify(token)
end
def action(state, token)
key = "#{state},#{token}"
return @action_table[key]
end
########################################################
# 生成DFA
# 首先計(jì)算first, follow集合, 產(chǎn)生第一個(gè)狀態(tài),然后依次產(chǎn)生每一個(gè)后繼
########################################################
def generate(parser)
calc_first_set(parser)
calc_follow_set(parser)
#@state_set.push(generate_first_state(parser))
#dump_first_follow
@state_set[@current_state] = generate_first_state(parser)
#p "fisrt state: #{@state_set[@current_state].to_s}"
while @current_state <= @max_state
successors(@current_state, parser)
@current_state = @current_state + 1
end
@action_table.store("0,nil", [ACCEPT, 0])
@action_table.store("0,$", [ACCEPT, 0])
end
########################################################
# 求DFA的第一個(gè)狀態(tài)
# 我們把nil = #S的item閉包作為第一個(gè)狀態(tài)，其中S是開始符號(hào)
########################################################
def generate_first_state(parser)
itemset = Array.new
parser.rules.each do |rule|
#p "DFA::#{rule}"
if token_type(rule.lt, parser) == Vocab::NULL
#p "DFA::match nil rule #{rule}"
itemset.push(Item.new(rule, 0))
end
end
first_state = closure(itemset, parser)
end
########################################################
# 求一個(gè)狀態(tài)的閉包
# 對于狀態(tài)集合中的任意一個(gè)item: S = av#BC, 如果B是nonterminal
# 那么把所有rule中rule.lt = B的rule加入到這個(gè)閉包中
########################################################
def closure(itemset, parser)
oldset = nil
begin
itemset.each do |item|
oldset = itemset.dup
nt = item.next_token
if !item.is_end? && token_type(nt, parser) == Vocab::NONTERMINAL
additem = Array.new
parser.rules.each do |rule|
if rule.lt == nt
expand = Item.new(rule, 0)
additem.push(expand) if (!itemset.include?(expand))
end
end
itemset.concat(additem)
end
end
end while !oldset.eql?(itemset) # end begin...end while
return itemset
end
########################################################
# 由item: S = a#vBC前進(jìn)到 S = av#BC
########################################################
def advance(itemset)
newitemset = Array.new
itemset.each do |item|
newitemset.push(item.step)
end
return newitemset
end
########################################################
# 求每一個(gè)狀態(tài)的所有后繼
# 對于狀態(tài)s中任意一個(gè)item:
# 1. 如果存在item: S = a#vBC, 那么當(dāng)下一個(gè) token是v時(shí)，意味著
# 將v進(jìn)行shift操作，并將狀態(tài)轉(zhuǎn)移到下一個(gè)狀態(tài)closure(S = av#BC);
# 2. 如果存在item: S = avBC#, 那么當(dāng)下一個(gè)token在follow(S)中
# 意味著需要救星reduce操作，將stack里的avBC序列替換為S, 并移動(dòng)到
# 下一個(gè)狀態(tài) goto(stack.last, S)
########################################################
def successors(state, parser)
itemset = @state_set[state]
parser.vocabs.each_token do |token|
key = "#{state},#{token}"
# 找到所有 s = a.vc中v=token的item
next_items = itemset.find_all { |item| item.next_token == token }
if !next_items.empty?
next_items_c = closure(advance(next_items), parser)
# 檢查next_items_s是否已經(jīng)在狀態(tài)表中
next_state_no = @state_set.index(next_items_c)
if !next_state_no
next_state_no = @max_state + 1
@max_state = next_state_no
@state_set[next_state_no] = next_items_c
end
@action_table.store(key, [SHIFT, next_state_no])
end
# 找到所有 s= av. 的rule, 并將@follow_set(rule.rt.last)
end_items = itemset.find_all { |item| item.is_end? == true }
if !end_items.empty?
end_items.each do |item|
if @follow_set[item.rule.lt].include?(token)
@action_table.store(key, [REDUCE, end_items])
end
end
end
# 如果沒有任何可用的項(xiàng)目
#@action_table.store(key, [ERROR, nil]) until @action_table[key]
end
end
########################################################
# 計(jì)算token的first集合
# 對于terminal, first(terminal) = [terminal]
# 對于nonterminal S, 如果有S = aBC, first(S) = first(aBC)
# if a -> nil , first(aBC) = first(BC), 依次類推
# if a not-> nil, first(aBC) = first(a).
########################################################
def calc_first_set(parser)
parser.vocabs.each_terminal do |terminal|
@first_set.store(terminal, terminal)
end
begin
old_first_set = @first_set.dup
parser.vocabs.each_nonterminal do |nonterminal|
parser.rules.each do |rule|
if rule.lt == nonterminal
if !rule.rt.empty? && @first_set[rule.rt[0]]
@first_set.store(nonterminal, @first_set[rule.rt[0]])
end
end
end
end
end while @first_set.eql?(old_first_set)
return @first_set
end
########################################################
# 計(jì)算token的follow集合
# 對每個(gè)rule(產(chǎn)生式進(jìn)行遍歷)
# S = aBC, 每個(gè)rule右邊的產(chǎn)生序列(rule.rt=aBC)的每一個(gè)非結(jié)尾符號(hào)
# 比如a,B; follow集合對于緊鄰符號(hào)的first集合;follow(a) = fisrt(B).
# 而每一個(gè)結(jié)尾符號(hào)，其follow集合等于左邊非終結(jié)符的follow集合
# follow(C) = follow(S)
########################################################
def calc_follow_set(parser)
begin
old_follow_set = @follow_set.dup
parser.rules.each do |rule|
if token_type(rule.lt, parser) == Vocab::NULL
@follow_set.store(rule.lt, Vocab.eofs)
end
for i in 0...rule.rt.length
if i < rule.rt.length-1
@follow_set.store(rule.rt[i], @first_set[rule.rt[i+1]])
else
@follow_set.store(rule.rt[i], @follow_set[rule.lt])
end
end #end for
end #end parser.rules.each
end while !@follow_set.eql?(old_follow_set)
return @follow_set
end
#### debug util function################
def dump_state_set
index = 0
@state_set.each do |state|
p "state:#{index}, item:#{state.to_s}"
index = index + 1
end
end
def dump_action_table
p "[action table]:"
@action_table.each_pair do |key, value|
cond = key.gsub(/,(.*)/, '(/1)')
p "#{cond} --> [#{DFA.action_name(value[0])}], #{value[1]}"
end
end
def dump_first_follow
p "first: #{@first_set.inspect}"
p "follow: #{@follow_set.inspect}"
end
def DFA.action_name(action)
DFA.constants.each do |x|
return x if eval(x) == action
end
return "unknown action"
end
#attr_reader :state_set, :action_table, :goto_table
end
而Yacc這時(shí)的實(shí)現(xiàn)也僅僅是轉(zhuǎn)調(diào)一下DFA的方法而已:
class Yacc
def initialize(file_name)
@parser = RuleParser.new(file_name)
@dfa = DFA.new
end
def rule_parser
@parser
end
def dfa
@dfa
end
def generate
@dfa.generate(@parser)
end
end
回頭運(yùn)行一下我們的test_yacc，看看有什么結(jié)果?
How To Build a Yacc(14)
既然已經(jīng)生成了DFA，按照之前的描述寫出shift_reduction算法就不是什么了不起的工作了。
class Compiler
def initialize(rule_file, src_file)
@yacc = Yacc.new(rule_file)
@lex = ExtendLex.new(src_file)
@parse_stack = Array.new
end
def run
@yacc.generate
shift_reduction
end
def shift_reduction
@parse_stack.push(0)
token = @lex.get_next_token2
while true
action = @yacc.dfa.action(@parse_stack.last, token)
return false until action
action_id = action[0]
new_state = action[1]
case action_id
when DFA::SHIFT
@parse_stack.push(token)
@parse_stack.push(new_state)
token = @lex.get_next_token2
when DFA::REDUCE
rule = new_state[0].rule
eval(rule.action)
# pop 2 * rt.length
rindex = 0 - 2 * rule.rt.length
@parse_stack[rindex..-1] = nil
goto = @yacc.dfa.action(@parse_stack.last, rule.lt)
if goto
if goto[0] == DFA::SHIFT
@parse_stack.push(rule.lt)
@parse_stack.push(goto[1])
elsif goto[0] == DFA::ACCEPT
return true
end
else
return false
end
when DFA::ACCEPT
return true
end
end
end
end
聯(lián)系客服
