- 1、本文档共10页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
编译器设计之语法分析算法:编译器设计之语法分析算法:LLParser:上下:上下
文无关文法与左递归文无关文法与左递归
编译器设计基础编译器设计基础
1.上下文无关文法简介上下文无关文法简介
1.1文法的基本概念文法的基本概念
在编译器设计中,文法文法是用于描述编程语言结构的一种形式化工具。它由一系列规则组成,这些
规则定义了语言中合法的语句和表达式。文法通常由四个部分组成:
•非终结符非终结符(Non-terminal):表示语言结构的抽象概念,如语句、表达式等。
•终结符终结符(Terminal):表示语言中的具体符号,如关键字、操作符、标识符等。
•开始符号开始符号(Startsymbol):文法中的一个非终结符,表示整个语言的起点。
•产生式产生式(Production):定义非终结符如何被终结符和/或其它非终结符替换的规则。
例如,考虑以下简单的文法,用于描述一个由数字和加号组成的表达式:
E-E+T|T
T-T*F|F
F-(E)|num
在这个文法中,E,T,和F是非终结符,+,*,(,),和num是终结符,E是开始符号,而每行的规
则是产生式。
1.2文法的类型与上下文无关文法文法的类型与上下文无关文法
文法根据其规则的复杂性被分为不同的类型,其中上下文无关文法上下文无关文法(Context-FreeGrammar,
CFG)是编译器设计中最常用的一种。在上下文无关文法中,产生式的左边是一个非终结符,右
边可以是终结符、非终结符或它们的组合,但不依赖于产生式左边非终结符的上下文。
上下文无关文法的产生式遵循以下形式:
A-α
其中A是非终结符,α是终结符和/或非终结符的序列。例如,以下文法描述了一个简单的算术
表达式:
S-aSb|ε
在这个例子中,是非终结符,a和b是终结符,ε表示空串。这个文法是上下文无关的,因为
的替换规则不依赖于它在句子中的位置或上下文。
2.LL解析器概述解析器概述
2.1LL解析器的定义解析器的定义
LL解析器解析器是一种自顶向下(Top-down)的解析算法,其中“LL”代表“Left-to-rightscan,Leftmost
derivation”。这意味着LL解析器从左到右扫描输入串,并尝试构建最左推导(Leftmost
Derivation)。LL解析器特别适用于上下文无关文法,尤其是那些没有左递归的文法。
2.2LL(1)解析器的工作原理解析器的工作原理
LL(1)解析器解析器是LL解析器的一种,它只需要查看输入串中的下一个符号(即“1”个符号的预视)
就能决定如何应用文法的产生式。LL(1)解析器的工作原理如下:
1.构建解析表构建解析表:LL(1)解析器需要一个解析表,该表根据当前非终结符和输入串中的下一个
符号来决定应用哪个产生式。
2.自顶向下解析自顶向下解析:从文法的开始符号开始,LL(1)解析器尝试构建输入串的最左推导。在每
个步骤中,解析器查看输入串中的下一个符号,并根据解析表决定应用哪个产生式。
3.预视和回溯预视和回溯:LL(1)解析器使用预视来避免回溯。如果解析表中没有明确的规则,或者输
入串与文法不匹配,解析器将无法继续解析。
示例:构建示例:构建LL(1)解析表解析表
假设我们有以下文法:
S-aSb|ε
为了构建LL(1)解析表,我们需要计算每个非终结符的FIRST集集和FOLLOW集集。FIRST集包含从
非终结符开始的任何推导序列的第一个符号,而FOLLOW集包含在任何推导序列中紧随非终结符
之后的符号。
对于文法S-aSb|ε:
•FIRST(S)={a,ε}
•FOLLOW(S)={$}
解析表如下:
当前符号当前符号输入符号输入符号
Sa
Sε
S$
在这个简单的例子中,解析表显示了如何根据输入串中的下一个符号来决定应用哪个产生式。当
输入串中的下一个符号是a时,解析器应用S-aSb;当输入串中的下一个符号是$或者
已经推导出ε时,解析器应用S-ε。
示例:使用示例:使用LL(1)解析器解析输入串解析器解析输入串
考虑以下输入串:aabb。使用上述文法和解析表,LL(1)解析器的解析过程如下:
1.从开始,输入串中的下一个符号是a,
您可能关注的文档
- 编译器设计之语法分析算法:LR Parser:LR(0)解析算法详解.pdf
- 编译器设计之语法分析算法:LR Parser:LR解析表的构造.pdf
- 编译器设计之语法分析算法:LR Parser:LR解析器的优化技术.pdf
- 编译器设计之语法分析算法:LR Parser:LR解析器的状态转换.pdf
- 编译器设计之语法分析算法:LR Parser:SLR(1)解析算法原理与实现.pdf
- 编译器设计之语法分析算法:LR Parser:编译器设计基础.pdf
- 编译器设计之语法分析算法:LR解析器的高级主题:冲突解决.pdf
- 编译器设计之语法分析算法:面向对象的LR解析器设计.pdf
- 编译器设计之语法分析算法:LL Parser:LL(1)文法解析.pdf
- 编译器设计之语法分析算法:LL Parser:LL解析器概论.pdf
文档评论(0)