关于编译原理 - 语法分析的原理

众语言皆有自己的语法
语法分析:顾名思义,就是检测语法的正确性

PS: 恩我来填坑了。目前完成了 C 语言小子集解释器,距一个能自举的编译器还任重道远

我看了一位大神写的 C4 编译器,深受影响。里面所用到的思想和代码上的设计,让人觉得实在是非常巧妙,以至于我在自己造轮子的时候,不知不觉往 C4 上模仿,毕竟在你眼前出现了一种绝妙的设计,真的是没有办法拒绝它…虽然这一点让我在写编译器的时候,有一丝丝的沮丧,毕竟有一种模仿的味道在里面,但是在编码的过程中还是非常快乐的。希望自己有一天也能有一个绝妙的想法,设计出十分简洁的编译器~

再次感谢 reswier 和他的 C4 所带给我的灵感

以下正文:

1.自顶向下与自底向上分析法

先简单说说这两种识别思想吧:

自顶向下分析法

(1).寻找 “匹配”:存在产生式 $U -> u_{1}|u_{2}|u_{3}$,确定用哪个 u 代替 U

(2).如图:

S             S                S
             / | \            / | \
            c  A  d          c  A  d
                               / \
                              a   b

自底向上分析法

(1).一种归约过程:从输入符号串开始,逐步进行“归约”,直至归约到文法的开始符号

(2).如图:

                                               S  
                                              / | \
                          A                  c  A  d
                         / \                   / \
c   a   b   d       c   a   b   d             a   b   

 

2.自顶向下分析法:递归下降

自底向上分析法的话,通常使用 LR(1), LALR(1),或者更强大的 LR(k), LALR(k)。它的功能很强大,也很快,但是内存开销太大,编码相对复杂,对新手并不友好。

自顶向下分析法可以根据文法轻松构造出递归函数,所以相对新手友好,更适合手写,并且在写递归的时候,还可以随时做一些优化,不足的是对于处理翻译模式上比较麻烦一点,不能存在左递归。

对于编译原理的小白文,我决定只说自顶向下这一种方法,最后也是实现的它。

(todo…)