编译原理笔记

Bertha 。 2023-09-29 14:36 9阅读 0赞

#### 编译原理笔记 ####

*  构造文法
 *  自顶向下、自底向上、子树、直接子树
 *  二义性文法、非二义性文法
 *  短语、直接短语、句柄
 *  化简文法
 *  右线性文法
 *  重点1
 *   *  消除左递归
     *  FIRST、FOLLOW集
     *  LL(1)文法
     *  LR(0)文法
     *  SLR(1)文法
     *  LR(1)文法
     *  LALR(1)文法
 *  重点2
 *   *  逆波兰式
     *  中缀式
     *  四元式
     *  布尔表达式

![在这里插入图片描述][ac968f9e296740a280383ce12902b838.png]

## 构造文法 ##

![在这里插入图片描述][ef043e5f6d24428da1f269cffd00d573.png]  
参考文档 [https://www.doc88.com/p-9436653550668.html][https_www.doc88.com_p-9436653550668.html]  
![在这里插入图片描述][6495a8af98c74689b97d62ac7b77791f.png]

## 自顶向下、自底向上、子树、直接子树 ##

![在这里插入图片描述][a0afd20673e84001b8969464d61d9202.png]  
![在这里插入图片描述][58a165c9a83a436b89ee203c3158ff0c.png]

![在这里插入图片描述][b7c67c8bb8c647b18bf76fe5a49d64a4.png]

## 二义性文法、非二义性文法 ##

![在这里插入图片描述][25e86af84ede4d3a87e0039b2dfd8913.png]

## 短语、直接短语、句柄 ##

![在这里插入图片描述][35b754208a604e7f9b9149fc69b4ade2.png]  
![在这里插入图片描述][ffc0415ac7ff4bc981e3159fdba30657.png]

直接短语和句柄的结果 以下图为准。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。  
![在这里插入图片描述][9c84de537d994f52b6800be41e038402.png]

综上结果为：
    短语         P，T*F，(T*F)，P↑(T*F)，T*P↑(T*F)
    直接短语 	P，T*F
    句柄	        P

## 化简文法 ##

![在这里插入图片描述][ec8f1c7d6636420e8d705366389412f7.png]

## 右线性文法 ##

![在这里插入图片描述][70df135f24e14b9693050180858b963f.png]

![在这里插入图片描述][92bc138778b44c99b2821b9cef5c0c01.png]  
![在这里插入图片描述][d956de9b10ba4c4a83f9bac54b4c6476.png]

## 重点1 ##

### 消除左递归 ###

![在这里插入图片描述][8d3d6aa48310410f887a912b074396f2.png]

### FIRST、FOLLOW集 ###

可参考文章[https://blog.csdn.net/qq\_66345100/article/details/124520295][https_blog.csdn.net_qq_66345100_article_details_124520295]  
![在这里插入图片描述][86921e655177450e8a1bb111ec1b880b.png]  
![在这里插入图片描述][08b7ec3da5444b6f9d12dbe60dc11674.png]

**多个符号形成的符号串的First结合：**

X -> ABC…，并且A不能推导出空串ε，显然根据定义First（ABC…）=First（A）
    
    X -> ABC…，并且A可能推导出空串ε，当A不是空串的时候，显然First（A）属于First（ABC…），但当A是空串的时候，ABC…就成了BC…，
    		   此时根据B是否能推出空串来决定是否将First（B）加入First （ABC…）。这是一个递归的推导，
    		   综上所述，符号串中的第一个不能推出空串的符号前面所有符号的First集合减去空串ε都属于First（ABC…），
    		   第一个不能推出空串的 符号的First集合也属于First（ABC…）。
    		   也就是假设A、B都可以推出空串，C不能推出空串，First（X）=(First（A）- ε) ∪ (First（B）- ε) ∪ (First（C）)。
    
    特殊的，符号串ABC...,A、B、C都可以推导出 ε ，那么把 ε 也加到First(X)中。
    
    注意：First集合中的符号一定是终结符，终结符也包括空串ε。

![在这里插入图片描述][3fa52d78833d4d4b9e69a36e78636d2e.png]

### LL(1)文法 ###

![在这里插入图片描述][55eea676af3c4113889eeb6a7a8aa0a6.png]  
![在这里插入图片描述][fdfdf3539d3f4b559215f4cef25d45d6.png]

### LR(0)文法 ###

不存在移进-归约冲突和归约-归约冲突则为 LR(0)文法  
![在这里插入图片描述][42fbab06b3f74d798ed0604facab578c.png]  
![在这里插入图片描述][b15d642ed3174042a25e8a4a5044faac.png]  
![在这里插入图片描述][84093acb3b094ed1a048b17f56cc2dec.png]  
![在这里插入图片描述][5c1fc4856eb340ca9061918eef541723.png]

### SLR(1)文法 ###

SLR文法不存在归约-归约冲突，有可能存在移进-归约冲突，但是如果可以用 follow集解决则是 SLR文法。换句话说，SLR文法分析过程可以解决归约-归约冲突，但是不一定能解决移进-归约冲突。用 follow集来处理即出现移进-归约冲突的两条产生式，如果其 follow集相交为空则为 SLR文法，反之不是。当然，如果以上两种冲突都不存在自然是了。  
![在这里插入图片描述][2c4aa196a6ae4390b39b6b83e053da64.png]  
![在这里插入图片描述][dd42dba87fa04db0aeb28fbc62f20c0e.png]  
![在这里插入图片描述][f4c623935258446a966e630a8a108c2b.png]

### LR(1)文法 ###

因为 LR(1)文法的范围比较大，所以文法几乎都是 LR(1)的，现在知道的只有当合并同心集产生了归约-归约冲突时才只属于 LR(1)文法，而不属于其他文法。  
![在这里插入图片描述][569da4fc5d6d4a53ab99da165200ca19.png]  
![在这里插入图片描述][20143386af1443fc995f6451f81b86e4.png]  
![在这里插入图片描述][fd8f17c503e648b6821984594f5b017e.png]  
![在这里插入图片描述][4f88d00bf4404466b76a1d404af0e09e.png_pic_left]

### LALR(1)文法 ###

合并同心集不会产生新的移进-归约冲突，但是会产生新的归约-归约冲突，如果没产生新的归约-归约冲突就是 LALR 文法，反之不是。  
![在这里插入图片描述][d22962be44354189872766a696639a3d.png_pic_left]  
![在这里插入图片描述][14d1a7a8164246c18291b4c0733655ea.png_pic_left]  
可参考文章：[https://blog.csdn.net/weixin\_44225182/article/details/105599118][https_blog.csdn.net_weixin_44225182_article_details_105599118]

## 重点2 ##

### 逆波兰式 ###

![在这里插入图片描述][7418c939c0894109872b33ce1dcd25d2.png]

### 中缀式 ###

逆波兰式的逆写  
![在这里插入图片描述][87f25807e568496a906505444856499b.png]

### 四元式 ###

![在这里插入图片描述][5317ba34c3d7472f8e597dd02d4d4a39.png]

### 布尔表达式 ###

![在这里插入图片描述][38b2481cba9b4b069532b0d4f5b01152.png]  
![在这里插入图片描述][609b37a4f0a4420c8e7200ca945e8cfb.png]

[ac968f9e296740a280383ce12902b838.png]: https://img-blog.csdnimg.cn/ac968f9e296740a280383ce12902b838.png
[ef043e5f6d24428da1f269cffd00d573.png]: https://img-blog.csdnimg.cn/ef043e5f6d24428da1f269cffd00d573.png
[https_www.doc88.com_p-9436653550668.html]: https://www.doc88.com/p-9436653550668.html
[6495a8af98c74689b97d62ac7b77791f.png]: https://img-blog.csdnimg.cn/6495a8af98c74689b97d62ac7b77791f.png
[a0afd20673e84001b8969464d61d9202.png]: https://img-blog.csdnimg.cn/a0afd20673e84001b8969464d61d9202.png
[58a165c9a83a436b89ee203c3158ff0c.png]: https://img-blog.csdnimg.cn/58a165c9a83a436b89ee203c3158ff0c.png
[b7c67c8bb8c647b18bf76fe5a49d64a4.png]: https://img-blog.csdnimg.cn/b7c67c8bb8c647b18bf76fe5a49d64a4.png
[25e86af84ede4d3a87e0039b2dfd8913.png]: https://img-blog.csdnimg.cn/25e86af84ede4d3a87e0039b2dfd8913.png
[35b754208a604e7f9b9149fc69b4ade2.png]: https://img-blog.csdnimg.cn/35b754208a604e7f9b9149fc69b4ade2.png
[ffc0415ac7ff4bc981e3159fdba30657.png]: https://img-blog.csdnimg.cn/ffc0415ac7ff4bc981e3159fdba30657.png
[9c84de537d994f52b6800be41e038402.png]: https://img-blog.csdnimg.cn/9c84de537d994f52b6800be41e038402.png
[ec8f1c7d6636420e8d705366389412f7.png]: https://img-blog.csdnimg.cn/ec8f1c7d6636420e8d705366389412f7.png
[70df135f24e14b9693050180858b963f.png]: https://img-blog.csdnimg.cn/70df135f24e14b9693050180858b963f.png
[92bc138778b44c99b2821b9cef5c0c01.png]: https://img-blog.csdnimg.cn/92bc138778b44c99b2821b9cef5c0c01.png
[d956de9b10ba4c4a83f9bac54b4c6476.png]: https://img-blog.csdnimg.cn/d956de9b10ba4c4a83f9bac54b4c6476.png
[8d3d6aa48310410f887a912b074396f2.png]: https://img-blog.csdnimg.cn/8d3d6aa48310410f887a912b074396f2.png
[https_blog.csdn.net_qq_66345100_article_details_124520295]: https://blog.csdn.net/qq_66345100/article/details/124520295
[86921e655177450e8a1bb111ec1b880b.png]: https://img-blog.csdnimg.cn/86921e655177450e8a1bb111ec1b880b.png
[08b7ec3da5444b6f9d12dbe60dc11674.png]: https://img-blog.csdnimg.cn/08b7ec3da5444b6f9d12dbe60dc11674.png
[3fa52d78833d4d4b9e69a36e78636d2e.png]: https://img-blog.csdnimg.cn/3fa52d78833d4d4b9e69a36e78636d2e.png
[55eea676af3c4113889eeb6a7a8aa0a6.png]: https://img-blog.csdnimg.cn/55eea676af3c4113889eeb6a7a8aa0a6.png
[fdfdf3539d3f4b559215f4cef25d45d6.png]: https://img-blog.csdnimg.cn/fdfdf3539d3f4b559215f4cef25d45d6.png
[42fbab06b3f74d798ed0604facab578c.png]: https://img-blog.csdnimg.cn/42fbab06b3f74d798ed0604facab578c.png
[b15d642ed3174042a25e8a4a5044faac.png]: https://img-blog.csdnimg.cn/b15d642ed3174042a25e8a4a5044faac.png
[84093acb3b094ed1a048b17f56cc2dec.png]: https://img-blog.csdnimg.cn/84093acb3b094ed1a048b17f56cc2dec.png
[5c1fc4856eb340ca9061918eef541723.png]: https://img-blog.csdnimg.cn/5c1fc4856eb340ca9061918eef541723.png
[2c4aa196a6ae4390b39b6b83e053da64.png]: https://img-blog.csdnimg.cn/2c4aa196a6ae4390b39b6b83e053da64.png
[dd42dba87fa04db0aeb28fbc62f20c0e.png]: https://img-blog.csdnimg.cn/dd42dba87fa04db0aeb28fbc62f20c0e.png
[f4c623935258446a966e630a8a108c2b.png]: https://img-blog.csdnimg.cn/f4c623935258446a966e630a8a108c2b.png
[569da4fc5d6d4a53ab99da165200ca19.png]: https://img-blog.csdnimg.cn/569da4fc5d6d4a53ab99da165200ca19.png
[20143386af1443fc995f6451f81b86e4.png]: https://img-blog.csdnimg.cn/20143386af1443fc995f6451f81b86e4.png
[fd8f17c503e648b6821984594f5b017e.png]: https://img-blog.csdnimg.cn/fd8f17c503e648b6821984594f5b017e.png
[4f88d00bf4404466b76a1d404af0e09e.png_pic_left]: https://img-blog.csdnimg.cn/4f88d00bf4404466b76a1d404af0e09e.png#pic_left
[d22962be44354189872766a696639a3d.png_pic_left]: https://img-blog.csdnimg.cn/d22962be44354189872766a696639a3d.png#pic_left
[14d1a7a8164246c18291b4c0733655ea.png_pic_left]: https://img-blog.csdnimg.cn/14d1a7a8164246c18291b4c0733655ea.png#pic_left
[https_blog.csdn.net_weixin_44225182_article_details_105599118]: https://blog.csdn.net/weixin_44225182/article/details/105599118
[7418c939c0894109872b33ce1dcd25d2.png]: https://img-blog.csdnimg.cn/7418c939c0894109872b33ce1dcd25d2.png
[87f25807e568496a906505444856499b.png]: https://img-blog.csdnimg.cn/87f25807e568496a906505444856499b.png
[5317ba34c3d7472f8e597dd02d4d4a39.png]: https://img-blog.csdnimg.cn/5317ba34c3d7472f8e597dd02d4d4a39.png
[38b2481cba9b4b069532b0d4f5b01152.png]: https://img-blog.csdnimg.cn/38b2481cba9b4b069532b0d4f5b01152.png
[609b37a4f0a4420c8e7200ca945e8cfb.png]: https://img-blog.csdnimg.cn/609b37a4f0a4420c8e7200ca945e8cfb.png