![第09讲-语法分析-V-浅色_第1页](http://file3.renrendoc.com/fileroot_temp3/2022-1/15/7a89aff8-abf5-471f-ba36-dc0b4f7bbff4/7a89aff8-abf5-471f-ba36-dc0b4f7bbff41.gif)
![第09讲-语法分析-V-浅色_第2页](http://file3.renrendoc.com/fileroot_temp3/2022-1/15/7a89aff8-abf5-471f-ba36-dc0b4f7bbff4/7a89aff8-abf5-471f-ba36-dc0b4f7bbff42.gif)
![第09讲-语法分析-V-浅色_第3页](http://file3.renrendoc.com/fileroot_temp3/2022-1/15/7a89aff8-abf5-471f-ba36-dc0b4f7bbff4/7a89aff8-abf5-471f-ba36-dc0b4f7bbff43.gif)
![第09讲-语法分析-V-浅色_第4页](http://file3.renrendoc.com/fileroot_temp3/2022-1/15/7a89aff8-abf5-471f-ba36-dc0b4f7bbff4/7a89aff8-abf5-471f-ba36-dc0b4f7bbff44.gif)
![第09讲-语法分析-V-浅色_第5页](http://file3.renrendoc.com/fileroot_temp3/2022-1/15/7a89aff8-abf5-471f-ba36-dc0b4f7bbff4/7a89aff8-abf5-471f-ba36-dc0b4f7bbff45.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、本讲纲要本讲纲要v回顾回顾 重点:重点:FIRSTFIRST集、集、FOLLOWFOLLOW集集v自上而下分析实现自上而下分析实现 非递归的预测分析方法非递归的预测分析方法 构造预测分析表构造预测分析表 预测分析的错误恢复预测分析的错误恢复23本讲纲要本讲纲要v回顾回顾 重点:重点:FIRSTFIRST集、集、FOLLOWFOLLOW集集v自上而下分析实现自上而下分析实现 非递归的预测分析方法非递归的预测分析方法 构造预测分析表构造预测分析表 预测分析的错误恢复预测分析的错误恢复4预测分析程序结构预测分析程序结构5v预测分析方法中的预测分析表的构建预测分析方法中的预测分析表的构建6v文法文法S
2、-ACD A-a| S-ACD A-a| C-c D-d C-c D-d7预测分析表的构建预测分析表的构建8 文法S-ACD A-a| C-c D-d910删除其解决二义性11本讲纲要本讲纲要v回顾回顾 重点:重点:FIRSTFIRST集、集、FOLLOWFOLLOW集集v自上而下分析实现自上而下分析实现 非递归的预测分析方法非递归的预测分析方法 构造预测分析表构造预测分析表 预测分析的错误恢复预测分析的错误恢复1213141516171819出错的一般处理方法出错的一般处理方法v1 1 查表,当前表项空白,指向记号流查表,当前表项空白,指向记号流的指针后移;的指针后移;v2 2 查表,当前表
3、项中含有同步记号查表,当前表项中含有同步记号synchsynch,将当前栈中的非终结符弹出栈;,将当前栈中的非终结符弹出栈;v3 3 栈顶终结符和当前指针指向的终结栈顶终结符和当前指针指向的终结符不匹配,将栈顶终结符弹出栈。符不匹配,将栈顶终结符弹出栈。v1 1 栈顶不动;栈顶不动;2,32,3指针不动指针不动20同步记号加到表同步记号加到表3.13.1的分析表的分析表上上非终非终结符结符输输 入入 符符 号号 id + * ( ) $E E TE E TE synch synchE E +TE E E T T FT synchT FT synch synchT T T * *FT T T F
4、 F id synch synchF (E) synch synch21栈输入输出$E+id*+id$出错,跳过$Eid*+id$id属于first(E)$E Tid*+id$E T Fid*+id$E T idid*+id$E T *+id$E T F* *+id$E T F+id$出错:“”正好在F的同步记号集合中,无须跳过任何记号;F被弹出$E T +id$22$E +id$E T+id$E Tid$E T Fid$E T idid$E T $E $2324 then aaaaa, bbbbcaaaaa, aa, bbbc, bbc当非终结符的产生式有多种选当非终结符的产生式有多种选择,
5、即意味着分析过程有不同择,即意味着分析过程有不同的展开方式。的展开方式。只能根据当前输入符号来决定只能根据当前输入符号来决定采用哪种展开方式(选择),采用哪种展开方式(选择),这样就有了这样就有了 FIRST()函数。()函数。25栈栈 输输 入入 输输 出出 $E id * * id $ $E T id * * id $ E TE $E T F id * * id $ T FT $E T id id * * id $ F id $E T * * id $ $E T F* * * * id $ T * *FT $E T F id $ $E T id id $ F id $E T $E $T $
6、E 26EE$栈栈 输输 入入 输输 出出 $E id * * id $ $E T id * * id $ E TE $E T F id * * id $ T FT $E T id id * * id $ F id $E T * * id $ $E T F* * * * id $ T * *FT $E T F id $ $E T id id $ F id $E T $E $T $E 27ETE TE$栈栈 输输 入入 输输 出出 $E id * * id $ $E T id * * id $ E TE $E T F id * * id $ T FT $E T id id * * id $ F
7、id $E T * * id $ $E T F* * * * id $ T * *FT $E T F id $ $E T id id $ F id $E T $E $T $E 28ETE FT FTE$栈栈 输输 入入 输输 出出 $E id * * id $ $E T id * * id $ E TE $E T F id * * id $ T FT $E T id id * * id $ F id $E T * * id $ $E T F* * * * id $ T * *FT $E T F id $ $E T id id $ F id $E T $E $T $E 29ETE FT idid
8、TE$栈栈 输输 入入 输输 出出 $E id * * id $ $E T id * * id $ E TE $E T F id * * id $ T FT $E T id id * * id $ F id $E T * * id $ $E T F* * * * id $ T * *FT $E T F id $ $E T id id $ F id $E T $E $T $E 30ETE FT idTE$栈栈 输输 入入 输输 出出 $E id * * id $ $E T id * * id $ E TE $E T F id * * id $ T FT $E T id id * * id $ F
9、 id $E T * * id $ $E T F* * * * id $ T * *FT $E T F id $ $E T id id $ F id $E T $E $T $E 31ETE FT id *T F*FTE$栈栈 输输 入入 输输 出出 $E id * * id $ $E T id * * id $ E TE $E T F id * * id $ T FT $E T id id * * id $ F id $E T * * id $ $E T F* * * * id $ T * *FT $E T F id $ $E T id id $ F id $E T $E $T $E 32ET
10、E FT id *T FFTE$栈栈 输输 入入 输输 出出 $E id * * id $ $E T id * * id $ E TE $E T F id * * id $ T FT $E T id id * * id $ F id $E T * * id $ $E T F* * * * id $ T * *FT $E T F id $ $E T id id $ F id $E T $E $T $E 33ETE FT id *T FididTE$栈栈 输输 入入 输输 出出 $E id * * id $ $E T id * * id $ E TE $E T F id * * id $ T FT
11、 $E T id id * * id $ F id $E T * * id $ $E T F* * * * id $ T * *FT $E T F id $ $E T id id $ F id $E T $E $T $E 34ETE FT id *T FidTE$栈栈 输输 入入 输输 出出 $E id * * id $ $E T id * * id $ E TE $E T F id * * id $ T FT $E T id id * * id $ F id $E T * * id $ $E T F* * * * id $ T * *FT $E T F id $ $E T id id $ F
12、 id $E T $E $T $E 35ETE FT id *T FidE$栈栈 输输 入入 输输 出出 $E id * * id $ $E T id * * id $ E TE $E T F id * * id $ T FT $E T id id * * id $ F id $E T * * id $ $E T F* * * * id $ T * *FT $E T F id $ $E T id id $ F id $E T $E $T $E 36ETE FT id *T Fid$37作业作业38本讲纲要本讲纲要v语言和文法语言和文法v语法分析方法语法分析方法v自上而下分析自上而下分析vFIR
13、STFIRST集和集和FOLLOWFOLLOW集集393.23.2 语言和文法语言和文法3.2.83.2.8 非上下文无关的语言结构非上下文无关的语言结构vL L1 1 = = wcw | wwcw | w属于属于( (a | ba | b) )* * 标识符的声明应先于其引用的抽象标识符的声明应先于其引用的抽象 vL L2 2 = = a an nb bm mc cn nd dm m | | n n 0, 0, m m 0 0 形参个数和实参个数应该相同的抽象形参个数和实参个数应该相同的抽象 vL L3 3 = = a an nb bn nc cn n | | n n 0 0 早先排版描述的
14、一个现象的抽象早先排版描述的一个现象的抽象403.23.2 语言和文法语言和文法vL L1 1 = = wcwwcwR R | w | w ( (a|ba|b) )* * S S aSa | bSb | c aSa | bSb | c vL L2 2 = = a a n nb bm mc cm md dn n | | n n 1, 1, m m 1 1 S S aSd | aAdaSd | aAdA A bAc | bcbAc | bcvL L 2 2 = = a a n nb bn nc cm md dm m | | n n 1 1,m m 1 1 S S ABABA A aAb | aba
15、Ab | abB B cBd | cdcBd | cd41有些类似的语言却是上下文无关的3.23.2 语言和文法语言和文法vL L3 3 =a a n nb b n n | | n n 1 1 S S aSb | ab aSb | abvL L3 3 是不能用正规式描述的语言的一个范例是不能用正规式描述的语言的一个范例 若存在接受若存在接受L L3 3 的的DFA DFA D D,状态数为状态数为k k个个 设设D D读完读完 , , a a, , aa aa, , , , a ak k 分别到达状态分别到达状态s s0 0, , s s1 1, , , , s sk k 至少有两个状态相同,
16、例如是至少有两个状态相同,例如是s si i和和s sj j,则则a aj jb bi i属于属于L L3 3 42sifs0标记为标记为ai的路径的路径标记为标记为bi的路径的路径标记为标记为aj i的路径的路径 有些类似的语言却是上下文无关的3.23.2 语言和文法语言和文法3.2.93.2.9 形式语言鸟瞰形式语言鸟瞰v 文法文法 G G = (= (V VT T , , V VN N, , S S, , P P) )v 0 0型文法:型文法: , , , ( (V VN N V VT T) )* *, | , | | | 1 1v 1 1型文法:型文法:| | | | | | | |,
17、但但S S 可以例外可以例外v 2 2型文法:型文法:A A ,A A V VN N , , ( (V VN N V VT T) )* *v 3 3型文法:型文法:A A aBaB或或A A a a,A, BA, B V VN N , , a a V VT T v 短语文法、上下文有关文法、上下文无关文法、正规文法短语文法、上下文有关文法、上下文无关文法、正规文法 433.23.2 语言和文法语言和文法v例:例:L L3 3 a a n nb b n nc c n n| | n n 1 1的上下文有关文的上下文有关文法法S S aSBCaSBC S S aBCaBC CBCB BCBCaB aB abab bB bB bbbb bC bC bcbccC cC cccca an nb bn nc cn n的推导过程如下:的推导过程如下:S S * * a a n n-1-1S S ( (BCBC) ) n n 1 1用用S S aSBC naSBC n-1-1次次 S S + + a an n( (BCBC) )n n 用用S S aBC aBC 1 1次次 S S
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 初中语文第一册第五单元教学设计 人教版
- 31 第二部分 高考听力综合特训(24)(教学设计)2025版高中英语听力Ⅲ(高考强化篇)
- 专题 隋唐以来的经济发展 教学设计 2023-2024学年统编版七年级历史下册
- 《高压开关设备技术规范》征求意见稿
- 《类和对象》课件
- 完整2024年国有企业管理人员处分条例专题课件
- 指数基金投资%2b:鑫选ETF策略超额新高沪深300净买入走阔
- 专题11.1 七年级(下)数学月考试卷(3月份)(考查范围:第5~6章)(人教版)(解析版)
- 医疗废物规范化管理知识培训课件
- 施工现场道路、车辆安全管理规定
- 超市员工理货技巧培训课件
- PV-1200-(中文版)气候交变稳定性试验
- 《线性代数》课程思政教学大纲
- 行动学习法PPT课件(PPT 93页)
- 居住建筑节能(绿色建筑)工程达标情况表(全面验收)
- L波段高空气象探测系统原理及维护
- 二甲医院评审应知应会手册
- 中国黄土高原水土流失的治理教案
- 价值需求测评结果分析
- (整理)高中研究性学习课题开题报告表.
- 最新中小学人工智能教育实验学校申报材料
评论
0/150
提交评论