ZUCC_编译语言原理与编译_实验06 07 语法分析 LL 分析

编译语言原理与编译实验报告

课程名称	编程语言原理与编译
实验项目	语法分析 LL 分析

实验内容

一 . 阅读ppt 相关内容 ，阅读教材第3章

1、理解Nullable集、First集、 Follow集 概念

1. Nullable集：可以推导出空串的非终结符的集合（属于NULLABLE集合意味着不用接受任何输入即可跳过该非终结符）
   • 注：只有当产生式右侧的式子都是非终结符并且都可以推导出 ε，才能把产生式左侧的符号加入到NULLABLE集合中。
2. FIRST集：FIRST(α)被定义为从 α 推导得到的句子的首符号的集合，α 是任意的文法符号串。
   • 可以理解为：FIRST集合是看箭头后面的第一个字符，如果这个字符是非终结符（大写字母），就继续找这个大写字母能推导出的东西，再看后面是不是非终结符，如果还是，继续找，如果是终结符（小写字母）或空串，则把终结符或空串放到相应的FIRST集合中。
3. Follow集：对于非终结符A，FOLLOW(A)被定义为可能在某些句型中紧跟在A右边的终结符号的集合。
   • 可以理解为：
     • 对于开始符号，直接把 # 加进开始符号的FOLLOW集合
     • 要求哪个符号的FOLLOW集合，就把所有包含这个符号的式子找出来，但只有这个符号在箭头右边的才有用
     • 如果这个符号在最后一个，就把这个符号所在的那个式子的箭头左边的符号的FOLLOW集合加进去
     • 如果要求的符号的后面还有非终结符，就把这个非终结符的FIRST集合减去空串加进去，此外，如果要求的这个符号的后面的非终结符和箭头左侧的符号相同，则把箭头左侧的FOLLOW集合加入到要求的符号的FOLLOW集合中
     • 如果要求的符号的后面是终结符，就把这个终结符加到FOLLOW集合中
     • 在第一个产生式箭头后面的非终结符，都要把开始符号的FOLLOW集合加到相应的FOLLOW集合中

• 阅读 NullableFirstFollow.pdf
• 理解 各个集合的构造方法
  • https://blog.csdn.net/YyjYsj/article/details/106379238

2、理解 自顶向下分析，自底向上分析的区别

• 自顶向下分析：
  • 从根到叶子节点的顺序构建分析树
  • 寻找从开始符号到最终句子的最左推导序列
  • 分析器输入Token序列
• 自底向上分析：
  • 分析树是从叶子节点到根节点的顺序构建的
  • 寻找从句子到开始符号的最左归约序列

3、理解确定性自顶向下分析方法，LL(1)分析

LL(1) 分析法又称预测分析法 ，是 一种不带回溯的非递归自上而下分析法。

• 第一个L 第二个L，数字1 各是什么含义

  • 

• LL(1) 预测分析表构造，中 与First集 Follow集的关系,

  • 
  • 

• 阅读NullableFirstFollow.pdf理解分析表的构造

4、理解 通过关系图计算First集 Follow集的方法

• 关系图计算First集
  • 
• 关系图计算 Follow集
  • 

5、理解 递归下降分析程序与文法的对应关系

https://blog.csdn.net/qq_45180475/article/details/107845953

6、通过学习可视化工具，理解LL(1)分析算法

• LL(1)可视化

  • 

• 在线分析工具 grammophone

  • 

二 . 设有文法

 S -> a | ^ |( T )
 T -> T , S | S

请消除文法的左递归。

三 . 设有文法

E -> T | T ^ E
T -> int * T | ( E ) | ( S )
S -> int T

请提取文法的左公因子。

四 . 设有如下文法

S -> A
A -> B | A i B
B -> C | B + C
C -> ) A * | (

判断能否将文法改为 LL（1）文法

• 求每个非终结符的 First集 与 Follow集

  • 

• 构造 LL（1）预测分析表，给出结论

  • 修改如下：
    • 
    • 

五 . 给定以下文法

S -> + S S
S -> * S S
S -> a

给出该文法的预测分析表

提取左公因式：

S -> S' S | a
S' -> + | *

利用预测分析器算法分析+*aaa，判断该句子是否属于上面文法的语言。