当前位置:首页 >> 计算机软件及应用 >> 5 语法分析(1)

5 语法分析(1)


回顾:自顶向下分析法 回顾:
若Z ? S
G[Z] +

则 S ∈ L(G[Z])

否则 S ? L(G[Z])

存在主要问题: 存在主要问题: 左递归问题 回溯问题

主要方法: 主要方法: ? 递归子程序法 ? LL分析法 LL分析法 输入串
#

LL分析程序构造及 LL分析程序构造及 分析过程
符号栈 此过程有三部分组成: 此过程有三部分组成: 分析表 总控程序) 执行程序 (总控程序) 分析栈) 符号栈 (分析栈)
#

执行程序
分析表

【例】已知文法 E→TE’ E’→+TE’|ε T→FT’ T’→*FT’|ε F→(E)|i
FIRST(F)={(,i} FIRST(T’)={*,ε} FIRST(T)={(,i} FIRST(E’)={+,ε} FIRST(E)={(,i} FOLLOW(F)={*,+,),#} FOLLOW(T’)={+,),#} FOLLOW(T)={+,),#} FOLLOW(E’)={#,)} FOLLOW(E)={#,)} FOLLOW(E)={#,)}

消除左递归

E::=TE’ E’::=+TE’|ε T ::=FT’ T’::=*FT’|ε F::=(E)|i

SELECT(E→TE’)={ (,i } SELECT(E’→+TE’)={ SELECT(E’→+TE’)={ + } SELECT(E’→ ε)={ ),# } SELECT(T→FT’)={ SELECT(T→FT’)={ (,i } SELECT(T′→ T SELECT(T′→*FT′)={*} ′→*F SELECT(T’→ε)={ SELECT(T’→ε)={ +,),# } SELECT (F→(E)={ ( } SELECT (F→i)={ i }

分析表
i E E’ T T’ F F→i T →FT’ T’→ε T’→*FT’ F→(E) E→TE’ E’→+T E’ T →FT’ T’→ε T’→ε + * ( E→TE’ E’→ε E’→ε ) #

注:矩阵元素空白表示Error 矩阵元素空白表示Error

i E E ::= T E ' F ::= i T ::= F T '

+

*

( E ::= T E '

)

#

请分析字符串 i+i*i是否合法 i+i*i是否合法。 是否合法。

E ' T

E '::= +T E ' T ::= FT '

E ::= ε

E ::= ε

T '

T '::= ε F ::= i

T '::= *FT '

T '::= ε F ::= (E )

T '::= ε

F

步骤 1. 2. 3. 4. 5. 6. 7.

符号栈 #E #E’T E# TE’#

读入符号 i i i i + + +

剩余符号串 +i*i# +i*i# +i*i# +i*i# i*i# i*i# i*i#

使用规则

E::=TE’ T::=FT’ F::= i (出栈,读下一个符号) (出栈,读下一个符号) 出栈 T::= ε E::=+TE’

#E’T’F FT’E’# #E’T’ i #E’T’ #E’ iT’E’# T’E’# E’#

#E’T+ +TE’#

i E E ' T T ::= F T ' E ::= T E '

+

*

( E ::= T E '

)

#

E '::= + T E ' T ::= F T '

E ::= ε

E ::= ε

T '

T '::= ε F ::= i

T '::= * F T '

T '::= ε

T '::= ε

F

F ::= (E )

步骤 8. 9. 10. 11. 12. 13. 14. 15. 16. 17.

符号栈 #E’T #E’T’F #E’T’ i #E’T’ #E’T’F* #E’T’F #E’T’ i #E’T’ #E’ #

读入符号 i i i * * i i # # #

剩余符号串 *i# *i# *i# i# i# # #

使用规则

T::=FT’ F::= i T’::=*FT’ F::= i T’::= ε E’::= ε

5

5 自底向上分析
5.1 移进-归约分析 移进(自底向上分析的一般过程) 自底向上分析的一般过程) 5.2 优先分析法 5.3 LR分析法 LR分析法

自底向上分析算法的基本思想为: 自底向上分析算法的基本思想为: 若Z ? S
+ G[Z]

则 S∈ L(G[Z])

否则 S ? L(G[Z])

存在主要问题: 存在主要问题: ? 句柄的识别问题

主要方法: 主要方法: ? 算符优先分析法 ? LR分析法 LR分析法

基本算法: 基本算法: 采用自左向右,基本算法是: 采用自左向右,基本算法是: 输入符号串开始 通过重复查找当前句型的句柄 开始, 句柄( 从 输入符号串 开始 , 通过重复查找当前句型的 句柄 ( 最 左直接短语) 并利用有关规则进行规约 规约, 左直接短语 ) , 并利用有关规则进行 规约 , 若能规约为 文法的开始符号,则表示分析成功, 文法的开始符号,则表示分析成功,输入符号串是文法 的合法句子,否则有语法错误。 的合法句子,否则有语法错误。

5.1 移进 — 归约分析
要点:建立符号栈,用来纪录分析的历史和现状, 要点:建立符号栈,用来纪录分析的历史和现状, 并根据所面临的状态, 并根据所面临的状态,确定下一步动作是 移进还是归约。 移进还是归约。 还是归约
输入串 # 符号栈 # L.R.P

例:G[S]: S→AcBe A→b A→Ab B→d
输入串为bbcde,检查是否是该文法的合法句子。 输入串为bbcde,检查是否是该文法的合法句子。

若采用自底向上分析,即能否一步步归约当前句型的句柄, 当前句型的句柄, 若采用自底向上分析,即能否一步步归约当前句型的句柄 最终规约到开始符号S 先设立一个符号栈, 规约到开始符号 最终规约到开始符号S。先设立一个符号栈,我们统一符号 #”作为待分析的符号串的左右分界符 作为待分析的符号串的左右分界符。 “#”作为待分析的符号串的左右分界符。 作为初始状态,先将符号串的分界符推进符号栈, 作为初始状态,先将符号串的分界符推进符号栈,作为栈底 符号。 符号。 分析过程如下表: 分析过程如下表:

例:G[S]:

S→AcBe A→Ab

A→b B→d

步骤 1 2 3 4 5 6 7 8 9 10

符号栈 # #b #A #Ab #A #Ac #Acd #AcB #AcBe #S

输入符号串 bbcde# bcde# bcde# cde# cde# de# e# e# # #

分析动作 移进 归约(A→b) 移进 归约(A→Ab) 移进 移进 归约(B→d) 移进 归约(S→AcBe) 接受

这一方法简单明了,不断地进行移进归约, 这一方法简单明了,不断地进行移进归约,

关键是确定当前句型的句柄 关键是确定当前句型的句柄. 句柄. 说明:例子的分析过程是一步步地归约当前句型 说明:例子的分析过程是一步步地归约当前句型的句柄 当前句型的句柄
该句子输入串为 该句子输入串为bbcde的 例:G[S]: 输入串为bbcde的 语法树的构造过程为: 语法树的构造过程为: S→AcBe A→Ab A→b B→d

S A A b a) A b b) b A b b c) c d A B A b b c d d) e A B

基本问题
? 检查是否为句柄—归约条件 检查是否为句柄—

? 选用哪一条规则进行归约—归约原则 选用哪一条规则进行归约—


更多相关文档:

编译原理-实验5-LR(1)分析法.doc

编译原理-实验5-LR(1)分析法 - 《编译原理》 实验报告 项目名称 专业班级 学姓号名 LR(1)分析法设计与实现 实验成绩: 批阅教师: 年 月 日 实验 5《LR...

第四章++语法分析(1)_图文.ppt

第四章++语法分析(1)_数学_自然科学_专业资料。上下文无关文法适于手工实现的...文法有助于语言的设计、演化、开发 5 4.2 上下文无关文法 ? RE的局限性 ? ...

LL(1)语法分析实验报告.doc

LL(1)语法分析实验目的和要求 编制一个能识别由词法分析给出的单词符号序列...(j=0;j<=5;j++) if(ch==v1[j]) { n=j;/*列号*/ break; } ...

第四章+语法分析(一)_图文.ppt

第四章+语法分析(一) - ? 课程内容 ? 第1章 概论 ? 第2章 词法分析 ? 第3章上下文无关文法 ? 第4章语法分析 ? 第5章语义分析 ? 第6章运行时环境 ...

实验5 LL(1)语法分析程序的设计与实现(C语言)_图文.doc

实验5 LL(1)语法分析程序的设计与实现(C语言)_计算机软件及应用_IT/计算机_专业资料。班级: 学号: 姓名: 实验五一、实验目的 LL(1)文法识别程序设计 通过 LL...

第4章 语法分析(5)_图文.ppt

第4章 语法分析(5) - 第四章 语法分析(5) 4.8~4.9 2016/1

编译5语法分析自下而上分析_图文.ppt

编译5语法分析自下而上分析 - 河南理工大学计算机学院编译原理PPT... 2016/12/11 17 5.1.3 符号栈的使用和分析树的表示 ? 栈是语法分析种基本数据结构...

LR(1)语法分析 - 副本.doc

20 编译原理课程设计报告 课题综述{ 1.1 课题来源{编译器设计的编译程序涉及到编译个阶段中的三个,即词法分析器、语法 分析器和中间代码生成器。编译程序...

第五章 语法分析1_图文.ppt

语法分析1 - 第 5语法分析 语法分析是编译的第二阶段;其任务是

5章 语法分析1_图文.ppt

5语法分析1 - 第 5语法分析 语法分析是编译的第二阶段;其任务是识

第五章 自顶向下的语法分析方法5.1-5.2_图文.ppt

章 自顶向下的语法分析方法5.1-5.2_理学_高等教育_教育专区。自顶向下 第5章 自顶向下的语法分析方法语法分析的作用是识别由词法分析给出 的单词符号...

5章 语法分析_习题_图文.ppt

5语法分析_习题 - 第5章 习题解答: 【习题:】 给定文法如下: G(S

编译原理ch5 自下而上语法分析-part1_图文.ppt

编译原理ch5 自下而上语法分析-part1_工学_高等教育_教育专区。 ? 5.1 ? 5.2 自下而上分析基本问题 算符优先分析 2013-7-6 2 5.1自下而上语法分析...

第5章 自顶向下语法分析方法1_图文.ppt

5章 自顶向下语法分析方法1 - 第章 自顶向下语法分析方法 5.1 确定的

编译原理_LL(1)文法源代码(实验三).doc

文法:无二义性的算术表达式的文法 (1)把词法分析作为语法分析的子程序实现(5 分) (2)独立的语法分析程序(4 分) (3)对表达式文法消除左递归、构造 LL(1)...

第五章 自顶向下的语法分析方法5.1-5.2_图文.ppt

章 自顶向下的语法分析方法5.1-5.2_IT/计算机_专业资料。编译原理PPT 第5章 自顶向下的语法分析方法语法分析的作用是识别由词法分析给出 的单词符号序列...

现代汉语语法分析的五种方法.doc

现代汉语语法分析种方法 - 北语之声论坛专业精华转贴 现代汉语语法的种分析

ch5-new自顶向下语法分析方法 (1)_图文.ppt

ch5-new自顶向下语法分析方法 (1) - 第章 自顶向下语法分析 在上一

编译原理LL(1)文法分析器实验(java).doc

编译原理 LL(1)文法分析器实验本程序是基于已构建好的某一个语法的预测分析表...{ // 初始化预测分析表 for (int i = 0; i < 5; i++) { for (...

第5章 自顶向下语法分析方法_图文.ppt

5章 自顶向下语法分析方法_IT/计算机_专业资料。自顶向下语法分析方法编译...教学重点:预测分析表构造,LL(1)文法 文法。 5.1 确定的自顶向下分析思想 ?...

更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com