编译原理 第4章1剖析.ppt

第四章 语法分析 本章讨论程序语言的语法分析方法，以及语法分析程序的设计原理和实现技术。 第四章 语法分析 语法分析程序的功能和语法分析方法 4.1 语法分析程序的功能 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 文法的左递归性和回溯的消除 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)文法的判断条件 LL(1)文法的判断条件 LL(1)文法的判断条件 LL(1)文法的判断条件 LL(1)文法的判断条件 LL(1)文法的判断条件 LL(1)文法的判断条件 LL(1)文法的判断条件 4.2.3 某些非LL(1)文法到LL(1)文法的改写方法 4.2.3 某些非LL(1)文法到LL(1)文法的改写方法 第一种情况: 文法中相同左部的规则，其右部左端第一个符号相同而引起回溯。 S→ aAb A→ de | d 例 设有文法G[S]： 第二种情况: 文法中相同左部的规则，其中某一右部能推出ε串，例如, 文法G： A→ Bx B→ x |ε 其非终结符B有两个右部，第二个右部能推导出ε串且两个右部左端第一个符号不相同，但在分析符号串 W＝x 时出现回溯。 试探分析过程如下图所示： A B x x A B x ε A→ Bx B→ x |ε W＝x 匹配失败 匹配成功 综上所述，在自上而下分析过程中，为了避免回溯， 对描述语言的文法有一定的要求: 对文法的某个非终结符A,当它有多个侯选式时: 若用A匹配输入串时,能根据当前读到的输入符号a唯一地选择一条规则去匹备输入串。或者说，能唯一地选择一条规则进行推导。 A → α1 | α2 | α3 |??????| αn 这也就是说，在自上而下分析过程中，为了避免回溯，要求描述语言的文法是LL(1)文法。 为了建立LL(1)文法的判断条件，需引进三个相关集： FIRST集 FOLLOW集 SELECT集 设α是文法G的任一符号串，定义文 法符号串α的首符号集合。 FIRST(α) = { a | α ?a…且 a∈VT } * ,则规定 ε∈ FIRST(α) 若α ? ε * 例 设有文法G[S]: S → Ap | Bq A → cA | a B → dB | b FIRST(Ap) = { c, a } AP ? cAp AP ? ap FIRST(Bq) = Bq ? bq { b, d } Bq ? dBq (2) 设文法G的开始符号为S，对于G的任 何非终结符A，定义非终结符A的后 继符号的集合 FOLLOW(A) ={ a | S ? …Aa …且a∈VT } * 若有S ? …A , * 则规定 $∈FOLLOW(A)。