语法分析

一、主要内容

1.语法分析的过程

2.文法的改造

3.递归下降分析器的设计

4.语法分析器的自动生成

二、

1.什么是语法分析：语法分析师编译过程的核心部分，它的任务是再次发分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。

语法分析的过程：语法分析就是判断一个输入串是否符合语法规则，判断的方法是自上而下的分析，自下而上的规约。分析的结果是构造一颗语法树。

（1）自上而下的分析：即对于一个输入串，从文法的根节点开始，根据文法自上而下的为输入串建立一个语法树。即为输入串寻找一个最左推导。

面临的问题:文法的左递归问题，回溯的不确定性，虚假匹配的问题，不能准确地确定出错的地方，效率低。

（2）LL（1）分析法:

消除直接左递归：

消除间接左递归：

将间接左递归改为直接左递归：

消除直接左递归：

消除回溯：

消除回溯，需要定义FIRST集，令文法G是不含左递归的文法，对G的非终结符的候选α，定义它的开始符号（终结首符）集合。

提取公共左因子：

假设A的产生式为：A→δβ1|δβ2|…|δβn|γ1| γ2|…|γm，其中每个γ不以δ开头，那么把这些产生式改写为:  A→δA’ |γ1| γ2|…|γm         A’→β1|β2|…|βn。

反复提取左因子(包括对新引进的非终结符，例如A’)。

（3）递归下降程序分析

递归下降分析器，就是一个由一组递归程序组成，每个程序对应一个非终结符的分析程序。具体做法是对文法的每一个非终结符都编一个分析程序。当根据文法和当时的输入符号预测到要用某个非终结符去匹配输入串时，就调用该非终结符的分析程序。

（4）预测分析从程序

预测分析程序就是LL（1）分析器的一种，它使用一张分析表和一个栈进行控制。

工作过程：

LL分析程序构造和分析过程，这一部分由三部分能组成：分析表，执行程序和符号栈。

构建预测分析表：

FIRST(X)：

FOLLOW(X)

构建预测分析表：

（5）LL（1）分析中的错误处理

跳过输入串中的一些符号，直到遇到同步符号。遇到同步符号时，将符号栈顶的非终结符出栈。将FOLLOW(A)设为同步符号。将FIRST(A)加入到同步符号。如果非终结符产生空串，可以自动匹配，以推迟检测到错误的时间。如果栈顶是终结符，当出错时，直接将栈顶出栈。

三、习题

  

总结：

这一张还挺难的，反正我是没怎么理解。看课件也只能看到一知半解，做的题也是找大神教着我做的。总的来说这一张承接了上一张的内容，可能是因为我上一章的内容就没怎么弄明白，所以这一章就更不会了，还要继续自己看。