How To Build a Yacc(1)
Yacc 是什麼？
編譯器的編譯器。
簡單來說，Yacc讀入一套文法定義規格(syntax rules), 然後分析一段代碼(source code), 判斷代碼是否符合定義好的syntax rules。
文法定義規格是由形式化的BNF表達式來定義；目前大多數語言都可以用它來定義。
一個BNF表達式由一個NONTERMINAL（非終結符）和它的産生式組成，産生式可以是終結符（TERMINAL）和非終結符組成的序列。比如，我們定義一個函數聲明:
function_decl := function func_name ( argment_list );
func_name := id
argument_list := argument_list , id
argument_list := id
斜體字表示非終結符，而粗體的是終結符。
一套完整的BNF文法意味着每一個NONTERMINAL最終都可以推導為一系列的TERMINAL。
一套文法定義了什麼樣的語言？如上面的function_decl, 非形式化的來說，一個function_decl 開頭是一個function關鍵字,然後緊接着一個func_name，也就是一個id,表示函數名字，然後是一個'(', 加上一個參數清單，再加上一個')'
參數清單是由','分隔的id清單。
例如：function foo (kick, so, by);
BNF或是擴充EBNF(擴充BNF)表達式有幾下幾種表達方式:
S := A B C (S 推導出A B C 三個部分)
S := A | B | C (S推導出A 或 B 或 C三個符号)
S := { A } (S推導出一個或多個A}
How To Build a Yacc(2)
如何識别一段代碼是否符合定義的文法？
如上面的例子：
function foo(kick, so, by);
首先，技術上來說，代碼文本是一段字元流，f, u, n, c....，而我們文法識别的最小級别是符号(token), 是以需要将其轉化為符号流，這個功能可以很容易的用lex實作，這個步驟不是講述重點，不加詳細叙述。
最直接的識别方法，以function_decl文法為例,我們從符号流中取一個目前符号，然後判斷這個符号是否屬于開始符号(function_decl)的某個産生式的第一個符号, 如果找到了這樣一個産生式，那麼認為應該按照這個産生式進行展開，比對并丢棄目前這個符号，并期望符号流中餘下的符号能比對該産生式剩餘的符号；那麼繼續從符号流中取去下一個符号，繼續上面的步驟。
如果要用一個算法來描述它，那麼看起來，象這個樣子。
// 比對一個符号token...
void match(token)
{
if (current_token == token) current_token = get_next_token();
else error("expect {token}, but give {current_token}")
}
// function_decl 用來比對一個函數聲明語句；
// function_decl 的産生式為:
// function_decl := function func_name ( argment_list );
void function_decl( )
{
current_token = get_next_token(); // 取出一個符号
match(function); // 比對function
func_name(); // 如果已經比對，那麼接下來應該比對函數名字了
match('('); // 比對'('
argument_list(); // 接下來應該參數清單
match(')'); // 比對')'
}
void func_name()
{
match(id);
}
void argument_list()
{
while (current_token == id) {
match(",");
}
}
如此簡單？是不是？
以上的分析技術被稱為遞歸下降分析技術，它對大多數簡單的文法規則非常有效。
這種分析方法可以很容易的被歸納成一些簡單的規則，根據這些規則，我們可以友善的編制分析程式。
在闡述這些規則之前，有必要介紹一個概念：fisrt集合。
什麼是fisrt集合？
一個産生式的first項目就是這個産生式(production)的比對第一個非終結符号。一套文法的所有産生式的first項目組成了first集合。求解first集合的方法：對于production: S = ABC
first(ABC) ， 如果A是一個terminal, 那麼first(ABC)= A, 如果A是一個NONTERMINAL, 那麼first(ABC) = first(A), 如果A最終被推出一個空的符号，那麼first(ABC) = first(BC), 依次類推。
這個概念之是以重要，是因為在遞歸下降算法中，在比對一個非終結符的過程中，需要檢測目前符号流中的符号是否屬于該非終結符的所有産生式的first集合；如果屬于，則用該産生式來擴充這個非終結符。
如何編寫遞歸下降解析程式？
是時候總結一下規律了，對于每個産生式a來說，我們定義T(a) 是比對a的程式代碼：
when: a = A (A是terminal)
T(a):
if (t == A) t = get_next_token();
else error (t 是目前符号，get_next_token取得下一個符号)
when: a = X (X是nonterminal)
T(a): X(); 定義一個X的函數，實作由X的産生式定義。
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)中，我們闡述了一個簡單高效的分析方法，最終産生一個文法的最左推導(即每次優先擴充左邊的NONTERMINAL)
但是遞歸下降算法有些許局限性，比如：對于兩個不同的NONTERMINAL，如果他們的FIRST集合有交集的話，就會産生歧義，很顯然，當目前的符号分别屬于兩個不同的NONTERMINAL的FIRST集合時，就無法決定采用哪個産生式了。
我們來考慮另外一種分析方法，與遞歸下降相反，它最終産生一個文法的最右推導。我們稱這種方法為LR分析。
LR分析基于一種有窮确定性自動機（DFA）原理，根據文法規則來建立一個DFA， 然後判斷輸入的符号流是否最後落入這個DFA的ACCEPT狀态。
如何根據文法規則建立DFA？
DFA是一個狀态集合，這些狀态由某些确定的有向邊連接配接；DFA由一個初始狀态開始，接受一個符号，進入下一個狀态。那麼LR分析中的DFA狀态是什麼？想象一個目前推導狀态這個概念，即對于一個文法來說，當它識别了一些符号流以後，進入到一個什麼樣的狀态。這個狀态要麼還剩下一些符号有待識别，要麼已經完成。
以前面的文法為例：
初始時候：
一個符号都沒有識别，DFA需要識别整個文法的初始符号。我們标記為：
S = # function_decl (I1)
将'#'定義為“目前識别位置”，S是一個虛拟符号，我們将這個表達式定義為一個項目(item) ,這個項目認為，沒有識别一個符号，DFA需要識别的是整個function_decl代表的符号串。
由于我們每次隻從符号流中取出一個符号，是以将DFA一步就将整個function_decl全部識别是不可能的，隻能将function_decl展開，看看function_decl下一個要識别的TERMINAL是什麼，這就引出了閉包(closure)的概念: 一個狀态的closure集合這樣定義的，周遊這個狀态中的所有item,如果#後面緊接的是一個NONTERMINAL，那麼将這個NONTERMINAL的所有産生式的初始化項目加入到這個集合中。
比如I1的closure集合S1為：
S := # function_decl (I1)
function_decl := # function func_name ( argment_list ); (I2)
這就是初始狀态(S1)
繼續推導(S1)以後的狀态，我們要求解後續狀态，主要方法是看目前位置(#)後面緊接的符号,如果符号流中下一個符号與之相同，那麼目前位置後移一位，DFA進入了下一個狀态(S2), 而由狀态(S1)到(S2)的邊的輸入符号，就是#後面的符号。
那麼如果下一個符号是 function , 那麼（S1）進入下一個狀态(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 (意思是：狀态S1當輸入符号function後變遷到S2)
新的問題産生了：S1中還有一個I1 中#後面是NONTERMINAL function_decl,
每次隻取一個符号，如何才能從 S := # function_decl 直接輸入一個 function_decl而直接進入到 S := function_decl # ? （DFA的終止狀态）
也就是說，當我們處于狀态S1(S := # function_decl)時，什麼時候才能認為已經輸入了 function_decl這個NONTERMINAL了呢。這涉及到另外一個概念：規約(reduction):
當DFA運作到一個狀态(SX)，SX中含有一個Item已經到達末尾，諸如：
function_decl := function func_name ( argment_list ); # 那麼我們認為DFA已經識别/輸入了一個等同的NONTERMINAL：function_decl。
先不考慮reduction在什麼時候進行，一會在讨論分析算法的時候再讨論它。
那麼由S1，我們還能推導出另一個狀态S3：
S := function_decl # (I5)
這是DFA的終止接受狀态。
根據上面的規則，我們由S2可以一直往下推導DFA中所有的狀态，一直到新的狀态中每個ITEM都是終止狀态(#在末尾)。
How To Build a Yacc(4)
有了DFA,接下來的事情好辦多了，隻要寫一個DFA識别算法就完了，通常我們把這個算法稱為移進-規約算法(shift-reduction)。
借助一個stack來描述shift-reduction：
1) 初始時，stack存放初始狀态S1
2) 取符号流中下一個符号(token)，在DFA中查找是否有邊S1(token) --> SX，如果有，将符号(token)移進stack, 并将狀态(SX)也移進stack。
3) 如果目前stack頂部的狀态(SX)中的所有Item都是非終止狀态，那麼繼續步驟2), 反之，如果含有一個Item(N := ABC#)到達了終止狀态 (#在末尾)，那麼檢視目前符号, 如果目前符号屬于follow(S), 那麼進行reduction,将stack中頂部的符号和狀态彈出(一個2* length of (ABC)個符号), 執行文法N := ABC的附加動作，并将NONTERMINAL (N) 移進stack, 然後在DFA中查找是否有邊SP(N) --> SX ，其中SP是目前stack頂部的狀态，即stack[-1]。如果DFA中存在這條邊，那麼把SX移進stack.繼續進行步驟2)
4) 如果目前stack頂部到達接受狀态SE，算法結束。
5) 算法在運作中如果發現DFA中沒有可以比對的邊，則算法失敗。
How To Build a Yacc(5)
現在是時候來讨論How To Build a Yacc?(1)中的最初提出的問題了。。
如何判斷一段代碼是否符合預定義的syntax rules，毫無疑問：用你的眼睛和大腦配合也能完成這個任務，或許你還需要一張白紙，以計算syntax rules生成的DFA和stack。但是在有計算機的情況下，誰還會用人腦去代替計算機呢？
用計算機來實作這個功能，有了上面的讨論後，一切似乎很明了：讀入syntax rules，生成DFA, 然後讀入源代碼，運用shift-reduction算法進行識别。
首先要花些時間來考慮用哪種語言來完成這個工作；因為生成DFA需要進行很多集合運算，我選擇使用ruby, 如果你不想被那些糟糕的細節拖入地獄，最好用比較進階一點的工具。
在興奮的往鍵盤上胡亂敲擊代碼之前，先轉換一下身份，想象自己是這個程式的使用者，該如何調用它？
或許我們會寫下如下的代碼：
compiler = Compiler.new("syntax.rule", "src")
assert ( compiler.run() == true )
Compiler類ctor有兩個參數：文法規則檔案syntax.rule, 源代碼src。Compiler類還有一個run方法，它用來決定src是否符合syntax.rule定義的規則。true表示符合，false表示不符合。
運作它，不奇怪，它失敗了；好象還沒寫Compiler類呢！
為了使這個test case通過，僅僅為了使它編譯通過，寫一個Compiler類：
class Compiler
def initialize(rule_file, src_file)
end
def run
return true
end
end
run方法實際上什麼也沒做，但是足夠了，test case已經通過了。一切看起來都很棒，我們邁出相當不錯的第一步。
畢竟，現在還沒有任何有意義的代碼，我們想要點漂亮的東西，就得實實在在的幹點活，不是嗎？不過我們已經掌握了一個辦法：在編寫代碼前先編寫它的測試代碼。看起來有點本末倒置，但是一旦你習慣了它，就會覺得這是個非常cool的想法。
測試優先 ---- 來自靈活方法。
How To Build a Yacc(6)
顯然，Compiler至少分為兩個明顯的部分：一部分是讀入源代碼，将其轉換成符号流，一部分是讀入文法規則檔案，生成DFA。
先來讨論字元流轉換成符号流的部分，由于這部分不是讨論的重點，就利用了目前已經相當通用的技術lex。
如果要想在ruby環境中利用lex工具生成的c代碼，隻有把c代碼封裝成ruby的擴充庫。
lex怎麼工作的？
首先編寫一個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到目标C檔案中，接下來是正規表達式定義；第2部分是模式，表示比對表達式需要執行什麼操作。第3部分是幾個 C函數，最終也是被copy到目标C檔案中，其中最核心的就是get_next_token()了，這個是提供給外部的函數。
關于lex的更多資訊，需要參考更多的參考書，滿大街都是。
好了，基礎的知道了解這麼多就夠了，不要忘了我們的遊戲規則：測試優先。那麼，假若有了這樣一個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類需要至少提供兩個方法：
get_next_token取得下一個符号
get_token_string取得目前識别符号的字元串
Lex類是一個ruby的擴充類，建立這個擴充類的方法如下：
1) 按prog.l的規則生成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
3) 編寫ruby擴充程式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) 運作nmake ,生成lex.so
這些步驟順利進行以後，隻需要require 'lex.so', 就擁有了一個好用的Lex類。
關于如何編寫ruby擴充的更多資訊，請參考更多的資料:) 很快，他們就會滿大街都是了。
How To Build a Yacc(7)
代碼，還是代碼！
要完成一個這樣相對複雜的功能，是需要寫一些代碼，不過我保證，他最終将比你想象的少的多。
我對Lex類還有些不盡滿意，實際上，我更希望lex.get_token_string能取得目前符号流中的任何一個符号，而不僅僅是目前的一個符号。。
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 )
設計一個類ExtendLex, 在初始化時将source code檔案全部分解成符号流讀入，儲存在成員裡。然後建立一個内部疊代變量。
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調用lex的get_next_token方法分析整個檔案，将所有識别的符号存儲在一個數組:
token_ids裡面，而将所有的符号字元串存儲在一個數組: token_strs裡面。
get_token_string方法帶了一個參數，如果對象擁有檔案中所有的符号，那麼可以根據index來取得任何一個位置的符号，符号字元串。
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裡面真正的幹點事，就需要一個shift-reduction算法來識别src_file中的符号流是否能符合rule_file
中所定義的規則。
我們目前隻有@lex, 從它那兒我們隻能得到符号流，要進行shift-reduction分析，我們需要從rule_file生成DFA,這一點才是關鍵。為了達到這個目的，得重新寫一個類來完成這個功能。
根據這個類的功能，一個緊迫的工作是定義規則檔案的格式，以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個'%%'後面是terminal定義，第2個‘%%’後面定義的是rule, rule的寫法就是普通的BNF表達式，後面跟着一個:引出的action表達式，目前我們隻執行ruby表達式。這裡有幾個特定限制：每個NONTERMINAL最終總能推出TERMINAL序列。開始符号由nil := Start_Symbol來定義。
好了，假設我們已經有了一個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]（開始狀态）應該是2個item：
item1:[nil = # function_decl]
item2:[function_decl = # function function_name ( argument_list ) ;]
當然我們可以編寫更多的assert, 不過對于一個想象中的類，還是不要對它要求過多。
How To Build a Yacc(9)
考慮該怎麼樣設計Yacc類。
顯然，Yacc面臨的第1個問題就是分析rule_file的内容。Yacc類本身不應該實作這個功能，因為還有一個功能是生成DFA，這是兩個沒有多大關系的功能，按照SRP（單一職責原則），不應該在一個類裡實作。
按照這個設計原則，很容易做出的決定，需要一個類Vocab識别rule_file定義的所有符号(TERMINAL,NONTERMINAL,EOF,START_SYMBOL)。另外需要一個類識别每一個Rule定義。
這兩個類的功能很單一，接口也不會太複雜。
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
同樣，實作他們也很簡單。
###### File : algo.rb #############
##############################
# Vocab
# 該類會存儲一個syntax define中的
# 所有符号，包括terminal, nonterminal
# nil(空), $(結束)
##############################
class Vocab
### @types
TERMINAL = 1
NONTERMINAL = 2
NULL = 3
EOF = 4
UNKNOWN = 5
### @vocabs list
@@nulls = ["nil"]
@@eofs = ["$"]
###
@@terminal_match = /^%token/s+(.*)$/
# @terminals 終結符的集合
# @nonterminals 非終結符的集合
def initialize
@terminals = Array.new
@nonterminals = Array.new
end
# @identify
# 判斷一個符号名字屬于哪一種符号
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
# 分析一個token定義語句并将其定義的所有符号加入集合
# 如果定義語句有錯誤,傳回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
# 加入非終結符集合
def add_nonterminal(name)
@nonterminals.push(name) if identify(name) == UNKNOWN &&
[email protected]?(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 , ( )"這一行内容識别為四個TERMINAL是由函數add_terminal完成的，它使用了正規表達式。容易推測，Rule也使用了這種方法：
###### File : algo.rb #############
##################################
# 一個Rule對象即代表一個文法規則(生成式)
##################################
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功能組合起來作為一個RuleParser類來提供分析rule_file的功能是個不錯的主意，因為對這兩個類而言并沒有太大的重用的意義，隻不過是為了将錯誤的出現盡可能的控制在局部。
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，實作RuleParser隻是舉手之勞。
class RuleParser
def initialize(file_name)
@vocabs = Vocab.new
@rules = Array.new
compile(file_name)
end
@@directive = 0
DIRECTIVE = "%%"
####################################################
# 對于 yacc的輸入規則檔案進行解析
# 将檔案中定義的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
實際上，對RuleParser的test case的設計，無意中凸顯了一個事實，那就是應該将RuleParser設計為一個interface, 對外提供至少兩個方法：get_rules（分析rule_file得到的rule集合）；get_vocabs（分析rule_file得到的vocab集合）。這樣，Yacc類就不必依賴于RuleParser的實作，意味着Yacc不必知曉rule_file的特定格式，這些細節隻應該由RuleParser的實作類來關心。
在ruby這種動态語言裡。。隻要你設計出一個類提供rules,vocabs兩個屬性就好。。
How To Build a Yacc(11)
分析完rule_file, 最後一個關鍵的步驟是生成DFA。
這是一個比較複雜的過程，首先我們要建立一個Item結構，這樣才能構造狀态(states)
item 應該是一個rule和一個相關的position(目前識别位置)組成。
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
##################################
# 一個Item即NFA中一個狀态集合中的成員
##################################
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步，計算first集合和follow集合。
first_set和follow_set都是一個hast set結構，這個hash的key是一個 vocab,而
value是一個集合，用一個array表示，這與普通的hash不同，是以寫了一個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?方法十分有用，在計算first和follow集合時，每遍循環都要檢查集合是否有
變化以決定集合是否計算終止。
class DFA
def initialize()
@first_set = Hash.new
@follow_set = Hash.new
@first_set.extend(HashDup)
@follow_set.extend(HashDup)
end
########################################################
# 計算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
########################################################
# 計算token的follow集合
# 對每個rule(産生式進行周遊)
# S = aBC, 每個rule右邊的産生序列(rule.rt=aBC)的每一個非結尾符号
# 比如a,B; follow集合對于緊鄰符号的first集合;follow(a) = fisrt(B).
# 而每一個結尾符号，其follow集合等于左邊非終結符的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 [email protected]_set.eql?(old_follow_set)
return @follow_set
end
end
How To Build a Yacc(13)
實際上，有了上面的準備後，計算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
# 首先計算first, follow集合, 産生第一個狀态,然後依次産生每一個後繼
########################################################
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的第一個狀态
# 我們把nil = #S的item閉包作為第一個狀态，其中S是開始符号
########################################################
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
########################################################
# 求一個狀态的閉包
# 對于狀态集合中的任意一個item: S = av#BC, 如果B是nonterminal
# 那麼把所有rule中rule.lt = B的rule加入到這個閉包中
########################################################
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前進到 S = av#BC
########################################################
def advance(itemset)
newitemset = Array.new
itemset.each do |item|
newitemset.push(item.step)
end
return newitemset
end
########################################################
# 求每一個狀态的所有後繼
# 對于狀态s中任意一個item:
# 1. 如果存在item: S = a#vBC, 那麼當下一個 token是v時，意味着
# 将v進行shift操作，并将狀态轉移到下一個狀态closure(S = av#BC);
# 2. 如果存在item: S = avBC#, 那麼當下一個token在follow(S)中
# 意味着需要救星reduce操作，将stack裡的avBC序列替換為S, 并移動到
# 下一個狀态 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是否已經在狀态表中
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
# 如果沒有任何可用的項目
#@action_table.store(key, [ERROR, nil]) until @action_table[key]
end
end
########################################################
# 計算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
########################################################
# 計算token的follow集合
# 對每個rule(産生式進行周遊)
# S = aBC, 每個rule右邊的産生序列(rule.rt=aBC)的每一個非結尾符号
# 比如a,B; follow集合對于緊鄰符号的first集合;follow(a) = fisrt(B).
# 而每一個結尾符号，其follow集合等于左邊非終結符的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 [email protected]_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這時的實作也僅僅是轉調一下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
回頭運作一下我們的test_yacc，看看有什麼結果?
How To Build a Yacc(14)
既然已經生成了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
![windows phone7 下 Silverlight 異步讀取網絡圖檔[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)