|
How To Build a Yacc(1)
Yacc 是什么？
編譯器的編譯器。
簡單來說，Yacc讀入一套語法定義規(guī)格(syntax rules), 然后分析一段代碼(source code), 判斷代碼是否符合定義好的syntax rules。
語法定義規(guī)格是由形式化的BNF表達式來定義；目前大多數(shù)語言都可以用它來定義。
一個BNF表達式由一個NONTERMINAL（非終結符）和它的產生式組成，產生式可以是終結符（TERMINAL）和非終結符組成的序列。比如，我們定義一個函數(shù)聲明:
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,表示函數(shù)名字，然后是一個'(',
加上一個參數(shù)列表，再加上一個')'
參數(shù)列表是由','分隔的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實現(xiàn)，這個步驟不是講述重點，不加詳細敘述。
最直接的識別方法，以function_decl文法為例,我們從符號流中取一個當前符號，然后判斷這個符號是否屬于開始符號
(function_decl)的某個產生式的第一個符號,
如果找到了這樣一個產生式，那么認為應該按照這個產生式進行展開，匹配并丟棄當前這個符號，并期望符號流中余下的符號能匹配該產生式剩余的符號；那么繼續(xù)
從符號流中取去下一個符號，繼續(xù)上面的步驟。
如果要用一個算法來描述它，那么看起來，象這個樣子。
// 匹配一個符號token...
void match(token)
{
if (current_token == token) current_token = get_next_token();
else error("expect {token}, but give {current_token}")
}
// function_decl 用來匹配一個函數(shù)聲明語句；
// function_decl 的產生式為:
// function_decl := function func_name ( argment_list );
void function_decl( )
{
current_token = get_next_token(); // 取出一個符號
match(function); // 匹配function
func_name(); // 如果已經匹配，那么接下來應該匹配函數(shù)名字了
match('('); // 匹配'('
argument_list(); // 接下來應該參數(shù)列表
match(')'); // 匹配')'
}
void func_name()
{
match(id);
}
void argument_list()
{
while (current_token == id) {
match(",");
}
}
如此簡單？是不是？
以上的分析技術被稱為遞歸下降分析技術，它對大多數(shù)簡單的語法規(guī)則非常有效。
這種分析方法可以很容易的被歸納成一些簡單的規(guī)則，根據(jù)這些規(guī)則，我們可以方便的編制分析程序。
在闡述這些規(guī)則之前，有必要介紹一個概念：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集合；如果屬于，則用該產生式來擴展這個非終結符。
如何編寫遞歸下降解析程序？
是時候總結一下規(guī)律了，對于每個產生式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的函數(shù)，實現(xiàn)由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)中，我們闡述了一個簡單高效的分析方法，最終產生一個文法的最左推導(即每次優(yōu)先擴展左邊的NONTERMINAL)
但是遞歸下降算法有些許局限性，比如：對于兩個不同的NONTERMINAL，如果他們的FIRST集合有交集的話，就會產生歧義，很顯然，當目前的符號分別屬于兩個不同的NONTERMINAL的FIRST集合時，就無法決定采用哪個產生式了。
我們來考慮另外一種分析方法，與遞歸下降相反，它最終產生一個文法的最右推導。我們稱這種方法為LR分析。
LR分析基于一種有窮確定性自動機（DFA）原理，根據(jù)語法規(guī)則來創(chuàng)建一個DFA， 然后判斷輸入的符號流是否最后落入這個DFA的ACCEPT狀態(tài)。
如何根據(jù)語法規(guī)則建立DFA？
DFA是一個狀態(tài)集合，這些狀態(tài)由某些確定的有向邊連接；DFA由一個初始狀態(tài)開始，接受一個符號，進入下一個狀態(tài)。那么LR分析中的DFA狀態(tài)是
什么？想象一個當前推導狀態(tài)這個概念，即對于一個文法來說，當它識別了一些符號流以后，進入到一個什么樣的狀態(tài)。這個狀態(tài)要么還剩下一些符號有待識別，要
么已經完成。
以前面的文法為例：
初始時候：
一個符號都沒有識別，DFA需要識別整個文法的初始符號。我們標記為：
S = # function_decl (I1)
將'#'定義為“當前識別位置”，S是一個虛擬符號，我們將這個表達式定義為一個項目(item) ,這個項目認為，沒有識別一個符號，DFA需要識別的是整個function_decl代表的符號串。
由
于我們每次只從符號流中取出一個符號，因此將DFA一步就將整個function_decl全部識別是不可能的，只能將function_decl展開，
看看function_decl下一個要識別的TERMINAL是什么，這就引出了閉包(closure)的概念:
一個狀態(tài)的closure集合這樣定義的，遍歷這個狀態(tài)中的所有item,如果#后面緊接的是一個NONTERMINAL，那么將這個
NONTERMINAL的所有產生式的初始化項目加入到這個集合中。
比如I1的closure集合S1為：
S := # function_decl (I1)
function_decl := # function func_name ( argment_list ); (I2)
這就是初始狀態(tài)(S1)
繼續(xù)推導(S1)以后的狀態(tài)，我們要求解后續(xù)狀態(tài)，主要方法是看當前位置(#)后面緊接的符號,如果符號流中下一個符號與之相同，那么當前位置后移一位，DFA進入了下一個狀態(tài)(S2), 而由狀態(tài)(S1)到(S2)的邊的輸入符號，就是#后面的符號。
那么如果下一個符號是 function , 那么（S1）進入下一個狀態(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當輸入符號function后變遷到S2)
新的問題產生了：S1中還有一個I1 中#后面是NONTERMINAL function_decl,
每次只取一個符號，如何才能從 S := # function_decl 直接輸入一個 function_decl而直接進入到 S := function_decl # ? （DFA的終止狀態(tài)）
也就是說，當我們處于狀態(tài)S1(S := # function_decl)時，什么時候才能認為已經輸入了 function_decl這個NONTERMINAL了呢。這涉及到另外一個概念：規(guī)約(reduction):
當DFA運行到一個狀態(tài)(SX)，SX中含有一個Item已經到達末尾，諸如：
function_decl := function func_name ( argment_list ); # 那么我們認為DFA已經識別/輸入了一個等同的NONTERMINAL：function_decl。
先不考慮reduction在什么時候進行，一會在討論分析算法的時候再討論它。
那么由S1，我們還能推導出另一個狀態(tài)S3：
S := function_decl # (I5)
這是DFA的終止接受狀態(tài)。
根據(jù)上面的規(guī)則，我們由S2可以一直往下推導DFA中所有的狀態(tài)，一直到新的狀態(tài)中每個ITEM都是終止狀態(tài)(#在末尾)。
How To Build a Yacc(4)
有了DFA,接下來的事情好辦多了，只要寫一個DFA識別算法就完了，通常我們把這個算法稱為移進-規(guī)約算法(shift-reduction)。
借助一個stack來描述shift-reduction：
1) 初始時，stack存放初始狀態(tài)S1
2) 取符號流中下一個符號(token)，在DFA中查找是否有邊S1(token) --> SX，如果有，將符號(token)移進stack, 并將狀態(tài)(SX)也移進stack。
3)
如果當前stack頂部的狀態(tài)(SX)中的所有Item都是非終止狀態(tài)，那么繼續(xù)步驟2), 反之，如果含有一個Item(N :=
ABC#)到達了終止狀態(tài) (#在末尾)，那么查看當前符號, 如果當前符號屬于follow(S),
那么進行reduction,將stack中頂部的符號和狀態(tài)彈出(一個2* length of (ABC)個符號), 執(zhí)行文法N :=
ABC的附加動作，并將NONTERMINAL (N) 移進stack, 然后在DFA中查找是否有邊SP(N) --> SX
，其中SP是當前stack頂部的狀態(tài)，即stack[-1]。如果DFA中存在這條邊，那么把SX移進stack.繼續(xù)進行步驟2)
4) 如果當前stack頂部到達接受狀態(tài)SE，算法結束。
5) 算法在運行中如果發(fā)現(xiàn)DFA中沒有可以匹配的邊，則算法失敗。
How To Build a Yacc(5)
現(xiàn)在是時候來討論How To Build a Yacc?(1)中的最初提出的問題了。。
如何判斷一段代碼是否符合預定義的syntax rules，毫無疑問：用你的眼睛和大腦配合也能完成這個任務，或許你還需要一張白紙，以計算syntax rules生成的DFA和stack。但是在有計算機的情況下，誰還會用人腦去代替計算機呢？
用計算機來實現(xiàn)這個功能，有了上面的討論后，一切似乎很明了：讀入syntax rules，生成DFA, 然后讀入源代碼，運用shift-reduction算法進行識別。
首先要花些時間來考慮用哪種語言來完成這個工作；因為生成DFA需要進行很多集合運算，我選擇使用ruby, 如果你不想被那些糟糕的細節(jié)拖入地獄，最好用比較高級一點的工具。
在興奮的往鍵盤上胡亂敲擊代碼之前，先轉換一下身份，想象自己是這個程序的使用者，該如何調用它？
或許我們會寫下如下的代碼：
compiler = Compiler.new("syntax.rule", "src")
assert ( compiler.run() == true )
Compiler類ctor有兩個參數(shù)：語法規(guī)則文件syntax.rule, 源代碼src。Compiler類還有一個run方法，它用來決定src是否符合syntax.rule定義的規(guī)則。true表示符合，false表示不符合。
運行它，不奇怪，它失敗了；好象還沒寫Compiler類呢！
為了使這個test case通過，僅僅為了使它編譯通過，寫一個Compiler類：
class Compiler
def initialize(rule_file, src_file)
end
def run
return true
end
end
run方法實際上什么也沒做，但是足夠了，test case已經通過了。一切看起來都很棒，我們邁出相當不錯的第一步。
畢竟，現(xiàn)在還沒有任何有意義的代碼，我們想要點漂亮的東西，就得實實在在的干點活，不是嗎？不過我們已經掌握了一個辦法：在編寫代碼前先編寫它的測試代碼?？雌饋碛悬c本末倒置，但是一旦你習慣了它，就會覺得這是個非常cool的想法。
測試優(yōu)先 ---- 來自敏捷方法。
How To Build a Yacc(6)
顯然，Compiler至少分為兩個明顯的部分：一部分是讀入源代碼，將其轉換成符號流，一部分是讀入語法規(guī)則文件，生成DFA。
先來討論字符流轉換成符號流的部分，由于這部分不是討論的重點，就利用了目前已經相當通用的技術lex。
如果要想在ruby環(huán)境中利用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部分是模式，表示匹配表達式需要執(zhí)行什么操作。第3部分是幾個
C函數(shù)，最終也是被copy到目標C文件中，其中最核心的就是get_next_token()了，這個是提供給外部的函數(shù)。
關于lex的更多信息，需要參考更多的參考書，滿大街都是。
好了，基礎的知道了解這么多就夠了，不要忘了我們的游戲規(guī)則：測試優(yōu)先。那么，假若有了這樣一個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的擴展類，創(chuàng)建這個擴展類的方法如下：
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擴展程序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方法分析整個文件，將所有識別的符號存儲在一個數(shù)組:
token_ids里面，而將所有的符號字符串存儲在一個數(shù)組: token_strs里面。
get_token_string方法帶了一個參數(shù)，如果對象擁有文件中所有的符號，那么可以根據(jù)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
中所定義的規(guī)則。
我們目前只有@lex, 從它那兒我們只能得到符號流，要進行shift-reduction分析，我們需要從rule_file生成DFA,這一點才是關鍵。為了達到這個目的，得重新寫一個類來完成這個功能。
根據(jù)這個類的功能，一個緊迫的工作是定義規(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個'%%'后面是terminal定義，第2個‘%%’后面定義的是rule,
rule的寫法就是普通的BNF表達式，后面跟著一個:引出的action表達式，目前我們只執(zhí)行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]（開始狀態(tài)）應該是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類本身不應該實現(xiàn)這個功能，因為還有一個功能是生成DFA，這是兩個沒有多大關系的功能，按照SRP（單一職責原則），不應該在一個類里實現(xiàn)。
按照這個設計原則，很容易做出的決定，需要一個類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
同樣，實現(xiàn)他們也很簡單。
###### 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 &&
!@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 , ( )"這一行內容識別為四個TERMINAL是由函數(shù)add_terminal完成的，它使用了正則表達式。容易推測，Rule也使用了這種方法：
###### File : algo.rb #############
##################################
# 一個Rule對象即代表一個語法規(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功能組合起來作為一個RuleParser類來提供分析rule_file的功能是個不錯的主意，因為對這兩個類而言并沒有太大的重用的意義，只不過是為了將錯誤的出現(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，實現(xiàn)RuleParser只是舉手之勞。
class RuleParser
def initialize(file_name)
@vocabs = Vocab.new
@rules = Array.new
compile(file_name)
end
@@directive = 0
DIRECTIVE = "%%"
####################################################
# 對于 yacc的輸入規(guī)則文件進行解析
# 將文件中定義的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的實現(xiàn)，意味著Yacc不必知曉rule_file的特定格式，這些細節(jié)只應該由
RuleParser的實現(xiàn)類來關心。
在ruby這種動態(tài)語言里。。只要你設計出一個類提供rules,vocabs兩個屬性就好。。
How To Build a Yacc(11)
分析完rule_file, 最后一個關鍵的步驟是生成DFA。
這是一個比較復雜的過程，首先我們要建立一個Item結構，這樣才能構造狀態(tài)(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中一個狀態(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步，計算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集合時，每遍循環(huán)都要檢查集合是否有
變化以決定集合是否計算終止。
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 !@follow_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集合, 產生第一個狀態(tài),然后依次產生每一個后繼
########################################################
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的第一個狀態(tài)
# 我們把nil = #S的item閉包作為第一個狀態(tài)，其中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
########################################################
# 求一個狀態(tài)的閉包
# 對于狀態(tài)集合中的任意一個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
########################################################
# 求每一個狀態(tài)的所有后繼
# 對于狀態(tài)s中任意一個item:
# 1. 如果存在item: S = a#vBC, 那么當下一個 token是v時，意味著
# 將v進行shift操作，并將狀態(tài)轉移到下一個狀態(tài)closure(S = av#BC);
# 2. 如果存在item: S = avBC#, 那么當下一個token在follow(S)中
# 意味著需要救星reduce操作，將stack里的avBC序列替換為S, 并移動到
# 下一個狀態(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是否已經在狀態(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
# 如果沒有任何可用的項目
#@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 !@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這時的實現(xiàn)也僅僅是轉調一下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
|
