编译原理第4章-自顶向下语法方法讲述.ppt

第四章 语法分析 本章讨论程序语言的语法分析方法，以及语法分析程序的设计原理和实现技术。 语法分析程序的功能和语法分析方法 4.1 语法分析程序的功能 4.1 语法分析程序的功能 4.1 语法分析程序的功能 4.2 自上而下语法分析法 4.2.1 非确定的自上而下分析法的思想 4.2.1 非确定的自上而下分析法的思想 4.2.1 非确定的自上而下分析法的思想 4.2.1 非确定的自上而下分析法的思想 4.2.1 非确定的自上而下分析法的思想 4.2.2 文法的左递归性和回溯的消除 4.2.2 文法的左递归性和回溯的消除 4.2.2 文法的左递归性和回溯的消除 4.2.2 文法的左递归性和回溯的消除 4.2.2 文法的左递归性和回溯的消除 4.2.2 文法的左递归性和回溯的消除 4.2.2 文法的左递归性和回溯的消除 4.2.2 文法的左递归性和回溯的消除 4.2.2 文法的左递归性和回溯的消除 4.2.2 文法的左递归性和回溯的消除 4.2.2 文法的左递归性和回溯的消除 4.2.2 文法的左递归性和回溯的消除 4.2.2 文法的左递归性和回溯的消除 4.2.2 文法的左递归性和回溯的消除 4.2.2 文法的左递归性和回溯的消除 4.2.2 文法的左递归性和回溯的消除 LL(1)文法的判断条件 LL(1)文法的判断条件 LL(1)文法的判断条件 LL(1)文法的判断条件 LL(1)文法的判断条件 LL(1)文法的判断条件 LL(1)文法的判断条件 LL(1)文法的判断条件 LL(1)文法的判断条件 LL(1)文法的判断条件 LL(1)文法的判断条件 LL(1)文法的判断条件 LL(1)文法的判断条件 4.2.3 某些非LL(1)文法到LL(1)文法的改写 4.2.4 递归下降分析法 预测分析器的总控程序在任何时候都是根据栈顶符号和当前输入符号a来决定分析器的动作。 不难验证改写后的文法为LL(1)文法。 因为 SELECT(A →e)∩SELECT(A →ε) ={e}∩{ε, b}= Ф S → aAb A → dA A → e | ε 例2 设有文法G[S]: S→ ad | Ae A→ aS | bA 将A的两条规则代入非终结符S的规则中 A→ aS | bA S→ ad | aSe | bAe 对S提取公共左因子得 S→ bAe | aS 改写后的文法是LL(1)文法。 S → d | Se A→ aS | bA A→ aS | bA S→ ad | aSe | bAe 应当指出的是并非一切非LL(1)文法都能改写为LL(1)文法。 例如，对于文法 S→ Ae | Bd A → aAe | b B→ aBd | b ∴ 该文法不为LL(1)文法 ∵ SELECT(S→Ae)∩SELECT(S→Bd) ={ a, b }∩{ a, b }≠Φ 对S提取公共左因子后，得 对于S的两条规则, 可先将非终结符A、B用相应规则右部进行替换，我们得到 S→ aAee | be | aBdd | bd A → aAe | b B→ aBd | b 显然，它仍不是一个LL(1)文法，且不难看出无论将上述步骤重复多少次, 都无法将它改写为LL(1)文法。 S→ aS | bS S → Aee | Bdd A→ aAe | b S→ e | d B→ aBd | b 递归下降分析法是确定的自上而下分析法，这种分析法要求文法是LL(1)文法。 基本思想 对文法中的每个非终结符编写一个函数 (或子程序), 每个函数（或子程序）的功能是识别由该非终结符所表示的语法成分。由于描述语言的文法常常是递归定义的，因此相应的这组函数（或子程序）必然以相互递归的方式进行调用，所以将此种分析法称为递归下降分析法。 构造递归下降分析程序的方法: 为每个非终结符编制一个递归下降分析函数，每个函数名是相应的非终结符，函数体则是根据规则右部符号串的结构和顺序编写。 A→α1α2…αn αi∈VT αi∈VN α1α2…αn=ε (1) 当遇到终结符a时，则编写语句 if (当前读来的输入符号==a) 读下一个输入符号； (2) 当遇到非终结符A时，则编写语句调 用 A( )； (4) 当某个非终结符的规则有多个候选式 时，按LL(1)文法的条件能唯一地选 择一个候选式进行推导。 (3) 当遇到规则A→ε 时，则编写语句 if (当前读来的输入符号?FOLLOW(A)) error( )； E→ E + T | T T