LL(1)语法分析的原理,利用预测分析方式构造语法分析器
时间: 2024-05-26 22:16:46 浏览: 18
LL(1)语法分析是一种自顶向下的语法分析方法,其中 LL 代表扫描输入流时先读入输入符号(Left-to-right),并从左到右地推导出语法树(Leftmost derivation),1 代表每个输入符号只需要查看输入符号串中的下一个符号就足以决定采用哪个产生式进行推导(Lookahead 1)。
LL(1)语法分析器采用预测分析方法,即根据当前输入符号和向前看符号(lookahead symbol),通过查找文法中的预测分析表(predictive parsing table)来确定下一步采取的产生式。预测分析表是一个二维表格,其中行代表非终结符,列表示向前看符号,每个表格元素则表示采用哪个产生式进行推导。构造预测分析表需要经过以下步骤:
1. 消除左递归:将文法中的左递归消除,保证不会出现无限循环推导。
2. 提取左公因子:将文法中的左公因子提取,避免重复计算。
3. 计算 FIRST 集合:针对每个非终结符和终结符,计算其 FIRST 集合,即该符号能够推导出的终结符集合。
4. 计算 FOLLOW 集合:针对每个非终结符,计算其 FOLLOW 集合,即该符号在右部出现时,后继的可能跟随符号集合。
5. 构造预测分析表:遍历文法中的每个产生式,对于每个产生式 A -> α,以及每个 a ∈ FIRST(α) 和 $ ∈ FOLLOW(A),将 M[A,a] 标记为 A -> α。如果 FIRST(α) 中包含 $,则将 M[A,$] 标记为 A -> α。
构造完预测分析表后,LL(1)语法分析器只需要根据当前输入符号和向前看符号,在预测分析表中查找对应的产生式,然后将其加入语法栈中,直到分析器成功推导出整个输入符号串,或者遇到语法错误。
总之,LL(1)语法分析器利用预测分析表来对输入符号串进行自顶向下的推导,其原理是通过查找预测分析表中的产生式,以确定下一步采用哪个产生式进行推导。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)