【20200408】编译原理课程课业打卡十三之判断文法是否为LL（1）型文法

蔚落 2023-07-24 11:56 9阅读 0赞

### 【20200408】编译原理课程课业打卡十三之判断文法是否为LL（1）型文法 ###

*  一、课业打卡十三之判断文法是否为LL（1）型文法
 *   *  1、问题一
     *  2、问题二
 *  二、知识巩固
 *   *  1、关于LL（1）型文法
     *  2、判断文法是否为LL（1）型文法求解方法步骤
     *  3、例题拓展

***叮嘟！这里是小啊呜的学习课程资料整理。好记性不如烂笔头，今天也是努力进步的一天。一起加油进阶吧！***  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center]

# 一、课业打卡十三之判断文法是否为LL（1）型文法 #

## 1、问题一 ##

问题描述：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 1]

解答过程：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 4]

## 2、问题二 ##

问题描述：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 5]

解答过程：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 7]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 9]

# 二、知识巩固 #

## 1、关于LL（1）型文法 ##

**LL(1) 文法的定义：**

(1) 文法不含左递归；
    (2) 对文法中的任一个非终结符A的各个产生式的侯选首终结符集两两不相交；
    即：若A->α1|α2|…|αn ，则 First(αi)∩ First(αj) = φ ( i ≠ j )；
    (3) 对文法中的每个非终结符A,若它的某个首终结符集含有ε ，则First(A)∩Follow(A) = φ。

## 2、判断文法是否为LL（1）型文法求解方法步骤 ##

**第一种判断方法：**

对于文法的产生式任一产生式：
    
    （1）文法不存在左递归
    （2）假设A->α | β是其中一个产生式,  如果α 或者 β都不能推出 ε，则FIRST（α ）∩first（ β）=∅
    （3）假设A->α | β是其中一个产生式， 如果α 或者 β至多有一个能推出 ε，或者其中一个经过若干步能推出ε，则first（α）∩follow（A）=∅（这里假设β能推出 ε）
    
    文法所有的产生式都要满足以上三种情况才符合LL（1）文法；

**第二种判断方法：** 【四步走】  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70]

## 3、例题拓展 ##

文法 G（S）:  
（1）S -> AB  
（2）A ->Da|ε  
（3）B -> cC  
（4）C -> aADC |ε  
（5）D -> b|ε

验证文法 G（S）是不是 LL（1）文法？

证明：FIRST(Da) = { b, a}
    　　　FIRST(ε) = { ε}
    　　　FIRST(aADC) = { a}
    　　　FIRST(b) = { b}
    　　　
    　　　FOLLOW(A) = { c, b, a, #}
    　　　FOLLOW(C) = { #,}
    　　　FOLLOW(D) = { a, #}
    　　　
    　　　SELECT(A -> Da) = FIRST(Da) = { b, a}
    　　　SELECT(A -> ε) = FIRST(ε) - { ε}UFOLLOW(A) 
    　　　              = FOLLOW(A) = { c, b, a, #}
    
    　　　因为SELECT(A -> Da) ∩ SELECT(A -> ε) ≠ Ø
    　　　所以G（S）不是 LL（1）文法。

**Ending！**  
更多课程知识学习记录随后再来吧！

就酱，嘎啦！

![在这里插入图片描述][20200207152559955.png_pic_center]

注：  
人生在勤，不索何获。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/61a45b4b969543fb84a027ce114a1b9e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230528/242008759a174610ac4d06dbe277431d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20230528/5e227e457efc4e14b15123cb2f92b600.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20230528/773edc953740486c9900a4e2b7233af8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20230528/23c6f04bed5d4228bb03e3791298bd67.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20230528/2dadd19747e343589f39eb61511bd93e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20230528/f5ed255ddf5644599434ba48de06ce03.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20230528/99a9b60dd0904bbf9f8afe3789b8c415.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20230528/bd16618991f84605a875b73f2e85aaf5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20230528/220f35aa1205482d922c130a0fcaedbe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzNzg5_size_16_color_FFFFFF_t_70]: /images/20230528/8472b1032c424fa69164d6c442efb98d.png
[20200207152559955.png_pic_center]: /images/20230528/e0d51a90e5b647edb279f58d5dc1835e.png