当前位置:首页 >> 计算机软件及应用 >> 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

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

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


更多相关文档:

编译原理实验二语法分析器LL(1)实现

编译原理实验二语法分析器LL(1)实现_工学_高等教育_教育专区。编译原理程序设计...[op].code==5||tokenlist[op].code==6) { push(&s,'Y'); push(&s...

北邮 编译原理 语法分析

编译原理语法分析班级: 学号: 姓名:ytinrete 程序设计 2 题目:语法分析程序的设计...('E'); cout<<" 栈 "<<endl;//23,20,5 int i=0, j=1;//temp ...

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

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

实验二语法分析201110405137

语法分析程序,实现对词法分析程序所提供的单词序列进行语法检 查和结构分析...打印分析成功 出错处理 (4)statement 语句分析程序流程如图 4、5 所示。 是否...

编译原理实验报告5-语法分析程序的设计(2)

实验5 、实验目的 语法分析程序的设计(2) 通过设计、编制、调试一个典型的语法分析程序,实现对词法分析程序所提供的单词序 列进行语法检查和结构分析,进一步掌握...

LL(1)语法分析程序设计

实验二 LL(1)语法分析程序设计【实验目的】 1.熟悉判断 LL(1)文法的方法及...5 #define MaxVtNum 5 #define MaxStackDepth 20 #define MaxPLength 20 #...

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

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

现代汉语下册第五章语法1·6章课后习题答案

现代汉语下册第语法1·6章课后习题答案_文学_高等教育_教育专区。增订版...(定语) 主语 谓语 补语出 (定语) 宾语 层次分析法 ①这篇 文章 批判了 ...

LL(1)文法语法分析——编译原理课程设计

LL(1)文法语法分析——编译原理课程设计_工学_高等教育_教育专区。编译原理课程...5 表结构图 - 3 - 2.2 程序流程图开始 读入 ll(1)文法文件,并显示出...

实验二 LL1语法分析器

实验二一、实验目的 LL(1)分析法 通过完成预测分析法的语法分析程序,了解预测...(8)F->i 输出的格式如下: 、实验源程序 LL1.java import import import...
更多相关标签:
网站地图

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