LL(1)文法及其分析算法的构造.docx

LL(1)文法及其分析算法的构造
LL(1)文法及其分析算法的构造
一、LL(1)文法概述
1.1简介
LL(1)文法是一种用于描述上下文无关文法的形式化语言。该文法是在语法分析中应用最为广泛的一种文法，可以使用其构建语法分析器。LL(1)文法由以下三部分构成：
（1）终结符
终结符是语法中不可再分的词汇单元，例如字符、数字、运算符等等。
（2）非终结符
非终结符是在规则重写中使用的符号。使用非终结符来描述语言的结构和规则。
（3）产生式
产生式是描述一个非终结符可以被重写成符号序列的规则，可以使用递归方式来重写非终结符。
产生式的形式如下：
A→α
其中A是一个非终结符，α是由终结符和非终结符组成的符号序列，表示A可以被替换成α。
1.2LL(1)文法的定义和要求
LL(1)文法是一种无二义性的上下文无关文法，同时满足以下三个条件：
（1）没有左递归
左递归指的是某个非终结符出现在其产生式的第一个位置。例如：A→Aα，其中A为非终结符，α为由终结符和非终结符组成的符号序列。左递归会导致递归产生式的无限循环，因此LL(1)文法不能存在左递归。
（2）具有左公因子消除
当一个非终结符的两个或多个产生式的开头部分相同时，就存在左公因子。为了消除左公因子，可以使用递归产生式，将两个或多个产生式合并成一个产生式。
例如：
S→aAb|aBc
可以使用递归产生式表示为：
S→aX
X→Ab|Bc
（3）可以通过查看下一个终结符来选择产生式
LL(1)文法中的每个非终结符在读取下一个终结符时只能选择一个产生式。因此，称之为“LL(1)”（Left-to-right,Left-most,1symbollookahead）。
二、LL(1)文法分析算法
2.1算法原理
LL(1)文法的分析算法是基于预测分析（PredictiveParsing）实现的。它利用栈和输入缓冲区，从左边向右边扫描输入，将栈顶元素与输入缓冲区中的下一个符号进行比较，通过分析栈的状态和下一个符号，预测下一个步骤，并使用产生式进行重写。
分析过程如下：
（1）创建一个栈来存储产生式和输入符号。
（2）将起始符号和终止符号放入栈中。
（3）扫描输入缓冲区，取出下一个符号。
（4）将栈顶元素与输入符号进行比较：
（a）如果栈顶元素等于输入符号，则将栈顶元素和输入符号都弹出，继续扫描下一个符号。
（b）如果栈顶元素是一个终结符，则表明输入符号与文法不吻合，分析失败。
（c）如果栈顶元素是一个非终结符，则查找预测分析表，使用该非终结符和输入符号的组合来选择一个产生式，将其推入栈中。
（5）重复步骤（3）-（4），直到栈为空或分析失败。
2.2预测分析表
预测分析表是一个二维数组，用于预测分析算法中产生式的选择。预测分析表的行表示非终结符，列表示终结符。表中的每个格子都包含一个产生式，用于表示非终结符和终结符之间的关系。
预测分析表可以使用以下步骤来构建：
（1）对于每个非终结符A，找到所有的A→α产生式。
（2）对于每个产生式A→α，使用FOLLOW(A)集合中的每个终结符b作为表格列。
（3）如果α是ε（空产生式），则使用FIRST(A)中的终结符作为列。
（4）将A→α中的产生式写入对应的格子中。
例如：
文法G(E):
1.E→E+T|T
2.T→T*F|F
3.F→(E)|id
该文法的预测分析表为：
非终结符+*()id$
E1-1-1-
T-2--2-
F--3-4-
其中，“-”表示匹配失败。
2.3处理冲突
当构造LL(1)文法的预测分析表时，如果不同的产生式指定了相同的终结符号，那么就会出现文法冲突，导致分析器无法正常工作。
解决冲突的方法有以下几种：
（1）调整产生式的顺序
根据预测分析表的构造过程，可以修改产生式的顺序，使得表中没有重复的条目。
例如：
假设文法G：
1.E→E+T|T
2.E→F-T|F
3.T→T*F|F
4.F→(E)|id
其中，在E→T+E和E→F-T产生式中，+和-重复了。可以改写产生式，避免出现相同的终结符号，更新这两个产生式：
1.E→TEE
2.EE→+TEE|ε
3.EE→-TEE
（2）调整非终结符的FOLLOW()集合
如果存在文法冲突，还可以尝试调整FOLLOW()集合中的非终结符来修复它。
例如：对于文法G：
1.S→aAa
2.A→bB|ε
3.B→cC|ε
如果FOLLOW(A)包括b和c，那么该文法不是LL(1)文法，因为b和c不能确定哪个产生式应该使用。可以通过调整FOLLOW(A)来消除该冲突。
可以将FOLLOW(A)包括c但不包括b，这样就可以明确地选择B→ε产生式。
（3）引入新的非终结符
如果上述方法都无法解决冲突，可以尝试引入新的非终结符和产生式来消除冲突。
例如：对于文法G：
1.A→aBd