大家好,欢迎来到IT知识分享网。
自底向上的语法解析,依赖于一种语法格式,我们可称之为LALR(1),第二个L表示在解析语法时,从左向右读取语法文本,R表示right most,也就是在做语法解析时,我们从推导表达式的最右边的非终结符开始进行替换解析,LA的意思是look ahead,需要预先读取一个输入字符才能做下一步解析。
LR语法比LL语法更灵活,也更容易实现,正由于他的灵活性,是的在编译器实现中,做语法解析时,使用的都是LALR(1)的解析算法,下面我们举个栗子,看看LALR语法解析的基本原理。
自底向上的语法解析算法,通过压栈式自动机,从底向上构建语法解析数,举个具体的栗子
0:statement->expr
1:expr->expr+term
2: expr->term
3:term->term*factor
4:term->factor
5:factor-> (expr)
6:factor->NUM
第一个表达式起始的第一个非终结符statement,我们称之为全局非终结符。自底向上的语法只能有一个全局非终结符,并且全局非终结符只能出现在一个推导表达式的左边,我们注意到,上面的语法含有左递归,直接使用自顶向下的解析算法是解析不了的。
我们看看上面的语法,如何通过自底向上的解析算法来识别输入表达式1*(2+3)
首先我们需要一个堆栈,初始化时堆栈为空
stack:
input:1*(2+3)
首先,我们读取一个输入,把输入的token压入堆栈,然后把输入的指针指向下一个字符:
stack:NUM
input:*(2+3)
读取一个输入,把输入对应的token压入堆栈,然后把输入指针指向下一个字符的动作,我们称之为shift操作。
根据表达式6:factor->NUM,此时堆栈的NUM刚好是他的右边,于是将NUM出栈,然后将factor压入堆栈:
stack:factor
input:*(2+3)
当堆栈上若干个元素恰好形成某个表达式的右边,算法会将这些元素全部出站,然后将该表达式对应的左边非终结符入站,这个动作,我们成为reduce。
根据表达式4:term->factor,于是我们再做一次reduce操作,将factor出栈,将term入栈,于是有:
stack:term
input:*(2+3)
此时堆栈里的term构成了表达式2:expr->term的右部,似乎我们还可以再做一次reduce操作,但是我们不能这么做,如果term出栈,expr入栈,然而接下来我们要读入的字符是*,在语法推导中,没有任何表达式右边是包含expr*这种形式的,所以我们不做reduce操作,于是我们做了一个shift操作,读入下一个字符,将他的token压入堆栈,将输入指针指向下一个字符:
stack:term*
input:(2+3)
term*无法构成任何一个推导表达式的右边,所以继续做shift操作:
stack:term*(
input:2+3)
堆栈上的元素仍然无法构成任何推导表达式的右边,所以继续做shift操作:
stack:term*(NUM
input:+3)
根据表达式4:term->factor在做一次reduce操作于是有:
stack:term*(term
input:+3)
由于下一个要读入的字符是+,没有任何推导表达式的右边可以包含term+,于是我们再做一次reduce操作,通过预读取下一个字符来决定做shift还是reduce,这就是语法解析中LA表示的look ahead。
根据表达式2:expr->term,我们做reduce操作,于是有:
stack:term*(expr
input:+3)
我们继续做shift操作:
stack:term*(expr+
input:3)
再做两次次shift:
stack:term*(expr+NUM)
再根据表达式6:factor->NUM,我们可以再做一次reduce操作:
stack:term*(expr+factor)
根据表达式4:term->factor,继续做reduce操作:
stack:term*(expr+term)
此时栈顶的前几个元素恰好构成了表达式1的右边:
expr->expr+term
于是我们再做一次reduce操作:
stack:term*(expr)
再根据表达式5:factor->(expr)
stack:term*factor
再根据term->term*factor,做一次reduce操作
stack:term
再根据expr->term,做一次reduce操作有:
stack:expr
再根据表达式0:statement->expr做一次reduce操作于是堆栈变成:
stack:statement
此时堆栈中含有全局非终结符,此时解析结束,输入的文本可以被语法接受。
由此我们可以总结一下自底向上的语法解析是如何进行的。
1 如果堆栈顶部的若干个元素可以构成某个推导表达式的右边,那么将这结果元素出栈,将表达式左边的非终结符入栈,也就是做一次reduce。
2 要不然将当前字符对应的token压入堆栈,同时将输入指针指向下一个字符,也就是做一次shift操作。
3 如果reduce操作后,全局非终结符被压入堆栈,并且输入为空,那么解析结束,输入的文本可以被语法接收。
对于自顶向下的解析语法,左递归是不允许的,然而自底向上的语法解析,完全可以处理语法中的左递归情况。
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/163622.html