编译原理复习——语法分析(自顶向下)_民生

编译原理复习——语法分析(自顶向下)

admin

2024-01-18 17:28:35

0次

自顶向下的语法分析定义： 从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。 语法树的构造 将文法的开始符号作为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。 所以解决这个问题的核心在于如何找到合适的产生式 从文法的开始符出发，如能根据当前的输入符号（单词符号）唯一地确定选用哪个产生式进行推导，则分析是确定的。 LL(1)文法是我们在语法分析自顶向下中所希望遇到的文法，我们在遇到判断一个文法是不是LL(1)前我们需要先学习三个集合即： 开始符号集FIRST 后跟符号集FOLLOW 选择集合SELECT FIRST集合 定义： G=(VN , VT , P, S)是上下文无关文法 α→β，(α∈VN , β∈(VN∪VT )* ) FIRST(β) = {a | a ∈VT 且β⇒* a......} 若β⇒* ε 则规定ε ∈FIRST(β) 直观上说文法符号串β 的开始符号集是由β推导出的所有的终结符开头和可能的ε组成。 例题：
文法G 2 [S]:
S→Ap
S→Bq
A→a
A→cA
B→b
B→dB
求出每条规则右部的符号串的FIRST集合
FIRST(Ap)={a,c}
FIRST(Bq)={b,d}
FIRST(a)={a }
FIRST(cA)={c}
FIRST(b)={b}
FIRST(dB)={d}
这里注意一点在求FIRST集合时很多时候会忘了ε，如果推导不出来那就没关系但是如果可以推导出来的话一定要写上。 FLLOW集合定义：
G=(V N , V T , P, S) 是上下文无关文法 B→xAy ， (A, B ∈ V N , x,y∈(VN∪ V T )* )
FOLLOW(A)={a|S=>*…Aa… ， a ∈ V T } ，若有 S=>* …A ，则规定 # ∈ FOLLOW(A)
注：输入串 # ，‘ # ’做为输入串的结束符
直观上说,非终结符A的后跟符号集是由句型中紧跟A后的那些终结符（包括 # ）组成
FOLLOW(A) 的计算方法
1 如果 A 为文法的识别符号，则规定 # ∈ FOLLOW(A)
2 如果有形如 B→α Aβ 的规则，则 FIRST(β) 的非空元素 ∈ FOLLOW(A)
3 如果有 β=>*ε ，或者形如 B→α A 的规则，则把 FOLLOW(B) 加入到 FOLLOW(A) 中
反复使用上述规则，直到每个非终结符的 FOLLOW 集不再增大为止
之所以说这个复杂跟他的第3条规则有很大的关系反复使用这个规则在计算中会很复杂。 注意哦在FOLLOW集合中我们是没有ε的只有# 例子：
文法 G 3 [S]: S→aA|d A→bAS|ε
FOLLOW(A)=Follow(S) ∪ {FIRST(S)-{ ε }} ={#} ∪{a,d} ={#, a, d}
FOLLOW(S)= {#} ∪ FOLLOW(A) ={#, a, d}
SELECT 集合定义： 这个是跟之前的FIRST集合和FOLLOW集合是有很大关系的。
G=(V N , V T , P, S) 是上下文无关文法
A → β ， (A ∈ V N , β ∈ (V N∪ V T )* )
若 β ≠>*ε, 则 SELECT(A→β)=FIRST(β)
若 β=>*ε, 则 SELECT(A→β)=(FIRST(β)-{ε} ) ∪ FOLLOW(A) 例子：
G 3 [S]:
S→aA
S→d
A→bAS
A→ε
SELECT(S→aA)=FIRST(aA)={ a }
SELECT(S→d)=FIRST(d)={ d }
SELECT(A→bAS)=FIRST(bAS)={ b }
SELECT(A→ε) =(FIRST(ε)-{ε})+ FOLLOW(A)={ #,a,d } 注意哦在SELECT集合中我们是没有#的只有ε 现在我们可以讨论LL(1)文法了 首先是部分定义 一个上下文无关文法为LL(1)文法的充分必要条件是，对每个非终结符A的两个不同产生式A→α与A→β，满足SELECT(A→α)∩SELECT(A→β)=Φ LL(1)文法的含义 第一个L——从左到右扫描输入串 第二个L——分析过程用最左推导 (1)——表明只需向前看 1 个输入符号便可以决定选哪个产生式进行推导（类似地，LL(k) 文法则需要向前看 k 个输入符号才可以确定选用哪个产生式） 要判别一个上下文无关文法是否是LL(1)文法，分为五步： 求能推出ε的非终结符集 计算每个产生式右部β的FIRST(β)集 计算每个非终结符A的FOLLOW(A)集 计算每个产生式A→β的SELECT(A→β)集按LL(1)文法的定义判别

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：java计算机毕业设计家庭财务管理系统设计与实现源码+mysql数据库+系统+lw文档+部署

下一篇：控制台程序中实现一个连接一个DBContext实例

编译原理复习——语法分析(自顶向下)

相关内容

热门资讯