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 := idargument_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 = ABCfirst(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 ... aNT(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存放初始状态S12) 取符号流中下一个符号(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 /ndigit [0-9]number [+-]?{digit}+(/.{digit}+)?bool true|falselbrace "("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) breakend
那么我们的Lex类需要至少提供两个方法：get_next_token取得下一个符号get_token_string取得当前识别符号的字符串
Lex类是一个ruby的扩展类，创建这个扩展类的方法如下：1) 按prog.l的规则生成prog.c flex -t prog.l >prog.c2) prog.h定义一些constant和外部接口
#ifndef PROG_H_#define PROG_H_#define MAX_ID_LENGTH 256enum {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.rbrequire 'mkmf'dir_config('lex')create_makefile("lex")
5) 生成makefileruby 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_tokenassert ( 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_strsend
如上面的代码：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.rbrequire '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) endend
在我们上面所定义的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") endend
同样，实现他们也很简单。###### 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是由函数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) endend
有了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, :vocabsend
实际上，对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) endend
################################### 一个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, :posend
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 endend
其中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 !@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集合, 产生第一个状态,然后依次产生每一个后继 ######################################################## 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 !@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_tableend
而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
