要想设计语法解析器,我们必须首先设计一种子程序,能够解析任何一个产生式,比如对于

A->TE’|BC| ϵ \epsilon ϵ

这样的表达式,如果我们写一个程序来检测他,应该怎么办呢?

PROCEDURE A;
BEGIN
	IF SYM IN FIRST(TE') THEN
		BEGIN T;E' END
	ELSE IF SYM IN FIRST(BC) THEN
		BEGIN B;C END
	ELSE IF SYM IN FOLLOW(A) THEM 
		BEGIN END
	ELSE ERROR

由代码可以轻易理解,这是一个判断A的子程序,SYM表示当前指针指向的字符,如果在TE‘中,就执行T E的子程序,在BC 中,就执行BC的子程序
如果在 ϵ \epsilon ϵ中,也就是A为空,那么直接跳过到下一个字符,就等同于在FOLLOW(A)中
如果三者都不是,就会报错

对于A的推导,一定是以上四种情况之一,执行完毕后,A推导完成


有趣的是,我们的语法是自顶向下递归的,但我们写程序可以按自己的相符顺序来写。
以下是较复杂的文法的子程序设计(来自中国大学mooc国防科技大学的ppt,讲得很不错,推荐!)

ADVANCE指的是指针往前指向下一个字符,比如在F的子程序设计中,如果SYM指向了i或者),那么F就推导完成,可以直接往下走了

下面图中
左下角的程序是E的,比较简单

右边两个程序,上面蓝色背景部分是精简版,和下面等价

绿字部分SYM!=’#’ AND SYM!=’)‘其实表示的就是不指向 ϵ \epsilon ϵ的意思,
开头已经解释,所谓指向 ϵ \epsilon ϵ就是指向自己的follow(),E’的follow()是’)‘和’#’,因为指向 ϵ \epsilon ϵ什么都没做,所以判定省略了,直接判定不指向 ϵ \epsilon ϵ的情况,返回error,

接下来是判定T和T’的,同一个模式,同一个答案

最后是主程序

小结:总体思路是确定当前的字符,然后继续往下,难点在于一个非终结符可以有多个产生式,此时就要多个if进行判定,如果为空,则可以跳过