用cpp编写的一个实现了最核心功能的YACC,供练习使用.
程序中构造了LALR(1) Parsing Table.
自底向上和自上而下两种Paser方法,各有千秋.
自上而下,比较适合手写,因为很简单,同时,而且在写的过程中,你还可以自己做一些优化,比如说在生成树的过程中,那些空的树可以手动裁剪掉,因此,一般而言,自顶向下的Parser生成的ast比自底而上的Parser生成的ast要小一些,更加精炼一点.
自底向上生成ast,这大概只能通过代码来做了,这种ast,你没有办法做裁剪,或者说,你只能等到生成了ast之后再来做裁剪.自底向上的Parser采用的方法一般是LR(1), LALR(1),或者更加强大的LALR(k)和LR(k),(k > 1), 这里需要强调的是LR(k)之流虽然更加强大,但是强大是有代价的,那就是这些玩意的内存开销实在太大,所以LR(k)并不是很实用.事实上即使是LR(1), 它的内存开销也很大,所以现实生活中比较实用的Parser算法当属LALR(1)了,它和LR(0)内存开销差不多,但是远比LR(0)强大(能解析更多的文法).
那么自底向上和自上而下这两种方法有什么区别呢?
自底向上的方法LR(1)或者LALR(1)一般都比自上而下的方法LL(1)之流更加强大,
正如前面说的,强大是有代价的,它们也因此变得更加复杂.
自上而下来解析的话,对文法一般都有这么两条限制:
- 不能存在左递归;
- 规则之间不能存在左公因式;
否则的话,自上而下的Parser是无法对文法进行解析的,你要对文法进行一定的转换后才行,而这些东西对于自下而上的LR(1)和LALR(1)都不是个事.
但是LR(1)和LALR(1)也有限制,那就是文法规则间不能存在两个公因式,比如
A -> abD
B -> abC这事实上已经不是LR(1)或者LALR(1)文法了,需要更加高级的LR(k)才能处理,说实话,你真的没有必要将文法弄得这么复杂.
最后特别强调一点,自上而下和自下而上并没有谁更好一说.彼此各有千秋.
现在暂时还没有写完,只实现了最核心的功能,还有很多地方需要完善,只能一步一步来写啦.