编译原理：LR(0)和SLR(1)-Syntax Analysi

2022-10-15 本文已影响0人树里的熊

LR(0)

1.写拓广文法
2.列出所有LR(0)项目：活前缀，求闭包
若点在非终结符前面就需要继续拓展，若在最后或在终结符前就不用
3.构造项目集规范族和识别活前缀的DFA：若有Iy=Go( $I_x$ , $\alpha$ ),就把x和y之间连一条弧，上面写 $\alpha$
4.写出LR(0)分析表：
三栏，状态|Action|Goto 如果是终结符，则在action部分，若非终结符则在goto部分

若 $\alpha$ 是终结符

若有 $I_x$ -- $\alpha$ --> $I_y$ :且 $I_y$ 中的点不在最后，则是移进，在对应表格填上 $s_y$
若有 $I_x$ -- $\alpha$ --> $I_y$ :且 $I_y$ 中的点在最后，则是归约，在对应表格填上 $r_m$ ,m的值是归约用到的产生式的序号，和状态无关！！

若 $\alpha$ 是非终结符
若有 $I_x$ -- $\alpha$ --> $I_y$ :则在对应表格填上y

按DFA写完之后，在有 $r_m$ 的那一行，action部分全部写上 $r_m$
其他空白格写上error

SLR(1)

有时LR(0)会产生冲突：
归约-归约冲突：不知道用哪个产生式归约，如A-> $\alpha$ ·，B-> $\alpha$ ·
归约-移进冲突：不知道当前是归约还是移进，如A-> $\alpha$ ·，B-> $\alpha$ · $\beta$

SLR（1）能在一定程度上解决这个问题，首先找到会产生冲突的项目集。
对于归约-归约冲突，若follow(A)和follow(B)不相交，则可以避免
对于归约-移进冲突，若follow(A)和first( $\beta$ )不相交，则可以避免

求follow集方法：
求谁的follow就找产生式中它出现在右边的时候，比如follow(B)

开始符号的follow集加入#
若有A-> $\alpha$ B $\beta$ ,就将first( $\beta$ ) \ $\varepsilon$ 放入follow(B)
若有A-> $\alpha$ B，就将follow(A)放入follow(B)

只有这一步不同： 按DFA写完之后，在有r_m的那一行，action部分全部写上r_m
求m号对应产生式左侧的follow集，比如r3,则看A->cA，求出follow(A),只在follow(A)中的元素对应部分写上r3

其他空白格写上error

上一篇下一篇

猜你喜欢

热点阅读