语法分析技术概况 -自顶向下及自下向上两种
38页1、语法分析技术概况,不确定的 自顶向下分析法 递归下降分析法 确定的 预测分析法LL(1) 语法分析方法 简单优先分析法 优先分析法 算符优先分析法 自底向上分析法 LR(0)分析法 LR分析法 SLR(1)分析法 LR(1)分析法 LALR(1)分析法,第五章 自顶向下语法分析方法,5.1 自顶向下分析法的相关问题 5.2 LL(1)文法的定义和判别 5.3 文法等价变换 5.4 确定的自顶向下分析法 (递归下降程序法和预测分析法),5.1 相关问题,1、什么是语法分析? 2、什么是自顶向下分析法? 3、在自顶向下的分析过程中,存在的问题 是什么? 4、什么是确定的自顶向下分析法?,文法G1S: S pA 1 S qB 2 A cAd 3 A a 4 输入串W= pccadd。自顶向下的推导过程为: S pA pcAd pccAdd pccadd 相应的语法树为:,p,A,c,A,d,c,A,d,a,S,5.1 相关问题,文法G1S: S pA 1 S qB 2 A cAd 3 A a 4 自顶向下的语法分析过程【Sf,Rest,Action(D/M/S/E)】 S # pccadd
2、# Derivation pA # pccadd # Match A # ccadd # Derivation cAd # ccadd # Match Ad # cadd # Derivation cAdd # cadd # Match Add # add # Derivation add # add # Match dd # dd # Match d # d # Match # # Success,5.1 相关问题,问:,当一个非终结符号对应若干个规则时,选择哪个 规则的右部对该非终结符号进行展开呢? 例如:如果要被代换的最左非终结符号是U,且 有n条规则:U:=A1|A2|An,那么如何确定用 哪个规则的右部去替代U?,5.1 相关问题,确定的自顶向下分析法: 对每一个非终结符,都能够确定地选择规则来展开它。LL(1)文法,文法G2S: S Ap 1 S Bq 2 A a 3 A cA 4 B b 5 B dB 6 输入串W=ccap。自顶向下的推导过程为: S Ap cAp ccAp ccap 相应的语法树为:,S,A,p,c,A,c,A,a,5.1 相关问题,First集的定义
3、,设G=(VT,VN,S,P)是上下文无关文法, 其中:(VT VN )*,则: First()= aVT | a.(if then ) 可以根据当前的输入符号是属于哪个产生式右部的首符集而决定选择相应产生式进行推导。,*,*,5.2 LL(1)文法的定义和判别,文法G3S: S aA 1 S d 2 A bAS 3 A 4 输入串W=abd。自顶向下的推导过程为: S aA abAS abS abd 相应的语法树为:,S,a,A,b,A,S,d,Follow集的定义,设G=(VT,VN,S,P)是上下文无关文法, AVN,S是开始符号 Follow(A) = aVT | S.Aa. (if SA then # ) 当文法中存在推导形如:A 时,如果 当前的字符属于Follow(A),则用空字符 串取代A的出现。,*,+,+,5.2 LL(1)文法的定义和判别,Select集的定义,Select(A) = First() , 当First() = First() Follow(A), 当First() 定义:文法G是LL(1)文法的充要条件是,对 于U的任意两个不同的规则有: Sele
4、ct(U) Select(U)=,5.2 LL(1)文法的定义和判别,LL(1)文法的判别,判别算法: 1、计算能推出的非终结符 2、构造First集 3、构造Follow集 4、构造Select集并作判别,5.2 LL(1)文法的定义和判别,文法GE:E T E E + T E | T F T T * F T | F i | ( E ),N,Y,Y,N,N,计算First(X)集,对每一文法符号X计算First(X) 若XVT,First(X)=X 若XVN则 First(X)= a | XaP,a VT 若XVN,且有产生式X,则 First(X) 若XVN,有产生式XY1Y2Yn,且Y1,Y2,Yi VN 当Y1,Y2,Yi-1,则 First(Y1)-,First(Y2)-, First(Yi-1)-, First(Yi)都包含在First(X)中。 当Yi (i=1,2,n), 将并入First(X)中。,*,*,文法GE:E T E E + T E | T F T T * F T | F i | ( E ),First(E),First(T),First(E),First(
《语法分析技术概况 -自顶向下及自下向上两种》由会员小**分享,可在线阅读,更多相关《语法分析技术概况 -自顶向下及自下向上两种》请在金锄头文库上搜索。
2020年高考真题——理科综合(全国卷Ⅲ)+Word版含答案
2021年绝味鸭脖策划书
2021年熟食店创业方案
2021年熟食店开店策划
2021年卤菜店创业计划书
2021年周黑鸭网络营销策划方案
东大21年1月考试《现代设计方法》考核作业
谈我国行政管理效率的现状及其改观对策(论文)
单证员考试-备考辅导-复习资料:无贸易背景信用证案分析.docx
土木工程毕业生答辩自述.docx
建筑学毕业后工作状态真实写照.doc
C#代码规范(湖南大学).doc
xx区食药监局2019年工作总结及2020年工作计划
2019年中医院药物维持治疗门诊工人先锋号先进事迹
2019年度xx乡镇林长制工作总结
2019年性艾科工作计划书
2019年人才服务局全国扶贫日活动开展情况总结
关于组工信息选题的几点思考
摘了穷帽子 有了新模样
2019年某集团公司基层党支部书记培训班心得体会
2024-01-31 15页
2024-01-31 21页
2024-01-31 37页
2024-01-31 30页
2024-01-31 22页
2024-01-31 48页
2024-01-31 32页
2024-01-31 40页
2024-01-31 31页
2024-01-31 20页