自底向上语法解析的基本原理

自底向上语法解析的基本原理自底向上的语法解析 依赖于一种语法格式 我们可称之为 LALR 1 第二个 L 表示在解析语法时 从左向右读取语法文本 R 表示 right most 也就是在做语法解析时 我们从推导表达式的最右边的非终结符开始进行替换解析 LA 的意思是 look

大家好,欢迎来到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

(0)
上一篇 2024-12-21 21:00
下一篇 2024-12-21 21:15

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信