编译器设计之语法分析算法：LL Parser：上下文无关文法与左递归.pdfVIP

编译器设计之语法分析算法：编译器设计之语法分析算法：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，